Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am exploring a large number of 2-player games. The Lemke-Howson algorithm is computationally very reasonable, and is able to find many equilibria. On the other hand, I know that there are equilibria such that the algorithm cannot find in principle.

I was wondering if there was any way, upon inspection of the payoff matrices, to find out whether the game in question is one for which L-H will give incomplete results, so that I could then try more computationally intensive algorithms on those.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

I think this might be an open problem. The closest remark that I could find is by Shapley in 1981. I haven't found much thereafter, but, of course, I could have overlooked something. (Naturally, I am excluding the trivial "inspection" of using a computationally less reasonable algorithm first, and see whether they differ in their solutions.)

enter image description here

Related: Gilboa and Zemel (1989). I know next to nothing about (average) complexity, but perhaps somebody else can comment on whether this means you're in bad luck.

share|improve this answer
    
Yes, I know that paper, and had overlooked that comment. That's helpful, thanks. I will wait a couple of days, in case some more recent literature might surface, and accept your answer otherwise. –  Schiphol Mar 22 '13 at 0:52

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.