Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

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

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

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.

share|cite|improve this answer
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: – GMB Mar 14 '14 at 22:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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