CSCI 1440/2440 Introduction to Game Theory - Homework 8: EPIC Auctions
Homework 8: EPIC Auctions CSCI 1440/2440
2022-04-07
Due Date: Tuesday, April 19, 2022. 11:59 PM.
We encourage you to work in groups of size two. Each group need only submit one solution. Your submission must be typeset using LATEX. Please submit via Gradescope with you and your partner’s Banner ID’s and which course you are taking.
For 1000-level credit, you need only solve the first three problems. For 2000-level credit, you should solve all four problems.
1 English Auctions
1. We say that an ascending auction is DSIC up to ε iff no bidder who deviates from sincere bidding can improve upon sincere bidding by more than ε, where ε is the price increment of the auction. Likewise, we can define the notion of any equilibrium “up to ε,” where by deviating from the equilibrium strategy, no bidder can improve their expected utility by more than ε, assuming the other players are conforming. Show by counterexample that the English auction is not DSIC, even up to ε.
Keep in mind that the other bidders need not bid sincerely, and that strategies in the English auction can be outright bizarre: i.e., behavior from one round to the next need not be consistent.
2. Prove that sincere bidding in the English auction is an ex-post Nash equilibrium (EPNE), up to ε.
3. Apply the Revelation Principle to transform the English auction, in which sincere bidding is an ε-EPNE, into a direct mechanism, which is DSIC up to ε. Describe in a sentence (or two) why it is reasonable that applying the Revelation Principle would close the loopholes in the English auction.
2 Japanese Auctions
This problem concerns Japanese auctions, a variant of the classic English auction that poses demand queries rather than value queries, and that forbids bidders from re-entering after exiting (i.e., skipping even one round of bidding in) the auction.
A k-good Japanese auction for k homogeneous goods can be for- mally specified as follows: Given a fixed price increment ε,
- Initialize the set of bidders S0 = I and the price p0 = 0.
- At each round i = 1,2,...,
– Let price pi = iε.
– Let Si be the bidders in Si−1 who remains interested at price pi. N.B. No bidder who expressed disinterest earlier can re-express their interest at some later round.
- Increment i until |Si| ≤ k. Call the final round t.
– Give |St| of the k goods to the bidders in St at price tε.
– Give the remaining k − |St| of the goods (if any) to random bidders in St−1 \ St at price (t − 1)ε.
Bidders with unit demand valuations do not demand more than one good. More specifically, their value for any bundle they might be allocated is simply their maximum value across all individual goods: i.e., a bidder i’s valuation is unit demand if their value for a bundle of goods X ⊆ G is given by
vi(X) = maxvi(j), j∈X
where vi(j) denotes i’s value for good j.
Assuming unit demand valuations, show the following:
1. The k-good Japanese auction is still not DSIC.
Hint: It suffices to exhibit a counterexample in the single-good case: i.e., when k = 1.
2. This k-good Japanese auction is DSIC up to ε.
3 Online Auctions
Online auctions are big business: eBay reported revenue upwardsof $10 billion in 2020! In online auctions, interested bidders reporta “value,” which can be understood as the maximum price they are willing to pay for a good. Valid bids are at least some fixed increment ε greater than the asking price of the good (which is initialized to the reserve price). Whenever a new and valid bid arrives, the auction ten- tatively allocates the good to a bidder with the highest valid bid, and the asking price is updated to the maximum of the second-highest bid and the reserve. (Ties are broken in favor of earlier bidders.)
Although eBay auctions are the most prevalent online auctions in use today, Amazon also ran auctions back in the day. The primary difference in rules between eBay and Amazon auctions is that eBay auctions end at a prespecified time, while Amazon auctions would continue until quiescence: i.e., until a grace period of, say, 24 hours had passed without any active bidding.
Consider the following four types of bidders in online auctions:
- “Truthful” bidders, namely those who bid as if the auction were sealed-bid—they enter their value once and only once.
- Incremental bidders, who bid on eBay as if it were an English auction—they never enter their value; they merely increment their bid so long as the asking price is below their value.
- Jump bidders, who again bid when the asking price is below their value, placing a bid that is below their value, but more than just the minimal acceptable increment above the current price.
- Snipers (only relevant on eBay, not Amazon), who place a bid below their value just a few seconds before the auction ends.
Let us assume that these four bidding strategies encompass the full space of possibilities in online auctions, in which case DSIC means incremental (i.e., sincere) bidding is optimal, regardless of whether the other bidders are truthful, jump bidders, or snipers.
- Are eBay auctions DSIC up to ε? If so, provide a proof; if not, provide a counterexample.
- What about Amazon’s now defunct auctions? Were they DSIC up to ε? Again, provide a proof or counterexample.
- Name at least one disadvantage of eBay’s auction design, from the point of view of revenue maximization, and another from the point of view of welfare maximization.
4 k Parallel English Auctions are EPIC
By following step 3 of the EPIC auction design recipe, complete the proof that k parallel English auctions are EPIC, assuming additive valuations. More specifically, show that for every inconsistent bid- ding strategy, there exists a consistent bidding strategy that generates at least as much utility.
You may assume integer valuations and ε = 1, so that there are no small additive discretization errors.
You may also make use of the following theorem, which we will discuss in class before the end of the semester.
Theorem: Assuming bidders with additive valuations, if sincere bidding in k parallel English auctions yields outcome (y, q), then y is ε-efficient (i.e., ε-welfare-maximizing) and for all goods j ∈ [k], qj ∈ [pj − ε, pj + ε], where p are the Vickrey prices.
