# Repeated auctions with impatient bidders and externalities.

1. IntroductionCollusive bidding behavior has been conventionally studied in a static setup, often relying on some unspecified repeated-interaction story for the enforcement of a cartel. (1) It is not clear, however, whether the results from static auctions immediately carry over to a repeated setup when bidders are impatient and the enforcement or the participation constraint is binding. Moreover, many empirical analyses for detecting collusion rely on an explicitly repeated structure, rendering a theoretical analysis of collusion in a repeated setup necessary. (2) Several recent theoretical developments in repeated auctions have been made by Aoyagi (2003, 2007), Skrzypacz and Hopenhayn (2004), and Blume and Heidhues (2006). Taking standard auctions as stage games, these articles present various collusive bidding schemes with asymmetric punishments that outperform the bid-rotation scheme, which is known to be optimal in static auctions (McAfee and McMillan 1992).

This article studies collusive bidding behavior in repeated auctions, among both patient and impatient bidders, when the outside option of the participation constraint is endogenized because of externalities. A stage game involves negative externalities among the bidders when any losing bidder is worse off if a rival wins the good than if no one wins it. Auctions with externalities have been introduced most notably by Jehiel and Moldovanu (1996) and Jehiel, Moldovanu, and Stacchetti (1996). These auctions describe environments in which the outcomes of auctions affect the nature of ensuing market interactions among potential bidders. A wide variety of situations in which bidders are a set of oligopoly firms competing in the same market apply to this setting. For example, procurement auctions for highway construction contracts, studied empirically by Porter and Zona (1993), may qualify as repeated independent private value auctions with negative externalities except that the lowest bidder wins. (3) Consecutive highway lettings were distributed by the Department of Transportation (DOT) to a set of oligopoly firms competing in the same industry. Negative externalities may arise because a firm that wins the auction may experience learning by doing, which provides the winning firm with a comparative cost advantage, or because the winning firm may gain a reputation that gives the firm an advantage in future private sector competition. As Jehiel and Moldovanu (1996) and Jehiel, Moldovanu, and Stacchetti (1996) discuss, the issue of participation is nontrivial in auctions with externalities because the ex ante payoff a bidder expects by not participating is no longer zero as in standard auctions but is rather endogenously determined by the actions of the other bidders. Thus, an analysis of collusive bidding behavior under both nonbinding and binding participation constraints seems especially worth studying for these auctions.

