I was going through the proof of existence of a Nash Equilibria in finite normal form games (Proof via Brouwer’s theorem) and got a question regarding the requirement of finiteness for the number of actions a player can play. In particular, the proof hints at the update equations where players "compute" their payoffs/utility of playing a best response, before going deeper into Brouwer's. I would think that, in this framework, the number of actions needs to be finite otherwise it would be impossible to compute those "utility-updates"... but is it the main point? Or am I missing something?

Edit: The proof I am looking at is: https://www.cs.ubc.ca/cgi-bin/tr/2007/TR-2007-25.pdf. The update rules are in "Theorem 23".

  • 1
    $\begingroup$ Can you tell which proof you saw where? There is more than one way to prove the result via Brouwer's fixed point theorem. $\endgroup$ – Michael Greinecker Apr 21 '18 at 22:57
  • $\begingroup$ I have added a link to a fac-simile proof. $\endgroup$ – gogu Apr 22 '18 at 8:37
  • 4
    $\begingroup$ Well, there are two steps in the proof where finiteness of action spaces is used. First, the Brouwer fixed-point theorem is for finite dimensional spaces only. There are infinite-dimensional versions of the Brouwer fixed point theorem, but guaranteeing continuity and compactness is not straightforward in this case. If you would have a continuum of strategies, you get the problem that the probability of all actions might well be zero, so you cannot handle probabilities "pointwise". $\endgroup$ – Michael Greinecker Apr 22 '18 at 9:08
  • 3
    $\begingroup$ But the existence of Nash equilibria works even without finiteness by work of Fan and Glicksberg. If action spaces are compact (metric spaces) and payoff function continuous, a Nash equilibrium will exist. $\endgroup$ – Michael Greinecker Apr 22 '18 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.