Equilibria in Ordinal Games:
A Framework based on Possibility Theory.
Abstract
The present paper proposes the first definition of
a mixed equilibrium in an ordinal game. This
definition naturally extends possibilistic (single
agent) decision theory. Our first contribution is
to show that ordinal games always admit a possibilistic mixed equilibrium, which can be seen as
a qualitative counterpart to mixed (probabilistic)
equilibrium. Then, we show that a possibilistic
mixed equilibrium can be computed in polynomial
time (wrt the size of the game), which contrasts
with mixed probabilistic equilibrium computation
in cardinal game theory. The definition we propose
is thus operational in two ways: (i) it tackles the
case when no pure Nash equilibrium exists in an
ordinal game; and (ii) it allows an efficient computation of a mixed equilibrium