The main findings of this article are that (i) there are no bidding wars along the equilibrium path, and bidders expect to receive the maximal continuation values when they are both patient and impatient; when bidders are impatient, the optimal collusive bidding scheme involves (ii) a lower threshold type above whom bidding starts when externalities are small or (iii) more frequent jumps (i.e., more sorting of bidders' types) when externalities are large. In both cases, seller's ex ante profit is higher when bidders are impatient.

If we consider patient bidders to be the ones that are interacting in a stable market, (4) results carry an empirical implication: either less frequent sales or fewer bid levels in auctions that are let out in stable markets will be observed. The fact that the cartel manipulates both the amounts of bids and the probabilities of sales is worth noting. While one might wonder how a cartel can manipulate the probability of sales and how a sale can actually not occur in reality, such an incidence has been reported to happen. Porter and Zona (1993) note a spell of periods of nonbidding in their study of auctions for highway construction contracts. In the case of a contract let out in Long Island in February 1983, the DOT did not award the contract because eight bids that were submitted were unusually high relative to its own estimate. The same contract was let out again in May 1983. This time, the lowest bid was 20% higher and was submitted by the same lowest bidder of the February auction. The contract was once again not awarded. Porter and Zona (1993) note that such unusual bidding patterns caused the contract not to be awarded until 1987.

This article is closely related to Rhee (2007) and Athey, Bagwell, and Sanchirico (2004). Rhee (2007) studies tacit collusion in auctions with externalities in a static setup. We extend the model to a repeated structure and analyze the case in which the enforcement of the cartel becomes an issue as bidders become impatient. Analytically, we draw on Athey, Bagwell, and Sanchirico (2004), who study infinitely repeated Bertrand games in which firms receive a privately observed i.i.d, cost shock in each period. For the case in which demand is inelastic, their analysis parallels that of a repeated first-price auction without externalities. We borrow the technical tools of Athey, Bagwell, and Sanchirico (2004) to transform the dynamic problem into a static mechanism design problem. The result that the cartel manipulates probabilities of sales can be also related to the optimal bidding scheme provided in Skrzypacz and Hopenhayn (2004), in which bidders collude by temporarily excluding a portion of bidders from the bidding process.

Despite the vast literature on collusive behavior in auctions, studies of collusion in a repeated auction setup are quite limited in number. It may be more appropriate to study the enforcement issue of the collusive effort in a repeated setup. Aoyagi (2003), Skrzypacz and Hopenhayn (2004), and Blume and Heidhues (2006) have shown the existence of dynamic bidding schemes that yield higher payoffs than the static bid-rotation schemes. These articles share a common theme, as in Athey and Bagwell (2001), that asymmetric continuation values may act as implicit transfers among bidders. The analysis here differs in that this article focuses on symmetric cases in which transfers among bidders are not allowed. Thus, in the terms of McAfee and McMillan (1992), we focus on "weak" cartels rather than "strong" cartels. This implies that any exchange of information that may happen in the preauction stage carries no value to bidders because there is no means with which the bidders can distribute the gains from informational advantage. Fabra (2003) is another article that studies repeated auctions and focuses on the enforcement problem faced by the cartel. Fabra (2003) compares collusive efforts under uniform versus discriminatory auctions and shows that bidders' incentives to deviate are weaker in uniform auctions.

This article is organized as follows. Section 2 introduces the model and formalizes the repeated game. A couple of static results for auctions with externalities are also reported in this section. The cartel's maximization problem for patient bidders is solved in section 3. In section 4, the critical discount factor below which bidders are considered impatient is defined, and the maximization problem for impatient bidders is solved. Section 5 concludes.

2. The Model and Preliminaries

The Stage Game

The stage game is a standard first-price independent private value auction with a seller's reservation price, except for the existence of negative externalities so that all losing bidders incur a cost whenever there is a winner. There are n risk-neutral potential bidders indexed by i = 1, ..., n. Each bidder's private valuation of the good is denoted by [v.sub.i]. (5) Bidder i's valuation is assumed to be independently and identically distributed on [V.sub.i] [equivalent to] [[x.bar], [v.bar]], with a distribution function F(x) and a density f(x). It is assumed that F(x) is twice continuously differentiable and f(x) is strictly positive on [V.sub.i]. The seller's reservation price is denoted by R [member of] ([b.bar], [bar.v]), and a > 0 denotes the symmetric negative externalities suffered by all losing bidders whenever there is a winner. No explicit side payments are available among bidders.

Because of externalities, there are three possible outcomes of the auction for any potential bidder i: (i) bidder i wins the auction and gets [v.sub.i] - [b.sub.i], where [b.sub.i] is the submitted bid; (ii) no one wins, and bidder i gets 0 utility; and (iii) some other bidder j [not equal to] i wins, and bidder i's payoff is -[alpha]. The third possible outcome creates an incentive for any bidder i to prevent his competitors from winning, which is a consequence of assuming externalities.

Let [b.sub.i] [not member of] [R.sub.+] denote the bid submitted by bidder i and let [q.sub.i]: b [right arrow] [summation] denote the equilibrium probability of winning, where b = ([b.sub.1], ..., [b.sub.n]) is the vector of bids and [summation] = {q [member of] [R.sup.n.sub.+]|[summation][q.sub.1] [less than or equal to] 1} is the set of probability vectors. A bidding strategy for bidder i is a mapping b(x) from the set of valuations or types to bids. A bidder's interim utility, which is the expected utility for bidder i when he realizes a type [v.sub.i] and bids [b.sub.i] while expecting others to bid according to b(x), is denoted by [bar.u]([b.sub.i], [v.sub.i]; b(x)), where the expectation is taken over other bidders' types. Because bidders suffer negative externalities when there is a winner, a bidder is no longer guaranteed a zero utility even when he submits a bid below the seller's reservation price or stays out of the auction. That is, any bidder should expect two different forms of interim utilities that are dependent on whether he submits a bid above the seller's reservation price or not. Formally, when i submits a bid below R ([b.sub.i] < R), i incurs negative externalities whenever there exists a bidder j who wins the auction, and when i submits a bid above R ([b.sub.i] [greater than or equal to] R), i gets his valuation when no one else bids above him; otherwise, he incurs negative externalities:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

In this setup, we report the following two static results. One is the Bayesian-Nash equilibrium when bidders are not colluding, and the other is the optimal collusive bidding scheme.

REMARK 1 (Brocas 2003; Rhee 2007). Given the seller's reservation price R and the profile of valuations ([v.sub.l], ..., [v.sub.n]), the Bayesian-Nash equilibrium bidding function is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

The terms in the first bracket in Equation 2 is the Nash equilibrium bidding strategy without externalities. The terms in the second bracket show how, because of externalities, bidders want to augment their bids because the true value of winning is now [v.sub.i] + [alpha] since a bidder avoids incurring - [alpha] by winning. (6) However, since the auction is a first-price auction, the bidder wants to shade the bid and not increase the bid amount by the full extent of [alpha]. (7)

While Equation 2 states the modifications required for the Nash equilibrium bidding strategy because of externalities, it is also worth noting the changes that are needed for collusive efforts. First, the bid-rotation scheme of McAfee and McMillan (1992), in which all bidders with valuations above R pool their bids at R, is no longer incentive compatible in the presence of externalities. Without externalities, a bidder with a valuation less than R does not have an incentive to bid. But with externalities, a bidder with a valuation slightly less than R may be tempted to bid above R since his true value of winning [v.sub.i] + [alpha] exceeds the reservation value. Thus, if the cartel wants to implement an incentive compatible bid-rotation scheme, it needs to lower the threshold type above which the bidding starts; that is, the cartel needs to become more inclusive. More specifically, let [v.sup.1.sub.R] be the threshold type that supports the bid-rotation scheme to be incentive compatible. It is defined implicitly by the equation [v.sup.1.sub.R] = R - [alpha]{1 - [F[([v.sup.1.sub.R]).sup.n-1]]/[[q.sup.R]([v.sup.1.sub.R])]}, where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is the probability of winning for those who bid above R. (8) It is straightforward to see that [v.sup.1.sub.R] < R, implying that to implement the bid-rotation scheme, the cartel must become more inclusive than with the Nash equilibrium scheme.

Given a weakly increasing function b: R [right arrow] R, let [v.sup.1] [equivalent to] [v.sup.1](b) be defined by [v.sup.1] = sup{v : b(v) < R}. Thus, [v.sup.1] is the threshold type above which the bidding function assigns a bid greater than R. Note that [v.sup.1] carries the information on the probability of sales since smaller [v.sup.1] implies a higher the probability of sales. Rhee (2007) establishes the optimal collusive bidding scheme with externalities in a one-shot game as follows.

REMARK 2 (Rhee 2007). Suppose the increasing hazard rate condition holds. There exist levels of externalities 0 [less or equal to] [[alpha].sup.+] < [[alpha].sup.++] < [infinity] such that the optimal collusive bidding scheme [b.sup.S](x) in static auctions with externalities is described as follows:

(i) For [alpha] < [[alpha].sup.+], [v.sup.1] = [v.sup.1.sub.R] and [b.sup.S](v) = R for v [greater than or equal to] [v.sup.1].

(ii) For [[alpha].sup.+] [less than or equal to] [alpha] < [[alpha].sup.++], [v.sup.1] [member of] [[v.sup.1.sub.R], R) and [b.sup.S](v) = [b.sup.k] for v [member of] [[v.sup.k], [v.sup.k+1]), k = 1 ..., K where [b.sup.1] = R, R < [b.sup.i] < [b.sup.k] for 1 < j < k [less than or equal to] K.

(iii) For [alpha] [greater than or equal to] [[alpha].sup.++], [v.sup.1] = R and [b.sup.S](v) = [b.sup.N](v) for v [greater than or equal to] [v.sup.1]. (9)

The result shows that the cartel balances between the incentives to maximize gains from trade (by implementing bidding schemes with bidders' types pooled at low bid amounts) and the incentives to minimize the probability of sales, so that bidders can avoid incurring negative externalities (by implementing bidding schemes with a higher threshold type.) When externalities are small, the first incentive is more important than the second. Thus, the cartel chooses a bid-rotation scheme such that all participating bidders are pooled to bid exactly R, but sales occur with the highest probability; that is, [v.sup.1.sub.R] is the lower bound on the set of feasible [v.sup.1]. (10) As externalities become larger, the cartel yields a higher expected payoff to the seller by sorting bidders' types. But this realizes at a lower expected probability of sales. Since the optimal bidding strategy is a step function, this implies that more bid levels will be observed since sorting introduces additional steps in the bidding strategy. For large-enough externalities, the cartel cannot do any better than the Nash outcome because the stakes of staying out of the auction are too large to force any bidder with [v.sup.i] > R to stay out of the auction.

The Repeated Game

Consider next an infinitely repeated game in which each bidder draws a new valuation [v.sup.t.sub.i] in each period t. Each [v.sup.t.sub.i], is i.i.d, across i and t. The objective of each bidder is to maximize the expected discounted stream of utilities, [[summation].sup.[infinity].sub.t=1] [[delta].sup.t-1] [bar.u]([b.sup.t.sub.i]([v.sup.t.sub.i]), [v.sup.t.sub.i]), where [delta] [member of] (0, 1) is a common discount factor. High [delta] implies either that bidders in the industry are patient or that the industry in which bidders compete is stable. On entering a period [tau], bidders observe the history of (i) their own valuations [{[v.sup.t.sub.i]}.sup.[tau]-1.sub.t=1], (ii) their own bidding strategies [{[b.sup.t.sub.i] ([v.sup.t.sub.i])}.sup.[tau]-1.sub.t=1], and (iii) realized bids of others [{[b.sup.t.sub.j]}.sup.[tau]-1.sub.t=1]. Let [h.sup.[tau].sub.i] = [{[v.sup.t.sub.i], [b.sup.t.sub.i](x), [b.sup.t.sub.- i]}.sup.[tau].sub.t=1] and [H.sup.t] = [{[b.sup.t-1]}.sup.[tau].sub.t=1], respectively, denote the private and public information sets at time [tau], where [b.sup.t] = ([b.sup.t.sub.1], ..., [b.sup.t.sub.n]). Finally, let [s.sub.i]([h.sub.i])([v.sub.i]) be the (pure) strategy that associates a bidding strategy with each information set [h.sub.i] and let each s = ([s.sub.1], ..., [s.sub.n]) induce a probability distribution over the full path of play [{[v.sup.t], [b.sup.t](x)}.sup.[infinity].sub.t=1] in the usual manner.

The repeated game has a recursive structure, and thus perfect public equilibrium is the natural solution concept to use (see Abreu, Pearce, and Stacchetti 1986, 1990; Fudenberg, Levine, and Maskin 1994). Our attention is also restricted to the symmetric perfect public equilibrium (SPPE), in which s = ([s.sub.1], ..., [s.sub.n]) is an SPPE if [s.sub.i]([b.sup.1], ..., [b.sup.[tau]]) = [s.sub.j]([b.sup.1], ..., [b.sup.[tau]]), [for all]i, [tau], [tau], [b.sup.1], ..., [b.sup.[tau]]. (11) That is, bidders adopt symmetric bidding strategies after every public history and go through any future punishments or rewards together.

Athey, Bagwell, and Sanchirico (2004) show that finding the optimal symmetric strategy profile [s.sup.*] = ([s.sup.*], ..., [s.sup.*]) is equivalent to solving for ([b.sup.*](x), [v.sup.*](x)), which solves

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

subject to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where b(x) is a first-period bidding strategy, [V.sub.S]([alpha], [delta]) [subset] R is the set of SPPE continuation values, v: [R.sup.n.sub.+] [right arrow] R is a continuation payoff function, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the set of attainable SPPE continuation values [V.sub.S]([alpha], [delta]) is dependent on the parameter values of [alpha] and [delta]. [V.sub.S] contracts when [alpha] increases, as bidders incur larger negative utilities whenever some other bidder wins. The set [V.sub.S] also contracts when [delta] decreases, as bidders discount the future more heavily. Let [bar.V]([alpha], [delta]) [equivalent to] sup [V.sub.S]([alpha], [delta]). The first (IC-off) constraint states that it should not be in the interest of a bidder to submit a bid not assigned to any type, that is, a bid not in the range of the bidding function. A bidder who violates this condition is considered to deviate "off the equilibrium path." Because such deviation is unambiguously detected by other bidders, (IC-off) roughly corresponds to a participation constraint in the static setup. The second (IC-on) constraint asserts that a bidder should always prefer to truthfully report his type than to misrepresent himself. This constraint is the usual incentive compatibility condition to ensure that there are no deviations "on the equilibrium path."

3. Optimal Collusion among Patient Bidders

This section assumes that bidders are sufficiently patient so that any temptation to deviate off the equilibrium path is deterred by a threat to revert to a Nash equilibrium. Note from the previous section that deviations off the equilibrium path cannot go undetected. Thus, members of the cartel can "punish" such behavior by playing the Nash equilibrium strategy whenever it yields a lower expected payoff than the collusive bidding scheme. Naturally, this type of deviation can be deterred as long as bidders value the future payoffs sufficiently high. Technically, this allows us to disregard the (IC-off) constraint and focus on the (IC-on).

The case of patient bidders is analyzed first for the following two reasons. First, as mentioned in the Introduction, the existing literature on collusive bidding behavior in static auctions overlooks the issue of participation. By assuming sufficiently patient bidders and disregarding the (IC-off) constraint, we refer to this literature since the (IC-off) constraint is analogous to the participation constraint in the static setup. This allows us to separate the effect of repetition from the effect of incorporating participation constraint, which is analyzed in the next section with the case of impatient bidders. Second, the optimal collusive bidding scheme developed in this section is used to define the critical discount rate above which bidders are considered to be "patient." The bidders are defined to be patient when they value the future high enough not to deviate in an obvious manner.

Drawing on Athey, Bagwell, and Sanchirico (2004), we define T(v) [equivalent to] [delta][bar.[V.sub.S]]([alpha], [delta]) - [bar.v](b(v); b(x))] [greater than or equal to] 0 as the "transfer function." The interpretation of T(x) is as follows. Suppose for a given SPPE, a bidder who announces v expects a continuation value below [bar.[V.sub.S]]([alpha], [delta]). Then, we may think of that SPPE as specifying a future war following the announcement of v. Consequently, it follows that T(v) > 0 is associated with a future in which there is a war. By the same reasoning, there is no future war after the announcement of v when T(v) = 0, that is, when the expected continuation value equals the supremum of the SPPE set. Substituting [delta][bar.v](b(v); b(x)) = [delta][bar.[V.sub.S]]([alpha], [delta]) - T(v) into (IC-on) in Equation 3 and letting [bar.u]([v.sub.i]; b(x)) [equivalent to] [bar.u](b([v.sub.i]), [v.sub.i]; b(x)) to simplify notation, (IC-on) can be replaced with the following condition:

[bar.u](v; b(x)) - T(v) [greater than or equal to] [bar.u]([??]; b(x)) - T([??]), [for all][??] [member of] [[v.bar]] (IC-on')

With the (IC-off) constraint ignored and the (IC-on) constraint replaced by (IC-on'), the dynamic problem in Equation 3 can now be treated as a mechanism design problem, and we can directly apply mechanism design tools. (12) Let q([v.sub.i]; b(x)) = [E.sub.v-i][[q.sub.i]([v.sub.1], ..., [v.sub.i], ..., [v.sub.n]; b(x))] be the interim probability of winning for player i when he reports [v.sub.i] and adopt a bidding strategy b(x). Then (IC-on') is equivalent to [bar.u](v, b(x)) - T(v) = [bar.u]([v.bar]; b((x)) - T([v.bar]) + [integral].sup.v.sub.[v.bar]] q(s; b(x)) ds, and q(x) is nondecreasing. (13) Substituting the first equation directly into the objective function in Equation 3 and solving the double integration, we arrive at the following cartel's maximization problem:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

s.t.

T(v) [greater than or equal to] 0, [for all] v (no subsidy) q(x; b(x)) nondecreasing (monotonicity).

The first result establishes that [T.sup.*] = 0 and extends the result in Athey, Bagwell, and Sanchirico (2004) that wars are not necessary along the equilibrium path in an environment with negative externalities.

PROPOSITION 3. Consider any scheme (b(x), T(x)) with T [??] 0 that satisfies the constraints of the mechanism design problem (Eq. 4). Then, there always exists an alternative scheme with no wars ([??](x), [??] [equivalent to] 0) that generates an expected profit as high as the profit generated by the original scheme (b(x), T(x)).

The proof of Proposition 3 can be found in the Appendix. The "no-war" result in Athey, Bagwell, and Sanchirico (2004) does not immediately extend to an environment with externalities. This is because the revenue equivalence property, which is central to establish [T.sup.*] = 0 in environments without externalities, holds with a caveat in environments with externalities. Because [bar.u](v, b(x)) - T(v) = [bar.u]([v.bar]; b(x)) - T(v) + [integral].sup.v.sub.[v.bar]] q(s; b(x))ds, the well-known revenue equivalence property states that a bidder's utility is fixed as long as the expected utility of the bidders with the lowest valuation (utility at bottom) and their probabilities of winning are the same. (14) Since utility at bottom is zero without externalities, revenue equivalence requires maintaining the same probabilities of winning. Athey, Bagwell, and Sanchirico (2004) use revenue equivalence by showing that any payment in the form of a future war can alternatively be paid by an increased bid in the current period without affecting the probabilities of winning.

With externalities, however, the utility at bottom [bar.u](v; b(x)) - T([v.bar]) = - [alpha] x prob[there exists v not equivalent to] [v.bar] s.t. b(v) > R] - T([v.bar]) is no longer zero and is dependent on the actions of other players, that is, the number of bidders bidding above the seller's reservation value. More importantly, for these bottom-step bidders, there are no effective bids that can be manipulated to replace the payment in the form of a future war. Nonetheless, we show in the proof of Proposition 3 that, for any bidding scheme with a future war associated with the bottom-step bidders (i.e., T([v.bar]) > 0), we can construct an alternative scheme that yields higher expected utilities for all types without any future wars. The intuitive logic behind the result is as follows. Given a bidding scheme (b(x), T(x)) with T([v.bar]) > 0, consider an alternative scheme ([??](x), [??](x)) that simply takes away the transfer ([??]([v.bar]) = 0) while preserving the same probability of sales. (15) This results in a higher current period utility at bottom since [bar.u]([v.bar]; b(x)) = [bar.u]([v.bar]; [??](x)) while T([v.bar]) > [??]([v.bar]) = 0. Then, by incentive compatibility, the remaining bidders must be better off because bidders with higher valuations must expect a larger rent than that of bottom-step bidders.

