Information, Incentives, and Mechanism Design
Delve into the course information provided by Nick Gravin at ITCS SUFE, exploring concepts of mechanism design and approximation. Textbooks by Jason Hartline are available, enriching your understanding of this field.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Information, Incentives, and Mechanism Design NICK GRAVIN COURSE INFO @ ITCS.SUFE.EDU.CN/~NICK 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
Prisoners dilemma Example I If you know what other person does, what will you do? A: any action of B Confess > Silent ! A confess A silent B confess A: -8 A: -20 B: -8 B: 0 B silent A: 0 A: -0.5 B: -20 B: -0.5
Dominant Strategy Equilibrium (DSE) Def [DSE] in a complete information game is a strategy profile such that each player s strategy is as least as good as all other strategies regardless of the strategies of all other players. Remark Rarely exists! Compare to Nash Equilibrium (NE), which always exists. Def [NE] Mixed strategy profile ? = (?1, ,??), such that each ?? is a best response of player ? to ? ?= (?1, ,?? 1,??+1, ,??)
Chicken game 2 Pure Nash Equilibria: 1. (A swerves, B stays) 2. (A stays, B swerves) PNE may not exist PNE is more likely than DSE. A stay A swerve B stay A: -10 A: -1 B: -10 B: 1 B swerve A: 1 A: 0 B: -1 B: 0
Incomplete information Agents have private information (types) Denoted by types ? = (?1, ,??) Strategy ??(??) of agent ? ??: maps ?? ?? ???????, or distribution of actions. Examples: ascending price & 2nd price auctions ??= ?? value of agent ? ??(??) drop at value ?? , bid ??= ?? these strategies truth telling.
Dominant strategy Equilibrium (DSE) Strategy profile ? = ?1, ,?? Def [DSE] is a strategy profile ? such that, for all ?,??, and ? ? (where ? ? generically refers to the actions of all players but i), agent ? s utility is maximized by following strategy ??(??). Rem Aside from strategies ?? being a map from types to actions DSE for incomplete information DSE for full information case.
Bayes-Nash Equilibrium (BNE) Equilibrium: ?best responds to other agents strategies. what about private types of other agents? depends on the ? s believes about types of other agents common prior assumption (standard in economics). Def [Prior] agent types ? are drawn at random from a prior distribution ? (a joint probability distribution over type profiles) and this prior distribution is common knowledge. ?- may be correlated distribution. Then ? does Bayesian update conditional on ??: ? ? ?? If ?- independent, i.e., ? = ?1 ??, then ? ? ??= ? ?.
Bayes-Nash Equilibrium (BNE) Def [BNE] for a game ? and common prior ? is a strategy profile ? = (?1, ,??) such that for all agents ? ? , and all types ?? ??(??) is a best response, when other agents play ? ?(? ?) for ? ? ? ? ??. Rem BNE can be regarded as a NE in appropriately defined game BNE (in mixed strategies) always exists.
Example of BNE Game: 1st price auction for 2 players ?1= ?1, ?2= ?2 ???????[0,1] i.i.d. common prior ? = ? ?, where ? ? = Pr ? ?? ? = ? Guess BNE: ??? =? fix strategy of agent 2 and treat ?2,?2 as random var. for any value ?1 and bid ?1 calculate utility ?1: E?2?1 = ?1 ?1 Pr 1 wins with bid ?1 Pr ?21 wins = Pr E?2?1= ?1 ?1 2?1 -maximized when ?1=?1 2 for ? {1,2}. Let s verify. ?2 2< ?1 = ? 2?1 = 2?1 ?2b2< b1 = Pr ?2 2
Stages of the Bayesian game When and what agent ? knows? Ex ante (before the game starts) ? only knows ?? (?? ??), and ? ? (? ? ? ?) Interim (learn private value, before the game) ? learnt ??, but does not know ? ? and ? ? Ex post (after the game is played) ? observes all actions in the game
Single-Dimensional Games Private type ?? - value ?? for receiving an abstract service. Independent types: distribution ? = ?1 ?? Outcome ? = ?1, ,??, where ?? - indicator if ? is served. Payments ? = ?1, ,??. Def Linear utility ??= ?? ?? ?? for the outcome (??,??) Def Game ?:? (?,?) maps actions to outcomes & payments. ?? ?? ??= 1 if served ??= 0 otherwise ?(?)= outcome for ? when actions are ?. ?(?)= payment from ? when actions are ?
Single-Dimensional Games Given a game ? and strategy profile ? ??? = ?? ??? = ?? are allocation rule and payment rule for (implicit) game ? and ?. Let s take agent ? interim perspective ? ??,?,? are implicit. We can specify allocation & payment ???? = Pr ???? = 1 ??] = ? ??? ??] ???? = ? ??? ??] ??= ?? ???? ??(??) [linearity of expectation] ?(?(?)) ?(?(?))
Bayes-Nash Equilibrium (BNE) Proposition When values are drawn from a product distribution ?, single-dimensional game ? and strategy profile ? is in BNE only if ( ) for all ?,??, and ? ?? ???? ???? ?? ??? ? ? . The converse ( ) is true if the strategy profile is onto. We say a strategy ??( ) is onto if every action ?? agent ? could play in the game is prescribed by ?? for some value ??, i.e., ?? ?? ???? = ??. A strategy profile is onto if the strategy of every agent is onto.
Characterization of BNE TheoremWhen values are drawn from a continuous product distribution ?, single-dimensional ? and strategy profile ? are in BNE only if ( ) for all ?, (i) [monotonicity] ??(??) is monotone non-decreasing, ????? ?? + ??0 , where often ??(0) = 0. (ii) [payment identity] ???? = ?? ???? 0 If the strategy profile is onto then the converse ( ) also holds.
Proof Plan (i) Monotonicity +(ii)Payment identity + onto BNE BNE (i) Monotonicity BNE (ii) Payment identity 1. 2. 3. Let s fix ? and drop subscript from notation. Key idea: deviation of playing ?( ?) instead of ?(?) Proof on the board.
Monotonicity 2. We want to prove that BNE ?(?) monotone. For any ?2,?1 ? ?1,?2 = ?1? ?2 ? ?2 ?1? ?1 ? ?1 = ? ?1,?1 ? ?2,?1 = ?2? ?1 ? ?1 ?2? ?2 ? ?2 = ? ?2,?2 + ?1? ?2 + ?2? ?1 ?1? ?1 + ?2? ?2 ?2 ?1 ? ?2 ? ?1 0
Payment identity ?? ? ?? + ? 0 . 3. BNE ? ? = ? ? ? 0 Let ?2> ?1, then ? ?1,?2 = ?1? ?2 ? ?2 ?1? ?1 ? ?1 = ? ?1,?1 ? ?2 ? ?1 ?1? ?2 ? ?1 ? ?2,?1 = ?2? ?1 ? ?1 ?2? ?2 ? ?2 = ? ?2,?2 ? ?2 ? ?1 ?2(? ?2 ?(?1)) ?2? ?2 ? ?1 ? ?2 ? ?1 ?1? ?2 ? ?1
Characterization: conclusions We did not assume: game is a single-round sealed-bid auction can be any wacky multi-round game only a winner makes payments can be a game with everyone paying We show that all BNE have a nice form.
Characterization: DSE Theorem ? and s are in DSE (Dominant strategy equilibrium) only if for all ? and ?, (i) [monotonicity] ??(??,? ?) is monotone non-decreasing, (ii) [payment identity] ?? ????,? ? = ?? ????,? ? ???,? ? ?? + ??0,? ?, 0 where ?,? ? is the valuation profile with i-th coordinate ?? ?. If the strategy profile is onto then the converse ( ) also holds.
Dominant strategy equilibrium (DSE) Proof Apply characterization for Bayes-Nash equilibria. DSE is stronger equilibrium concept than BNE. ??? ???, and in 1st price auction there is a ??? ???. Proof follows from characterization of BNE fix ? ? to be point mass distributions. apply BNE characterization. RemWhen game is deterministic, i.e., ??? {0,1}, then by monotonicity condition ???,? ? must be a step function.
Deterministic games CorollaryA deterministic game ? and deterministic strategies ? are in DSE only if for all ? and ?, (i) [step-function] ??(??,? ?) steps from 0 to 1 at some ??(? ?), (ii) [critical value] If the strategy profile is onto then the converse also holds. Rem There is uncertainty about tie breaking. E.g., in 2nd price auction who gets the item when ?1= ?2? Natural rules: lexicographical or randomized tie-breaking.
Revenue Equivalence Corollary For any two mechanisms where 0-valued agents pay nothing, if the mechanisms have the same BNE outcome then they have same expected revenue. Explanation:?( ) in the BNE of both mechanisms is the same, then the [payment identity] tells that expected payments must be equal.
Revenue Equivalence: application Let s compare revenue of the 1st and 2nd price auctions. Assume that values are distributed i.i.d. Equilibrium outcome in 2nd price auction: agent with the highest value wins Equilibrium outcome in 1st price auction: (a little tricky) may have many equilibria (reasonable to assume) exists symmetric & monotone BNE monotone: higher types bid higher values. then highest value win.
Revenue Equivalence: application Corollary When agents values are i.i.d. according to a continuous distribution, the 2nd price and 1st price auction have the same expected revenue. Recall The 1st price auction with n=2 bidders, ?? ? 0,1 . An equilibrium: bid half your value. ?1 2 =2 3 1 2=1 Then the revenue is: ? 3 . Revenue of the 2nd price auction is: ? ?(2) =1 3 .
