I have a polynomial time best-response function that has the same properties as a game-theory game (convexity, compactness, set-valued). I don't know that much topology, but my understanding is that the Kakutani fixed-point theorem confirms that this function has a fixed point, i.e., there exists a strategy profile whose best response is itself.

The "game" I have is not really a game, in the sense that there are no payoffs; there is only a best-response function.

My question is: Given such a function, can one find a fixed-point quickly? Ordinarily, there are polytime approximation algorithms for this task (finding a Nash equilibrium), but here I do not have the game in normal form, or an easy way to put it in normal form given the lack of payoffs specified.

Edit: More specific information: Given a fixed input, find a polytime machine bounded by n^8+8 s.t. the machine outputs its description on the input. (There are ways of making this convex by allowing mixing over the edges of the machine.)

  • 1
    $\begingroup$ what kind of access do you have to the function ? what are its inputs/outputs etc ? Can you provide an example ? $\endgroup$ Mar 14 '14 at 20:58
  • $\begingroup$ Yes, I'll edit the question. $\endgroup$ Mar 14 '14 at 21:21
  • $\begingroup$ Ordinarily, there are polytime approximation algorithms for this task (finding a Nash equilibrium) -- not known to be true, by my understanding. $\endgroup$
    – usul
    Mar 15 '14 at 18:47
  • $\begingroup$ Regarding your edit: Any quine that ignores its input seems to be a solution, right? $\endgroup$
    – usul
    Mar 15 '14 at 18:48
  • $\begingroup$ Yes, that is one solution, but I want to find as many fixed points as possible. $\endgroup$ Mar 15 '14 at 19:08

A fixed point of a best response function is a Nash equilibrium -- the fact that you do not have the payoff matrix cannot make the problem easier (since if you know the payoff matrix, you also know the best response function, but not vice versa). Unfortunately, there are not in general good algorithms for computing approximate Nash equilibria in multi-player games. It is known that in general settings, computing a fixed point of a function is equivalent in difficulty to computing a Nash equilibrium -- see for instance http://homepages.inf.ed.ac.uk/kousha/nash_focs07_full_j_spec_issue_sub.pdf

There are not believed to be efficient algorithms for computing fixed points for general (best response) functions, and it is open whether they can be approximated well in general.

  • 2
    $\begingroup$ If anyone is interested in learning more about PPAD (the complexity class that contains Nash equilibria/fixed point problems), this is a pretty good gentle introduction: cgi.csc.liv.ac.uk/~pwg/PPADintro/PPADintro.html $\endgroup$
    – GMB
    Mar 14 '14 at 22:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.