1
$\begingroup$

Computing Pure Nash Equilibria (PNE) is a Game Theory related problem. Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.).

I want to design a metaheuristic algorithm that spits out a strategy that is either a PNE or an approximation of such. A metaheuristic algorithm would not guarantee a global optimal solution but might produce a sufficiently good solution. i.e. I want to view the problem as an optimization problem.

To the best of my efforts, I couldn't find any exact algorithms that solves the decision problem other than iterating over all possible strategies (brute-force).

I've tried implementing some basic metaheuristics (evolutionary algorithm, GSAT-like algorithm, ...) and find 'good' solutions in a 'timely' fashion. I put quotation marks because I can't prove if the algorithm is in fact good and/or fast (it uses metaheuristics). Hence the following question:

Is it useful to design metaheuristic algorithms for a problem like this when its performance can not be shown by comparing it to other (exact) algorithms?

$\endgroup$
  • 1
    $\begingroup$ IIRC you can compute equilibria using integer linear programming. Have you tried that? $\endgroup$ – adrianN Mar 15 '16 at 16:20
  • $\begingroup$ I have some background in Linear Programming but not in Integer Programming. Thanks, I will look into it and try to compare the algorithms to Integer Programming solvers (Gurobi ?) if possible. $\endgroup$ – Auberon Mar 15 '16 at 16:25
  • $\begingroup$ "Is it useful?" - What kind of answer are you expecting here? Seems like the only possible answer is "it depends what you're looking for, but sure, it might be, if you can accept the limitations". I don't really understand what your question is. What are your thoughts, and what prevents you from answering that question on your own? $\endgroup$ – D.W. Mar 15 '16 at 17:29
  • $\begingroup$ I tried to express my doubt over usefulness by saying I hadn't any exact algorithms to compare them to. Because when designing a metaheuristic algorithm for the problem, you want to show that the algorithm can provide a fair solution (although not optimal per se) in a timely manner by comparing it to an exact method or other metaheuristics. But since there are no exact algorithms, I was wondering if it is useful/plausible/sensible/... to design a metaheuristic algorithm because its performance can't be (dis)proved $\endgroup$ – Auberon Mar 15 '16 at 17:35
1
$\begingroup$

Thanks to user AdrianN (see comments) I was able to find a paper which presents a Mixed 0-1 Linear Program to find all Pure Nash Equilibria in n-player games. The method is an exact method and the authors provide performance results.

Zhengtian Wu et al. “A Mixed 0-1 Linear Programming Approach to the Computation of All Pure-Strategy Nash Equilibria of a Finite n-Person Game in Normal Form”

This, however, only answers half the question. This question remains:

Is it useful to design metaheuristic algorithms for a problem like this when its performance can not be shown by comparing it to other (exact) algorithms?

I realize this is a subjective question as, I think, D.W. tried to point out. I would like to answer this question myself by agreeing to D.W. and saying: It might be, it depends.

As a lot of references on metaheuristics will point out, it is important to be fully aware of the state-of-the-art before trying to design one. Metaheuristics tend to perform better than alternatives in certain (preferably interesting) situations, which should be shown by comparing them to said alternatives. Even if there is only a brute-force algorithm, it is likely that the brute-force algorithm will perform better in certain (interesting) situations and your metaheuristic will perform preferably much better in other situations. As D.W. said: "It depends what you're looking for, but sure, [metaheuristics] might be (useful), if you can accept the limitations."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.