Satisfaction equilibrium – Wikipedia

Posted on August 25, 2019 by lordneo

Solution Concept for Noncooperative games

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.

Table of Contents

History[edit]

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.
^[1]

Later, the notion of satisfaction equilibrium was introduced as a solution concept for Games in satisfaction form.^[2]
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,
^[3]
spectrum sharing
^[4]
and transmit power control.
^[5]^[6]
In the smart grid, games in satisfaction form have been used for modelling the problem of data injection attacks.
^[7]

Games in Satisfaction Form[edit]

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^[2]]
A game in satisfaction form is described by a tuple

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right),}

where, the set

{displaystyle {mathcal {K}}=lbrace 1,ldots ,Krbrace subset mathrm {N} }

${displaystyle {mathcal {K}}=lbrace 1,ldots ,Krbrace subset mathrm {N} }$ , with

{displaystyle 0

${displaystyle 0<K<+infty }$ , represents the set of players; the set

{displaystyle {mathcal {A}}_{k}}

${displaystyle {mathcal {A}}_{k}}$ , with

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ and

{displaystyle 0<|{mathcal {A}}_{k}|<+infty }

${displaystyle 0<|{mathcal {A}}_{k}|<+infty }$ , represents the set of actions that player

{displaystyle k}

$k$ can play. The preference mapping

{displaystyle f_{k}:{mathcal {A}}_{1}times ldots times {mathcal {A}}_{k-1}times {mathcal {A}}_{k+1}times ldots ,times {mathcal {A}}_{K}rightarrow 2^{{mathcal {A}}_{k}}}

determines the set of actions with which player

{displaystyle k}

$k$ is satisfied given the actions played by all the other players. The set

{displaystyle 2^{{mathcal {A}}_{k}}}

${displaystyle 2^{{mathcal {A}}_{k}}}$ is the power set of

{displaystyle {mathcal {A}}_{k}}

${displaystyle {mathcal {A}}_{k}}$ .

In contrast to other existing game formulations, e.g., normal form and normal form with constrained action sets,^[8] 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[edit]

An action profile is a tuple

{displaystyle {boldsymbol {a}}=left(a_{1},ldots ,a_{K}right)in {mathcal {A}}_{1}times ldots times {mathcal {A}}_{K}}

${displaystyle {boldsymbol {a}}=left(a_{1},ldots ,a_{K}right)in {mathcal {A}}_{1}times ldots times {mathcal {A}}_{K}}$ . 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^[2]]
The action profile

{displaystyle {boldsymbol {a}}}

${boldsymbol {a}}$ is a satisfaction equilibrium in pure strategies for the game

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right),}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right),}$ if for all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ ,

{displaystyle a_{k}in f_{k}left(a_{1},ldots ,a_{k-1},a_{k+1},ldots ,a_{K}right)}

Satisfaction Equilibrium in Mixed Strategies[edit]

For all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ , denote the set of all possible probability distributions over the set

{displaystyle {mathcal {A}}_{k}=lbrace A_{k,1},A_{k,2},ldots ,A_{k,N_{k}}rbrace }

${displaystyle {mathcal {A}}_{k}=lbrace A_{k,1},A_{k,2},ldots ,A_{k,N_{k}}rbrace }$ by

{displaystyle triangle left({mathcal {A}}_{k}right)}

${displaystyle triangle left({mathcal {A}}_{k}right)}$ , with

{displaystyle N_{k}=|{mathcal {A}}_{k}|}

${displaystyle N_{k}=|{mathcal {A}}_{k}|}$ . Denote by

{displaystyle {boldsymbol {pi }}_{k}=left(pi _{k,1},pi _{k,2},ldots ,pi _{k,N_{k}}right)}

${displaystyle {boldsymbol {pi }}_{k}=left(pi _{k,1},pi _{k,2},ldots ,pi _{k,N_{k}}right)}$ the probability distribution (mixed strategy) adopted by player

{displaystyle k}

$k$ to choose its actions. For all

{displaystyle jin lbrace 1,ldots ,N_{k}rbrace }

${displaystyle jin lbrace 1,ldots ,N_{k}rbrace }$ ,

