"Congestion-Averse Games"

Speaker: Maria Polukarov, University of Southampton
Date: Wednesday, 6 January 2010
Time: 12noon
Place: Ross 201

Abstract:

Congestion games---in which players strategically choose from a set of
``resources'' and derive utilities that depend on the congestion on
each resource---are important in a wide range of
applications. However, to date, such games have been constrained to
use utility functions that are linear sums with respect to
resources. To remove this restriction, we consider a generalisation to
the case where a player's payoff can be given by any real-valued
function over the set of possible congestion vectors. Under weak
assumptions on the structure of player strategy spaces, we
constructively prove the existence of a pure strategy equilibrium for
the very wide class of these generalised games in which player utility
functions are congestion-averse---i.e., monotonic, submodular and
independent of irrelevant alternatives. Although, as we show, these
games do not admit a generalised ordinal potential function (and
hence---the finite improvement property), any such game does possess a
Nash equilibrium in pure strategies. A polynomial time algorithm for
computing such an equilibrium is presented. Moreover, we show that if
a player utility function does not satisfy any one of the
congestion-averse conditions, then a pure strategy equilibrium need
not exist, and in fact the determination of whether or not a game has
a pure strategy Nash equilibrium is NP-complete. We further prove
analogous results for our assumed properties of player strategy
spaces, thus showing that current assumptions on strategy and utility
structures in this model cannot be relaxed anymore.