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?


Yes (assuming you truly did mean "if" rather than "if and only if").

Add any objective function you want (e.g., 1, or the sum of the variables, or anything), then feed it to a MILP solver and see whether it returns 'Feasible' or 'Infeasible'. Then the resulting MILP is feasible if and only if the original MILP was feasible. Any optimal solution to the resulting MILP is feasible and thus also a feasible solution to the original MILP problem, and consequently represents a valid pure Nash equilibrium.

| cite | improve this answer | |
  • $\begingroup$ That answers the "without to with" part. What about the other way around ("without from with")? $\endgroup$ – Auberon Jun 3 '16 at 5:33
  • $\begingroup$ @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. $\endgroup$ – D.W. Jun 3 '16 at 18:31
  • $\begingroup$ Maybe the answer I was fishing for was something in the lines of: "yes because both problems belong to the same complexity class" or "no/partially, because ..." $\endgroup$ – Auberon Jun 6 '16 at 15:30

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.