Bayesian games and mechanism designBayesian gamesConverting Bayesian games to normal formBayes-Nash equilibriumMechanism design: settingWhat should the center do?Quasilinear utility functionsDefinition of a (direct-revelation) mechanismIncentive compatibilityIndividual rationalityThe Clarke (aka. VCG) mechanism [Clarke 71]The Clarke mechanism is strategy-proofAdditional nice properties of the Clarke mechanismClarke mechanism is not perfectWhy restrict attention to truthful direct-revelation mechanisms?The revelation principleA few computational issues in mechanism designBayesian games and mechanism designVincent Conitzer [email protected] games •In a Bayesian game a player’s utility depends on that player’s type as well as the actions taken in the game –Notation: θi is player i’s type, drawn according to some distribution from set of types Θi–Each player knows/learns its own type, not those of the others, before choosing action•Pure strategy si is a mapping from Θi to Ai (where Ai is i’s set of actions)–In general players can also receive signals about other players’ utilities; we will not go into this4 62 4UDL Rrow playertype 1 (prob. 0.5)row playertype 2 (prob. 0.5)2 44 2UDL R4 64 6UDL Rcolumn playertype 1 (prob. 0.5)column playertype 2 (prob. 0.5)2 24 2UDL RConverting Bayesian games to normal form4 62 4UDL Rrow playertype 1 (prob. 0.5)row playertype 2 (prob. 0.5)type 1: U type 2: U type 1: U type 2: D type 1: D type 2: U type 1: D type 2: D 2 44 2UDL R4 64 6UDL Rcolumn playertype 1 (prob. 0.5)column playertype 2 (prob. 0.5)2 24 2UDL R3, 3 4, 3 4, 4 5, 44, 3.5 4, 3 4, 4.5 4, 42, 3.5 3, 3 3, 4.5 4, 43, 4 3, 3 3, 5 3, 4type 1: L type 2: L type 1: L type 2: R type 1: R type 2: L type 1: R type 2: R exponential blowup in sizeBayes-Nash equilibrium•A profile of strategies is a Bayes-Nash equilibrium if it is a Nash equilibrium for the normal form of the game–Minor caveat: each type should have >0 probability•Alternative definition: for every i, for every type θi, for every alternative action ai, we must have:Σθ-i P(θ-i) ui(θi, σi(θi), σ-i(θ-i)) ≥ Σθ-i P(θ-i) ui(θi, ai, σ-i(θ-i))Mechanism design: setting•The center has a set of outcomes O that she can choose from–Allocations of tasks/resources, joint plans, …•Each agent i draws a type θi from Θi–usually, but not necessarily, according to some probability distribution•Each agent has a (commonly known) utility function ui: Θi x O → –Note: depends on θi, which is not commonly known•The center has some objective function g: Θ x O → –Θ = Θ1 x ... x Θn–E.g. social welfare (Σi ui(θi, o))–The center does not know the typesWhat should the center do?•She would like to know the agents’ types to make the best decision•Why not just ask them for their types?•Problem: agents might lie•E.g. an agent that slightly prefers outcome 1 may say that outcome 1 will give him a utility of 1,000,000 and everything else will give him a utility of 0, to force the decision in his favor•But maybe, if the center is clever about choosing outcomes and/or requires the agents to make some payments depending on the types they report, the incentive to lie disappears…Quasilinear utility functions•For the purposes of mechanism design, we will assume that an agent’s utility for –his type being θi,–outcome o being chosen, –and having to pay πi, can be written as ui(θi, o) - πi•Such utility functions are called quasilinear•Some of the results that we will see can be generalized beyond such utility functions, but we will not do soDefinition of a (direct-revelation) mechanism•A deterministic mechanism without payments is a mapping o: Θ → O•A randomized mechanism without payments is a mapping o: Θ → Δ(O)–Δ(O) is the set of all probability distributions over O•Mechanisms with payments additionally specify, for each agent i, a payment function πi : Θ →  (specifying the payment that that agent must make)•Each mechanism specifies a Bayesian game for the agents, where i’s set of actions Ai = Θi–We would like agents to use the truth-telling strategy defined by s(θi) = θiIncentive compatibility•Incentive compatibility (aka. truthfulness) = there is never an incentive to lie about one’s type•A mechanism is dominant-strategies incentive compatible (aka. strategy-proof) if for any i, for any type vector θ1, θ2, …, θi, …, θn, and for any alternative type θi’, we haveui(θi, o(θ1, θ2, …, θi, …, θn)) – πi(θ1, θ2, …, θi, …, θn) ≥ ui(θi, o(θ1, θ2, …, θi’, …, θn)) – πi(θ1, θ2, …, θi’, …, θn)•A mechanism is Bayes-Nash equilibrium (BNE) incentive compatible if telling the truth is a BNE, that is, for any i, for any types θi, θi’, Σθ-i P(θ-i) (ui(θi, o(θ1, θ2, …, θi, …, θn)) – πi(θ1, θ2, …, θi, …, θn)) ≥ Σθ-i P(θ-i) (ui(θi, o(θ1, θ2, …, θi’, …, θn)) – πi(θ1, θ2, …, θi’, …, θn))Individual rationality•A selfish center: “All agents must give me all their money.” – but the agents would simply not participate–If an agent would not participate, we say that the mechanism is not individually rational•A mechanism is ex-post individually rational if for any i, for any type vector θ1, θ2, …, θi, …, θn, we haveui(θi, o(θ1, θ2, …, θi, …, θn)) – πi(θ1, θ2, …, θi, …, θn) ≥ 0•A mechanism is ex-interim individually rational if for any i, for any type θi, Σθ-i P(θ-i) (ui(θi, o(θ1, θ2, …, θi, …, θn)) – πi(θ1, θ2, …, θi, …, θn)) ≥ 0–i.e. an agent will want to participate given that he is uncertain about others’ types (not used as often)The Clarke (aka. VCG) mechanism [Clarke 71]•The Clarke mechanism chooses some outcome o that maximizes Σi ui(θi’, o)–θi’ = the type that i reports•To determine the payment that agent j must make:–Pretend j does not exist, and choose o-j that maximizes Σi≠j ui(θi’, o-j)–Make j pay Σi≠j (ui(θi’, o-j) - ui(θi’, o))•We say that each agent pays the externality that he imposes on the other agents•(VCG = Vickrey, Clarke, Groves)The Clarke mechanism is strategy-proof•Total utility for agent j is uj(θj, o) - Σi≠j (ui(θi’, o-j) - ui(θi’, o)) = uj(θj, o) + Σi≠j ui(θi’, o) - Σi≠j ui(θi’, o-j) •But agent j cannot affect the choice of o-j•Hence, j can focus on maximizing