# Does there always exist equivalent (M)(I)LPs with and without objective functions?

For computing pure Nash equilibria (game theory), there exists a MILP method in literature (clicky).

In the proposed MILP, there is no objective function. A solution is a pure Nash equilibrium if it is a feasible solution of the MILP.

Should there, in theory, exist an equivalent MILP with an objective function so that a solution is a pure Nash equilibrium if the objective function is minimized/maximized (e.g. equal to 0). Such MILP would be useful in this context as to still have an approximation if there exists no feasible solution in the first 'objective function-less' MILP (i.e. there exists no pure Nash equilibrium).

I gave context to the question but the question is general: for a (M)(I)LP without an objective function, is there always a reduction from and to a (equivalent) (M)(I)LP with an objective function? Can such reduction be done in polynomial time?

• @Auberon, yes, there's always one the other way, assuming integer/discrete variables, by using binary search on the objective function. e.g., to maximize $y$, add a constraint $y \ge 32$ and see if that's feasible; if it isn't, add $y \ge 16$; and so on. – D.W. Jun 3 '16 at 18:31