Equilibrium-path wars are often the central feature in hidden action models. In those models, uncertainties about other players' actions are imperfectly reflected on (publicly observed) outcomes that may trigger punishment phases even when no one has deviated. Thus, players prefer to collude on a scheme that specifies occasional wars on the equilibrium path in order to relax such tensions. In repeated hidden information models, however, there are no such uncertainties, and the only uncertainties rest on the reports of bidders regarding their true types. Proposition 3 shows that recourses to equilibrium-path wars are not beneficial since engaging in future wars neither mitigates tension arising from incentive compatibility constraints nor supports higher utilities in the current period, even in the presence of negative externalities.

By the definition of the transfer function, [T.sup.*] = 0 implies that [bar.v]([b.sup.*] (v); [b.sup.*](x)) = [[??].sub.S]([alpha], [delta]). That is, bidders expect to receive the highest possible continuation value as long as they follow the equilibrium bidding strategy [b.sup.*](x) that maximizes the current period's payoff. (16) The optimal bidding strategy in a repeated game is then the same as the one that maximizes the stage game payoffs.

COROLLARY 4. Suppose the increasing hazard rate condition holds. Then, the optimal collusive bidding scheme when bidders are patient is ([b.sup.*](x), [v.sup.*](x)) = ([b.sup.S](x), [bar.[V.sub.S]]([alpha], [delta])).

4. Optimal Collusion among Impatient Bidders

