Information, Incentives, and Mechanism Design NICK GRAVIN COURSE INFO @ ITCS.SUFE.EDU.CN/~NICK AND @LOGIC.PDMI.RAS.RU/~GRAVIN/TEACHING.PHP TEXTBOOKS AVAILABLE AT : MECHANISM DESIGN & APPROXIMATION: JASONHARTLINE.COM/MDNA /MDNA-CH1TO8.PDF GAME THEORY, ALIVE: HOMES.CS.WASHINGTON.EDU /~KARLIN/GAMETHEORYBOOK.PDF Course structure (Tentative) Week 1, 2: Mechanism Design and Approximation Overview (Chapter 1, MDA) Topics: mechanism design, approximation, philosophy thereof, first-price auction, second-price auction, lottery, posted-pricings

Week 2, 3, 4: Equilibrium (Chapter 2, MDA) Topics: Bayes-Nash equilibirum, dominant strategy equilibrium, single-dimensional agents, BNE characterization, revenue equivalence, uniqueness, revelation principle, incentive compatibility. Week 4, 5, 6, 7, 8: Optimal Mechanism Design (Chapter 3, MDA) Topics: single-dimensional mechanism design, surplus-optimal mechanism (VCG), revenue-optimal mechanism (Myerson), amortized analysis, virtual values, revenue curves, revenue linearity. Week 8, 9, 10, 11: Bayesian Approximation (Chapter 4, MDA) Topics: reserve pricing, posted pricing, prophet inequalities, correlation gap, monotone hazard rate distributions. Week 12, 13: Price of Anarchy in games (Chapter 8, GTA) Topics: selfish routing, existence of equilibrium, affine latencies, network formation games, market sharing games.

Week 14, 15: Stable Matchings and allocations (Chapter 10, GTA) Topics: applications, Gale-Shapley algorithm, properties of Gale-Shapley algorithm, truthfulness considerations Grading Homework (50%) 5 assignments (your score best 4 out of 5). Work in pairs (same score for both) No copying, No late turn in. Final exam (50%) Based on problem solving recommendation: do homework. Course report (50%) [bonus] read a research paper/chapter in a book, write a report.

Economic & Computational Systems System: Individuals take actions optimize their own (usually selfish) goals System combines actions to produce an outcome applies its laws and restrictions. Systems producing good outcomes: Spectrum auctions, Residency matching program, Auctions for online advertising, etc. Bad outcomes: Financial markets meltdowns, traffic jams, scandals in Olympics games.

Example I: Residency Matching Medical student graduates in USA needs to be assigned to Hospitals for residency. Preferences: > > MGH Northwestern Memorial H.

Pennsylvania hospital Example II: Adward auctions Auction: buyers compete for better click probability umbrella Click-through rate/ success probability Ads Slot 1 0.5

Slot 2 0.2 Slot 3 0.1 30 billion $ of revenue for Google! 6 Example III: spectrum auctions How to reallocate spectrum Run a double Auction

Buys spectrum: From inefficient provides Meet budget constraint Sells spectrum: Complex preferences demand & value uncertainty Run an auction Example IV: Congestion regulation People choose: the fastest route between & are selfish => suboptimal outcomes

Government: introduces tolls to induce socially optimal outcomes Similar model for selfish routing of packages in a network. Remarks These systems are complex individuals strategy spaces are large difficult to optimize over Successful systems have :

simple rules individual strategies are simple This course: trade-off between optimality vs. simplicity simplicity => robustness, easy computations, practicality. Means: theory of approximation. compare the loss of performance of a simple practical mechanism to the complex optimal mechanism. Example IV: a model Network of routers strategic users

Routers/links: capacity constraints We need a mechanism for congestion control! Issues: dynamic demands complex network structure strategic user behaviour etc. Let us isolate this issue: Competition for 1 link

Single-item Allocation Problem Definition [single-item problem] is given by 1 indivisible item available strategic agents competing for the item each agent has a value for receiving the item. Objective: maximize social surplus (social welfare), i.e., gets the item. Optimal solution: - allocate to the highest value Notation: Mechanism I : I. ask agents to report their values

agent reports , II. select the agent with the highest report III. allocate the item to You (say, value 100 RMB): How to address: 1. Bids are meaningless? 2. Pay for overbidding? How do you bid? You bid highest number you can think of!

No payments: Lottery Definition [Lottery] I. select a uniformly random agent, and II. allocate the item to this agent. Theorem Lottery is an approximation. Proof. The expected social welfare (SW) = The optimum = . Bound is tight, when . Single-item Auction Def [Single-item auction] Solution to the allocation problem that solicits bids, picks a winner, determines payments. A natural example:

