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 🤯.

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:

  1. Given other agent’s bids , the allocation function is a monotonically increasing function
    1. i.e. if then
  2. 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


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.