In this section, we address the problem of enforcing the cartel by studying collusion among impatient bidders. We consider bidders to be "impatient" if the discount factor falls below the critical discount factor. The critical discount factor is defined as the discount rate that supports the optimal bidding scheme found in Corollary 4 using Nash reversion as a punishment. Technically, we examine the case in which the (IC-off) constraint in Equation 3 binds. This is the case when bidders are so impatient that they are tempted to deviate even in an obvious manner, thereby breaking the collusive effort altogether.

As previously mentioned, (IC-off) corresponds to the participation constraint in the static setup. The analogy is especially strong in an environment with externalities. As discussed in section 2, the bidders in this environment are affected by the outcome of the auction regardless of their physical participation in the auction. That is, a bidder cannot guarantee herself a zero payoff as an outside option by simply walking away. When the collusive ring adopts the Nash strategy when a bidder does not participate, it is the best response of the nonparticipating bidder to adopt the Nash strategy as well. Therefore, the Nash equilibrium outcome credibly becomes the outside option of not participating. It is worth noting that the outside option is endogenized due to externalities because it is not a constant value but rather an equilibrium outcome. We first define the critical discount factor below which bidders are considered impatient. We then show that equilibrium-path wars are still not necessary and that collusion among impatient bidders requires either a higher probability of sales or more frequent jumps in the bidding function than in the function of patient bidders.

Assume that bidders revert to playing the Bayesian-Nash equilibrium bidding scheme forever whenever some bidder deviates in an obvious manner, that is, by submitting a bid that is not in the range of the bidding function. Given the Nash reversion punishment, a bidder will comply with a collusive bidding scheme only if the current-period benefit from deviation is smaller than the lost present discounted value of future cooperation. The present discounted value of future cooperation increases as bidders become patient. Thus, the critical discount factor is defined as the lowest discount factor that supports the optimal bidding scheme found in section 3. Let ([b.sup.*]([alpha]), [v.sup.*]([alpha])) = ([b.sup.S]([alpha]), [bar.[V.sub.S]]([alpha], [delta])) denote the optimal static bidding scheme given the levels of externalities as described in Remark 2. The (IC-off) constraint for a bidder who realizes a type vi is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The left-hand side is the net gain from deviating in the current period by submitting a bid [??] that is not in the range of the bidding function [b.sup.*]([alpha]). The right-hand side is the present discounted value of the net loss from deviation. The critical discount factor [[delta].sup.*]([alpha]) is defined as the lowest [delta] that satisfies the above (IC-off) constraint.

The following proposition establishes that wars along the equilibrium path are still not necessary, even when bidders are impatient.

PROPOSITION 5. Suppose the increasing hazard rate condition holds. Then, for any scheme (b(x), v(x)) that satisfies both (IC-on) and (IC-off), there exists an alternative stationary scheme (b(x), [??](x) = [[??].sub.S]([alpha], [delta])) where playing [??](x) after any equilibrium-path history satisfies both (IC-on) and (IC-off) while generating as high an expected payoff as the original scheme.

The proof of Proposition 5 is in the Appendix. We show that the alternative no-war scheme as constructed in Proposition 3 in fact relaxes the (IC-off) constraint while still satisfying the (IC-on) constraint. An intuitive explanation of the proof is as follows. For any bidding scheme with wars that are not associated with the bottom step, we have constructed an alternative no-war scheme in Proposition 3 by replacing future wars with higher current-period bids. This effectively reduces the net gain from cheating in the current period because outbidding others is more costly. At the same time, the net loss from deviation is higher because the value of future cooperation increases because of the elimination of future wars. The (IC-off) constraint is, thus, relaxed since the left-hand side decreases while the right-hand side increases with the alternative stationary scheme. A similar reasoning holds for bidding schemes that have wars associated with bottom-step bidders. Remember from Proposition 3 that we have constructed an alternative no-war scheme that generated higher expected payoffs than the original scheme. Again, the net gain from deviation is lower because bidders already expect higher payoffs with the new alternative scheme, and, as with the previous case, the net loss from deviation is higher since a future war is eliminated.

Proposition 5 once again transforms the problem of solving for the optimal bidding scheme in a dynamic setup to that of finding a stationary scheme that maximizes the cartel's current-period revenue, with the exception that now the (IC-off) constraint as well as the (IC-on) constraint bind. We first define the critical discount factor [[delta].sup.*]([alpha]). Let ([v.sup.*1], ..., [v.sup.*K]), ([q.sup.*1], ..., [q.sup.*K]), and ([b.sup.*1], ..., [b.sup.*K]) be the step jump points, win probabilities, and bid amounts associated with the (weakly) increasing step function [b.sup.*]([alpha]) = [b.sup.S]([alpha]). Note that, for any given step, the (IC-off) constraint is satisfied for every bidder as long as it is satisfied for the highest type on that step. (17) When deviating off the equilibrium path, a bidder deviates by submitting a bid amount that is slightly above the bid amount assigned to his step, that is, [??] [congruent to] b([v.sup.*k]). Since [bar.v]([b.sup.*]([v.sub.i]; [alpha]); [b.sup.*]([alpha])) = [[bar.u]([v.sub.i]); [b.sup.*]([alpha])]/[1 - [delta]] by Proposition 5, the (IC-off) constraint for step k can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [[delta].sup.k] is the critical discount factor for bidders on step k. The smallest discount factor that satisfies (IC-off: [v.sup.k]) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