{displaystyle pi _{k,j}}

${displaystyle pi _{k,j}}$ represents the probability with which player

{displaystyle k}

$k$ chooses action

{displaystyle A_{k,j}in {mathcal {A}}_{k}}

${displaystyle A_{k,j}in {mathcal {A}}_{k}}$ . The notation

{displaystyle {boldsymbol {pi }}_{-k}}

${displaystyle {boldsymbol {pi }}_{-k}}$ represents the mixed strategies of all players except that of player

{displaystyle k}

$k$ .

Definition [Extension to Mixed Strategies of the Satisfaction Form ^[2]]
The extension in mixed strategies of the game

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}$ is described by the tuple

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}$ ,
where the correspondence

{displaystyle {bar {f}}_{k}:prod _{jin {mathcal {K}}setminus lbrace krbrace }triangle left({mathcal {A}}_{j}right)rightarrow 2^{triangle left({mathcal {A}}_{k}right)}}

determines the set of all possible probability distributions that allow player

{displaystyle k}

$k$ to choose an action that satisfies its individual conditions with probability one, that is,

{displaystyle {bar {f}}_{k}left({boldsymbol {pi }}_{-k}right)=leftlbrace {boldsymbol {pi }}_{k}in triangle left({mathcal {A}}_{k}right):mathrm {Pr} left(a_{k}in f_{k}left({boldsymbol {a}}_{-k}right)|a_{k}sim {boldsymbol {pi }}_{k},{boldsymbol {a}}_{-k}sim {boldsymbol {pi }}_{-k}right)=1rightrbrace .}

A satisfaction equilibrium in mixed strategies is defined as follows.

Definition [Satisfaction Equilibrium in Mixed Strategies^[2]]
The mixed strategy profile

{displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times ldots times triangle left({mathcal {A}}_{K}right)}

${displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times ldots times triangle left({mathcal {A}}_{K}right)}$ is an SE in mixed strategies if for all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ ,

{displaystyle {boldsymbol {pi }}_{k}^{*}in {bar {f}}_{k}left({boldsymbol {pi }}_{-k}^{*}right)}

Let the

{displaystyle j}

$j$ -th action of player

{displaystyle k}

$k$ , i.e.,

{displaystyle A_{k,j}}

${displaystyle A_{k,j}}$ , be associated with the unitary vector

{displaystyle {boldsymbol {e}}_{j}=left(e_{1},e_{2}ldots ,e_{N_{k}}right)in mathrm {R} ^{N_{k}}}

${displaystyle {boldsymbol {e}}_{j}=left(e_{1},e_{2}ldots ,e_{N_{k}}right)in mathrm {R} ^{N_{k}}}$ , where, all the components are zero except its

{displaystyle j}

$j$ -th component, which is equal to one. The vector

{displaystyle {boldsymbol {e}}_{j}}

${displaystyle {boldsymbol {e}}_{j}}$ represents a degenerated probability distribution, where the action

{displaystyle A_{k,j}}

${displaystyle A_{k,j}}$ is deterministically chosen. Using this argument, it becomes clear that every satisfaction equilibrium in pure strategies of the game

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}$ is also a satisfaction equilibrium in mixed strategies of the game

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}$ .

At an SE of the game

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}$ ,
players choose their actions following a probability distribution such that only action profiles that allow all players to simultaneously satisfy their individual conditions with probability one are played with positive probability. Hence, in the case in which one SE in pure strategies does not exist, then, it does not exist a SE in mixed strategies in the game

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}$ .

ε-Satisfaction Equilibrium[edit]

Under certain conditions, it is always possible to build mixed strategies that allow players to be satisfied with probability

{displaystyle 1-epsilon }

$1-epsilon$ , for some

{displaystyle epsilon >0}

$epsilon >0″/>. This observation leads to the definition of a solution concept known as <span class=$

{displaystyle epsilon }

$epsilon$ -satisfaction equilibrium (

{displaystyle epsilon }

$epsilon$ -SE).

Definition: [ε-Satisfaction Equilibrium^[2]]
Let

{displaystyle epsilon }

$epsilon$ satisfy

{displaystyle epsilon in left]0,1right]}

