Satisfaction equilibrium
Satisfaction equilibrium
In game-theory, a satisfaction equilibrium is a solution-concept for a class of non-cooperative games, namely games in satisfaction form. Games in satisfaction form model situations in which players aim at satisfying a given individual constraint, e.g., a performance metric must be smaller or bigger than a given threshold. When a player satisfies its own constraint, the player is said to be satisfied. A satisfaction equilibrium, if it exists, arises when all players in the game are satisfied.
History The term Satisfaction equilibrium (SE) was first used to refer to the stable point of a dynamic interaction between players that are learning an equilibrium by taking actions and observing their own payoffs. The equilibrium lies on the satisfaction principle, which stipulates that an agent that is satisfied with its current payoff does not change its current action.
Later, the notion of satisfaction equilibrium was introduced as a solution-concept for Games in satisfaction form. Such solution-concept was introduced in the realm of electrical engineering for the analysis of quality of service (QoS) in Wireless ad hoc networks. In this context, radio devices (network components) are modelled as players that decide upon their own operating configurations in order to satisfy some targeted QoS.
Games in satisfaction form and the notion of satisfaction equilibrium have been used in the context of the fifth generation of cellular communications (5G) for tackling the problem of energy efficiency,
spectrum sharing
and transmit power control.
In the smart grid, games in satisfaction form have been used for modelling the problem of data injection attacks.
Games in Satisfaction Form In static games of complete, perfect-information, a satisfaction-form representation of a game is a specification of the set of players, the players' action sets and their preferences. The preferences for a given player are determined by a mapping, often referred to as the preference mapping, from the Cartesian product of all the other players' action sets to the given player's power set of actions. That is, given the actions adopted by all the other players, the preference mapping determines the subset of actions with which the player is satisfied.
- Definition [Games in Satisfaction Form the notion of performance optimization, i.e., utility maximization or cost minimization, is not present. Games in satisfaction-form model the case in which players adopt their actions aiming to satisfy a specific individual constraint given the actions adopted by all the other players. An important remark is that, players are assumed to be careless of whether other players can satisfy or not their individual constraints.
Satisfaction Equilibrium An action profile is a tuple <math>\boldsymbol{a} = \left(a_{1}, \ldots, a_{K} \right) \in \mathcal{A}_1 \times \ldots \times \mathcal{A}_K</math>. The action profile in which all players are satisfied is an equilibrium of the corresponding game in satisfaction form. At a satisfaction equilibrium, players do not exhibit a particular interest in changing its current action.
- Definition [Satisfaction Equilibrium in Pure Strategies
Definition: [Generalized Satisfaction Form] A game in generalized satisfaction form is described by a tuple <math>\left( \mathcal{K}, \left\lbrace \mathcal{A}_k \right\rbrace_{k \in \mathcal{K}},\left\lbrace g_{k}\right\rbrace_{ k \in\mathcal{K}} \right)</math>, where, the set <math>\mathcal{K} = \lbrace 1, \ldots, K \rbrace \subset \mathrm{N}</math>, with <math> 0 < K < +\infty </math>, represents the set of players; the set <math>\mathcal{A}_{k} </math>, with <math> k \in \mathcal{K} </math> and <math> 0< |\mathcal{A}_k | < +\infty</math>, represents the set of actions that player <math> k </math> can play; and the preference mapping ::<math>g_k: \prod_{j\in\mathcal{K}\setminus\lbrace k \rbrace} \triangle\left(\mathcal{A}_j\right) \rightarrow 2^{\triangle\left(\mathcal{A}_{k}\right)}</math>, determines the set of probability mass functions (mixed strategies) with support <math>\mathcal{A}_k</math> that satisfy player <math>k</math> given the mixed strategies adopted by all the other players.
The generalized satisfaction equilibrium is defined as follows.
Definition: [Generalized Satisfaction Equilibrium (GSE)] The mixed strategy profile <math>\boldsymbol{\pi}^* \in \triangle\left(\mathcal{A}_1\right)\times\ldots\times\triangle\left(\mathcal{A}_K\right)</math> is a generalized satisfaction equilibrium of the game in generalized satisfaction form <math>\left( \mathcal{K}, \left\lbrace \mathcal{A}_k \right\rbrace_{k \in \mathcal{K}},\left\lbrace g_{k}\right\rbrace_{ k \in\mathcal{K}} \right)</math> if there exists a partition of the set <math>\mathcal{K}</math> formed by the sets <math>\mathcal{K}_{\mathrm{s}}</math> and <math>\mathcal{K}_{\mathrm{u}}</math> and the following holds: (i) For all <math> k \in \mathcal{K}_{\mathrm{s}}</math>, <math> \boldsymbol{\pi}_k \in g_{k}\left( \boldsymbol{\pi}_{-k}\right) </math>; and (ii)For all <math> k \in \mathcal{K}_{\mathrm{u}}</math>, <math>g_{k}\left( \boldsymbol{\pi}_{-k}\right) = \empty. </math>
Note that the GSE boils down to the notion of <math>\epsilon</math>-SE of the game in satisfaction form <math> \left( \mathcal{K}, \left\lbrace \mathcal{A}_k \right\rbrace_{k \in \mathcal{K}},\left\lbrace \bar{f}_{k}\right\rbrace_{ k \in\mathcal{K}} \right),</math> when, <math>\mathcal{K}_{\mathrm{u}} = \emptyset</math> and for all <math>k \in \mathcal{K}</math>, the correspondence <math>g_k</math> is chosen to be ::<math>g(\boldsymbol{a}_{-k}) = \bar{\bar{f}}_k\left( \boldsymbol{\pi}_{-k}^* \right),</math> with <math>\epsilon > 0</math>. Similarly, the GSE boils down to the notion of SE in mixed strategies when <math>\epsilon = 0</math> and <math>\mathcal{K}_{\mathrm{u}} = \emptyset</math>. Finally, note that any SE is a GSE, but the converse is not true.