6.896: Topics in Algorithmic Game Theory Lecture 18 Constantinos DaskalakisOverview Social Choice Theory Gibbard-Satterwaite Theorem Mechanisms with Money (Intro) Vickrey’s Second Price Auction Mechanisms with Money (formal)Social-Choice PreliminariesSetting: A : Set of alternatives (“candidates”) Social Choice Theory I : Set of n voters L : Preferences on A ; usually this is the set of total orders on A Social Welfare Function: f : Ln → L Social Choice Function: f : Ln → ATheorem [Arrow ’51] Every social welfare function on a set A of at least 3 alternatives that satisfies unanimity and independence of irrelevant alternatives is a dictatorship. Arrow’s Impossibility Theorem Proof: Last Lecture- use a social choice function f Electing a President - ideally f should satisfy the following properties: 2. it should not be susceptible to strategic manipulation 1. it should not be a dictatorship Def: A social choice function f is a dictatorship if there exists some voter i such that f ( <1, <2, …,<n) = top( <i ) ; Such voter i is called the dictator of f. Def: f can be strategically manipulated by voter i if there exist preferences <1, <2, …, <n and <i’ such that f (<1,…, <i, …, <n) =a <i a’ = f (<1,…, <i’, …, <n) i.e. i can elect a preferable candidate by lying If f cannot be manipulated it is called incentive compatible.Monotonicity Def: f is monotone iff f (<1,…, <i, …, <n) = a ≠ a’ =f (<1,…, <i’, …, <n) a’ <i a and a <i’ a’ Proposition: (f is incentive compatiable) iff (f is monotone) i.e. if the outcome changes from a to a’ when i changes his vote from >i to >i’, then it must be because the swing voter i also switched his preference from a to a’ Proof: Immediate by definition.Gibbard-Satterthwaite ThmGibbard-Satterthwaite Theorem Theorem: If f is an incentive compatible social choice function onto a set of alternatives A, where |A|≥3, then f is a dictatorship. Remark: “onto” is important; if |A|=2 then the majority function is both incentive compatible and non-dictatorship. Proof Idea: Suppose f is both incentive compatible and non-dictatorship. Use f to obtain a social welfare function F that satisfies unanimity, independence of irrelevant alternatives and non-dictatorship, which is impossible by Arrow’s theorem.Proof of the GS theorem From the social choice function f to a social welfare function F Notation: If S ⊆ A, and < ∈ L, we denote by <S the preference obtained from < by moving all elements of S to the top of <. e.g. S = {a, b}, and x < a < y < b < z then x <S y <S z <S a <S b. Definition of F( <1, <2,…, <n) =: < a < b iff f ( <1{a, b}, <2{a, b},…, <n{a, b}) = b Claim 1: F is a social welfare function. What can go wrong? Claim 2: F satisfies unanimity, IIA, and non-dictatorship.Proof of the GS theorem (cont.) Lemma: For any S, <1, <2,…, <n, f ( <1S, <2S,…, <nS) ∈ S. Proof: hybrid argument, on board. Claim 1: F is a social welfare function. Proof: By direct application of lemma, F is a total order and it is anti-symmetric. Transitivity? Suppose that a < b < c < a (*). W.l.o.g. suppose that f ( <1{a, b, c}, <2{a, b, c},…, <n{a, b, c}) = a. Hybrid argument: by sequentially changing <{a, b, c} to <{a, b} argue that f ( <1{a, b}, <2{a, b},…, <n{a, b}) = a, contradiction to (*).Proof of the GS theorem (cont.) Proof: Claim 2: F satisfies unanimity, IIA, and non-dictatorship. unanimity, IIA on board non-dictatorship: 2 pointsMechanisms with Money- The GS theorem applies to the setting where voters declare ordinal preferences over the alternatives, rather than cardinal preferences. - What if the voters assign a “score” to each alternative ? Going beyond the GS obstacle valuation function vi: A → Rvi(a) : value of alternative a for voter i, in terms of some currency- Voter’s utility if alternative a is chosen and money mi is given to him ui= vi(a)+miquasi-linear preferencesExample 1: Auctioning off a single item - each bidder i has value wi for the item - alternatives A ={ 1 wins, 2 wins, …, n wins} - for all i: vi(i wins) = wivi(j �= i wins) = 0- suppose we want to implement the social choice function that gives the item to the bidder with the highest value for the item - unfortunately we don’t know the wi’s - want to cleverly design the payment scheme to make sure that the social choice cannot be strategically manipulatedExample 1: Auctioning off a single item (cont) - first attempt: no payment - second attempt: pay your bid - third attempt: Vickrey’s second price auction the winner is the bidder i with the highest declared value wi = maxj wj non-winners pay 0, and the winner pays maxj≠i wj Theorem (Vickrey): For all w1, w2,…,wn and wi’ , let ui be bidder i ’s utility if she bids her true value wi and let ui’ be her utility if she bids an untrue value wi’. Then ui ≥ ui’ .General FrameworkSetting: A : Set of alternatives (“candidates”) Mechanisms with Money I : Set of n players vi: A → Rvaluation function of player i vi∈ Vi⊆ RAset of possible valuations Def: A direct revelation mechanism is a collection of functions where (f, p1,...,pn)f : V1× ...× Vn→ Ais a social choice function and is the payment function of player i. pi: V1× ...× Vn→ RIncentive Compatibility Def: A mechanism is called incentive compatible, or truthful , or strategy-proof iff for all i, for all and for all (f, p1,...,pn)v1∈ V1,...,vn∈ Vnv�i∈ Vivi(a) − pi(vi,v−i) ≥ vi(a�) − pi(v�i,v−i)a = f(vi,v−i)a�= f(v�i,v−i)utility of i if he says the truth utility of i if he lies i.e. no incentive to lie! but isn’t it too good to be true
View Full Document