First-price sealed-bid auction

A first-price sealed-bid auction (FPSBA) is a common type of auction. It is also known as blind auction,.^[1] In this type of auction, all bidders simultaneously submit sealed bids, so that no bidder knows the bid of any other participant. The highest bidder pays the price they submitted.^[2]^:p2^[3]

Strategic analysis

In a FPSBA, each bidder is characterized by his/her monetary valuation of the item for sale.

Suppose Alice is a bidder and her valuation is a. Then, if Alice is rational:

She will never bid more than a, because bidding more than a can only make her lose net value.
If she bids exactly a, then she will not lose but also not gain any positive value.
If she bids less than a, then she may have some positive gain, but the exact gain depends on the bids of the others.

Alice would like to bid the smallest amount that can make her win the item, as long as this amount is less than a. For example, if there is another bidder Bob and he bids $y$ and $y<a$ , then Alice would like to bid $y+\varepsilon$ (where $\varepsilon$ is the smallest amount that can be added, e.g. one cent).

Unfortunately, Alice does not know what the other bidders are going to bid. Moreover, she does not even know the valuations of the other bidders. Hence, strategically, we have a Bayesian game - a game in which agents do not know the payoffs of the other agents.

The interesting challenge in such a game is to find a Bayesian Nash equilibrium. However, this is not easy even when there are only two bidders. The situation is simpler when the valuations of the bidders are i.i.d. random variables, i.e: there is a known prior distribution and the valuations of the bidders are all drawn from the same distribution.^[4]^:234–236

Example

Suppose there are two bidders, Alice and Bob, whose valuations a and b are drawn from a Continuous uniform distribution over the interval [0,1]. Then, it is a Bayesian-Nash equilibrium when each bidder bids exactly half his/her value: Alice bids $a/2$ and Bob bids $b/2$ .

PROOF: The proof takes the point-of-view of Alice. We assume that she knows that Bob bids $f(b)=b/2$ , but she does not know $b$ . We find the best response of Alice to Bob's strategy. Suppose Alice bids $x$ . There are two cases:

$x\geq f(b)$ . Then Alice wins and enjoys a net gain of $a-x$ . This happens with probability $f^{-1}(x)=2x$ .
$x<f(b)$ . Then Alice loses and her net gain is 0. This happens with probability $1-f^{-1}(x)$ .

All in all, Alice's expected gain is: $G(x)=f^{-1}(x)\cdot (a-x)$ . The maximum gain is attained when $G'(x)=0$ . The derivative is (see Inverse functions and differentiation):

G'(x)=-f^{-1}(x)+(a-x)\cdot {1 \over f'(f^{-1}(x))}

and it is zero when Alice's bid $x$ satisfies:

f^{-1}(x)=(a-x)\cdot {1 \over f'(f^{-1}(x))}

Now, since we are looking for a symmetric equilibrium, we also want Alice's bid $x$ to equal $f(a)$ . So we have:

f^{-1}(f(a))=(a-f(a))\cdot {1 \over f'(f^{-1}(f(a)))}

a=(a-f(a))\cdot {1 \over f'(a)}

af'(a)=(a-f(a))

The solution of this differential equation is: $f(a)=a/2$ .

Generalization

Denote by:

$v_{i}$ - the valuation of bidder $i$ ;
$y_{i}$ - the maximum valuation of all bidders except $i$ , i.e, $y_{i}=\max _{j\neq i}{v_{i}}$ .

Then, a FPSBA has a unique symmetric BNE in which the bid of player $i$ is given by:^[5]^:33-40

E[y_{i}|y_{i}<v_{i}]

Incentive-compatible variant

The FPSBA is not incentive-compatible even in the weak sense of Bayesian-Nash-Incentive-Compatibility (BNIC), since there is no Bayesian-Nash equilibrium in which bidders report their true value.

However, it is easy to create a variant of FPSBA which is BNIC, if the priors on the valuations are common knowledge. For example, for the case of Alice and Bob described above, the rules of the BNIC variant are:

The highest bidder wins;
The highest bidder pays 1/2 of his/her bid.

In effect, this variant simulates the Bayesian-Nash equilibrium strategies of the players, so in the Bayesian-Nash equilibrium, both bidders bid their true value.

This example is a special case of a much more general principle: the revelation principle.

Comparison to second-price auction

The following table compares FPSBA to sealed-bid second-price auction (SPSBA):

Auction:	First-price	Second-price
Winner:	Agent with highest bid	Agent with highest bid
Winner pays:	Winner's bid	Second-highest bid
Loser pays:	0	0
Dominant strategy:	No dominant strategy	Bidding truthfully is dominant strategy^[6]
Bayesian Nash equilibrium^[7]	Bidder $i$ bids ${\frac {n-1}{n}}v_{i}$	Bidder $i$ truthfully bids $v_{i}$
Auctioneer's revenue^[7]	${\frac {n-1}{n+1}}$	${\frac {n-1}{n+1}}$

The auctioneer's revenue is calculated in the example case, in which the valuations of the agents are drawn independently and uniformly at random from [0,1]. As an example, when there are $n=2$ agents:

In a first-price auction, the auctioneer receives the maximum of the two equilibrium bids, which is $\max(a/2,b/2)$ .
In a second-price auction, the auctioneer receives the minimum of the two truthful bids, which is $\min(a,b)$ .

In both cases, the auctioneer's expected revenue is 1/3.

This fact that the revenue is the same is not a coincidence - it is a special case of the revenue equivalence theorem. This holds only when the agents' valuations are statistically independent; when the valuations are dependent, we have a common value auction, and in this case, the revenue in a second-price auction is usually higher than in a first-price auction.

Comparison to other auctions

A FPSBA is distinct from the English auction in that bidders can only submit one bid each. Furthermore, as bidders cannot see the bids of other participants, they cannot adjust their own bids accordingly.^[3]

FPSBA has been argued to be strategically equivalent to the Dutch auction.^[2]^:p13

What are effectively FPSBA are commonly called tendering for procurement by companies and organizations, particularly for government contracts and auctions for mining leases.^[3]

A Generalized first-price auction is a non-truthful auction mechanism for sponsored search (aka position auction).

References

↑ Shor, Mikhael, "blind auction" Dictionary of Game Theory Terms
1 2 Krishna, Vijay (2002), Auction Theory, San Diego, USA: Academic Press, ISBN 0-12-426297-X
1 2 3 McAfee, Dinesh Satam; McMillan, Dinesh (1987), "Auctions and Bidding" (PDF), Journal of Economic Literature, American Economic Association (published June 1987), 25 (2), pp. 699–738, JSTOR 2726107, retrieved 2008-06-25
↑ Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
↑ Daron Acemoglu and Asu Ozdaglar (2009). "Networks Lectures 19-21: Incomplete Information: Bayesian Nash Equilibria, Auctions and Introduction to Social Learning". MIT. Retrieved 8 October 2016.
↑ Hence a second-price auction is a truthful mechanism.
1 2 Calculated for $n$ bidders whose valuations are drawn independently and uniformly at random from [0,1]

External links

Nash equilibrium in first price auction - in math.stackexchange.com.

This article is issued from Wikipedia - version of the 10/13/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.