Learning Notes: Multiagent Decision-making and Control
Static games
Game theory: mathematical models of decision-making of multiple players
To characterize a game:
- The players are the agents that make decisions
- The actions available to each player at each decision point
- The information structure specifies what each player knows before making each decision, in particular with respect to other players’ decisions
- The cost function for each player, which depends on all players’ decisions
Matrix games
- two players \(P_1\), \(P_2\)
- a finite number of actions (strategies) \(\Gamma = \{\gamma_1, ..., \gamma_m\}\), \(\Sigma = \{\sigma_1, ..., \sigma_n\}\)
- costs: \(J_1(\gamma_i, \sigma_j)\) and \(J_2(\gamma_i, \sigma_j)\)
- \(P_1\) is the row player, \(P_2\) is the column player
- each element of the matrix corresponds to the resulting costs for the two players, as an ordered pair \((a_{ij}, b_{ij})\): \[ a_{ij} = J_1(\gamma_i, \sigma_j), \qquad b_{ij} = J_2(\gamma_i, \sigma_j) \]
Matrix games or equivalently normal form games, strategic form games:
- players act simultaneously
- players don’t have knowledge of each other’s choice of actions
Strategy: a complete description of how to play the game
- equivalent to control policy/law in control theory or decision rule in optimization in matrix games strategy and actions are equivalent, and the terms are used
- interchangeably (not the case in extensive form games/dynamic games).
Strictly dominant and dominated actions: \[ A = \left[ \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & \ddots & & \vdots\\ \vdots & & \ddots & \vdots\\ a_{m1} & \cdots & \cdots & a_{mn}\\ \end{matrix}\right] \] Without loss of generality, lets’ consider \(P_1\), choosing rows:
- action \(i\) is strictly dominant action if \[ a_{ij} < a_{kj}, \quad \forall j\in\{1, ..., n\}, \forall k \neq i \] rational player will play strictly dominant action.
- action \(k\) is strictly dominated action if \(\exists i\) \[ a_{ij} < a_{kj}, \quad \forall j\in\{1, ..., n\} \] rational player will not play strictly dominated action.
Nash Equilibrium
A pair of of actions \((\gamma^*, \sigma^*)\) is a Nash Equilibrium if no player can do better by unilaterally changing her/his decision..
Given a static two-player game described by the two payoff matrices \(A\) and \(B\) (for \(P_1\) and \(P_2\), respectively), we say that the pair of actions \(i^*\in\{1, ..., m\}\) and \(j^*\in\{1, ..., n\}\) are a Nash Equilibrium if \[ a_{i^*j^*} \leq a_{kj^*}\quad\forall k= 1, ..., m \quad \text{and} \quad b_{i^*j^*} \leq b_{i^*k}\quad\forall k= 1, ..., n \]
Given a pair of strategies \((\gamma, \sigma)\) in \(\Gamma\times\Sigma\), define the best-response maps: \[ (\gamma, \sigma) \mapsto R(\gamma, \sigma) = \left(R_1(\sigma), R_2(\gamma)\right) \] where \[ R_1(\sigma) = \left\{ \gamma \in \Gamma \mid J_1(\gamma, \sigma) \leq J_1(\gamma', \sigma), \forall \gamma' \in \Gamma \right\} \] \[ R_2(\gamma) = \left\{ \sigma \in \Sigma \mid J_2(\gamma, \sigma) \leq J_2(\gamma, \sigma'), \forall \sigma' \in \Sigma \right\} \]
Nash equilibria are fixed points of best-response maps.
Strictly dominant strategies if they exist are Nash equilibrium; strictly dominated strategies cannot be Nash equilibrium.
Mixed strategies
- A mixed strategy is a probability distribution on the actions; Pure strategies exist within the mixed strategy space.
- Expected outcome of the game: \[ J_1(y,z) = \sum_{i=1}^m\sum_{j=1}^n y_i z_j a_{ij} = y^\top A z \] \[ J_2(y,z) = \sum_{i=1}^m\sum_{j=1}^n y_i z_j b_{ij} = y^\top B z \]
- Given a static two-player game described by the two payoff matrices \(A\) and \(B\) (for \(P_1\) and \(P_2\), respectively), a pair of mixed strategies \(y^* \in \mathcal{Y}\) and \(z^* \in \mathcal{Z}\) is a mixed Nash Equilibrium if \[ (y^*)^{\top} A z^* \leq y^{\top} A z^* \quad \forall y \in \mathcal{Y} \] and \[ (y^*)^{\top} B z^* \leq (y^*)^{\top} B z \quad \forall z \in \mathcal{Z} \]
- In general terms, \(y^* \in \mathcal{Y}\) and \(z^* \in \mathcal{Z}\) are a Nash Equilibrium if \[ J_1(y^*, z^*) \leq J_1(y, z^*) \quad \forall y \in \mathcal{Y} \] and \[ J_2(y^*, z^*) \leq J_2(y^*, z) \quad \forall z \in \mathcal{Z} \]
Zero-sum games
- Zero-sum games: Two-person games in which the two players have opposite payoffs.
- The security level of \(P_1\) (minimizer) is defined by: \[ \overline{V} := \min_{i\in \{1,...,n\}}\,\max_{j\in \{1,...,m\}} a_{ij} \] \(\overline{V}\) is the worst outcome that \(P_1\) can guarantee herself. The security strategy of \(P_1\) (minimizer) is defined by \[ \overline{i} \in {\arg\!\min}_{i\in \{1,...,n\}}\,\max_{j\in \{1,...,m\}} a_{ij} \] The security level of \(P_2\) (maximizer) is defined by: \[ \underline{V} := \max_{j\in \{1,...,n\}}\,\min_{i\in \{1,...,m\}} a_{ij} \] \(\underline{V}\) is the worst possible outcome that \(P_2\) can guarantee himself. The security strategy of \(P_2\) (maximizer) is defined by \[ \underline{j} \in {\arg\!\max}_{j\in \{1,...,n\}}\,\min_{i\in \{1,...,m\}} a_{ij} \]
- Min-Max Property, For every finite matrix A, the following properties hold:
- Security levels are well defined and unique
- Both players have security strategies (not necessarily unique)
- The security levels always satisfy \[ \underbrace{\underline{V} := \max_{j\in \{1,...,n\}}\,\min_{i\in \{1,...,m\}} a_{ij}}_{P_2} \, \leq\, \underbrace{\overline{V} := \min_{i\in \{1,...,n\}}\,\max_{j\in \{1,...,m\}} a_{ij}}_{P_1} \]
- Given a zero-sum game described by the payoff matrix \(A\), we say that the pair of actions \(\gamma_{i^*}\in\Gamma\) and \(\sigma_{j^*}\in\Sigma\) are a Nash Equilibrium if \[ a_{i^*j}\leq a_{i^*j^*} \leq a_{ij^*} \quad \forall i\in\{1,...,m\}, \ \forall j\in\{1,...,n\} \] also known as saddle-point equilibrium. call \(V^* := a_{i^*j^*}\) saddle-point value.
A zero-sum game defined by A has a saddle-point equilibrium if and only if \[ \underbrace{\underline{V} := \max_{j\in \{1,...,n\}}\,\min_{i\in \{1,...,m\}} a_{ij}}_{P_2} \, =\, \underbrace{\overline{V} := \min_{i\in \{1,...,n\}}\,\max_{j\in \{1,...,m\}} a_{ij}}_{P_1} \] and \(\underline{V}=\overline{V}\) is the saddle-point value.
- All saddle-point equilibria (Nash equilibria) of a zero-sum game have the same value \(V^*\), which we denote as the value of the game.
- Order interchangeability: if \((i_1^*,j_1^*)\) and \((i_2^*,j_2^*)\) are saddle-point equilibria for a zero-sum game, then \((i_2^*,j_1^*)\) and \((i_1^*,j_2^*)\) are also saddle-point equilibria.
- The mixed security level of \(P_1\) (minimizer) is defined by: \[ \overline{V}_m := \min_{y\in\mathcal{Y}}\,\max_{z\in\mathcal{Z}} \, y^\top Az = \min_{y\in\mathcal{Y}}\,\max_{z\in\mathcal{Z}}\, \sum_{i=1}^{m}\sum_{j=1}^{n} y_iz_ja_{ij} \] The mixed security strategy of \(P_1\) (minimizer) is any \[ \overline{y} \in {\arg\!\min}_{y\in\mathcal{Y}}\,\max_{z\in\mathcal{Z}}\, y^\top Az \] The mixed security level of \(P_2\) (maximizer) is defined by: \[ \underline{V}_m := \max_{z\in\mathcal{Z}}\,\min_{y\in\mathcal{Y}} \, y^\top Az = \max_{z\in\mathcal{Z}}\,\min_{y\in\mathcal{Y}}\, \sum_{i=1}^{m}\sum_{j=1}^{n} y_iz_ja_{ij} \] \(\underline{V}\) is the worst possible outcome that \(P_2\) can guarantee himself. The mixed security strategy of \(P_2\) (maximizer) is defined by \[ \underline{z} \in {\arg\!\max}_{z\in\mathcal{Z}}\,\min_{y\in\mathcal{Y}} y^\top Az \]
For every (finite) matrix A, the following properties hold: - Average security levels are well defined and unique - Both players have mixed security strategies (not necessarily unique) - The average security levels always satisfy the following inequalities: \[ \underline{V} \leq \underline{V}_m \leq \overline{V}_m \leq \overline{V} \]
- A pair of strategies \((y^*, z^*)\in \mathcal{Y} \times \mathcal{Z}\) is called a mixed-strategy saddle-point equilibrium (or Nash equilibrium) if \[ {y^*}^\top Az^* \leq y^\top Az^*, \quad \forall y \in \mathcal{Y} \] \[ {y^*}^\top Az^* \geq {y^*}^\top Az, \quad \forall z \in \mathcal{Z} \] \({y^*}^\top Az^*\) is called the saddle point value.
Potential games
N-player non-zero-sum games
- \(N\) players
- Player \(i\) can choose one among \(m_i\) pure actions \[ \Gamma_i = \{\gamma_i^1, \gamma_i^2,,..., \gamma_i^{m_i}\} \]
- Let \(\Gamma= \Gamma_1\times...\times\Gamma_N\) , the cost of player \(i\) is given by \(J_i:\Gamma\rightarrow\mathbb{R}\): \[ J_i(\gamma_1, \gamma_2,,..., \gamma_N) = J_i(\gamma_i, \gamma_{-i}), \quad \gamma_{-i} = (\gamma_1,..., \gamma_{i-1}, \gamma_{i+1},... \gamma_N) \]
- Pure Nash equilibrium: A strategy profile \(\gamma^* = (\gamma_1^*, \gamma_2^*,,..., \gamma_N^*) \in \Gamma\) is a pure Nash equilibrium if for every player \(i\) \[ J_i(\gamma_i^*, \gamma_{-i}^*) \leq J_i(\gamma_i^\prime, \gamma_{-i}^*), \quad \gamma_i^\prime\in\Gamma_i \]
- Best-response map: the best-response of player \(i\) is the set \(R_i(\gamma_{-i}) \subseteq \Gamma_i\) such that \[ \gamma_i \in R_i(\gamma_{-i}) \ \Longleftrightarrow\ J_i(\gamma_i, \gamma_{-i}) \leq J_i(\gamma_i^\prime, \gamma_{-i}), \quad \forall\gamma_i^\prime\in\Gamma_i \] In other words: \(R_i(\gamma_{-i}) := \arg\!\min_{\gamma_i\in\Gamma_i} J_i(\gamma_i, \gamma_{-i})\)
Potential functions and potential games
A function \(P : \Gamma_1 \times \Gamma_2 \times \dots \times \Gamma_N \to \mathbb{R}\) is an ordinal potential function if for every player \(i\) and every \(\gamma_{-i}\), \[ J_i(\gamma_i', \gamma_{-i}) - J_i(\gamma_i'', \gamma_{-i}) > 0 \quad \text{iff} \quad P(\gamma_i', \gamma_{-i}) - P(\gamma_i'', \gamma_{-i}) > 0 \] for every \(\gamma_i', \gamma_i'' \in \Gamma_i\).
A function \(P : \Gamma_1 \times \Gamma_2 \times \dots \times \Gamma_N \to \mathbb{R}\) is an exact potential function if for every player \(i\) and every \(\gamma_{-i}\), \[ J_i(\gamma_i', \gamma_{-i}) - J_i(\gamma_i'', \gamma_{-i}) = P(\gamma_i', \gamma_{-i}) - P(\gamma_i'', \gamma_{-i}) \] for every \(\gamma_i', \gamma_i'' \in \Gamma_i\).
A game is an (ordinal/exact) potential game if it admits an (ordinal/exact) potential function.
If the game admits a potential function, then
- it has a pure strategy Nash equilibrium;
- the best response dynamics converge in finitely many steps.
A path in \(\Gamma\) is a sequence \[ \mathcal{P} = (\gamma(0), \gamma(1), \dots, \gamma(M)), \quad \gamma(k) \in \Gamma \] such that for every \(k\), there exists a unique player \(i_k\) such that \[ \gamma(k - 1) = (\gamma_{i_k}, \gamma_{-i_k}) \quad \to \gamma(k) = (\gamma_{i_k}', \gamma_{-i_k}), \quad \text{with } \gamma_{i_k} \neq \gamma_{i_k}' \]
Consider any finite path \(\mathcal{P} = (\gamma(0), \gamma(1), \dots, \gamma(M))\).
A path is closed if \(\gamma(0) = \gamma(M)\).
A path is simple if \(\gamma(k) \neq \gamma(k')\), for every \(k, k'\) (except \(\gamma(0)\) and \(\gamma(M)\)).
Continue from page 18/35