Def [First-price auction] 1. 2. 3. 4. Used in government procurements Not easy to calculate your best strategy ask agents to report their values ( agent reports ), Social welfare select with highest

report ( , ),= agents utility sellers allocate the item to agent charge this winning agent her bid . How to play? Def [utility] agent , derives utility , if she wins in the auction if she does not get the item Assumption: agents want to maximize their utility

if responding to others play (pure) Nash Equilibrium. uncertainty about bids maximize utility in expectation. Experiment: 20 people got usd randomly split into 10 pairs and played first-price auction winner of each auction would get usd. Over-biding compared to equilibrium (Assumption?) Ascending-price Auction Def [ascending-price auction] a.k.a. English auction.

1. 2. 3. 4. (gradually) raise an offered price up from zero, let agents to drop out if dont want to win at the offered price, stop at the price : the second-to-last agent drops out, item the last remaining agent, charge her . Agents strategy (value ): drop at price certainly dont get the item bad idea. continue above if win, pay more than bad idea. dominant strategy: drop at . Ascending-price Auction

View at the system: every agent follows dominant strategy second-highest bidder will drop highest bidder gets the item, pays utility SW: = optimal social surplus. Theorem The ascending-price auction maximizes the social surplus in dominant strategy equilibrium. Question: How to extend this to routing example? Issues:

too slow to implement in practice ascending prices dont find socially optimal routing scheme. Second-Price Auction Def [Second-price auction] a.k.a. Vickrey auction 1. accept sealed bids, 2. item the agent with the highest bid, 3. charge the second-highest bid. Strategically equivalent to the ascending price auction Theorem Truthful bidding is dominant strategy. Truthfulness Theorem Truthful bidding is dominant strategy. Proof Fix all values . Let . For agent i: Case 1. bid wins, pays .

Case 2. bid loses . max utility: if wants case 1, if wants case 2. Bidding achieves that dominant strategy. Corollary Second-price auction maximizes social surlplus. Observations: - infimum of bids can make and still win; - agent s critical value = the price charged to ; - a function only of the other agents reports. General routing problem Def [second-price routing mech.] a.k.a. Vickrey-Clarke-Groves 1. solicit sealed bids, 2. find the set of messages that can be routed simultaneously

with the largest total value, 3. charge the agents of each routed message their critical values. Theorem The second-price routing mechanism has truthful bidding as a dominant strategy. Corollary Proof similar to 2nd-price auction The mechanism maximizes the social surplus. Example C Can let only 1 message through

A Optimal value: (1) & (4) D What are the payments for senders of messages (1) and (4)? Critical value for (1)? B Example C A

D What are the payments for senders of messages (1) and (4)? Critical value for (1)? B What if (1) bids 0, does she win? Yes. =0 $ Example C A D What are the payments for senders of messages (1) and (4)?

Critical value for (4)? B Example C A D What are the payments for senders of messages (1) and (4)? Critical value for (4)? B What if (4) bids 1, does she win? No. >1 $

Example C A D What are the payments for senders of messages (1) and (4)? Critical value for (4)? B What if (4) bids 2, does she win? Tie. =2 $ VCG: collusion C

A D What are the payments for senders of messages (1) and (4)? B VCG: collusion C A D What are the payments for senders of messages (1) and (4)?

B What if (1) & (4) both bid 5? Win, = =0 $ Posted Pricing (single item) Question: What if even 2nd-price auction is too complicated? Def [uniform-pricing] for a given price , mechanism serves the first agent willing to pay (break ties in arrival order). Assumption: Distributional knowledge of demand. i.i.d. for all , where is a known cdf (cumulative density function). E.g.,, Posted pricing (single item) 2

nd price auction: ax ante probability of winning is Before the values are drawn Theorem Mimic by posted price: For values drawn i.i.d. from any distribution F, the uniform pricing of is an approximation to the optimal social surplus. Proof On the board Discussion Vickrey-Clarke-Groves (VCG) routing. Can be tricky to compute the optimal solution. Actually, for Border Gateway Protocol (BGP) is NP-hard.

Algorithmic theory: if computing the optimal solution is intractable try instead to compute an approximately optimal solution. Question: Can we use an approximation algorithm and still retain the dominant-strategy incentive property? Question: Is there a general theory for designing approximation mechanisms from approximation algorithms? Theory: what we want Informative: pinpoints salient features of the environment and characteristics of the good mechanisms. Prescriptive: gives concrete suggestions for how a good mechanism should be designed.

Predictive: The mechanisms that the theory predicts should be the same as the ones observed in practice. Tractable: The theory should not assume super-natural ability for the agents or designer to optimize. Philosophy of approximation Picassos Bull study