The critical discount factor [[delta].sup.*]([alpha]) is then defined as [[delta].sup.*1]([alpha]) = max([[delta].sup.*1]([alpha]), ..., [[delta].sup.*K]([alpha])). Therefore, the static optimal bidding scheme ([b.sup.*]([alpha]) = [b.sup.S]([alpha]), [v.sup.*]([alpha]) = [bar.[V.sub.S]([alpha], [delta])) is also optimal, as long as 8 [greater than or equal to] [[delta].sup.*]([alpha]).

Now we can ask what happens when bidders become impatient, that is, [delta] < [[delta].sup.*]([alpha]). When bidders are impatient, it becomes challenging for the cartel to keep a low payment to the seller by implementing a (partially) rigid bidding scheme. This is because impatient bidders care less about the future, and it becomes challenging for the cartel to force high-type bidders to share the same probability of winning with low-type bidders just with the promise of a better future. To make matters worse, the low bid amount makes it more tempting for high-type bidders to slightly outbid others. Without loss of generality, suppose the (IC-off) constraint binds first for step k. That is, [[delta].sup.*]([alpha]) = [[delta].sup.k]([alpha]), and for [delta] < [[delta].sup.*]([alpha]) the inequality in (IC-off: [v.sup.k]) is reversed. The changes we can make to the left-hand side of (IC-off: [v.sup.k]) to restore the inequality are either increase the current-period bid [b.sup.*k] so that outbidding others become less profitable or increase the win probabilities [q.sup.*k] so that there is less temptation to deviate. Since [b.sup.*]([alpha]) is optimal without the (IC-off) constraint, the option that restores the (IC-off) constraint with the smaller change to [b.sup.*]([alpha]) is optimal for impatient bidders. We show below that the first option (increase [b.sup.*k]) leads to a high probability of sales (lower [v.sup.*.sub.1]) and that the second option (increase [q.sup.*k]) leads to an increase in bid levels. We explain each option in more detail below.

Let [b.sup.**]([alpha], [delta]) for some 8 < 8*(a) denote the optimal bidding strategy when bidders are impatient. Let ([v.sup.**1], ..., [v.sup.**L]), ([q.sup.**1], ..., [q.sup.**L]), and ([b.sup.**1], ..., [b.sup.**L]) be the associated step jump points, win probabilities, and bid amounts, where L reflects the total number of jumps or the number of bid levels observed by the auctioneer. First consider increasing the bid amount to [b.sup.**k](> [b.sup.*k]) so that the net gain from deviation is smaller. The (IC-on) constraint requires that an increase in the bid for bidders on step k should be followed by an increase in bid for all other types (while maintaining the same win probabilities). However, there is no bid that can be increased for the lowest-type bidders whose utilities depend only on the probability of sales.

Thus, the probability of sales should be increased by lowering [v.sup.**1](< [v.sup.*1]). (18) But a lower threshold type [v.sup.**1] in turn affects the right-hand side of (IC-off: [v.sup.k]) negatively since

[bar.u](v; [b.sup.**]([alpha], [delta])) = - [alpha][[1 - F([v.sup.**1]).sup.n-1] + [E.sub.v][(1 - F(v))/f(v) x q(v; [b.sup.**]([alpha], [delta]))].

This decreases the net loss from deviation as well and such negative influence is magnified by the extent of externalities. Thus, restoring the (IC-off) constraint by means of an increased current-period bid is optimal only when externalities are small. Or, more specifically, when (19)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Second, consider increasing the probability of winning for the type [v.sup.k] so that the temptation of deviation is reduced. This can be done by inducing sorting, that is, letting bidders to bid close to their true valuations while keeping the same probability of sales [v.sup.**1] = [v.sup.*1]. However, more sorting decreases the right-hand side of (IC-off: [v.sup.k]). This is because such a bidding scheme is expected to yield a higher payoff to the seller, thereby negatively influencing the second term in the equation of [bar.u](v, [b.sup.**]([alpha], [delta])). As the second term is not dependent on the extent of externality, this method is preferable when externalities are large, that is, [alpha] [greater than or equal to] [??]([delta]). The following proposition summarizes the discussion above and describes [b.sup.**]([alpha], [delta]) in comparison to the optimal bidding strategy of patient bidders [b.sup.*]([alpha]).

PROPOSITION 6. Suppose the increasing hazard rate condition holds and suppose that [delta] < [[delta].sup.*]([alpha]). There exists 0 < [??]([delta]) < [infinity] such that (i) if [alpha] [greater than or equal to] [??]([delta]), then L > K so that [b.sup.**]([alpha], [delta]) exhibits more jumps than b*([alpha]) and (ii) if [alpha] < [??]([delta]), then either L = K and [v.sup.**1] [member of] min(R - [alpha], [v.sup.R.sub.1]) < [v.sup.*1] so that [b.sup.**] ([alpha], [delta]) exhibits a higher probability of sales than [b.sup.*]([alpha]), or L > K and [v.sup.**1] = min (R - [alpha], [v.sup.R.sub.1]) so that [b.sup.**]([alpha], [delta]) exhibits both a higher probability of sales and more jumps than [b.sup.*]([alpha]).

While Proposition 6 characterizes [b.sup.**]([alpha], [delta]) only in relation to [b.sup.*]([alpha]) for some specified values of ([alpha], [delta]), where [delta] < [[delta].sup.*]([alpha]), we can extend the logic presented in Proposition 6 to describe [b.sup.**]([alpha], [delta]) more generally in relation to the parameter values of [alpha] and [delta] as presented in Figure 1. The optimal bidding scheme when bidders are fully patient ([delta] = 1) is presented at the top of the figure in accordance with Remark 2. Suppose that the optimal bidding scheme when bidders are fully patient and given some value [alpha] is a K-step function. That is, [b.sup.*]([alpha]) = [b.sup.*]([alpha]; K) for 2 [less than or equal to] K < [infinity] with associated values ([v.sup.*1], ..., [v.sup.*K]), ([q.sup.*1], ..., [q.sup.*K]), and ([b.sup.*1], ..., [b.sup.*K]). We can use the (IC-off) constraint to find the combinations of [alpha]s and [delta]s that support [b.sup.*]([alpha]; K) to be optimal, even when bidders become impatient. Fixing ([v.sup.*1], ..., [v.sup.*K]), ([q.sup.*1], ..., [q.sup.*K]), and ([b.sup.*1], ..., [b.sup.*K]), it is clear from Equation 5 that [[partial derivative][[delta].sup.*]([alpha])/([partial derivative][alpha])] [greater than or equal to] 0. Thus, as [alpha] decreases, the critical discount factor [[delta].sup.*]([alpha]) above which the K-step function [b.sup.*]([alpha]; K) is optimal decreases as well. Intuitively, when [alpha] decreases, the expected current period utility increases, and this loosens the threshold level of patience that is required to support a K-step function. Let [??]([b.sup.K]) denote the levels of [alpha] that support a K-step function to be optimal for all ranges of [alpha]. Figure 1 presents the [??]([b.sup.R]) above which the bid-rotation scheme is optimal and the [??]([b.sup.N]) below which no pooling is possible and bidders must use the strictly increasing Nash bidding scheme (with K [right arrow] [infinity]). We explain [??]([b.sup.R]) and [??]([b.sup.N]) in more detail below. From Remark 2, we know that the rigid bidding scheme [b.sup.R] is optimal for [alpha] < [[alpha].sup.+] when [delta] [approximately equal to] 1. And since [([partial derivative][[delta].sup.*]([alpha])/([partial derivative][alpha])] [greater than or equal to] 0, as [alpha] decreases, the critical discount factor that supports [b.sup.R] to be optimal decreases as well. This explains [??]([b.sup.R]). As for [??]([b.sup.N]), we know from Remark 2 that no pooling is possible for [alpha] [greater than or equal to] [[alpha].sup.++] even when [delta] = 1. As [delta] [right arrow] 0, the (IC-off: [v.sup.k]) constraint suggests that the Nash bidding scheme where win probability [q.sup.*k] equals F([v.sup.*k]) for each type is the only supportable bidding scheme. Note that both sides of the (IC-offf : [v.sup.k]) constraint equal zero when the Nash bidding scheme is employed. We can also present [??]([delta]) as the dotted curve in Figure 1 since [lims.sub.[delta]-1] [??]([delta]) = 0 and [lims.sub.[delta]-0] [??]([delta]) = [infinity].

[FIGURE 1 OMITTED]

Now consider some [??] [member of] ([[alpha].sup.+], [[alpha].sup.++]). By Remark 2 and Proposition 3, we know that there exists 2 [less than or equal to] K < [infinity], such that a K-step function is optimal when bidders are patient. The critical discount factor [[delta].sup.*]([alpha]) above which the bidders are considered patient can be solved using Equation 5 and is represented in Figure 1. When the discount factor falls to some [??] below [[delta].sup.*]([??]), Proposition 6 states that the new optimal bidding scheme b**([??], [??]) exhibits more steps if [??] [greater than or equal to] [??]([??]) and a higher probability of sales if [??] < [??]([??]), as long as it is feasible. Note that as [delta] decreases farther away from [[delta].sup.*]([??]), the magnitude of change in [v.sup.**1] that is required to restore the (IC-off) constraint becomes larger. But since [v.sup.**1] is bounded below by max(R - [alpha], [v.sup.1.sub.R]), bidders need to generate more sorting (i.e., collude on a bidding scheme with more steps) when [v.sup.**1] hits the lower feasible bound. (20) While it is difficult to calculate the exact number of steps and the threshold types above which bidding starts for different values of ([alpha], [delta]), Figure 1 does present the general direction of changes that must be made to the optimal bidding scheme [b.sup.**]([alpha], [delta]) for all ranges of ([alpha], [delta]).

The result that the optimal bidding scheme exhibits a larger degree of sorting (i.e., a higher number of observed bids) when facing impatient bidders can be related to the results in Athey, Bagwell, and Sanchirico (2004) and Caillaud and Jehiel (1998). Athey, Bagwell, and Sanchirico (2004) find that a fully rigid pricing scheme (which is optimal for patient bidders) cannot be supported when firms are less patient and that, given certain conditions on density, there exists an optimal two-step pricing scheme where low-cost types are allowed to price at a lower level. Such a two-step pricing scheme certainly involves a larger number of observed prices than the fully rigid scheme and thus carries a similar intuition to the one found in this article. Caillaud and Jehiel (1998) study a case when the participation constraint binds in static auctions with externalities when transfers are available. They show that the threshold type above which bidding starts must decrease to respond to binding participation constraints, compared to the first-best collusion case, in which every bidder is guaranteed at least a zero utility level. Our result bridges these two results depending on the extent of externalities.

5. Conclusion

While extensive research exists on collusive bidding behavior in static auctions, not much has been studied in a repeated auction setup despite the fact that the implementation of most collusive schemes relies on some repeated interaction story. We explicitly modeled an infinitely repeated auction structure to study collusive bidding behavior when bidders are both patient and impatient. For the case of patient bidders, we showed that no wars are necessary along the equilibrium path and that the solution to the static mechanism design problem coincides with the solution to the dynamic programming problem, even in the presence of externalities. The cartel controls both the payment to the seller and the probability of sales, and the optimal collusive bidding scheme is dependent on the extent of externalities. For the case with impatient bidders, we showed that bidding wars are again not necessary along the equilibrium path. However, compared to the optimal bidding scheme with patient bidders, the collusive scheme requires either a higher probability of sales or a larger number of observed bids.

While this article considers the stage game with negative externalities, it is possible for the stage game to involve positive externalities. Consider, for example, a merger of competing firms creating a positive synergy (Jehiel and Moldovanu 1996) or foreign countries bidding for retaliation rights against the home country in case of trade violations (Bagwell, Mavroidis, and Staiger 2006). In such environments, any bidder would want another bidder to win the auction rather than winning himself but still would prefer winning the auction to no one winning at all. Thus, bidders with low valuation may bid more aggressively than bidders with high valuation since they are less assured that the sale will occur. Jehiel and Moldovanu (1996) show that such an incentive difference results in the absence of a pure strategy symmetric separating equilibrium and that there must be some pooling in a symmetric noncooperative equilibrium. Therefore, one can conjecture that the collusive equilibrium may also involve some pooling.

Appendix

PROOF OF PROPOSITION 3. Any scheme can be approximated arbitrarily closely by a scheme where the bid function takes only finitely many values. Hence, without loss of generality, b(x) is a step function. Let b(x) be a K-step function,

where [b.sup.k] = b([[v.sup.k], [p.sup.k+1]]) is the amount of bid assigned to step k, which covers [[v.sup.k], [v.sup.k+1]), k = 0, ..., K, while [v.sup.0] = [v.bar] and [v.sup.K+1] = [bar.v]. (21) The probability of winning for each step is then defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then, b(x) will satisfy the (IC-on) constraint as long as the (IC-on)s at each breakpoint of the steps are satisfied. As indicated in the main text, define [v.sup.1] [equivalent to] [v.sup.1](b) as [v.sup.1] = sup{v : b(v) < R}.

The proof consists of two parts. First, we consider bidding schemes with wars that are not on the bottom step and show that there is an alternative scheme with no wars that gives the same utility to each bidder. Second, we consider bidding schemes with bottom-step wars and show that there exists an alternative scheme that yields higher expected utility with no wars.

First consider any (b, T) that satisfies (IC-on) with [T.sup.k] > 0 for some k [not equal to] 0 and [T.sup.0] = 0. We construct ([??], [??], which yields the same utility for each type, and [[??].sup.k] = 0, [for all] k. Preserve the probabilities of winning [q.sup.k] = [[??].sup.k], [for all]k by fixing [v.sup.k] = [[??].sup.k], [for all]k. Suppose k is the first step for which [T.sup.k] > 0, for some k [greater than or equal to] 1. Note that for j = 0, ..., k - 1, [[??].sup.j] = [b.sup.j], and [[??].sup.j] = 0 satisfies (IC-on). Then define [[??].sup.k] as

[[??].sup.k] = [b.sup.k] + [T.sup.k]/[q.sup.k]. (A1)

Noting that the (IC-on) constraint is satisfied as long as [v.sup.k] has no incentive to deviate, (IC-on) for step k is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A2)

Substituting Equation A1 into Equation A2 and since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], by construction we get

- [alpha] + ([v.sup.k] + [alpha] - [b.sup.*])[q.sup.k] - [T.sup.k] = - [alpha] + ([v.sup.k] + [alpha] - [b.sup.k- 1])[q.sup.k-1] - [T.sub.k-1]. (A3)

which is the IC condition for (b, 7). Since the original scheme (b, 7) satisfies the IC, so does ([??], [??]). Any other wars in subsequent steps can be removed in a similar manner.

Second, consider (b, T) with [T.sup.0] > 0 and [T.sup.k] = 0, [for all] k [greater than or equal to] 1. (22) As discussed in the main text, this part is complicated due to externalities because the bottom-step bidders' utilities depend on the actions of other bidders, that is, the number of bidders that bid above R, which is determined solely by [v.sup.1]. Since there is no bid we can consider for these bidders, we must work with probabilities of winning, which are defined by the step widths ([v.sup.1], [v.sup.2], ..., [v.sup.K]), to construct ([??], [??] = 0) that satisfies IC and yields higher utilities than (b, 7). Despite the length of the proof, the idea is relatively simple. We take away the bottom-step war, which increases the utility at bottom. Then, by incentive compatibility, everyone else's utility increases, which is represented by more favorable probabilities of winning. Equations A4-A8 show what kind of changes are necessary when we set [??] = 0. Then, Equations A9-A12 show that utilities for all types in different steps are indeed higher under the new scheme.

Consider ([??], [??] = 0) with the following step widths: p[??].sup.1] = [v.sup.1], where [v.sup.1] [member of] [max(R - [alpha], [v.sup.1.sub.R]), R] (23); [[??].sup.2] [member of] [[v.sup.j], [v.sup.j+1]) for some j [greater than or equal to] 2; and [[??].sup.l] = [v.sup.j+l-2] for l [greater than or equal to] 3. We show that the alternative bidding scheme ([??], [??] = 0) that generates as high an expected profit as the original bidding scheme (b, T > 0) takes the following form:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We first explain the changes made to ([??], [??] = 0) to guarantee that the incentive compatibility condition is satisfied. To satisfy (IC-on) at [[??].sup.1] = [v.sup.1],

-[alpha] + [alpha]F[([v.sup.1]).sup.n-1] = -[alpha]+([v.sup.1] + [alpha] - R)[[??].sup.1] (A4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (A5)

where the equation for [q.sup.1] comes from (b, T) satisfying IC at [v.sup.1]. Equation A5 suggests that [[??].sup.2] > [v.sup.2] since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let j be the step under (b, T) such that [v.sup.j] [less than or equal to] [[??].sup.2] < [v.sup.j+l]. Set [[??].sup.3] = [v.sup.j+l-2] for l [greater than or equal to] 3. By (IC-on) at [v.sup.2],

-[alpha]+([v.sup.2] + [alpha] - R) x [q.sup.1] = -[alpha] + ([v.sup.2] + [alpha] - [b.sup.2]) x [q.sup.2] (A6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A7)

By (IC-on)s at each step,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A8)

Thus, ([partial derivative][q.sup.j]/[partial derivative][T.sup.0]) [less than or equal to] 0 for j [greater than or equal to] 1.

Now we show that the utility for each bidder is higher under ([??], [??] = 0) using the relationship [bar.u](v, b(x)) - T(v) = [bar.u]([v.bar], b(x)) - T([v.bar]) + [[integral].sup.v.sub.[v.bar]] q(s; b(x))ds, which holds under incentive compatibility. (24) For types v [member of] [[v.bar], [v.sup.1]],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A9)

