Reader errata for Twenty Lectures on Algorithmic Game Theory — tie-breaking

Lecture 2, §2.4, pp. 13–14 · Single-item second-price auction

Suppose Alice and Bob each bid 10 and Carol bids 7. The definition on p. 13 identifies Alice and Bob as the highest bidders but leaves open who gets the item. Either winner pays 10, because the other bid of 10 still counts when determining the price.

Suggested addition to the definition (p. 13). Fix a priority order over bidders before any bids are submitted. Among the bidders tied for the highest bid, award the item to the first in that order. Let $w$ denote the selected winner. With at least two bidders, the second price is the highest bid remaining after removing the winner’s bid. Thus $p_w=\max_{j\ne w} b_j$. Every other bidder pays zero. If Alice wins the tie, Bob's 10 and Carol's 7 remain, so Alice pays 10.

Equality case in Proposition 2.1 (p. 14). Let $B$ be the highest bid among bidder $i$’s opponents. If $b_i>B$, bidder $i$ wins at price $B$. If $b_i<B$, she loses. If $b_i=B$, the priority order decides. Footnote 4 gives $i$ priority for the proof and invites the reader to check other rules. Here is that check: when $v_i>B$, a truthful bid wins and earns $v_i-B>0$. When $v_i<B$, a truthful bid loses and earns zero, while winning would give negative utility. When $v_i=B$, winning and losing both give zero. Truthful bidding therefore remains weakly dominant whichever tied bidder has priority. English edition, §2.4 and footnote 4 (preview) (opens in a new tab)