Equilibria in Ordinal Games: A Framework based on Possibility Theory

Nahla Ben Amor, Hélène Fargier, Régis SabbadinIJCAI 2017 · DOI

TL;DR

This paper introduces the first formal definition of "mixed equilibria" for ordinal games, extending existing decision theory to scenarios where players only have ranked preferences, not precise numerical payoffs. They demonstrate that these equilibria always exist and, crucially, can be computed efficiently, offering a practical solution for games where pure strategy equilibria are absent.

What Problem Does This Paper Address?

In traditional game theory, players are assumed to have cardinal utility functions, meaning they can quantify their preferences (e.g., "I get 5 units of happiness from winning"). However, many real-world situations, like public-private partnerships or situations with incomplete information, involve players whose preferences are only ordinal – they can rank outcomes (e.g., "Outcome A is better than Outcome B") but not assign precise numerical values. This limitation makes it difficult to apply standard game theory concepts like Nash equilibria.

While ordinal game theory exists, it primarily focuses on "pure Nash equilibria" (where no player can unilaterally improve their outcome by changing their strategy). A significant challenge arises when no pure Nash equilibrium exists. Existing methods for finding mixed equilibria (where players randomize their strategies) in cardinal games are computationally expensive (PPAD-complete). This paper tackles the problem of defining and computing equilibria in ordinal games, especially when pure equilibria are absent, by leveraging possibility theory.

Methods

The core of this paper is the development of "possibilistic mixed equilibria" for ordinal games. Here's a breakdown of their approach:

  • Ordinal Games and Possibility Theory: They define an ordinal game using players' finite, totally ordered sets of utility values (L). They then use possibility theory, which deals with degrees of belief or preference, to model players' strategies. A "possibilistic mixed strategy" for a player is a normalized possibility distribution over their available actions, indicating the degree to which each action is plausible or preferred.
  • Joint Possibilistic Distribution: The joint strategy of all players is represented by the minimum of their individual possibility distributions, reflecting a pessimistic aggregation of preferences.
  • Possibilistic Mixed Equilibrium (PME): A PME is a set of possibilistic mixed strategies where no player has an incentive to unilaterally change their strategy to improve their "pessimistic utility" (a measure of their worst-case outcome given others' strategies). This definition is analogous to the standard Nash equilibrium but adapted for ordinal preferences and possibility theory.
  • IMPROVE Function: A key algorithmic component is the IMPROVE function. Given a game, a joint strategy, and a player, it finds the "least specific" way for that player to unilaterally adjust their strategy to strictly improve their pessimistic utility, or leaves the strategy unchanged if no improvement is possible. This function is crucial for constructing equilibria.
  • Algorithm for PME Construction: They propose an iterative algorithm that repeatedly applies the IMPROVE function for each player. This process converges to a PME.

Datasets

Not discussed in the paper. The paper uses theoretical examples to illustrate its concepts and algorithms.

Key Insights and Ideas

  • Ordinal Games Always Have PMEs: A fundamental result is that, unlike pure Nash equilibria which may not exist, every ordinal game admits at least one possibilistic mixed equilibrium. This provides a robust solution concept.
  • Efficient Computation: A major breakthrough is that these possibilistic mixed equilibria can be computed in polynomial time with respect to the size of the game. This stands in stark contrast to the computational hardness of mixed equilibria in cardinal games.
  • Negotiation Interpretation: PMEs can be interpreted as the outcome of a negotiation process where players iteratively adjust their commitments (possibilistic strategies) to improve their situation, until a stable state is reached.
  • Specificity as Improvement: The concept of "specificity" in possibility theory is directly linked to improving a player's utility. More specific strategies (where actions are assigned lower possibility values) can lead to better outcomes, but there's a trade-off with the player's own commitment.

Key Results

  • Definition of Possibilistic Mixed Equilibrium: The paper provides the first formal definition of mixed equilibria for ordinal games using possibility theory.
  • Existence Proof: They prove that every ordinal game possesses at least one possibilistic mixed equilibrium.
  • Polynomial-Time Algorithm: An algorithm is presented that computes a PME in polynomial time. This is a significant practical advantage.
  • Example Illustration: A concrete example demonstrates the algorithm's steps and how it converges to a PME.

Limitations and Future Work

  • Computational Complexity of Specific Variants: While the proposed PME is polynomial-time computable, the authors suggest that extending this to "possibilistic boolean games" (a more concise representation) might lead to NP-hard computation.
  • Generalizing to More Complex Scenarios: Future work could explore:
  • Possibilistic Boolean Games: Applying the PME concept to games expressed in possibilistic logic.
  • Competitive Markov Decision Processes (MDPs): Extending the framework to sequential decision-making under uncertainty and competition.
  • Partial Observability: Incorporating incomplete information into possibilistic game theory, potentially by building on existing frameworks for partially observable stochastic games.

Summary updated

BibTeX
@inproceedings{amor2017equilibria,
  author = {Nahla Ben Amor and Hélène Fargier and Régis Sabbadin},
  title = {{Equilibria in Ordinal Games: A Framework based on Possibility Theory}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/16},
}
Figure