For types v [member of] [[v.sup.1], [v.sup.2]],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A10)

For types v [member of] [[v.sup.2], [[??].sup.2]],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A11)

Differentiating with respect to [T.sup.0],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

since ([partial derivative][q.sup.j]/[partial derivative][T.sup.0]) < 0 for j [greater than or equal to] 1. Then, because [bar.u](v; ([??],[??]) = [bar.u](v; (b, 7)) when [T.sup.0] = 0, this implies that [bar.u](v: ([??],[??]) > [bar.u](v; (b, T)) for [T.sup.0] > 0. The intuition is that once the bottom-step utility is increased by eliminating a war, subsequent step bidders must have higher probabilities of winning to satisfy (IC-on), which in turn increases their expected utilities.

Finally, for types v [member of] [[[??].sup.2], v],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A12)

since [bar.u]([[??].sup.2]; ([??],[??])) > [bar.u]([[??].sup.2]; (b, T)) by Equation A11, [[??].sup.2] > [q.sup.j] because [[??].sup.2] [greater than or equal to] [v.sup.j] and [[??].sup.3] = [v.sup.j+1], and finally [[??].sup.l] = [q.sup.j-l-2] for l [greater than or equal to] 3 by construction of ([??],[??]). Q.E.D.

PROOF OF PROPOSITION 5: From Proposition 3, we have already shown that for any scheme (b(x), v(x)) that satisfies the (IC-on) constraint, there exists an alternative scheme ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) that also satisfies the (IC-on) constraint. Thus, we need only to show that the alternative no-war scheme ([??](x), [??](x) = [[bar.V].sub.S]) as constructed in the proof of Proposition 3 also satisfies the (IC-off') constraint.

Since the original scheme satisfies (IC-off') and substituting [bar.v](b([v.sub.i]); b(x)) = [[bar.V].sub.S] - [T([v.sub.i])]/[delta], we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A13)

The alternative scheme implements T(x) = 0, so immediately the right-hand side of Equation A13 increases under the alternative scheme.

As for the left-hand side of Equation A13, note that for any bidder to deviate in an obvious manner, it is profitable to slightly outbid the bid that is assigned to that bidder's step, that is, [??] [equivalent] b([b.sub.i]). Any bid lower than that would not enable the bidder to win while only exposing cheating from the collusive agreement. Any bid higher than that must be as high as the bid assigned to the step above the bidder's type, but this is not profitable as long as the (IC-on) constraint is satisfied. Thus, the left-hand side of Equation A13 can be reduced to ([v.sub.i] + [alpha] - b([v.sub.1])) [F[([v.sub.i]).sup.n-1] - q([v.sub.i]; b(x))]. The alternative scheme constructed in the proof of Proposition 3 specifies either a higher current-period bid (Equation A 1) or a higher probability of winning (Equation A8). Thus, we conclude that the (IC-off') constraint is relaxed with the alternative scheme ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). Q.E.D.

PROOF OF PROPOSITION 6: First consider increasing [b.sup.*k] < [b.sup.**k] so that the (IC-off' : [v.sup.k]) is satisfied. We need to show that [b.sup.**](x) is still incentive compatible. Fix the step widths [v.sup.**k] = [v.sup.*k], [for all]k [greater than or equal to] 2 so that [q.sup.**k] = [q.sup.*k]; that is, probabilities of winning stay the same for all k [greater than or equal to] 2. Then, incentive compatibility requires for bids in all other steps to increase as well. That is, [b.sup.**k] > [b.sup.*k] for all k [greater than or equal to] 2. But, on the first step, it becomes implausible to keep the same step width since no bid in the bottom step can be used as an instrument. From (IC-on) at [v.sup.*2], we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A14)

Since [v.sup.**2] is fixed at [v.sup.*2], by the definition of [q.sup.**1] = q([v.sup.**1], [v.sup.**2]), it must be true that [v.sup.**1] < [v.sup.*1], and thus there will be a higher probability of sales. In addition, while the change in v**l decreases the left-hand side of Equation A16, it also influences the right-hand side through

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A decrease in [v.sup.**1] decreases [bar.u]([v.sub.i]; [b.sup.**](x)) and at a faster rate if [alpha] is large. Hence, constructing [b.sup.**](x) to satisfy (IC-off') by means of an increased bid amounts as constructed above is optimal only when [alpha] is small. More specifically, the change induced to the left-hand side of (IC-off' : [v.sup.k]) by increasing [b.sup.*k] to [b.sup.**k] must be larger than the change induced to the right-hand side of (IC-off' : [v.sup.k]). Formally, differentiating (IC-off' : [v.sup.k]) with respect to [b.sup.**k], we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (A15)

where [partial derivative][v.sup.**1]/[[partial derivative].sup.b**2] is negative as explained above and is found implicitly from (IC-on) at

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Solving the inequality for [alpha], we get that this method is effective only when

[v.sup.*] 2[q.sup.**1] ([v.sup.**1], [v.sup.*2]) = ([v.sup.*2] + [alpha] - [b.sup.**2])/[v.sup.*2] + [alpha] - R) x [q.sup.*2.]

Also, [partial derivative][b.sup.**k-1]/[partial derivative][b.sup.**k] are positive and are found from (IC-on) at each (25)

[v.sup.*] k [b.sup.**k-1] = [v.sup.*k] + [alpha] - ([v.sup.*k] + [alpha] - [b.sup.**k] x [q.sup.*k]/[q.sup.*k-1].

Solving the inequality for [alpha], we get that this method is effective only when

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that this method is feasible only for the feasible range of [v.sup.**1] [member of] max[R - [alpha], [v.sup.1.sub.R]]. When the magnitude of the change required for [b.sup.**k] is so large that it requires a v**l below the feasible range, we need to resort to the second method, which is described below.

Second, consider increasing [q.sup.*k], that is, [q.sup.**k] > [q.sup.*k] for [alpha] [greater than or equal to] [??]([delta]). To implement a higher [q.sup.**k] = q([v.sup.**k], [V.sup.**k+1]), increase [v.sup.**k+1] while fixing the threshold type for the first step, that is, [v.sup.*1] = [v.sup.**1]. The probability of sales stays the same. Since [b.sup.*](x) as constructed in Proposition 5 is the most rigid incentive compatible bidding scheme given [v.sup.*1], it must be that this change induces more sorting than [b.sup.*](x). This change also affects the right-hand side of (IC-off' : [v.sup.k]) through [bar.u](v, [b.sup.**](x)) but in a way that the change does not depend on the extent of externalities. Thus, constructing [b.sup.**](x) by means of an increased sorting is effective when [alpha] is large. Also note that this method is always feasible since [q.sup.*k] gets closer to [F.sup.(v*k+1)] as we induce more sorting, which reduces the left-hand side of (IC-off' : [v.sup.k]) to as low as zero. Q.E.D.

References

Abdulkadiroglu, A., and K. S. Chung. 2002. Mechanism design with tacit collusion. Columbia University Department of Economics Discussion Paper Series 0102-68.

Abreu, D. 1986. Extremal equilibria of oligopolistic supergames. Journal of Economic Theory 39:191-228.

Abreu, D. 1988. On the theory of infinitely repeated games with discounting. Econometrica 56:383-96.

Abreu, D., D. Pearce, and E. Stacchetti. 1986. Optimal cartel equilibria with imperfect monitoring. Journal of Economic Theory 39:251-69.

Abreu, D., D. Pearce, and E. Stacchetti. 1990. Toward a theory of discounted repeated games with imperfect monitoring. Econometrica 58:1041-63.

Aoyagi, M. 2003. Bid rotation and collusion in repeated auctions. Journal of Economic Theory 112:79-105.

Aoyagi, M. 2007. Efficient collusion in repeated auctions with communication. Journal of Economic Theory 134:61-92.

Athey, S., and K. Bagwell. 2001. Optimal collusion with private information. RAND Journal of Economics 32:428-65.

Athey, S., K. Bagwell, and C. Sanchirico. 2004. Collusion and price rigidity. Review of Economic Studies 71:317-49.

Bagwell, K., P. Mavroidis, and R. Staiger. 2006. Private monitoring in auctions. Journal of International Economics 73:309-32.

Blume, A., and P. Heidhues. 2006. Private monitoring in auctions. Journal of Economic Theory 131:179-211.

Brocas, I. 2003. Endogenous entry into auctions with negative externalities. Theory and Decision 54:125-49.

Caillaud, B., and P. Jehiel. 1998. Collusion in auctions with externalities. RAND Journal of Economics 29:680-702.

Fabra, N. 2003. Tacit collusion in repeated auctions: uniform versus discriminatory. Journal of Industrial Economics 51:271-93.

Fudenberg, D., D. Levine, and E. Maskin. 1994. The folk theorem with imperfect public information. Econometrica 62(5):87-100.

Hendricks, K., and R. Porter. 1989. Collusion in auctions. Annales D'economie Et Statistique (15 16):217-30.

Jehiel, P., and B. Moldovanu. 1996. Strategic nonparticipation. RAND Journal of Economics 27:84-98.

Jehiel, P., B. Moldovanu, and E. Stacchetti. 1996. How (not) to sell nuclear weapons. American Economic Review 86:814-29.

Jofre-Bonet, M., and M. Pesendorfer. 2000. Bidding behavior in repeated procurement auctions: A summary. European Economic Review 44:1006-20.

Lu, J. 2007. Unifying identity-specific and financial externalities in auction design. Paper presented at the annual meeting of the American Economic Association. Available http://www.aeaweb.org/annual_mtg_papers/2008/2008_489.pdf.

McAfee, R., and J. McMillan. 1992. Bidding rings. American Economic Review 82:579-99.

Myerson, R. 1983. Optimal auction design. Mathematics of Operations Research 6:58-73.

Porter, R., and D. Zona. 1993. Detection of bid rigging in procurement auctions. Journal of Political Economy 101:518-39.

Rhee, K. 2007. Collusion in the presence of externalities. Journal of Industrial Economics 55:475-97.

Skrzypacz, A., and H. Hopenhayn. 2004. Tacit collusion in repeated auctions. Journal of Economic Theory 114:153-69.

Ki-Eun Rhee, KDI School of Public Policy, 207-43 Cheongnyangridong, Dongdaemun-gu, Seoul Korea 130-868; E-mail krhee@kdischool.ac.kr.

I am grateful to Kyle Bagwell for providing invaluable advice and support throughout the research process. I also thank Michael Riordan, Eiichi Miyagawa, and two anonymous referees for helpful comments.

Received August 2008; accepted January 2010.

(1) See, for example, section 1 (Enforcement) of McAfee and McMillan (1992) or Abdulkadiroglu and Chung (2002) for a discussion on this issue.

(2) See Jofre-Bonet and Pesendorfer (2000), Porter and Zona (1993), and comments in Hendricks and Porter (1989) on needs for theoretical treatments of repeated auctions.

(3) The analysis of procurement auctions is a mirror image of standard auctions (i.e., auctions in which the high bidder wins).

(4) The discount factor in a repeated game may also represent the likelihood of meeting the same group of players again by redefining the discount factor to be [??] = p[delta], where p is the probability of playing the game again. Then, a game with patient players can be viewed as a game in which players believe that there is a high probability of the game being repeated and thus assigns a high value to the future. The market where this probability is high would certainly be a more stable market than an unstable one.

(5) Note that. in auctions with externalities, the set of bidders includes all players that are influenced by the outcome of the auction. Consider the example of auctions for highway construction contracts. As discussed in the introduction, the externalities may arise when the winning firm gains comparative advantage in the private sector competition after the auction. In such case, any firm that is operating within the industry may be affected by the outcome of the auction even if that firm does not physically participate in the auction. Such bidders can be considered as one of the bidders who do not bid above the seller's reservation value.

(6) Caillaud and Jehiel (1998) call this value [v.sub.i] + [alpha] the "augmented valuation" and show that the dominant strategy is to bid the augmented value truthfully in a second-price auction.

(7) Note that the threshold type above whom the bidding functions assigns to bid above R is [v.sub.i] = R for Nash equilibrium, that is, [b.sup.N](R) = R. While one may wonder why a bidder with [v.sub.i] = R - [epsilon] for [epsilon] small is not tempted to bid above R to avoid incurring - [alpha] when [alpha] is large, Equation 1 provides the answer quite straightforwardly. If such bidder adheres to [b.sup.N](x) by submitting [b.sub.i] < R, he receives [bar.u]([b.sub.i] < R, [v.sub.i] = R - [epsilon]) = - [epsilon] + [alpha] x prob[b([v.sub.j]) < R, [for all]j [not equal to] i]. But when he deviates by submitting [b.sub.i] = R, he receives [bar.u]([b.sub.i] = R, [v.sub.i] = R - [epsilon]) = - [alpha] + (R - [epsilon] + [alpha] - R) x prob[b([v.sub.j]) < R, [for all]j [not equal to] i]. The net difference is - [epsilon] x prob[b([v.sub.j]) < R, [for all]j [not equal to] t], and thus such deviation can never be profitable. Because [[db.sup.N]([v.sub.i])]/d[v.sub.i] is strictly positive, any deviation with [b.sub.i] > R is also not profitable.

(8) For a detailed derivation of [v.sup.1.sub.R]. see Rhee (2007, proposition 2).

(9) For the exact qualifications of [[alpha].sup.+] and [[alpha].sup.++], see the proof of proposition 7 in Rhee (2007, p. 493). The exact value of [v.sup.1] can be determined given the parameter values of [alpha], R, and n through the algorithm provided in appendix B of Rhee (2007).

(10) More specifically, the lower bound on the set of feasible threshold type [v.sup.1] is max(R - [alpha], [v.sup.1.sub.R]) since a bidder with a valuation less than R - [alpha] has no reason to bid above R at all because his "augmented bid" v + [alpha] is less than R.

(11) SPPE arise when asymmetric treatment of bidders is not possible (e.g., when the seller does not disclose the identity of the winner, as often is the case in practice). Additionally, focusing on SPPE greatly alleviates technical difficulty in solving for optimality as asserted in Abreu (1986, 1988).

(12) See section 3 of Athey, Bagwell, and Sanchirico (2004) for more details on this transformation.

(13) See Myerson (1981), McAfee and McMillan (1992), or MasCollel et al. (proposition 23.D.2).

(14) In a related matter, Lu (2007, proposition 1) establishes a version of revenue equivalence in environments with externalities by showing that the expected payoffs of all players are determined by the expected payoffs of the lowest types and the players' probabilities of winning.

(15) Note that the probability of sales is different from probabilities of winning. The probability of sales is the probability that there exists a bidder who bids above the seller's reservation value, that is, prob[there exists v [not equal to] [v.bar] s.t. b(v) > R]. Given the distribution of types, this depends only on the lowest type above whom bidding starts.

(16) Indeed, the expected continuation value is simply the expected per-period profit when bidders follow [b.sup.*](x) in each period, that is, [bar.[V.sub.S]]([alpha], [delta])) - [bar.u](v; [b.sup.*](x))/(1 - [delta]).[b.sup.*](x) in each period, that is, [bar.[V.sub.S]([alpha], [delta])) = [bar.u](v; [b.sup.*](x))/(1 - [delta]).

(17) This can be easily verified by examining (IC-off). As the type increases, the right-hand side of the equation stays the same, and the left-hand side increases monotonically in type while all bidders on the same step share the same bid [b.sub.i] and probability of winning [q.sup.i]. Thus, if the highest type on any given step finds it unprofitable to slightly outbid others, the rest of the bidders on that step will have no incentives to do so either.

(18) See the proof in the Appendix for technical details.

(19) The equation for [??]([delta]) is derived by taking partial derivatives of the left- and the right-hand sides (IC-off: [v.sup.k]). See the Appendix for a more detailed derivation.

(20) See the discussion following Remark 2 and footnote 10 for the lower bound of feasible [v.sup.1].

(21) The analysis for any nondecreasing function can by treated by constructing a sequence of step functions that converges to b as K [right arrow] [infinity]. That is, each element of the sequence is equal to b on intervals where b is constant or strictly increasing and is equal to the limit of a convergent subsequence.

(22) Here we assume that any [T.sup.k] > 0 for some k [not equal to] 0 is eliminated via Equation AI. In a special case where the original (b, T) involves [T.sup.1] > 0, [b.sup.1] > R will result after eliminating [T.sup.1] via Equation A1. In such a case, replace R by [b.sup.1] in the rest of the proof, and the result will still hold.

(23) For trivial cases of (b(x), T(x)) with [v.sup.1] < max[R - [alpha], [v.sup.1.sub.R]] and [T.sup.0] > 0 is dominated by a one-step function ([??](x), [??] = 0) with [[??].sup.1] = [v.sup.1.sub.R]. First, compare a one-step function with [v.sup.1] < max[R - [alpha], [v.sup.1.sub.R]] to the one-step function with [[??].sup.1] = [v.sup.1.sub.R], that is, the bid-rotation scheme. For types v [member of] [[v.bar], [v.sup.1]], they are better off because the bottom-step war is gone, and also [[??].sup.1] > [v.sup.1]. For types [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and thus they are better off. Finally, types v [member of] [[[??].sup.1], [??]] are also better off because they enjoy higher probabilities of winning. Now for bidding functions with [v.sup.1] < max[R - [alpha], [v.sup.1.sub.R]] and more than two steps, these are dominated by the one-step function with the same [v.sup.1] because the expectation term in Equation 4, which is the cartel profit without externalities, is maximized by the one-step function (i.e., the bid-rotation scheme in McAfee and McMillan 1992), while the first two terms in Equation 4 stay the same.

(24) See footnote 12 for references on this.

(25) Dervied from similar equation to Equation A2.

Printer friendly Cite/link Email Feedback | |

Comment: | Repeated auctions with impatient bidders and externalities. |
---|---|

Author: | Rhee, Ki-Eun |

Publication: | Southern Economic Journal |

Date: | Oct 1, 2010 |

Words: | 11847 |

Previous Article: | Liquidity risk and banks' asset composition: implications for monetary policy. |

Next Article: | An international economics classroom experiment. |

Topics: |