CS4261/5461 Algorithmic
Mechanism Design
Instructor: Warut Suksompong
2025
Auctions
Truthful Auctions and Bidding
Auctions Around Us
eBay
• Online Auction Website
• $22.3 billion in revenue in 2016
Spectrum auctions
• selling access to the wireless spectrum to the telecom companies
• US: $60 billion in revenue since 1994
Sponsored search auctions
• selling context-dependent ads on search pages
• Google: $116B in ad revenue in 2018
Single-item auction:
• the seller has one object for sale
• bidders compete to purchase the object
Multi-unit auction:
• seller has several identical items for sale
• each bidder wants to get one or more units
• license plates, airline tickets, US treasury bills
Combinatorial auction:
• seller has several distinct items for sale
• each bidder is interested in some combination of items
• airport departure and landing slots, spectrum auctions
Single Item Auctions
• We have a single item for sale.
• Each bidder 𝑖 ∈ 𝑁 values the item at 𝑣 .
• Seller can decide on a price.
• What are the outcomes?
Single Item Auction Formats
• English auction:
• auctioneer sets a starting price
• bidders take turns raising their bids
• the person who makes the last bid wins and
pays his bid
English Auction, Dynamics
• 𝑣1 = 50, 𝑣2 = 30, 𝑣3 = 70, 𝛿 = 1.
• The auction starts at 𝑝 = 0.
• While 𝑝 < 30, all bidders are submitting bids.
• At 𝑝 = 30, player 2 stops bidding.
• At 𝑝 = 50, player 1 stops bidding.
• If player 3 was the one to bid 50,
she wins and pays 50.
• If player 1 was the one to bid 50,
player 3 bids 51 and wins. $50 $30 $70
• Winning bid is either 𝑣1 or 𝑣 + 𝛿
English Auction
• Suppose your value for the object is 𝑣, the current price is 𝑝,
and the minimum bid increment is 𝛿
• It is rational to bid if and only if 𝑝 + 𝛿 ≤ 𝑣, and your bid
should be 𝑝 + 𝛿
• If 𝑝 + 𝛿 > 𝑣, and you end up winning, you will pay more than the
object is worth to you.
• If you bid more than 𝑝 + 𝛿, but no one else was willing to pay more
than 𝑝, you pay more than is necessary to win.
Single Item Auction Formats
• Japanese auction:
• auctioneer sets a starting price and then
starts raising it
• a bidder can drop out, and cannot return
once he dropped
• the bidder who stays in last gets the object,
pays the current price
Japanese Auction, Dynamics
• 𝑣1 = 50, 𝑣2 = 30, 𝑣3 = 70, 𝛿 = 1
• The auction starts at 𝑝 = 0
• At 𝑝 = 30, player 2 drops out
• At 𝑝 = 50, player 1 drops out
• Player 3 wins and pays 50
• Communication:
• English auction: 50 messages
• Japanese auction: 2 messages $50 $30 $70
Single Item Auction Formats, Continued
• Dutch auction:
• auctioneer sets a (high) starting price and then starts lowering it
• the auction ends when some bidder accepts the price
• used in the Amsterdam flower market
• Sealed-bid auction:
• all bidders simultaneously submit their bid
• the highest bidder gets the item and pays....
• his bid (first-price auction)
• 2nd highest bid (second-price, or Vickrey, auction)
Vickrey (Second-Price) Auction
• All bidders submit bids simultaneously in sealed envelopes
• The highest bidder wins and pays the second highest price
• Strategic game
• 𝑛 players (bidders)
• actions: bids (continuous action space)
• payoff: if a player values the object at 𝑣 and the 2nd highest bid is 𝑝,
her payoff is
• 𝑣 − 𝑝 if she gets the object
• 0 if she does not get the object
In a Vickrey auction, truthful
bidding is a dominant strategy
• Proof:
𝑏 𝑏 𝑏 𝑣
• suppose your value is 𝑣
• suppose other players’ bids are 𝑏 ≤⋯≤𝑏
• Case 1: 𝑣 ≥ 𝑏
• if you bid 𝑏 ≥ 𝑏 , you win and pay 𝑏
• payoff is 𝑣 − 𝑏 , same as what you would get from truthfully
reporting 𝑣
• if you bid 𝑏 < 𝑏 , you lose; payoff is 0.
• Proof: 𝑏 𝑏 𝑣 𝑏
• suppose your value is 𝑣
• suppose other players’ bids are 𝑏 ≤⋯≤𝑏
• Case 2: 𝑣 < 𝑏
• if you bid 𝑏 ≥ 𝑏 , you win and pay 𝑏
• payoff is 𝑣 − 𝑏 <0
• if you bid 𝑏 < 𝑏 , you lose; payoff is 0, same as what you
get from truthfully bidding 𝑣.
English auction
• person with the highest value wins
• pays 2nd highest value or 2nd highest value+𝛿
Japanese auction
• person with the highest value wins
• pays 2nd highest value
Vickrey auction
• person with the highest value wins
• pays 2nd highest value
• + easy to implement, computationally efficient
• - bidders must trust the auctioneer
Nash Equilibria in Auction
•𝑣 = 50, 𝑣 = 30, 𝑣 = 70
•𝑏 = 50, 𝑏 = 30, 𝑏 = 70 is an equilibrium in dominant strategies.
•𝑏 = 0, 𝑏 = 0, 𝑏 = 70 is also a NE
• auctioneer makes no profit
•𝑏 = 70, 𝑏 = 0, 𝑏 = 0 is also a NE
• Player 1 gets the object and pays nothing
• if player 3 increases her bid in order to beat player 1, she will end up paying at least 70,
so she cannot increase her profit
Are 1st Price Auctions
Truthful?
Let’s play a game!
• Suppose you’re participating in a first-price auction
• Your true value for the item is the last two digits of your
NUS login ID
• For example, if your student number is e0123456, your value
is $56.
• Your bid should be an integer amount of dollars.
• The prize for the winner is his/her utility divided by 10.
Multi Unit Auctions
• We have 𝑘 ≤ 𝑛 identical items for sale.
• Each bidder 𝑖 ∈ 𝑁 wants one item; values the item at 𝑣 .
• What is the analog of Vickrey auction?
Multi Unit Auctions
Design a mechanism
where:
Truthful bidding is a Items are allocated to
dominant strategy the 𝑘 highest bidders.
Auctions
Voting in Mechanism Matching
elections Design markets
Rent
division
Mechanism Design
• Players: 𝑁 = 1, … , 𝑛
• Outcomes 𝑂 = 𝑜 , … , 𝑜 .
• Each player 𝑖 has a valuation function 𝑣 : 𝑂 → ℝ.
• Can sometimes assign payments 𝜋 , … , 𝜋 ; utility is then 𝑢 𝑜 = 𝑣 (𝑜) − 𝜋 .
• Center chooses on outcome 𝑜 ∗ to maximize some function (perhaps ∑ 𝑣 𝑜∗ )
What are the outcomes in:
• Single item auctions? Multi unit auctions?
• Rent division?
• Allocation of indivisible goods?
• Matching Markets?
Incentive Compatibility
• Reporting your true valuations is a NE
Dominant Strategy Incentive
Compatibility
• Reporting your true valuations is a
(weakly) dominant strategy.
Why do we want truthful
reporting?
Vickrey Clarke Groves (VCG)
Mechanism
• A general framework of truthful mechanisms
• Selects socially optimal outcome
• Ensures truthful reporting by careful
payment design
Choose some outcome 𝑜 ∗ that maximizes 𝛴 𝑏 𝑜 ∗
To determine the payment that agent 𝑗 must make:
• Pretend 𝑗 does not exist, and choose 𝑜 ∗ that maximizes ∑ 𝑏 𝑜 .
• 𝑗 pays ∑ 𝑏 𝑜∗ −∑ 𝑏 𝑜∗ = ∑ 𝑏 𝑜∗ − 𝑏 𝑜∗
Each agent pays the externality that she imposes on the other
agents.
• Agent 𝑗’s externality:
(max. welfare of others if 𝑗 were absent) - (max. welfare of others when 𝑗 is present)
In VCG mechanisms, truthful
reporting is a dominant strategy.
Utility of player 𝑗 when she reports truthfully:
𝑣 𝑜∗ − 𝑏 𝑜∗ − 𝑏 𝑜∗ =
𝑣 𝑜∗ + 𝑏 𝑜∗ − 𝑏 𝑜∗
Total social Does not
welfare depend on
under 𝑜 ∗ - 𝒋’s report
optimal
Utility of player 𝑗 when she misreports:
𝑣 𝑜′ − 𝑏 𝑜∗ − 𝑏 𝑜 =
𝑣 𝑜′ + 𝑏 𝑜 − 𝑏 𝑜∗
Total social Does not
welfare depend on
under 𝑜 - 𝒋’s report
at most (same as
under 𝑜 ∗ before)
Combinatorial Auctions
• We have 𝑚 (possibly distinct) items for sale.
• 𝑛 + 1 possible outcomes (allocation of the items to the bidders)
• Bidders can have valuations for different subsets of items
• VCG is truthful, but some challenges:
• Preference elicitation: Each bidder has 2 private parameters
• Computational issues: Finding the optimal outcome 𝑜 ∗ may be NP-hard
• Revenue non-monotonicity (see next slide)
Revenue non-monotonicity of VCG
• Two bidders, two items A and B
• First bidder only wants both items together
• 𝑣 𝐴, 𝐵 = 1, 𝑣 𝐴 = 𝑣 𝐵 = 0
• Second bidder only wants item A
• 𝑣 𝐴, 𝐵 = 𝑣 𝐴 = 1, 𝑣 𝐵 = 0
• Revenue of VCG is 1
• Third bidder is added, who only wants item B
• 𝑣 𝐴, 𝐵 = 𝑣 𝐵 = 1, 𝑣 𝐴 = 0
• Revenue of VCG drops to 0!