Unformatted text preview:

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
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?