${displaystyle epsilon in left]0,1right]}$ . The mixed strategy profile

{displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times triangle left({mathcal {A}}_{2}right)times ldots times triangle left({mathcal {A}}_{K}right)}

${displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times triangle left({mathcal {A}}_{2}right)times ldots times triangle left({mathcal {A}}_{K}right)}$
is an epsilon-satisfaction equilibrium (

{displaystyle epsilon }

$epsilon$ -SE) of the game

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right)}$ ,
if for all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ , it follows that

{displaystyle {boldsymbol {pi }}_{k}^{*}in {bar {bar {f}}}_{k}left({boldsymbol {pi }}_{-k}^{*}right)}

where

{displaystyle {bar {bar {f}}}_{k}left({boldsymbol {pi }}_{-k}^{*}right)=leftlbrace {boldsymbol {pi }}_{k}in triangle left({mathcal {A}}_{k}right):mathrm {Pr} left(a_{k}in f_{k}left({boldsymbol {a}}_{-k}right)|a_{k}sim {boldsymbol {pi }}_{k},{boldsymbol {a}}_{-k}sim {boldsymbol {pi }}_{-k}^{*}right)geqslant 1-epsilon rightrbrace .}

From the definition above, it can be implied that if the mixed strategy profile

{displaystyle {boldsymbol {pi }}^{*}}

${displaystyle {boldsymbol {pi }}^{*}}$ is an

{displaystyle epsilon }

$epsilon$ -SE, it holds that,

{displaystyle mathrm {Pr} left(a_{k}in f_{k}left({boldsymbol {a}}_{-k}right)|a_{k}sim {boldsymbol {pi }}_{k}^{*},{boldsymbol {a}}_{-k}sim {boldsymbol {pi }}_{-k}^{*}right)geqslant 1-epsilon .}

That is, players are unsatisfied with probability

{displaystyle epsilon }

$epsilon$ . The relevance of the

{displaystyle epsilon }

$epsilon$ -SE is that it models the fact that players can be tolerant a certain unsatisfaction level. At a given

{displaystyle epsilon }

$epsilon$ -SE, none of the players is interested in changing its mixed strategy profile as long as it is satisfied with a probability higher than or equal to

{displaystyle 1-epsilon }

$1-epsilon$ , for some

{displaystyle epsilon >0}

$epsilon >0″/>. In contrast to the conditions for the existence of a SE in either pure or mixed strategies, the conditions for the existence of an <span class=$

{displaystyle epsilon }

$epsilon$ -SE are mild.

Proposition [Existence of an

${displaystyle epsilon }$

$epsilon$ -SE^[2]]
Let

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}$ ,
be a finite game in satisfaction form. Then, if for all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ , there always exists an action profile

{displaystyle {boldsymbol {a}}in {mathcal {A}}}

${displaystyle {boldsymbol {a}}in {mathcal {A}}}$ such that

{displaystyle a_{k}in f_{k}left({boldsymbol {a}}_{-k}right)}

then there always exists a strategy profile

{displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times triangle left({mathcal {A}}_{2}right)times ldots times triangle left({mathcal {A}}_{K}right)}

${displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times triangle left({mathcal {A}}_{2}right)times ldots times triangle left({mathcal {A}}_{K}right)}$ and a real

{displaystyle epsilon }

$epsilon$ , with

{displaystyle 1>epsilon >0}

${displaystyle 1>epsilon >0}”/>, such that, <span class=$

{displaystyle {boldsymbol {pi }}^{star }}

${displaystyle {boldsymbol {pi }}^{star }}$ is an

{displaystyle epsilon }

$epsilon$ -SE.

Equilibrium Selection[edit]

Games in satisfaction form might exhibit several satisfaction equilibria. In such a case, players might associate to each of their own actions a value representing the effort or cost to play such action. From this perspective, if several SEs exist, players might prefer the one that requires the lowest (global or individual) effort or cost.
To model this preference, games in satisfaction form might be equipped with cost functions for each of the players.

For all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ , let the function

{displaystyle c_{k}:{mathcal {A}}_{k}rightarrow left[0,1right]}

