DOC PREVIEW
MIT 6 896 - Topics in Algorithmic Game Theory

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.896: Topics in Algorithmic Game Theory Lecture 20 Yang CaiRecapGames with Strict Incomplete Information Def: A game with (independent private values and) strict incomplete information for a set of n players is given by the following ingredients: (ii) For every player i, a set of types Ti. A value ti∈ Tiis the private informationthat i has(i) For every player i, a set of actions Xi(iii) For every player i, a utility function ui: Ti× X1× ...× Xn→ R,whereui(ti,x1,...,xn) is the utility achieved by player i, if his type (private informa-tion) is ti, and the profile of actions taken by all players is x1,...,xnStrategy and Equilibrium Def: A strategy of a player i is a function si: Ti→ XiDef: Equilibrium (ex-post Nash and dominant strategy) ● A profile of strategies is an ex-post Nash equilibrium if for all i, all , and all we have that s1...snt1...tnx�iui(ti,si(ti),s−i(t−i)) ≥ ui(ti,x�i,s−i(t−i))● A profile of strategies is a dominant strategy equilibrium if for all i, all , and all we have that s1...snx�iui(ti,si(ti),x−i) ≥ ui(ti,x�i,x−i)x−iEquilibrium (cont’d) Proposition: Let be an ex-post Nash equilibrium of a game . Define , then is a dominant strategy equilibrium in the game . s1...sn(X1,...,Xn; T1,...,Tn; u1,...,un)X�i= {si(t)|ti∈ Ti}s1...sn(X�1,...,X�n; T1,...,Tn; u1,...,un)Formal Definition of MechanismsGeneral Mechanisms Vickrey’s auction and VCG are both single round and direct-revelation mechanisms. We will give a general model of mechanisms. It can model multi-round and indirect-revelation mechanisms.Mechanism Def: A (general-non direct revelation) mechanism for n players is given by (a) players’ type spaces T1,...,Tn.(b) players’ action spaces X1,...,Xn.(c) an alternative set A.(d) players’ valuation functions vi: Ti× A :→ R.(e) an outcome function a : X1× ...× Xn→ A.(f) players’ payment functions pi: X1× ...× Xn→ R.The game with strict incomplete information induced by the mechanism has the same type spaces and action spaces, and utilities ui(ti,x1,...,xn)=vi(ti,a(x1,...,xn)) − pi(x1,...,xn)Implementing a social choice function Given a social choice function f : T1× ...× Tn→ AEx: Vickrey’s auction implements the maximum social welfare function in dominant strategies, because is a dominant strategy equilibrium, and maximum social welfare is achieved at this equilibrium. si(ti)=tiSimilarly we can define ex-post Nash implementation. Remark: We only requires that for some equilibrium and allows other equilibria to exist. f(t1,...,tn)=a(s1(t1),...,sn(tn))A mechanism implements in dominant strategies if for some dominant strategy equilibrium of the induced game, we have that for all , . fs1,...,snt1,...,tnf(t1,...,tn)=a(s1(t1),...,sn(tn))outcome of the mechanism at the equilibrium outcome of the social choice functionThe Revelation PrincipleRevelation Principle We have defined direct revelation mechanisms in previous lectures. Clearly, the general definition of mechanisms is a superset of the direct revelation mechanisms. But is it strictly more powerful? Can it implement some social choice functions in dominant strategy that the incentive compatible (direct revelation dominant strategy implementation) mechanism can not?Revelation Principle Proposition: (Revelation principle) If there exists an arbitrary mechanism that implements in dominant strategies, then there exists an incentive compatible mechanism that implements . The payments of the players in the incentive compatible mechanism are identical to those, obtained at equilibrium, of the original mechanism. ffIncentive Compatible utility of i if he says the truth utility of i if he lies i.e. no incentive to lie! a = f(ti,t−i)a�= f(t�i,t−i)Def: A mechanism is called incentive compatible, or truthful , or strategy-proof iff for all i, for all and for all (f, p1,...,pn)t1∈ T1,...,tn∈ Tnt�i∈ Tivi(ti,a) − pi(ti,t−i) ≥ vi(ti,a�) − pi(t�i,t−i)Revelation Principle Proposition: (Revelation principle) If there exists an arbitrary mechanism that implements in dominant strategies, then there exists an incentive compatible mechanism that implements . The payments of the players in the incentive compatible mechanism are identical to those, obtained at equilibrium, of the original mechanism. ffProof idea: SimulationRevelation Principle (cont’d) t1s1s1(t1)t2s2s2(t2)tnsnsn(tn)original mechanism a(s1(t1),...,sn(tn))············new mechanismProof of Revelation Principle sis1,...,snProof: Let be a dominant strategy equilibrium of the original mechanism such that , we define a new direct revelation mechanism: Since each is a dominant strategy for player i, for every , we have that Thus in particular this is true for all and any we have that which gives the definition of the incentive compatibility of the mechanism.  ti,x−i,x�ivi(ti,a(si(ti),x−i)) − pi(si(ti),x−i) ≥ vi(ti,a(x�i,x−i)) − pi(x�i,x−i)x−i= s−i(t−i)x�i= si(t�i)p�i(t1,...,tn)=pi(s1(t1),...,sn(tn))f(t1,...,tn)=a(s1(t1),...,sn(tn))f�(t1,...,tn)=a(s1(t1),...,sn(tn))vi(ti,f�(ti,t−i)) − p�i(ti,t−i) ≥ vi(ti,f�(t�i,t−i)) − p�i(t�i,t−i)Revelation Principle (cont’d) Corollary: If there exists an arbitrary mechanism that ex-post Nash equilibrium implements , then there exists an incentive compatible mechanism that implements . Moreover, the payments of the players in the incentive compatible mechanism are identical to those, obtained in equilibrium, of the original mechanism. ffProof sketch: Restrict the action spaces of each player. By the


View Full Document

MIT 6 896 - Topics in Algorithmic Game Theory

Download Topics in Algorithmic Game Theory
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 Topics in Algorithmic Game Theory 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 Topics in Algorithmic Game Theory 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?