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?