${displaystyle c_{k}:{mathcal {A}}_{k}rightarrow left[0,1right]}$ determine the effort or cost paid by player

{displaystyle k}

$k$ for using each of its actions. More specifically, given a pair of actions

{displaystyle (a_{k},a_{k}’)in {mathcal {A}}_{k}^{2}}

${displaystyle (a_{k},a_{k}')in {mathcal {A}}_{k}^{2}}$ , the action

{displaystyle a_{k}}

$a_{k}$ is preferred against

{displaystyle a_{k}’}

${displaystyle a_{k}'}$ by player

{displaystyle k}

$k$ if

{displaystyle c_{k}left(a_{k}right)

Note that this preference for player

{displaystyle k}

$k$ is independent of the actions adopted by all the other players.

Definition: [Efficient Satisfaction Equilibrium (ESE)]
Let

{displaystyle {mathcal {S}}}

${mathcal {S}}$ be the set of satisfaction equilibria in pure strategies of the game in satisfaction form

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace f_{k}rightrbrace _{kin {mathcal {K}}}right)}$ .
The strategy profile

{displaystyle {boldsymbol {a}}^{star }=left(a_{1}^{star },a_{2}^{star },ldots ,a_{K}^{star }right)in {mathcal {A}}}

${displaystyle {boldsymbol {a}}^{star }=left(a_{1}^{star },a_{2}^{star },ldots ,a_{K}^{star }right)in {mathcal {A}}}$
is an efficient satisfaction equilibrium
if for all

{displaystyle {boldsymbol {a}}in {mathcal {A}}}

${displaystyle {boldsymbol {a}}in {mathcal {A}}}$ , it follows that

{displaystyle sum _{k=1}^{K}c_{k}left(a_{k}^{star }right)leqslant sum _{k=1}^{K}c_{k}left(a_{k}right)}

In the trivial case in which for all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ the function

{displaystyle c_{k}}

$c_{k}$ is a constant function, the set of ESE and the set of SE are identical. This highlights the relevance of the ability of players to differentiate the effort of playing one action or another in order to select one (satisfaction) equilibrium among all the existing equilibria.

In games in satisfaction form with nonempty sets of satisfaction equilibria, when all players assign different costs to its actions, i.e., for all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ and for all

{displaystyle (a,a’)in {mathcal {A}}_{k}times {mathcal {A}}_{k}}

${displaystyle (a,a')in {mathcal {A}}_{k}times {mathcal {A}}_{k}}$ , it holds that

{displaystyle c_{k}(a)neq c_{k}(a’)}

${displaystyle c_{k}(a)neq c_{k}(a')}$ , there always exists an ESE. Nonetheless, it is not necessarily unique, which implies that there still exists room for other equilibrium refinements beyond the notion of individual cost functions. ^[5]^[6]

Generalizations[edit]

Games in satisfaction form for which it does not exists an action profile in which all players are satisfied are said not to possess a satisfaction equilibrium. In this case, an action profile induces a partition of the set

{displaystyle {mathcal {K}}}

${mathcal {K}}$ formed by the sets

{displaystyle {mathcal {K}}_{mathrm {s} }}

${displaystyle {mathcal {K}}_{mathrm {s} }}$ and

{displaystyle {mathcal {K}}_{mathrm {u} }}

${displaystyle {mathcal {K}}_{mathrm {u} }}$ . On one hand, the players in

{displaystyle {mathcal {K}}_{mathrm {s} }}

${displaystyle {mathcal {K}}_{mathrm {s} }}$ are satisfied. On the other hand, players in

{displaystyle {mathcal {K}}_{mathrm {u} }}

${displaystyle {mathcal {K}}_{mathrm {u} }}$ are unsatisfied. If players in the set

{displaystyle {mathcal {K}}_{mathrm {u} }}

${displaystyle {mathcal {K}}_{mathrm {u} }}$ cannot be satisfied by any of its actions given the actions of all the other players, these players are not interested in changing its current action. This implies that action profiles that satisfy this condition are also equilibria. This is because none of the players is particularly interested in changing their current actions, even those that are unsatisfied. This reasoning led to another solution concept known as generalized satisfaction equilibrium (GSE).
This generalization is proposed in the context of a novel game formulation, namely the generalized satisfaction form.
^[9]

Definition: [Generalized Satisfaction Form]
A game in generalized satisfaction form is described by a tuple

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace g_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace g_{k}rightrbrace _{kin {mathcal {K}}}right)}$ ,
where, the set

{displaystyle {mathcal {K}}=lbrace 1,ldots ,Krbrace subset mathrm {N} }

${displaystyle {mathcal {K}}=lbrace 1,ldots ,Krbrace subset mathrm {N} }$ , with

{displaystyle 0

${displaystyle 0<K<+infty }$ , represents the set of players; the set

{displaystyle {mathcal {A}}_{k}}

${displaystyle {mathcal {A}}_{k}}$ , with

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ and

{displaystyle 0<|{mathcal {A}}_{k}|<+infty }

${displaystyle 0<|{mathcal {A}}_{k}|<+infty }$ , represents the set of actions that player

{displaystyle k}

$k$ can play; and the preference mapping

{displaystyle g_{k}:prod _{jin {mathcal {K}}setminus lbrace krbrace }triangle left({mathcal {A}}_{j}right)rightarrow 2^{triangle left({mathcal {A}}_{k}right)}}

determines the set of probability mass functions (mixed strategies) with support

{displaystyle {mathcal {A}}_{k}}

${displaystyle {mathcal {A}}_{k}}$ that satisfy player

{displaystyle k}

$k$ given the mixed strategies adopted by all the other players.

The generalized satisfaction equilibrium is defined as follows.

Definition: [Generalized Satisfaction Equilibrium (GSE)^[9]]
The mixed strategy profile

{displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times ldots times triangle left({mathcal {A}}_{K}right)}

${displaystyle {boldsymbol {pi }}^{*}in triangle left({mathcal {A}}_{1}right)times ldots times triangle left({mathcal {A}}_{K}right)}$ is a generalized satisfaction equilibrium of the game in generalized satisfaction form

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace g_{k}rightrbrace _{kin {mathcal {K}}}right)}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace g_{k}rightrbrace _{kin {mathcal {K}}}right)}$
if there exists a partition of the set

{displaystyle {mathcal {K}}}

${mathcal {K}}$ formed by the sets

{displaystyle {mathcal {K}}_{mathrm {s} }}

${displaystyle {mathcal {K}}_{mathrm {s} }}$ and

{displaystyle {mathcal {K}}_{mathrm {u} }}

${displaystyle {mathcal {K}}_{mathrm {u} }}$ and the following holds:
(i) For all

{displaystyle kin {mathcal {K}}_{mathrm {s} }}

${displaystyle kin {mathcal {K}}_{mathrm {s} }}$ ,

{displaystyle {boldsymbol {pi }}_{k}in g_{k}left({boldsymbol {pi }}_{-k}right)}

${displaystyle {boldsymbol {pi }}_{k}in g_{k}left({boldsymbol {pi }}_{-k}right)}$ ; and
(ii)For all

{displaystyle kin {mathcal {K}}_{mathrm {u} }}

${displaystyle kin {mathcal {K}}_{mathrm {u} }}$ ,

{displaystyle g_{k}left({boldsymbol {pi }}_{-k}right)=emptyset .}

${displaystyle g_{k}left({boldsymbol {pi }}_{-k}right)=emptyset .}$

Note that the GSE boils down to the notion of

{displaystyle epsilon }

$epsilon$ -SE of the game in satisfaction form

{displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right),}

