Chapter 9. Auctions

# Chapter 9. Auctions [ToC] ## 9.1 Types of Auctions - In this chapter, we'll consider the case of a seller auctioning one item to a set of buyers - Underlying assumption: Each bidder has an **intrinsic value** for the item being auctioned - _the highest price she is willing to pay_ - 4 main types: - interactive 1. Ascending-bid auctions 2. Descending-bid auctions - simultaneous 3. First-price sealed-bid auctions 4. Second-price sealed-bid auctions --- ## 9.2 When are Auctions Appropriate? 1. Sellers do not have a good estimate of the buyers’ intrinsic values for an item 2. Buyers do not know each other’s values (private, independent) :::info **If the values are known, auctions are not needed.** Consider this: Suppose that a seller values at $x$, and the maximum value held by a potential buyer of the item is some larger number $y$. Then what would happen is either _1. Seller announces that the item is for sale at a fixed price just below $y$_ or _2. Buyer announces that she is willing to purchase the item for a price just above the larger of $x$ and the values held by all other buyers_ ::: --- ## 9.3 Relationships between Different Auction Formats This section gives some **informal** observations about different auction formats ### Descending-Bid and First-Price Auctions - The seller is lowering the price from its high initial starting point - During the auctions, bidders **learn nothing** except that no one has accepted the current price yet - The process is equivalent to a **sealed-bid first-price auction** --- ### Ascending-Bid and Second-Price Auctions - Bidders gradually drop out as the seller steadily raises the price - The item goes to the highest bidder at a price equal to the second-highest bid - ||Ascending-bid|Sealed-bid second-price| |---|---|---| |Difference|involve real-time interaction|purely through sealed bids| - However, the latter can be viewed as a **simulation** of the former --- ## 9.4 Second-Price Auctions Let's formulate the second-price auction as a game - Players: the bidders $i$ - Strategies: an amount to bid $b_i = f(v_i)$, where $v_i$ is bidder $i$'s true value - Payoffs: $$ \begin{cases}0 & \text{, if $b_i$ is not the winning bid}\\ v_i-b_j & \text{, if $b_i$ is the winning bid, and $b_j$ is the second-place bid}\end{cases} $$ > **Note**: > 1. If $b_i = v_i$, and $b_i$ and $b_j$ are tied for the largest, then the one summitted first wins, but with payoff of $b_i-b_j=0$ > 2. $b_i$ only affects whether $i$ wins or loses, but never affects how much $i$ pays in the event that she wins :::info **Claim:** In a sealed-bid second-price auction, it is a _dominant strategy_ for each bidder $i$ to choose a bid $b_i = v_i$. ::: :::success **Proof** We need to show that no deviation from this bid would improve her payoff, regardless of what strategy everyone else is using 1. If bidder $i$ chooses $b_i'>v_i$ ![](https://i.imgur.com/PMKSFwd.jpg) - Payoff is affected only if $i$ would lose with bid $v_i$ but would win with bid $b_i'$ - In such case, $i$ wins but pays more than her value $v_i$ after the change 2. If bidder $i$ chooses $b_i''<v_i$ ![](https://i.imgur.com/BMjAGCX.jpg) - Payoff is affected only if $i$ would win with bid $v_i$ but would lose with bid $b_i''$ ::: **Conclusion:** In a second-price auction, it makes sense to bid your true value even if other bidders are overbidding, underbidding, colluding, or behaving in other unpredictable ways. --- ## 9.5 First-Price Auctions and Other Formats Unlike second-price auctions, the value of your bid not only affects whether you win **but also how much you pay**. As a result, the conclusions are now different. > **Game formulation** > - Players: the bidders $i$ > - Strategies: an amount to bid $b_i = f(v_i)$, where $v_i$ is bidder $i$'s true value > - Payoffs: $$ \begin{cases}0 & \text{, if $b_i$ is not the winning bid}\\ v_i-b_i & \text{, if $b_i$ is the winning bid}\end{cases} $$ - Bidding $v_i$ is no longer a dominant strategy - The optimal way depends on knowledge of the other bidders and their distribution of possible values - Intuition: - with many competing bidders => higher bid - with only a few competing bidders => lower bid (More detail in Section 9.7) --- ### All-pay auctions All bidders pay their bids, regardless of whether they win or lose > **Game formulation** > - Players: the bidders $i$ > - Strategies: an amount to bid $b_i = f(v_i)$, where $v_i$ is bidder $i$'s true value > - Payoffs: $$ \begin{cases}-b_i & \text{, if $b_i$ is not the winning bid}\\ v_i-b_i & \text{, if $b_i$ is the winning bid}\end{cases} $$ - Like first-price auctions, one must balance the trade-off between bidding high and bidding low - In general, bids will typically be shaded much lower than in a first-price auction - Games of this type: - Political lobbying - Design competitions (More detail in Section 9.7) --- ## 9.6 Common Values and The Winner's Curse - In situations that the bidders intend to resell the object, there should be a common eventual value for the object - Each bidder has an estimation $v_i$ of the common value $v$ based on her private information about it $$ v_i = v + x_i $$ , where $x_i$ is a random error with a mean of 0 - The winning bid is more likely to be an **over-estimate** of the common value, so the winner will lose money on the resale - The phenomenon is known as **winner's curse** - Rational bidders who take the winner’s curse into account will shade their bids downward when the second-price format is use. _(Of course, bids will be reduced even further with first-price format.)_ ## 9.7 Advanced Material: Bidding Stragegies in First-Price and All-Pay Auctions ### Equilibrium Bidding in First-Price Auctions #### Private Value The **private value** for bidders $1,\ldots,n$ are i.i.d. $X_1,\ldots,X_n$ with probability density function $f$, distribution function $F$ on $[0,1]$. #### Strategy A **strategy** for a bidder is a function $s:[0,1]\to[0,1]$ satisfy - $s$ is continuous on $[0,1]$ and differentiable on $(0,1)$ - $s$ is stritly increasing - $s(v)\leq v$ where $s(v)=b$, $v$ is the true value and $b$ is the bid #### Bidders with the Same $s$ For bidder $i$ with his true value $v_i\in[0,1]$, bid price $v$, then the probability that $i$ win the item is $$ \begin{split} &P(X_1\leq v,X_2\leq v,\ldots,X_n\leq v)\\ =&\prod_{j=1,j\neq i}^n P(X_j\leq v)\\ =&P(X_1\leq v)^{n-1}\\ =&F(v)^{n-1} \end{split} $$ and thus the expect payoff is $$ g(v)=F(v)^{n-1}\cdot(v_i-s(v))+(1-F(v)^{n-1})\cdot0=F(v)^{n-1}(v_i-s(v)) $$ We want $g(v)$ to be maximized when setting $v=v_i$. That is, $g'(v_i)=0$. Then we have $$ \begin{split} &g'(v)\mid_{v=v_i}\\ =&(n-1)F(v)^{n-2}f(v)(v_i-s(v))-F(v)^{n-1}s'(v)\mid_{v=v_i}\\ =&(n-1)F(v_i)^{n-2}f(v_i)(v_i-s(v_i))-F(v_i)^{n-1}s'(v_i)\\ =&0 \end{split} $$ Now solve $s(v_i)$, $$ s'(v_i)=(n-1)f(v_i)\left(\frac{v_i-s(v_i)}{F(v_i)}\right) $$ which don't have explicit form of solution. #### Uniform Distribution If we consider the special case, the distribution is uniform $U(0,1)$, then $f(v)=1$, $F(v)=v$. We have $$ s'(v_i)=(n-1)\left(\frac{v_i-s(v_i)}{v_i}\right)=(n-1)\left(1-\frac{s(v_i)}{v_i}\right) $$ Observe that $$ s(v_i)=\frac{n-1}{n}v_i $$ is a solution. :::warning Let $s(x)=\sum_{k=0}^\infty a_kx^k$, then apply in $xs(x)=(n-1)x-(n-1)s(x)$, we have $$ \sum_{k=0}^\infty a_kkx^{k}=(n-1)x-(n-1)\sum_{k=0}^\infty a_kx^k $$ Thus, $$ \begin{cases} a_0=-(n-1)a_0\\ a_1=(n-1)-(n-1)a_1\\ a_k=-(n-1)a_k & ,k\geq 2 \end{cases} $$ Hence $$ \begin{cases} a_1=(n-1)/n\\ a_k=0 & ,k\neq 1 \end{cases} $$ and $s(x)=(n-1)x/n$ ::: Hence, every bidder bidding for a ratio $\frac{n-1}{n}$ of his/her true value is an equilibrium. ### Seller Revenue :::info **Theorem.** Let $X_1,\ldots,X_n\stackrel{\small i.i.d}{\sim}U(0,1)$, $X_{(1)},\ldots,X_{(n)}$ be their order statistics, then for $1\leq k\leq n$, $$ E(X_{(k)})=\frac{k}{n+1} $$ ::: > For seller, which type of auctions should be used? In a Second-Price Auction, the bidders follow their dominant strategies and bid truthfully, then the expected revenue is $$ \frac{n-1}{n+1} $$ By theorem and $\frac{n-1}{n}v_i$ being an equilibrium, in a First-Price Auction, the expected revenue is $$ \frac{n}{n+1}\frac{n-1}{n}=\frac{n-1}{n+1} $$ Observe that the expected revenue is the same. #### Reserve Prices The seller announce a **reserve price** $r$ before the auction. At the end of the auction, if the concluded price is smaller than $r$, then the item is reserved. > What value of $r$ should the seller set? Assume the seller values the item $u$, the reserve price $r$. Consider the special case: Second-Price Auction with one bidder with $v\sim U(0,1)$. In this case, we regard the seller as a bidder bidding with a constant price $r$. Then the expected revenue is $$ g(v)=P(v\leq r)\cdot u+P(v> r)\cdot r=ru+(1-r)r $$ which is maximized when setting $r=(1+u)/2$. ### Equilibrium Bidding in All-Pay Auctions Similar to the way we find the equilibrium of first-price auction. Recall that the chance to win the item is $F(v)^{n-1}=v^{n-1}$ if the distribution is $U(0,1)$. Then now the expected payoff is $$ \begin{split} g(v)=&v^{n-1}\cdot(v_i-s(v))+(1-v^{n-1})\cdot(-s(v))\\ =&v_iv^{n-1}-s(v) \end{split} $$ Then $$ g'(v)=(n-1)v_iv^{n-2}-s'(v) $$ Consider $g'(v_i)=0$, we have $$ s'(v_i)=(n-1)v_i^{n-1} $$ solve that $$ s(v_i)=\left(\frac{n-1}{n}\right)v_i^n $$ Note that $v_i<1$, $s(v)$ decreases exponentially as $n$ increases. The expected revenue of one bidder is $$ \int_0^1s(v)f(v)dv=\int_0^1\left(\frac{n-1}{n}\right)v^ndv=\left(\frac{n-1}{n}\right)\left(\frac{1}{n+1}\right) $$ Thus the total revenue is $$ n\left(\frac{n-1}{n}\right)\left(\frac{1}{n+1}\right)=\frac{n-1}{n+1} $$ is the same as before.