In solving a certain game, I've ended up with a set of equalities like these:
a == Max[b,c]/2+Max[d,e]/2
b == Min[f,g]/2+Min[h,i]/2
...
o == (1-d)/2+r/2
p == (1-d)/2
q == s/2+1/2
r == Max[1-h,1-i]/2+Max[t,u]/2
...
I create 2^N
different equation sets, where N
is the number of Max statements, and try to solve them individually using gaussian elimination or something like that. That would be something like $O(2^N*n^3)$.
By considering disjoin cycles and other heuristics, I could perhaps get it a bit faster, but I would still only be able to solve very simple games.
Are you aware of any algorithms, deterministic or approximate, that could make the above problem feasible for 30-50 or maybe even more Max statements?
Update:
- Each equation is a simple linear combination of variables, constants and Max/Mins of two (or more) variables. The number of terms in each equation is constant
- It is known, that there is an unique solution {a,b,c,...}
- All variables are fractions in
(0,1)
.
I can reduce the system by using Max[a,b] = (a+b-|a-b|)/2
and Snowie showed how to eliminate Max[a,b]
by adding two inequalities and a binary variable. The complexity still seams to be O(2^N)
.