${displaystyle left({mathcal {K}},leftlbrace {mathcal {A}}_{k}rightrbrace _{kin {mathcal {K}}},leftlbrace {bar {f}}_{k}rightrbrace _{kin {mathcal {K}}}right),}$
when,

{displaystyle {mathcal {K}}_{mathrm {u} }=emptyset }

${displaystyle {mathcal {K}}_{mathrm {u} }=emptyset }$ and for all

{displaystyle kin {mathcal {K}}}

${displaystyle kin {mathcal {K}}}$ , the correspondence

{displaystyle g_{k}}

$g_{k}$ is chosen to be

{displaystyle g({boldsymbol {a}}_{-k})={bar {bar {f}}}_{k}left({boldsymbol {pi }}_{-k}^{*}right),}

with

{displaystyle epsilon >0}

$epsilon >0″/>. Similarly, the GSE boils down to the notion of SE in mixed strategies when <span class=$

{displaystyle epsilon =0}

$epsilon = 0$ and

{displaystyle {mathcal {K}}_{mathrm {u} }=emptyset }

${displaystyle {mathcal {K}}_{mathrm {u} }=emptyset }$ .
Finally, note that any SE is a GSE, but the converse is not true.

References[edit]

^ Ross, S.; Chaib-draa, B. (May 2006). “Satisfaction Equilibrium: Achieving Cooperation in Incomplete Information Games”. Proceedings of the Canadian Conference on Artificial Intelligence. Ottawa, ON, Canada. doi:10.1007/11766247_6.
^ ^a ^b ^c ^d ^e ^f ^g Perlaza, S.; Tembine, H.; Lasaulce, S.; Debbah, M. (April 2012). “Quality-Of-Service Provisioning in Decentralized Networks: A Satisfaction Equilibrium Approach”. IEEE Journal of Selected Topics in Signal Processing. 6 (2): 104–116. arXiv:1112.1730. doi:10.1109/JSTSP.2011.2180507. S2CID 9567688.
^ Elhammouti, H.; Sabir, E.; Benjillali, M.; Echabbi, L.; Tembine, H. (September 2017). “Self-Organized Connected Objects: Rethinking QoS Provisioning for IoT Services”. IEEE Communications Magazine. 55 (9): 41–47. doi:10.1109/MCOM.2017.1600614. S2CID 27329276.
^ Southwell, R.; Chen, X.; Huang, J. (March 2014). “Quality of Service Games for Spectrum Sharing”. IEEE Journal on Selected Areas in Communications. 32 (3): 589–600. arXiv:1310.2354. doi:10.1109/JSAC.2014.1403008. S2CID 9227076.
^ ^a ^b Promponas, P.; Tsiropoulou, E-E.; Papavassiliou, S. (May 2021). “Rethinking Power Control in Wireless Networks: The Perspective of Satisfaction Equilibrium”. IEEE Transactions on Control of Network Systems. 8 (4): 1680–1691. doi:10.1109/TCNS.2021.3078123. S2CID 236728675.
^ ^a ^b Promponas, P.; Pelekis, C.; Tsiropoulou, E-E.; Papavassiliou, S. (July 2021). “Games in Normal and Satisfaction Form for Efficient Transmission Power Allocation Under Dual 5G Wireless Multiple Access Paradigm”. IEEE/ACM Transactions on Networking. 29 (6): 2574–2587. doi:10.1109/TNET.2021.3095351. S2CID 237965568.
^ Sanjab, A.; Saad, W. (July 2016). “Data Injection Attacks on Smart Grids With Multiple Adversaries: A Game-Theoretic Perspective”. IEEE Transactions on Smart Grid. 7 (4): 2038–2049. arXiv:1604.00118. doi:10.1109/TSG.2016.2550218. S2CID 14309194.
^ Debreu, G. (October 1952). “A Social Equilibrium Existence Theorem” (PDF). Proceedings of the National Academy of Sciences of the United States of America. 38 (10): 886–893. doi:10.1073/pnas.38.10.886. PMC 1063675. PMID 16589195.
^ ^a ^b Goonewardena, M.; Perlaza, S.; Yadav, A.; Ajib, W. (June 2017). “Generalized Satisfaction Equilibrium for Service-Level Provisioning in Wireless Networks”. IEEE Transactions on Communications. 65 (6): 2427–2437. doi:10.1109/TCOMM.2017.2662701. S2CID 25391577.

Satisfaction equilibrium – Wikipedia

History[edit]

Games in Satisfaction Form[edit]

Satisfaction Equilibrium[edit]

Satisfaction Equilibrium in Mixed Strategies[edit]

ε-Satisfaction Equilibrium[edit]

Equilibrium Selection[edit]

Generalizations[edit]

References[edit]

Recent Posts

Recent Comments

Archives

Categories

Meta