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