# How do you compute the fixed point of a best-response function efficiently?

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

• what kind of access do you have to the function ? what are its inputs/outputs etc ? Can you provide an example ? Commented Mar 14, 2014 at 20:58
• Yes, I'll edit the question.
– user1338
Commented Mar 14, 2014 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
Commented Mar 15, 2014 at 18:47
• Regarding your edit: Any quine that ignores its input seems to be a solution, right?
– usul
Commented Mar 15, 2014 at 18:48
• Yes, that is one solution, but I want to find as many fixed points as possible.
– user1338
Commented Mar 15, 2014 at 19:08