# 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 ? –  Suresh Venkat Mar 14 at 20:58
Yes, I'll edit the question. –  Philip White Mar 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 at 18:47
Regarding your edit: Any quine that ignores its input seems to be a solution, right? –  usul Mar 15 at 18:48
Yes, that is one solution, but I want to find as many fixed points as possible. –  Philip White Mar 15 at 19:08