# Metaheuristic for NP-complete problem without exact algorithms other than brute-force

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?

• IIRC you can compute equilibria using integer linear programming. Have you tried that? – adrianN Mar 15 '16 at 16:20
• 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. – Auberon Mar 15 '16 at 16:25
• "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? – D.W. Mar 15 '16 at 17:29
• 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 – Auberon Mar 15 '16 at 17:35