On Cheating in Sealed-Bid Auctions Ryan Porter rwporter@stanford.edu Yoav Shoham shoham@stanford.edu Computer Science Department Stanford University Stanford, CA 94305 ABSTRACT Motivated by the rise of online auctions and their relative lack of security, this paper analyzes two forms of cheating in sealed-bid auctions. The first type of cheating we consider occurs when the seller spies on the bids of a second-price auction and then inserts a fake bid in order to increase the payment of the winning bidder. In the second type, a bidder cheats in a first-price auction by examining the competing bids before deciding on his own bid. In both cases, we derive equilibrium strategies when bidders are aware of the possibility of cheating. These results provide insights into sealedbid auctions even in the absence of cheating, including some counterintuitive results on the effects of overbidding in a first-price auction. Categories and Subject Descriptors J.4 [Computer Applications]: Social and Behavioral Sciences-Economics General Terms Economics, Security 1. INTRODUCTION Among the types of auctions commonly used in practice, sealed-bid auctions are a good practical choice because they require little communication and can be completed almost instantly. Each bidder simply submits a bid, and the winner is immediately determined. However, sealed-bid auctions do require that the bids be kept private until the auction clears. The increasing popularity of online auctions only makes this disadvantage more troublesome. At an auction house, with all participants present, it is difficult to examine a bid that another bidder gave directly to the auctioneer. However, in an online auction the auctioneer is often little more than a server with questionable security; and, since all participants are in different locations, one can anonymously attempt to break into the server. In this paper, we present a game theoretic analysis of how bidders should behave when they are aware of the possibility of cheating that is based on knowledge of the bids. We investigate this type of cheating along two dimensions: whether it is the auctioneer or a bidder who cheats, and which variant (either first or second-price) of the sealed-bid auction is used. Note that two of these cases are trivial. In our setting, there is no incentive for the seller to submit a shill bid in a first price auction, because doing so would either cancel the auction or not affect the payment of the winning bidder. In a second-price auction, knowing the competing bids does not help a bidder because it is dominant strategy to bid truthfully. This leaves us with two cases that we examine in detail. A seller can profitably cheat in a second-price auction by looking at the bids before the auction clears and submitting an extra bid. This possibility was pointed out as early as the seminal paper [12] that introduced this type of auction. For example, if the bidders in an eBay auction each use a proxy bidder (essentially creating a second-price auction), then the seller may be able to break into eBay"s server, observe the maximum price that a bidder is willing to pay, and then extract this price by submitting a shill bid just below it using a false identity. We assume that there is no chance that the seller will be caught when it cheats. However, not all sellers are willing to use this power (or, not all sellers can successfully cheat). We assume that each bidder knows the probability with which the seller will cheat. Possible motivation for this knowledge could be a recently published expos´e on seller cheating in eBay auctions. In this setting, we derive an equilibrium bidding strategy for the case in which each bidder"s value for the good is independently drawn from a common distribution (with no further assumptions except for continuity and differentiability). This result shows how first and second-price auctions can be viewed as the endpoints of a spectrum of auctions. But why should the seller have all the fun? In a first-price auction, a bidder must bid below his value for the good (also called shaving his bid) in order to have positive utility if he 76 wins. To decide how much to shave his bid, he must trade off the probability of winning the auction against how much he will pay if he does win. Of course, if he could simply examine the other bids before submitting his own, then his problem is solved: bid the minimum necessary to win the auction. In this setting, our goal is to derive an equilibrium bidding strategy for a non-cheating bidder who is aware of the possibility that he is competing against cheating bidders. When bidder values are drawn from the commonly-analyzed uniform distribution, we show the counterintuitive result that the possibility of other bidders cheating has no effect on the equilibrium strategy of an honest bidder. This result is then extended to show the robustness of the equilibrium of a first-price auction without the possibility of cheating. We conclude this section by exploring other distributions, including some in which the presence of cheating bidders actually induces an honest bidder to lower its bid. The rest of the paper is structured as follows. In Section 2 we formalize the setting and present our results for the case of a seller cheating in a second price auction. Section 3 covers the case of bidders cheating in a first-price auction. In Section 4, we quantify the effects that the possibility of cheating has on an honest seller in the two settings. We discuss related work, including other forms of cheating in auctions, in Section 5, before concluding with Section 6. All proofs and derivations are found in the appendix. 2. SECOND-PRICE AUCTION, CHEATING SELLER In this section, we consider a second-price auction in which the seller may cheat by inserting a shill bid after observing all of the bids. The formulation for this section will be largely reused in the following section on bidders cheating in a first-price auction. While no prior knowledge of game theory or auction theory is assumed, good introductions can be found in [2] and [6], respectively. 2.1 Formulation The setting consists of N bidders, or agents, (indexed by i = 1, · · · , n) and a seller. Each agent has a type θi ∈ [0, 1], drawn from a continuous range, which represents the agent"s value for the good being auctioned.2 Each agent"s type is independently drawn from a cumulative distribution function (cdf ) F over [0, 1], where F(0) = 0 and F(1) = 1. We assume that F(·) is strictly increasing and differentiable over the interval [0, 1]. Call the probability density function (pdf ) f(θi) = F (θi), which is the derivative of the cdf. Each agent knows its own type θi, but only the distribution over the possible types of the other agents. A bidding strategy for an agent bi : [0, 1] → [0, 1] maps its type to its bid.3 Let θ = (θ1, · · · , θn) be the vector of types for all agents, and θ−i = (θ1, · · · , θi−1, θi+1, · · · θn) be the vector of all types except for that of agent i. We can then combine the vectors so that θ = (θi, θ−i). We also define the vector of bids as b(θ) = (b1(θ1), . . . , bn(θn)), and this vector without 2 We can restrict the types to the range [0, 1] without loss of generality because any distribution over a different range can be normalized to this range. 3 We thus limit agents to deterministic bidding strategies, but, because of our continuity assumption, there always exists a pure strategy equilibrium. the bid of agent i as b−i(θ−i). Let b[1](θ) be the value of the highest bid of the vector b(θ), with a corresponding definition for b[1](θ−i). An agent obviously wins the auction if its bid is greater than all other bids, but ties complicate the formulation. Fortunately, we can ignore the case of ties in this paper because our continuity assumption will make them a zero probability event in equilibrium. We assume that the seller does not set a reserve price.4 If the seller does not cheat, then the winning agent pays the highest bid by another agent. On the other hand, if the seller does cheat, then the winning agent will pay its bid, since we assume that a cheating seller would take full advantage of its power. Let the indicator variable µc be 1 if the seller cheats, and 0 otherwise. The probability that the seller cheats, Pc , is known by all agents.5 We can then write the payment of the winning agent as follows. pi(b(θ), µc ) = µc · bi(θi) − (1 − µc ) · b[1](θ−i) (1) Let µ(·) be an indicator function that takes an inequality as an argument and returns is 1 if it holds, and 0 otherwise. The utility for agent i is zero if it does not win the auction, and the difference between its valuation and its price if it does. ui(b(θ), µc , θi) = µ bi(θi) > b[1](θ−i) · θi − pi(b(θ), µc ) (2) We will be concerned with the expected utility of an agent, with the expectation taken over the types of the other agents and over whether or not the seller cheats. By pushing the expectation inward so that it is only over the price (conditioned on the agent winning the auction), we can write the expected utility as: Eθ−i,µc [ui(b(θ), µc , θi)] = Prob bi(θi) > b[1](θ−i) · θi − Eθ−i,µc pi(b(θ), µc ) | bi(θi) > b[1](θ−i) (3) We assume that all agents are rational, expected utility maximizers. Because of the uncertainty over the types of the other agents, we will be looking for a Bayes-Nash equilibrium. A vector of bidding strategies b∗ is a Bayes-Nash equilibrium if for each agent i and each possible type θi, agent i cannot increase its expected utility by using an alternate bidding strategy bi, holding the bidding strategies for all other agents fixed. Formally, b∗ is a Bayes-Nash equilibrium if: ∀i, θi, bi Eθ−i,µc ui b∗ i (θi), b∗ −i(θ−i) , µc , θi ≥ Eθ−i,µc ui bi(θi), b∗ −i(θ−i) , µc , θi (4) 2.2 Equilibrium We first present the Bayes-Nash equilibrium for an arbitrary distribution F(·). 4 This simplifies the analysis, but all of our results can be applied to the case in which the seller announces a reserve price before the auction begins. 5 Note that common knowledge is not necessary for the existence of an equilibrium. 77 Theorem 1. In a second-price auction in which the seller cheats with probability Pc , it is a Bayes-Nash equilibrium for each agent to bid according to the following strategy: bi(θi) = θi − θi 0 F( N−1 P c ) (x)dx F( N−1 P c ) (θi) (5) It is useful to consider the extreme points of Pc . Setting Pc = 1 yields the correct result for a first-price auction (see, e.g., [10]). In the case of Pc = 0, this solution is not defined. However, in the limit, bi(θi) approaches θi as Pc approaches 0, which is what we expect as the auction approaches a standard second-price auction. The position of Pc is perhaps surprising. For example, the linear combination bi(θi) = θi − Pc · θi 0 F (N−1) (x)dx F (N−1)(θi) of the equilibrium bidding strategies of first and second-price auctions would have also given us the correct bidding strategies for the cases of Pc = 0 and Pc = 1. 2.3 Continuum of Auctions An alternative perspective on the setting is as a continuum between first and second-price auctions. Consider a probabilistic sealed-bid auction in which the seller is honest, but the price paid by the winning agent is determined by a weighted coin flip: with probability Pc it is his bid, and with probability 1 − Pc it is the second-highest bid. By adjusting Pc , we can smoothly move between a first and second-price auction. Furthermore, the fact that this probabilistic auction satisfies the properties required for the Revenue Equivalence Theorem (see, e.g., [2]) provides a way to verify that the bidding strategy in Equation 5 is the symmetric equilibrium of this auction (see the alternative proof of Theorem 1 in the appendix). 2.4 Special Case: Uniform Distribution Another way to try to gain insight into Equation 5 is by instantiating the distribution of types. We now consider the often-studied uniform distribution: F(θi) = θi. Corollary 2. In a second-price auction in which the seller cheats with probability Pc , and F(θi) = θi, it is a Bayes-Nash equilibrium for each agent to bid according to the following strategy: bi(θi) = N − 1 N − 1 + Pc θi (6) This equilibrium bidding strategy, parameterized by Pc , can be viewed as an interpolation between two well-known results. When Pc = 0 the bidding strategy is now welldefined (each agent bids its true type), while when Pc = 1 we get the correct result for a first-price auction: each agent bids according to the strategy bi(θi) = N−1 N θi. 3. FIRST-PRICE AUCTION, CHEATING AGENTS We now consider the case in which the seller is honest, but there is a chance that agents will cheat and examine the other bids before submitting their own (or, alternatively, they will revise their bid before the auction clears). Since this type of cheating is pointless in a second-price auction, we only analyze the case of a first-price auction. After revising the formulation from the previous section, we present a fixed point equation for the equilibrium strategy for an arbitrary distribution F(·). This equation will be useful for the analysis the uniform distribution, in which we show that the possibility of cheating agents does not change the equilibrium strategy of honest agents. This result has implications for the robustness of the symmetric equilibrium to overbidding in a standard first-price auction. Furthermore, we find that for other distributions overbidding actually induces a competing agent to shave more off of its bid. 3.1 Formulation It is clear that if a single agent is cheating, he will bid (up to his valuation) the minimum amount necessary to win the auction. It is less obvious, though, what will happen if multiple agents cheat. One could imagine a scenario similar to an English auction, in which all cheating agents keep revising their bids until all but one cheater wants the good at the current winning bid. However, we are only concerned with how an honest agent should bid given that it is aware of the possibility of cheating. Thus, it suffices for an honest agent to know that it will win the auction if and only if its bid exceeds every other honest agent"s bid and every cheating agent"s type. This intuition can be formalized as the following discriminatory auction. In the first stage, each agent"s payment rule is determined. With probability Pa , the agent will pay the second highest bid if it wins the auction (essentially, he is a cheater), and otherwise it will have to pay its bid. These selections are recorded by a vector of indicator variables µa = (µa1 , . . . , µan ), where µai = 1 denotes that agent i pays the second highest bid. Each agent knows the probability Pa , but does not know the payment rule for all other agents. Otherwise, this auction is a standard, sealed-bid auction. It is thus a dominant strategy for a cheater to bid its true type, making this formulation strategically equivalent to the setting outlined in the previous paragraph. The expression for the utility of an honest agent in this discriminatory auction is as follows. ui(b(θ), µa , θi) = θi − bi(θ) · j=i µaj · µ bi(θi) > θj + (1 − µaj ) · µ bi(θi) > bj(θj) (7) 3.2 Equilibrium Our goal is to find the equilibrium in which all cheating agents use their dominant strategy of bidding truthfully and honest agents bid according to a symmetric bidding strategy. Since we have left F(·) unspecified, we cannot present a closed form solution for the honest agent"s bidding strategy, and instead give a fixed point equation for it. Theorem 3. In a first-price auction in which each agent cheats with probability Pa , it is a Bayes-Nash equilibrium for each non-cheating agent i to bid according to the strategy that is a fixed point of the following equation: bi(θi) = θi − θi 0 Pa · F(bi(x)) + (1 − Pa) · F(x) (N−1) dx Pa · F(bi(θi)) + (1 − Pa) · F(θi) (N−1) (8) 78 3.3 Special Case: Uniform Distribution Since we could not solve Equation 8 in the general case, we can only see how the possibility of cheating affects the equilibrium bidding strategy for particular instances of F(·). A natural place to start is uniform distribution: F(θi) = θi. Recall the logic behind the symmetric equilibrium strategy in a first-price auction without cheating: bi(θi) = N−1 N θi is the optimal tradeoff between increasing the probability of winning and decreasing the price paid upon winning, given that the other agents are bidding according to the same strategy. Since in the current setting the cheating agents do not shave their bid at all and thus decrease an honest agent"s probability of winning (while obviously not affecting the price that an honest agent pays if he wins), it is natural to expect that an honest agent should compensate by increasing his bid. The idea is that sacrificing some potential profit in order to regain some of the lost probability of winning would bring the two sides of the tradeoff back into balance. However, it turns out that the equilibrium bidding strategy is unchanged. Corollary 4. In a first-price auction in which each agent cheats with probability Pa , and F(θi) = θi, it is a BayesNash equilibrium for each non-cheating agent to bid according to the strategy bi(θi) = N−1 N θi. This result suggests that the equilibrium of a first-price auction is particularly robust when types are drawn from the uniform distribution, since the best response is unaffected by deviations of the other agents to the strategy of always bidding their type. In fact, as long as all other agents shave their bid by a fraction (which can differ across the agents) no greater than 1 N , it is still a best response for the remaining agent to bid according to the equilibrium strategy. Note that this result holds even if other agents are shaving their bid by a negative fraction, and are thus irrationally bidding above their type. Theorem 5. In a first-price auction where F(θi) = θi, if each agent j = i bids according a strategy bj(θj) = N−1+αj N θj, where αj ≥ 0, then it is a best response for the remaining agent i to bid according to the strategy bi(θi) = N−1 N θi. Obviously, these strategy profiles are not equilibria (unless each αj = 0), because each agent j has an incentive to set αj = 0. The point of this theorem is that a wide range of possible beliefs that an agent can hold about the strategies of the other agents will all lead him to play the equilibrium strategy. This is important because a common (and valid) criticism of equilibrium concepts such as Nash and BayesNash is that they are silent on how the agents converge on a strategy profile from which no one wants to deviate. However, if the equilibrium strategy is a best response to a large set of strategy profiles that are out of equilibrium, then it seems much more plausible that the agents will indeed converge on this equilibrium. It is important to note, though, that while this equilibrium is robust against arbitrary deviations to strategies that shave less, it is not robust to even a single agent shaving more off of its bid. In fact, if we take any strategy profile consistent with the conditions of Theorem 5 and change a single agent j"s strategy so that its corresponding αj is negative, then agent i"s best response is to shave more than 1 N off of its bid. 3.4 Effects of Overbidding for Other Distributions A natural question is whether the best response bidding strategy is similarly robust to overbidding by competing agents for other distributions. It turns out that Theorem 5 holds for all distributions of the form F(θi) = (θi)k , where k is some positive integer. However, taking a simple linear combination of two such distributions to produce F(θi) = θ2 i +θi 2 yields a distribution in which an agent should actually shave its bid more when other agents shave their bids less. In the example we present for this distribution (with the details in the appendix), there are only two players and the deviation by one agent is to bid his type. However, it can be generalized to a higher number of agents and to other deviations. Example 1. In a first-price auction where F(θi) = θ2 i +θi 2 and N = 2, if agent 2 always bids its type (b2(θ2) = θ2), then, for all θ1 > 0, agent 1"s best response bidding strategy is strictly less than the bidding strategy of the symmetric equilibrium. We also note that the same result holds for the normalized exponential distribution (F(θi) = eθi −1 e−1 ). It is certainly the case that distributions can be found that support the intuition given above that agents should shave their bid less when other agents are doing likewise. Examples include F(θi) = −1 2 θ2 i + 3 2 θi (the solution to the system of equations: F (θi) = −1, F(0) = 0, and F(1) = 1), and F(θi) = e−e(1−θi) e−1 . It would be useful to relate the direction of the change in the best response bidding strategy to a general condition on F(·). Unfortunately, we were not able to find such a condition, in part because the integral in the symmetric bidding strategy of a first-price auction cannot be solved without knowing F(·) (or at least some restrictions on it). We do note, however, that the sign of the second derivative of F(θi)/f(θi) is an accurate predictor for all of the distributions that we considered. 4. REVENUE LOSS FOR AN HONEST SELLER In both of the settings we covered, an honest seller suffers a loss in expected revenue due to the possibility of cheating. The equilibrium bidding strategies that we derived allow us to quantify this loss. Although this is as far as we will take the analysis, it could be applied to more general settings, in which the seller could, for example, choose the market in which he sells his good or pay a trusted third party to oversee the auction. In a second-price auction in which the seller may cheat, an honest seller suffers due the fact that the agents will shave their bids. For the case in which agent types are drawn from the uniform distribution, every agent will shave its bid by P c N−1+P c , which is thus also the fraction by which an honest seller"s revenue decreases due to the possibility of cheating. Analysis of the case of a first-price auction in which agents may cheat is not so straightforward. If Pa = 1 (each agent cheats with certainty), then we simply have a second-price auction, and the seller"s expected revenue will be unchanged. Again considering the uniform distribution for agent types, it is not surprising that Pa = 1 2 causes the seller to lose 79 the most revenue. However, even in this worst case, the percentage of expected revenue lost is significantly less than it is for the second-price auction in which Pc = 1 2 , as shown in Table 1.6 It turns out that setting Pc = 0.2 would make the expected loss of these two settings comparable. While this comparison between the settings is unlikely to be useful for a seller, it is interesting to note that agent suspicions of possible cheating by the seller are in some sense worse than agents actually cheating themselves. Percentage of Revenue lost for an Honest Seller Agents Second-Price Auction First-Price Auction (Pc = 0.5) (Pa = 0.5) 2 33 12 5 11 4.0 10 5.3 1.8 15 4.0 1.5 25 2.2 0.83 50 1.1 0.38 100 0.50 0.17 Table 1: The percentage of expected revenue lost by an honest seller due to the possibility of cheating in the two settings considered in this paper. Agent valuations are drawn from the uniform distribution. 5. RELATED WORK Existing work covers another dimension along which we could analyze cheating: altering the perceived value of N. In this paper, we have assumed that N is known by all of the bidders. However, in an online setting this assumption is rather tenuous. For example, a bidder"s only source of information about N could be a counter that the seller places on the auction webpage, or a statement by the seller about the number of potential bidders who have indicated that they will participate. In these cases, the seller could arbitrarily manipulate the perceived N. In a first-price auction, the seller obviously has an incentive to increase the perceived value of N in order to induce agents to bid closer to their true valuation. However, if agents are aware that the seller has this power, then any communication about N to the agents is cheap talk, and furthermore is not credible. Thus, in equilibrium the agents would ignore the declared value of N, and bid according to their own prior beliefs about the number of agents. If we make the natural assumption of a common prior, then the setting reduces to the one tackled by [5], which derived the equilibrium bidding strategies of a first-price auction when the number of bidders is drawn from a known distribution but not revealed to any of the bidders. Of course, instead of assuming that the seller can always exploit this power, we could assume that it can only do so with some probability that is known by the agents. The analysis would then proceed in a similar manner as that of our cheating seller model. The other interesting case of this form of cheating is by bidders in a first-price auction. Bidders would obviously want to decrease the perceived number of agents in order to induce their competition to lower their bids. While it is 6 Note that we have not considered the costs of the seller. Thus, the expected loss in profit could be much greater than the numbers that appear here. unreasonable for bidders to be able to alter the perceived N arbitrarily, collusion provides an opportunity to decrease the perceived N by having only one of a group of colluding agents participate in the auction. While the non-colluding agents would account for this possibility, as long as they are not certain of the collusion they will still be induced to shave more off of their bids than they would if the collusion did not take place. This issue is tackled in [7]. Other types of collusion are of course related to the general topic of cheating in auctions. Results on collusion in first and second-price auctions can be found in [8] and [3], respectively. The work most closely related to our first setting is [11], which also presents a model in which the seller may cheat in a second-price auction. In their setting, the seller is a participant in the Bayesian game who decides between running a first-price auction (where profitable cheating is never possible) or second-price auction. The seller makes this choice after observing his type, which is his probability of having the opportunity and willingness to cheat in a second-price auction. The bidders, who know the distribution from which the seller"s type is drawn, then place their bid. It is shown that, in equilibrium, only a seller with the maximum probability of cheating would ever choose to run a second-price auction. Our work differs in that we focus on the agents" strategies in a second-price auction for a given probability of cheating by the seller. An explicit derivation of the equilibrium strategies then allows us relate first and second-price auctions. An area of related work that can be seen as complementary to ours is that of secure auctions, which takes the point of view of an auction designer. The goals often extend well beyond simply preventing cheating, including properties such as anonymity of the bidders and nonrepudiation of bids. Cryptographic methods are the standard weapon of choice here (see [1, 4, 9]). 6. CONCLUSION In this paper we presented the equilibria of sealed-bid auctions in which cheating is possible. In addition to providing strategy profiles that are stable against deviations, these results give us with insights into both first and second-price auctions. The results for the case of a cheating seller in a second-price auction allow us to relate the two auctions as endpoints along a continuum. The case of agents cheating in a first-price auction showed the robustness of the first-price auction equilibrium when agent types are drawn from the uniform distribution. We also explored the effect of overbidding on the best response bidding strategy for other distributions, and showed that even for relatively simple distributions it can be positive, negative, or neutral. Finally, results from both of our settings allowed us to quantify the expected loss in revenue for a seller due to the possibility of cheating. 7. REFERENCES [1] M. Franklin and M. Reiter. The Design and Implementation of a Secure Auction Service. In Proc. IEEE Symp. on Security and Privacy, 1995. [2] D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991. 80 [3] D. Graham and R. Marshall. Collusive bidder behavior at single-object second-price and english auctions. Journal of Political Economy, 95:579-599, 1987. [4] M. Harkavy, J. D. Tygar, and H. Kikuchi. Electronic auctions with private bids. In Proceedings of the 3rd USENIX Workshop on Electronic Commerce, 1998. [5] R. Harstad, J. Kagel, and D. Levin. Equilibrium bid functions for auctions with an uncertain number of bidders. Economic Letters, 33:35-40, 1990. [6] P. Klemperer. Auction theory: A guide to the literature. Journal of Economic Surveys, 13(3):227-286, 1999. [7] K. Leyton-Brown, Y. Shoham, and M. Tennenholtz. Bidding clubs in first-price auctions. In AAAI-02. [8] R. McAfee and J. McMillan. Bidding rings. The American Economic Review, 71:579-599, 1992. [9] M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In EC-99. [10] J. Riley and W. Samuelson. Optimal auctions. American Economic Review, 71(3):381-392, 1981. [11] M. Rothkopf and R. Harstad. Two models of bid-taker cheating in vickrey auctions. The Journal of Business, 68(2):257-267, 1995. [12] W. Vickrey. Counterspeculations, auctions, and competitive sealed tenders. Journal of Finance, 16:15-27, 1961. APPENDIX Theorem 1. In a second-price auction in which the seller cheats with probability Pc , it is a Bayes-Nash equilibrium for each agent to bid according to the following strategy: bi(θi) = θi − θi 0 F( N−1 P c ) (x)dx F( N−1 P c ) (θi) (5) Proof. To find an equilibrium, we start by guessing that there exists an equilibrium in which all agents bid according to the same function bi(θi), because the game is symmetric. Further, we guess that bi(θi) is strictly increasing and differentiable over the range [0, 1]. We can also assume that bi(0) = 0, because negative bids are not allowed and a positive bid is not rational when the agent"s valuation is 0. Note that these are not assumptions on the setting- they are merely limitations that we impose on our search. Let Φi : [0, bi(1)] → [0, 1] be the inverse function of bi(θi). That is, it takes a bid for agent i as input and returns the type θi that induced this bid. Recall Equation 3: Eθ−i,µc ui(b(θ), µc , θi) = Prob bi(θi) > b[1](θ−i) · θi − Eθ−i,µc pi(b(θ), µc ) | bi(θi) > b[1](θ−i) The probability that a single other bid is below that of agent i is equal to the cdf at the type that would induce a bid equal to that of agent i, which is formally written as F(Φi(bi(θi))). Since all agents are independent, the probability that all other bids are below agent i"s is simply this term raised the (N − 1)-th power. Thus, we can re-write the expected utility as: Eθ−i,µc ui(b(θ), µc , θi) = FN−1 (Φi(bi(θi)))· θi − Eθ−i,µc pi(b(θ), µc ) | bi(θi) > b[1](θ−i) (9) We now solve for the expected payment. Plugging Equation 1 (which gives the price for the winning agent) into the term for the expected price in Equation 9, and then simplifying the expectation yields: Eθ−i,µc pi(b(θ), µc ) | bi(θi) > b[1](θ−i) = Eθ−i,µc µc · bi(θi) + (1 − µc ) · b[1](θ−i) | bi(θi) > b[1](θ−i) = Pc · bi(θi) + (1 − Pc ) · Eθ−i b[1](θ−i) | bi(θi) > b[1](θ−i) = Pc · bi(θi) + (1 − Pc ) · bi(θi) 0 b[1](θ−i)· pdf b[1](θ−i) | bi(θi) > b[1](θ−i) db[1](θ−i) (10) Note that the integral on the last line is taken up to bi(θi) because we are conditioning on the fact that bi(θi) > b[1](θ−i). To derive the pdf of b[1](θ−i) given this condition, we start with the cdf. For a given value b[1](θ−i), the probability that any one agent"s bid is less than this value is equal to F(Φi(b[1](θ−i))). We then condition on the agent"s bid being below bi(θi) by dividing by F(Φi(bi(θi))). The cdf for the N − 1 agents is then this value raised to the (N − 1)-th power. cdf b[1](θ−i) | bi(θi) > b[1](θ−i) = FN−1 (Φi(b[1](θ−i))) FN−1(Φi(bi(θi))) The pdf is then the derivative of the cdf with respect to b[1](θ−i): pdf b[1](θ−i) | bi(θi) > b[1](θ−i) = N − 1 FN−1(Φi(bi(θi))) · FN−2 (Φi(b[1](θ−i)))· f(Φi(b[1](θ−i))) · Φi(b[1](θ−i)) Substituting the pdf into Equation 10 and pulling terms out of the integral that do not depend on b[1](θ−i) yields: Eθ−i,µc pi(b(θ), µc ) | bi(θi) > b[1](θ−i) = Pc · bi(θi)+ (1 − Pc ) · (N − 1) FN−1(Φi(bi(θi))) · bi(θi) 0 b[1](θ−i) · FN−2 (Φi(b[1](θ−i)))· f(Φi(b[1](θ−i))) · Φi(b[1](θ−i)) db[1](θ−i) 81 Plugging the expected price back into the expected utility equation (9), and distributing FN−1 (Φi(bi(θi))), yields: Eθ−i,µc ui(b(θ), µc , θi) = FN−1 (Φi(bi(θi))) · θi− FN−1 (Φi(bi(θi))) · Pc · bi(θi)− (1 − Pc ) · (N − 1) · bi(θi) 0 b[1](θ−i) · FN−2 (Φi(b[1](θ−i)))· f(Φi(b[1](θ−i))) · Φi(b[1](θ−i)) db[1](θ−i) We are now ready to optimize the expected utility by taking the derivative with respect to bi(θi) and setting it to 0. Note that we do not need to solve the integral, because it will disappear when the derivative is taken (by application of the Fundamental Theorem of Calculus). 0 = (N−1)·FN−2 (Φi(bi(θi)))·f(Φi(bi(θi)))·Φi(bi(θi))·θi− FN−1 (Φi(bi(θi))) · Pc − Pc ·(N−1)·FN−2 (Φi(bi(θi)))·f(Φi(bi(θi)))·Φi(bi(θi))·bi(θi)− (1−Pc )·(N−1)· bi(θi)·FN−2 (Φi(bi(θi)))·f(Φi(bi(θi)))·Φi(bi(θi)) Dividing through by FN−2 (Φi(bi(θi))) and combining like terms yields: 0 = θi − Pc · bi(θi) − (1 − Pc ) · bi(θi) · (N − 1) · f(Φi(bi(θi))) · Φi(bi(θi)) − Pc · F(Φi(bi(θi))) Simplifying the expression and rearranging terms produces: bi(θi) = θi − Pc · F(Φi(bi(θi))) (N − 1) · f(Φi(bi(θi))) · Φi(bi(θi)) To further simplify, we use the formula f (x) = 1 g (f(x)) , where g(x) is the inverse function of f(x). Plugging in function from our setting gives us: Φi(bi(θi)) = 1 bi(θi) . Applying both this equation and Φi(bi(θi)) = θi yields: bi(θi) = θi − Pc · F(θi) · bi(θi) (N − 1) · f(θi) (11) Attempts at a derivation of the solution from this point proved fruitless, but we are at a point now where a guessed solution can be quickly verified. We used the solution for the first-price auction (see, e.g., [10]) as our starting point to find the answer: bi(θi) = θi − θi 0 F( N−1 P c ) (x)dx F( N−1 P c ) (θi) (12) To verify the solution, we first take its derivative: bi(θi) = 1− F(2· N−1 P c ) (θi) − N−1 P c · F( N−1 P c −1) (θi) · f(θi) · θi 0 F( N−1 P c ) (x)dx F(2· N−1 P c ) (θi) This simplifies to: bi(θi) = N−1 P c · f(θi) · θi 0 F( N−1 P c ) (x)dx F( N−1 P c +1) (θi) We then plug this derivative into the equation we derived (11): bi(θi) = θi − Pc · F(θi) · N−1 P c · f(θi) · θi 0 F( N−1 P c ) (x)dx (N − 1) · f(θi) · F( N−1 P c +1) (θi) Cancelling terms yields Equation 12, verifying that our guessed solution is correct. Alternative Proof of Theorem 1: The following proof uses the Revenue Equivalence Theorem (RET) and the probabilistic auction given as an interpretation of our cheating seller setting. In a first-price auction without the possibility of cheating, the expected payment for an agent with type θi is simply the product of its bid and the probability that this bid is the highest. For the symmetric equilibrium, this is equal to: F(N−1) (θi) · θi − θi 0 F(N−1) (x)dx F(N−1)(θi) For our probabilistic auction, the expected payment of the winning agent is a weighted average of its bid and the second highest bid. For the bi(·) we found in the original interpretation of the setting, it can be written as follows. F(N−1) (θi) · Pc θi − θi 0 F( N−1 P c ) (x)dx F( N−1 P c ) (θi) + (1 − Pc ) 1 F(N−1)(θi) · θi 0 x− x 0 F( N−1 P c ) (y)dy F( N−1 P c ) (x) ·(N −1)·F(N−2) (x)·f(x)dx By the RET, the expected payments will be the same in the two auctions. Thus, we can verify our equilibrium bidding strategy by showing that the expected payment in the two auctions is equal. Since the expected payment is zero at θi = 0 for both functions, it suffices to verify that the derivatives of the expected payment functions with respect to θi are equal, for an arbitrary value θi. Thus, we need to verify the following equation: F(N−1) (θi) + (N − 1) · F(N−2) (θi) · f(θi) · θi − F(N−1) (θi) = Pc · F(N−1) (θi) · 1 − 1− (N−1 P c ) · F( N−1 P c −1) (θi) · f(θi) · θi 0 F( N−1 P c ) (x)dx F2( N−1 P c ) (θi) + (N − 1) · F(N−2) (θi) · f(θi) · θi − θi 0 F( N−1 P c ) (x)dx F( N−1 P c ) (θi) + (1−Pc ) θi− θi 0 F( N−1 P c ) (y)dy F( N−1 P c ) (θi) ·(N−1)·F(N−2) (θi)·f(θi) 82 This simplifies to: 0 = Pc · (N−1 P c ) · F(N−2) (θi) · f(θi) · θi 0 F( N−1 P c ) (x)dx F( N−1 P c ) (θi) + (N − 1) · F(N−2) (θi) · f(θi) · − θi 0 F( N−1 P c ) (x)dx F( N−1 P c ) (θi) + (1−Pc ) − θi 0 F( N−1 P c ) (y)dy F( N−1 P c ) (θi) ·(N−1)·F(N−2) (θi)·f(θi) After distributing Pc , the right-hand side of this equation cancels out, and we have verified our equilibrium bidding strategy. Corollary 2. In a second-price auction in which the seller cheats with probability Pc , and F(θi) = θi, it is a Bayes-Nash equilibrium for each agent to bid according to the following strategy: bi(θi) = N − 1 N − 1 + Pc θi (6) Proof. Plugging F(θi) = θi into Equation 5 (repeated as 12), we get: bi(θi) = θi − θi 0 x( N−1 P c ) dx θi ( N−1 P c ) = θi − P c N−1+P c θi ( N−1+P c P c ) θi ( N−1 P c ) = θi − Pc N − 1 + Pc · θi = N − 1 N − 1 + Pc · θi Theorem 3. In a first-price auction in which each agent cheats with probability Pa , it is a Bayes-Nash equilibrium for each non-cheating agent i to bid according to the strategy that is a fixed point of the following equation: bi(θi) = θi − θi 0 Pa · F(bi(x)) + (1 − Pa) · F(x) (N−1) dx Pa · F(bi(θi)) + (1 − Pa) · F(θi) (N−1) (8) Proof. We make the same guesses about the equilibrium strategy to aid our search as we did in the proof of Theorem 1. When simplifying the expectation of this setting"s utility equation (7), we use the fact that the probability that agent i will have a higher bid than another honest agent is still F(Φi(bi(θi))), while the probability is F(bi(θi)) if the other agent cheats. The probability that agent i beats a single other agent is then a weighted average of these two probabilities. Thus, we can write agent i"s expected utility as: Eθ−i,µa ui(b(θ), µa , θi) = θi − bi(θi) · Pa · F(bi(θi)) + (1 − Pa ) · F(Φi(bi(θi))) N−1 As before, to find the equilibrium bi(θi), we take the derivative and set it to zero: 0 = θi − bi(θi) · (N − 1)· Pa · F(bi(θi)) + (1 − Pa ) · F(Φi(bi(θi))) N−2 · Pa · f(bi(θi)) + (1 − Pa ) · f(Φi(bi(θi))) · Φi(bi(θi)) − Pa · F(bi(θi)) + (1 − Pa ) · F(Φi(bi(θi))) N−1 Applying the equations Φi(bi(θi)) = 1 bi(θi) and Φi(bi(θi)) = θi, and dividing through, produces: 0 = θi − bi(θi) · (N − 1)· Pa · f(bi(θi)) + (1 − Pa ) · f(θi) · 1 bi(θi) − Pa · F(bi(θi)) + (1 − Pa ) · F(θi) Rearranging terms yields: bi(θi) = θi − Pa · F(bi(θi)) + (1 − Pa) · F(θi) · bi(θi) (N − 1) · Pa · f(bi(θi)) · bi(θi) + (1 − Pa) · f(θi) (13) In this setting, because we leave F(·) unspecified, we cannot present a closed form solution. However, we can simplify the expression by removing its dependence on bi(θi). bi(θi) = θi − θi 0 Pa · F(bi(x)) + (1 − Pa) · F(x) (N−1) dx Pa · F(bi(θi)) + (1 − Pa) · F(θi) (N−1) (14) To verify Equation 14, first take its derivative: bi(θi) = 1 − 1− (N − 1) · Pa · F(bi(θi)) + (1 − Pa ) · F(θi) (N−2) · Pa · f(bi(θi)) · bi(θi)) + (1 − Pa ) · f(θi) · θi 0 Pa · F(bi(x)) + (1 − Pa ) · F(x) (N−1) dx Pa · F(bi(θi)) + (1 − Pa) · F(θi) 2(N−1) This equation simplifies to: bi(θi) = (N −1)· Pa ·f(bi(θi))·bi(θi))+(1−Pa )·f(θi) · θi 0 Pa · F(bi(x)) + (1 − Pa ) · F(x) (N−1) dx Pa · F(bi(θi)) + (1 − Pa) · F(θi) N Plugging this equation into the bi(θi) in the numerator of Equation 13 yields Equation 14, verifying the solution. 83 Corollary 4. In a first-price auction in which each agent cheats with probability Pa , and F(θi) = θi, it is a BayesNash equilibrium for each non-cheating agent to bid according to the strategy bi(θi) = N−1 N θi. Proof. Instantiating the fixed point equation (8, and repeated as 14) with F(θi) = θi yields: bi(θi) = θi − θi 0 Pa · bi(x) + (1 − Pa ) · x (N−1) dx Pa · bi(θi) + (1 − Pa) · θi (N−1) We can plug the strategy bi(θi) = N−1 N θi into this equation in order to verify that it is a fixed point. bi(θi) = θi − θi 0 Pa · N−1 N x + (1 − Pa ) · x (N−1) dx Pa · N−1 N θi + (1 − Pa) · θi (N−1) = θi − θi 0 x(N−1) dx θ (N−1) i = θi − 1 N θN i θ (N−1) i = N − 1 N θi Theorem 5. In a first-price auction where F(θi) = θi, if each agent j = i bids according a strategy bj(θj) = N−1+αj N θj, where αj ≥ 0, then it is a best response for the remaining agent i to bid according to the strategy bi(θi) = N−1 N θi. Proof. We again use Φj : [0, bj(1)] → [0, 1] as the inverse of bj(θj). For all j = i in this setting, Φj(x) = N N−1+αj x. The probability that agent i has a higher bid than a single agent j is F(Φj(bi(θi))) = N N−1+αj bi(θi). Note, however, that since Φj(·) is only defined over the range [0, bj(1)], it must be the case that bi(1) ≤ bj(1), which is why αj ≥ 0 is necessary, in addition to being sufficient. Assuming that bi(θi) = N−1 N θi, then indeed Φj(bi(θi)) is always welldefined. We will now show that this assumption is correct. The expected utility for agent i can then be written as: Eθ−i ui(b(θ), θi) = Πj=i N N − 1 + αj bi(θi) · θi −bi(θ) = Πj=i N N − 1 + αj · θi· bi(θi) (N−1) − bi(θi) N Taking the derivative with respect to bi(θi), setting it to zero, and dividing out Πj=i N N−1+αj yields: 0 = θi · (N − 1) · bi(θi) (N−2) − N · bi(θi) (N−1) This simplifies to the solution: bi(θi) = N−1 N θi. Full Version of Example 1: In a first-price auction where F(θi) = θ2 i +θi 2 and N = 2, if agent 2 always bids its type (b2(θ2) = θ2), then, for all θ1 > 0, agent 1"s best response bidding strategy is strictly less than the bidding strategy of the symmetric equilibrium. After calculating the symmetric equilibrium in which both agents shave their bid by the same amount, we find the best response to an agent who instead does not shave its bid. We then show that this best response is strictly less than the equilibrium strategy. To find the symmetric equilibrium bidding strategy, we instantiate N = 2 in the general formula the equation found in [10], plug in F(θi) = θ2 i +θi 2 , and simplify: bi(θi) = θi − θi 0 F(x)dx F(θi) = θi− 1 2 · θi 0 (x2 + x)dx 1 2 · (θ2 i + θi) = θi− 1 3 θ3 i + 1 2 θ2 i θ2 i + θi = 2 3 θ2 i + 1 2 θi θi + 1 We now derive the best response for agent 1 to the strategy b2(θ2) = θ2, denoting the best response strategy b∗ 1(θ1) to distinguish it from the symmetric case. The probability of agent 1 winning is F(b∗ 1(θ1)), which is the probability that agent 2"s type is less than agent 1"s bid. Thus, agent 1"s expected utility is: Eθ2 ui((b∗ 1(θ1), b2(θ2)), θ1) = F(b∗ 1(θ1)) · θ1 − b∗ 1(θ1) = (b∗ 1(θ1))2 + b∗ 1(θ1) 2 · θ1 − b∗ 1(θ1) Taking the derivative with respect to b∗ 1(θ1), setting it to zero, and then rearranging terms gives us: 0 = 1 2 · 2 · b∗ 1(θ1) · θ1 − 3 · (b∗ 1(θ1))2 + θ1 − 2 · b∗ 1(θ1) 0 = 3 · (b∗ 1(θ1))2 + (2 − 2 · θ1) · b∗ 1(θ1) − θ1 Of the two solutions of this equation, one always produces a negative bid. The other is: b∗ 1(θ1) = θ1 − 1 + θ2 1 + θ1 + 1 3 We now need to show that b1(θ1) > b∗ 1(θ1) holds for all θi > 0. Substituting in for both terms, and then simplifying the inequality gives us: 2 3 θ2 1 + 1 2 θ1 θ1 + 1 > θ1 − 1 + θ2 1 + θ1 + 1 3 θ2 1 + 3 2 θ1 + 1 > (θ1 + 1) θ2 1 + θ1 + 1 Since θ1 ≥ 0, we can square both sides of the inequality, which then allows us to verify the inequality for all θ1 > 0. θ4 1 + 3θ3 1 + 17 4 θ2 1 + 3θ1 + 1 > θ4 1 + 3θ3 1 + 4θ2 1 + 3θ1 + 1 1 4 θ2 1 > 0 84
cheating auction agent case seller payment possibility game theory cheat
sealed-bid bidsecond-price auction first-price auction sealed-bid auction