Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
1  
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

1 Answer 1

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

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

Your Answer

 
discard

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.