Chapter 7 Sealed-bid Auctions - Centrum Wiskunde & …

1 Chapter 7 Sealed-bid AuctionsAnauctionis a procedure used for selling and buying items by offering themup for bid. Auctions are often used to sell objects that have avariable price(for example oil) or an undetermined price (for example radio frequencies).There are several types of Auctions . In its most general formthey can involvemultiple buyers and multiple sellers with multiple items being offered forsale, possibly in succession. Moreover, some items can be sold in fractions,for example we shall limit our attention to a simple situation in which only oneseller exists and offers one object for sale that has to be soldin its entirety(for example a painting).

2 So in this case an auction is a procedure thatinvolves one seller who offers an object for sale, nbidders, each bidderihaving a valuationvi 0 of the procedure we discuss here involves submission ofsealed bids. Moreprecisely, the bidders simultaneously submit their bids inclosed envelopesand the object is allocated, in exchange for a payment, to thebidder whosubmitted the highest bid (thewinner). Such an auction is called asealed-bid auction. To keep things simple we assume that when more than onebidder submitted the highest bid the object is allocated to the highest bidderwith the lowest formulate a Sealed-bid auction as a strategic game we consider eachbidder as a player.

3 Then we view each bid of playerias his possible allow any nonnegative real as a assume that the valuationsviare fixed and publicly known. Thisis an unrealistic assumption to which we shall return in a later , this assumption is necessary, since the valuations are used in thedefinition of the payoff functions and by assumption the players have commonknowledge of the game and hence of each others payoff functions. Whendefining the payoff functions we consider two options, each being determinedby the underlying payment a sequenceb:= (b1, .. , bn) of reals, we denote the leastlsuchthatbl= maxk {1,..,n}bkby argsmaxb. That is, argsmaxbis the smallestindexlsuch thatblis a largest element in the sequenceb.

4 For example,argsmax (6,7,7,5) = First-price auctionThe most commonly used rule in a Sealed-bid auction is that the winneripays to the seller the amount equal to his bid. The resulting mechanism iscalled thefirst-price the winner is bidderi, whose bid isbi. Since his value for thesold object isvi, his payoff (profit) isvi bi. For the other players the payoff(profit) is 0. Note that the winner s profit can be negative. This happenswhen he wins the object byoverbidding, , submitting a bid higher thanhis valuation of the object being sold. Such a situation is called thewinner summarize, the payoff functionpiof playeriin the game associatedwith the first-price auction is defined as follows, wherebis the vector of thesubmitted bids:pi(b) :={vi biifi= argsmaxb0otherwiseLet us now analyze the resulting game.}

5 The following theoremprovidesa complete characterization of its Nash 21 (Characterization I)Consider the game associated with thefirst-price auction with the players valuationsv. Thenbis a Nash equilib-rium iff fori=argsmaxb(i)bi vi55(the winner does not suffer from the winner s curse),(ii)maxj6=ivj bi(the winner submitted a sufficiently high bid),(iii)bi= maxj6=ibj(another player submitted the same bid as playeri).These three conditions can be compressed into the single statementmaxj6=ivj maxj6=ibj=bi vi,wherei= argsmaxb. Also note that (i) and (ii) imply thatvi= maxv, whichmeans that in every Nash equilibrium a player with the highest valuation isthe ( )(i) Ifbi> vi, then player sipayoff is negative and it increases to 0 if hesubmits the bid equal tovi.

6 (ii) If maxj6=ivj> bi, then playerjsuch thatvj> bican win the objectby submitting a bid in the open interval (bi, vj), sayvj . Then his payoffincreases from 0 to .(iii) Ifbi>maxj6=ibj, then playerican increase his payoff by submitting abid in the open interval (maxj6=ibj, bi), saybi . Then his payoff increasesfromvi bitovi bi+ .So if any of the conditions (i) (iii) is violated, thenbis not a Nashequilibrium.( ) Suppose that a vector of bidsbsatisfies (i) (iii). Playeriis the winnerand by (i) his payoff is non-negative. His payoff can increase only if hebidsless, but then by (iii) another player (the one who initially submitted thesame bid as playeri) becomes the winner, while player sipayoff becomes payoff of any other playerjis 0 and can increase only if he bidsmore and becomes the winner.

7 But then by (ii), maxj6=ivj< bj, so his payoffbecomes a Nash an illustration of the above theorem suppose that the vector of thevaluations is (1,6,5,2). Then the vectors of bids (1,5,5,2) and (1,5,2,5)satisfy the above three conditions and are both Nash equilibria. The firstvector of bids shows that player 2 can secure the object by bidding the secondhighest valuation. In the second vector of bids player 4 overbids but his payoffis 0 since he is not the thetruthful biddingwe mean the vectorbof bids, such that foreach playeriwe havebi=vi, , each player bids his own valuation. Notethat by the Characterization Theorem 21 truthful bidding, ,v, is a Nashequilibrium iff the two highest valuations , note that for no playerisuch thatvi>0 his truthful bidding isa dominant strategy.

8 Indeed, truthful bidding by playerialways results inpayoff 0. However, if all other players bid 0, then playerican increase hispayoff by submitting a lower, positive that the above analysis does not allow us to concludethat in eachNash equlibrium the winner is the player who wins in the case of truthfulbidding. Indeed, suppose that the vector of valuations is (0,5,5,5), so thatin the case of truthful bidding by all players player 2 is the winner. Thenthe vector of bids (0,4,5,5) is a Nash equilibrium with player 3 being , notice the following strange consequence of the above theorem:in no Nash equilibrium the last player,n, is a winner. The reason is that weresolved the ties in the favour of a bidder with the lowest index.

9 Indeed, byitem (iii) in every Nash equilibriumbwe have argsmaxb < Second-price auctionWe consider now an auction with the following payment rule. As before thewinner is the bidder who submitted the highest bid (with a tiebroken, asbefore, to the advantage of the bidder with the smallest index), but now hepays to the seller the amount equal to thesecondhighest bid. This Sealed-bid auction is called thesecond-price auction. It was proposed by and is alternatively calledVickrey auction. So in this auction inthe absence of ties the winner pays to the seller a lower pricethan in thefirst-price us formalize this auction as a game. The payoffs are now defined asfollows:57pi(b) :={vi maxj6=ibjifi= argsmaxb0otherwiseNote that biddingvialways yields a non-negative payoff but can now leadto a strictly positive payoff, which happens whenviis a unique winning , when the highest two bids coincide the payoffs are still the same asin the first-price auction, since then fori= argsmaxbwe havebi= maxj6= , note that the winner s curse still can take place here, namely whenvi< biand some other bid is in the open interval (vi, bi).}

10 The analysis of the second-price auction as a game leads to differentconclusions that for the first-price auction. The followingtheorem providesa complete characterization of the Nash equilibria of the corresponding 22 (Characterization II)Consider the game associated withthe second-price auction with the players valuationsv. Thenbis a Nashequilibrium iff fori=argsmaxb(i)maxj6=ivj bi(the winner submitted a sufficiently high bid),(ii)maxj6=ibj vi(the winner s valuation is sufficiently high).Proof.( )(i) If maxj6=ivj> bi, then playerjsuch thatvj> bican win the object bysubmitting a bid in the open interval (bi, vj). Then his payoff increases from0 tovj bi.