Advanced Topics in Algorithmic Game Theory Review
Explore Equilibrium concepts, Complexity classes, Selfish Routing, Auctions, and more in this review session covering a range of game theory topics like Nash Equilibrium, PPAD, PLS, Potential Games, Smoothness framework, Cost-sharing games, and more.
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
CS 598 RM Review Session May 3rd, 2017
Topics Covered Equilibrium in two player games: Nash, Correlated, Stackelberg Computation and hardness. Complexity classes PPAD, PPA, PLS, and PPP Selfish Routing Non-atomic and Atomic. Potential Games. PoA and Smoothness framework Cost-sharing games Auctions Truthful Auction, Myerson s Lemma Myerson s optimal Auction. Bulow-Kempler Theorem Without money: Voting, House Allocation, Stable Matching Markets: Fisher and Exchange model Equilibrium Characterization and Computation
Nash Equilibrium Game (A,B) ?? ? ?? ?. x,y ? ?is a NE ??> 0 ???= max ??> 0 ????= max ??? ???? ? ?
1. Given a subsets ? and ? of pure actions of players one and two respectively, we can check in polynomial time if there is a NE with support (?,?).
Smooth Games and PoA ,? ? ? ???? ? + ? ???? ? ?,? smooth: ?????
3. Suppose the cost on each edge ? is not a constant but a non- decreasing concave function of the number of agents using it, i.e., ??0 = 0, ??(?) is non-decreasing, and (??? + 1 ??? ) is decreasing. PoS ?(?)
Myersons Lemma For single parameter setting, an allocation and a payment rule is DSIC iff 1) Allocation rule ??(.,? ?) is monotone for each ? and ? ? 2) ????,? ? = ???.???? ?? ??.,? ? ?? ??
Myersons Optimal Auction ??~ ??. Virtual value: ???? = ?? 1 ???? ???? Maximizing expected revenue = maximizing expected virtual welfare Optimal DSIC auction: 1) Given bids (?1, ,??) allocate so that ???????is maximized 2) If monotone allocation, then decide prices as per Myerson s lemma
?1~ uniform over 0,1 ? ? = 1, ? ? = ? ?2~ exponential distribution with rate 3 ? ? = 3 ? 3?,? ? = 1 ? 3? 5. Allocation:
VCG : set of outcomes. Allocation: Social welfare maximizing ? ??????? ???(?) Payment of agent ?: Harm it causes by participating max ? ? ??? ? ? ????
6. Procurement Auction: Auctioneer needs to buy out a house. There is a set A of sellers, and seller ? ? has a house with cost ??. Design a VCG mechanism.
8. Compute equilibrium for the following market: two buyers, 3 goods ?1= 2,?2= 6, ?1?1 = ?11+ ?12+ ?13,?2?2 = ?22+ 2?23
9. Computing equilibrium of exchange market with Leontief utilities and pairing economy is PPAD-hard.
