def. Sealed Bid Auction. An auction is a game where there are a certain number of buyers, buyers each have their value, and bid, . The auction process takes in the bids of all buyers , and outputs the allocation and price .
- where is the allocation for buyer
- where is the price charged for buyer
- e.g. if there is one item to be sold, and the i-th player gets it, then:
- \vec{p}= \langle 0,\dots,0,\9.37,0,\dots0 \rangle$
- Nobody except knowns their true value:
def. Quasilinear Utility Model. Each bidder, after the auction process finishes, has utility and welfare:
Types of Auctions
Remark. An auction can be not DSIC and welfare-maximizing 🤯.
- Single-Item
- Deterministic Valuations
- Second Price (DSIC, Welfare-Max)
- First-Price (Revenue-Max)
- Bayesian values
- Vickery Auction with Reserve (DSIC if regular, Revenue-max)
- Deterministic Valuations
- Multi-Item
- Single-item Demand, Indivisible (=sponsored search)
- Generalized Second Price (Welfare-Max)
- Virtual Second Price (Revenue-Max)
- Combinatorial Demand, Indivisible
- VCG Auction (DSIC, Welfare-Max)
- Ascending Item Price → W.E. (Welfare-Max)
- Combinatorial Demand, Indivisible—Price discriminatory
- Ascending Individual Bundle Price → C.E. (Welfare-Max)
- Combinatorial Demand, Indivisible, Bayesian
- ? (Welfare-max)
- ? (Revenue-max)
- Single-item Demand, Indivisible (=sponsored search)
Properties of an Auction
Motivation. An auction’s goal is to:
- Make sure each person tells the truth, i.e.
- Maximize total utility, i.e.
- Sometimes, to maximize seller revenue. Therefore, we want an auction that will satisfy the following two properties.
def. Welfare Maximizing (=Socially Efficient). An auction is welfare-maximizing iff Given all bidders are truthful, then it maximizes
def. Dominant Strategy Incentive Compatibility (DISC). Intuition: all bidders are incentivized to tell the truth. An auction is DISC iff:
def. Revenue Maximizing (=Optimal). See Revenue-Maximizing Auctions.
Myerson’s Lemma (or, How to Be DSIC)
Motivation. Instead of directly showing that an auction mechanism is DSIC, it is enough for it to satisfy the properties of the following Myerson’s lemma.
thm. Myerson’s Lemma. An auction is DSIC (=truthful) if and only if it satisfies the following to properties:
- Given other agent’s bids , the allocation function is a monotonically increasing function
- i.e. if then
- Given , the optimal price
Proof. Property 1. Allocation is monotonic w.r.t. bid amount. (=bid more, get more) proof. By definition of DSIC, both of the following holds:
- reports , actual value : ⇒
- reports , actual value : ⇒
- This is an argument from the fact that for any DSIC guara ntees it’s the best possible From the two inequalities we get
Thus ■
Intuition. and have the same signs. Which means is monotonically increasing.
Property 2. Optimal Price. From the two inequalities in property 1 we get
We take the limit by pushing
Thus . And integrating both sides
■ Intuition. The geometric intuition for this is that the price for the allocated person is the rectangle minus the area under the graph, i.e. the blue region.