Unformatted text preview:

Algorithmic Game Theory Problem Set 3CS 684 Fall 2005 Due Friday, November 18, 2005We will maintain a FAQ for the problem set on the course Web page. You may use any factwe proved in class without proving the proof or reference. However, you may not use publish edpapers.You are expected to attempt all p roblems. If you cannot solve a problem, write d own h ow faryou got, and why are you stuck.Cooperation in developing answers is encouraged. However, each student must write down allanswers separately.(1) We know that in a game with a finite set of players, where each player has a finite set ofpure strategies, the game has a Nash equilibrium. Our algorithm was based on Brouwer’s fixedpoint theorem. Unfortunately, the proof of the fi xed point theorem is not algorithm. It is a majoroutstanding open problem whether a Nash equilibrium in such a game can be found in polynomialtime. In this problem, we explore if one can at least d o this in finite time (maybe exponential).Consider the special case with two players. To be more formal, assume that there are 2 players, andplayer i chooses between nipure strategies. Assume that the game is given by listing th e payofffor each player for each n1× n2possible plays (this is the traditional p ayoff matrix that we calledmatrix A and B in class on Wednesday, Nov 2nd).(a) Give a polynomial time algorithm to check if there is a Nash equilibrium strategy for thegame in which each player mixes between at most two strategies.(b) Give a finite algorithm for finding a Nash equilibrium for general games with two players.Your algorithm may run in exponential time.(2) Consider a two player game with with two reward matrices A and B as also used in theprevious problem, and assume that both players have n possible strategies (so A and B are n byn matrices. Assume that the matrix A and B has random entries, say all entries in the range [0, 1]filed out uniformly independently at random. Show that the provability that this random gamehas a pure (deterministic) Nash equilibr ium is roughly 1 − 1/e if n is large. You may u se the factthat for large n we have that (1 − 1/n)n≈ 1/e.Warning. You may want to compute the probability that a pair of strategies (i, j) forms aNash. Unfortunately, these events are not independent!(3) We have seen that finding a Nash in a 2-person 0-sum game is significantly easier thangeneral 2 person games. Now consider a 3 person 0-sum game, that is a game when the reward ofthe 3 players always sums to 0. Show that finding a Nash equilibrium in a 3 person 0-sum game isat least as hard as a 2-person general game.(4) Consider an n person game where each player has only two strategies. This game has 2npossible outcomes (for the 2nways the n people can play, so even giving the game in the abovematrix form is rather problematic (takes exponential information). On e special class of games thatone can consider is called graphical games. T he idea is that the value (or payoff) of a player canonly depend on a subset of players. We can defi ne a dependence graph G whose n odes are the1players, and we put an edge between two players i and j if the payoff of player i depends on thestrategy of player j or vica versa. This way if node i has only some k neighbors, than his payoff onlydepends on his own strategy and the strategy of his neighbors. If the degree is a nice is boundedby 3 then h is payoff values can be given by only 24= 16 entries. Now consider a game where theplayers each have 2 pure strategies, and assume that the graph G is a tree with maximum degree 3.Give a polynomial time algorithm to decide if the game has a pure Nash equilibrium. (Note thatthere are 2npossible pure strategies.)(5) Cons ider an n person game where each player has 2 strategies. For this problem, think ofthe strategies as “on” an d “off”, i.e., the strategy is either to participate, or not to p articipate.Further assume that all players have the same payoff functions, and that the payoff for a player onlydepends on whether this player is “on”, and the number of people play ing strategy “on”. So thegame is defined by 2n values: uon(k) and uoff(k) that denote the payoff for playing the “on” and“‘off” strategy assuming k players chose to play “on” with k = 0, . . . n (where uon(0) and uoff(n)is meaningless). Give a polynomial time algorithm to find a correlated equilibrium for such agame. Note that the input to this problem consists of the 2n numbers above, so polynomial means,polynomial in this input length. You may use that linear programming is solvable in


View Full Document

CORNELL CS 684 - Study Guide

Download Study Guide
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 Study Guide 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 Study Guide 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?