Abstract
We consider 2-players, 2-values minimization games where the players' costs take on two values, a,b, a<b. The players play mixed strategies and their costs are evaluated by unimodal valuations. This broad class of valuations includes all concave, one-parameter functions F: [0,1]→ R with a unique maximum point. Our main result is an impossibility result stating that: If the maximum is obtained in (0,1) and F(1/2)≠ b, then there exists a 2-players, 2-values game without F-equilibrium. The counterexample game used for the impossibility result belongs to a new class of very sparse 2-players, 2-values bimatrix games which we call normal games. In an attempt to investigate the remaining case F(1/2) = b, we show that: - Every normal, n-strategies game has an F-equilibrium when F( 1/2 ) = b. We present a linear time algorithm for computing such an equilibrium. - For 2-players, 2-values games with 3 strategies we have that if F(1/2) ≤ b, then every 2-players, 2-values, 3-strategies game has an F-equilibrium; if F(1/2) > b, then there exists a normal 2-players, 2-values, 3-strategies game without F-equilibrium. To the best of our knowledge, this work is the first to provide an (almost complete) answer on whether there is, for a given concave function F, a counterexample game without F-equilibrium.