Chapter history 5.3

Matrices - Definition

• A matrix ($A$) is a rectangular array of numbers.
• $A$ is represented as: $\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & \ddots & \vdots \ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$
• The elements $a_{ij}$ are real ($\mathbb{R}$) or complex ($\mathbb{C}$) numbers.
• $i$ denotes the row, and $j$ denotes the column of an element in the matrix.
• An $m \times n$ matrix has $m$ rows and $n$ columns.
• $\mathbb{R}^{m \times n}$ (or $\mathbb{C}^{m \times n}$) represents the set of all $m \times n$ matrices.
• A matrix is square if $m = n$.

Special Matrices

• Null Matrix: All elements $a_{ij} = 0$.
• Identity Matrix: $I_n = \begin{pmatrix} 1 & 0 & \cdots & 0 \ 0 & 1 & \cdots & 0 \ \vdots & \vdots & \ddots & \vdots \ 0 & 0 & \cdots & 1 \end{pmatrix}$
• Diagonal Matrix: $A = (a_{ij})$ with $a_{ij} = 0$ for $i \neq j$.
• Triangular Matrix:
  • Upper Triangular Matrix: $A = (a_{ij})$ with $a_{ij} = 0$ for $i > j$.
  • Lower Triangular Matrix: $A = (a_{ij})$ with $a_{ij} = 0$ for $i < j$.
• Symmetric Matrix: $A = (a_{ij})$ with $a_{ij} = a_{ji}$ for all $i, j$.
• Antisymmetric Matrix: $A = (a_{ij})$ with $a_{ij} = -a_{ji}$ for all $i, j$.

Matrix Arithmetic

• Addition: For $A = (a_{ij}), B = (b_{ij}) \in \mathbb{R}^{m \times n}$, $A + B = (a_{ij} + b_{ij}) \in \mathbb{R}^{m \times n}$.
• Scalar Multiplication: For $A = (a_{ij}) \in \mathbb{R}^{m \times n}$ and $\lambda \in \mathbb{R}$, $\lambda A = (\lambda a_{ij}) \in \mathbb{R}^{m \times n}$.
• Matrix Multiplication: For $A = (a_{ij}) \in \mathbb{R}^{m \times n}$ and $B = (b_{jk}) \in \mathbb{R}^{n \times p}$, $AB = (c_{ik}) \in \mathbb{R}^{m \times p}$ with $c_{ik} = \sum_{j=1}^{n} a_{ij} b_{jk}$.
  • Matrix multiplication is not commutative ($AB \neq BA$ in general).
  • Matrix multiplication is associative: $(AB)C = A(BC)$.
  • Matrix multiplication is distributive: $A(B + C) = AB + AC$ and $(A + B)C = AC + BC$.
• Transposition: For $A = (a_{ij}) \in \mathbb{R}^{m \times n}$, $A^T = (a_{ji}) \in \mathbb{R}^{n \times m}$.
  • $(A + B)^T = A^T + B^T$.
  • $(\lambda A)^T = \lambda A^T$.
  • $(AB)^T = B^T A^T$.
  • $(A^T)^T = A$.
• Inverse Matrix: For $A \in \mathbb{R}^{n \times n}$, if $\exists A^{-1} \in \mathbb{R}^{n \times n}$ such that $AA^{-1} = A^{-1}A = I_n$, then $A^{-1}$ is the inverse of $A$.
  • Not every matrix has an inverse.

Linear Equation Systems

• A linear equation system (LGS) has the form:
  • $a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1$
  • $a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2$
  • $\vdots$
  • $a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m$
  • where $a_{ij}, b_i \in \mathbb{R}$ (or $\mathbb{C}$).
• In matrix form: $Ax = b$ where $A = (a_{ij}) \in \mathbb{R}^{m \times n}$, $x = \begin{pmatrix} x_1 \ x_2 \ \vdots \ x_n \end{pmatrix} \in \mathbb{R}^n$ and $b = \begin{pmatrix} b_1 \ b_2 \ \vdots \ b_m \end{pmatrix} \in \mathbb{R}^m$.

Solving Linear Equation Systems

• An LGS can have no solution, exactly one solution, or infinitely many solutions.
• An LGS is solvable if it has at least one solution.
• An LGS is uniquely solvable if it has exactly one solution.
• Methods to solve an LGS:
  • Gauss-Elimination: Transform the LGS into an equivalent triangular form.
  • Cramer's Rule: Applicable when the matrix $A$ is square and invertible.
  • Matrix Inversion: If $A$ is invertible, then $x = A^{-1}b$.

Algorithmic Game Theory - Lecture 9

• Last Time: Discussed the price of anarchy with weighted players, potential games, and valid utility functions.
• Today's Focus: Existence of pure Nash equilibria (PNE), computing a PNE, and coarse correlated equilibrium.

Potential Function (Definition)

• A game $G = (N, S = \prod_{i \in N} S_i, (u_i)_{i \in N})$ is a potential game if there exists a function $\Phi: S \rightarrow \mathbb{R}$
• For all $i \in N$ and $s_{-i} \in S_{-i}$: $\Phi(s_i, s_{-i}) - \Phi(s'i, s{-i}) = u_i(s_i, s_{-i}) - u_i(s'i, s{-i})$
• The difference in potential equals the difference in utility.
• $\Phi$ is the potential function for $G$.

Potential Game Theorem

• If $G$ is a potential game, then $G$ has a pure Nash equilibrium (PNE).
• Let $s^* = \operatorname{argmax}_{s \in S} \Phi(s)$. Then $s^*$ is a Nash equilibrium.
• If a player $i$ can improve their utility, $u_i(s'i, s^*{-i}) > u_i(s^_i, s^{-i})$, then $\Phi(s'i, s^*{-i}) > \Phi(s^_i, s^{-i})$, contradicting that $s^*$ maximizes $\Phi$.

Example: Congestion Games

• $N$ players.
• $M$ resources.
• Each player chooses a set of resources.
• $S_i$: set of strategies for player i (each strategy is a set of resources).
• $x_e$: number of players using resource $e$.
• $c_e(x_e)$: cost of resource $e$ if $x_e$ players use it.
• $u_i(s) = -\sum_{e \in s_i} c_e(x_e)$.

Congestion Games as Potential Games

• Congestion games are potential games.
• Define $\Phi(s) = \sum_{e \in E} \sum_{j=1}^{x_e} c_e(j)$, where $x_e$ is the number of players using resource $e$ in state $s$.
• The change in potential when player $i$ switches from strategy $s_i$ to $s'i$ is $\Phi(s'i, s{-i}) - \Phi(s_i, s{-i}) = \sum_{e \in s'i \setminus s_i} c_e(x_e + 1) - \sum{e \in s_i \setminus s'_i} c_e(x_e)$
• The change in utility for player $i$ is $u_i(s'i, s{-i}) - u_i(s_i, s_{-i}) = -\sum_{e \in s'i \setminus s_i} c_e(x_e + 1) + \sum{e \in s_i \setminus s'_i} c_e(x_e)$
• $\Phi(s'i, s{-i}) - \Phi(s_i, s_{-i}) = - (u_i(s'i, s{-i}) - u_i(s_i, s_{-i}))$.

Existence of PNE for Max Cut Game

• Definition: Undirected graph $G = (V, E)$. Each player $i \in V$ chooses a side $s_i \in {0, 1}$.
• $u_i(s) =$ number of neighbors $j$ such that $s_i \neq s_j$.
• $\Phi(s) =$ number of edges crossing the cut.
• The change in utility is equal to the change in the number of edges crossing the cut.

General Existence Result

• A game $G$ has a PNE if every sequence of best response moves is finite.
• If a sequence of best response moves is finite, it must end at a state $s^*$, which is a PNE.
• If any player could improve by switching, the sequence wouldn't end.
• If G is a finite game (finite players and strategies) and has the finite improvement property, G has a PNE.
• The finite improvement property (FIP) means any sequence of improving moves is finite.

Computing Pure Nash Equilibrium (PNE)

• Potential Function Maximization: If a game is a potential game, compute a PNE by maximizing the potential function, though this can be computationally hard.
• Best-Response Dynamics: Start with an arbitrary state and let players take turns playing best-response strategies. If the game has the finite improvement property, this converges to a PNE.

Regret

• The regret of player $i$ in round $t$ is the difference between the utility player $i$ received and the utility player $i$ would have received if they had played the best strategy in hindsight.
• $\operatorname{Regret}^t_i = \max_{s_i \in S_i} \sum_{\tau=1}^t u_i(s_i, s_{-i}(\tau)) - \sum_{\tau=1}^t u_i(s_i(\tau), s_{-i}(\tau))$

No-Regret Dynamics

• A strategy update rule that guarantees that the average regret goes to zero as $t \rightarrow \infty$: $\lim_{T \rightarrow \infty} \frac{1}{T} \operatorname{Regret}^T_i \leq 0$

Coarse Correlated Equilibrium

• A probability distribution $p$ over joint strategy spaces is a coarse correlated equilibrium if for every player $i$ and every strategy $s_i \in S_i$: $\mathbb{E}{s \sim p}[u_i(s)] \geq \mathbb{E}{s \sim p}[u_i(s'i, s{-i})]$
• No player has an incentive to deviate to a single fixed strategy ex ante, given the distribution $p$.

Complex Numbers

• A complex number is in the form $a + bi$
  • $a$ and $b$ are real numbers.
  • $i$ is the imaginary unit ($i^2 = -1$).
  • $\Re(z) = a$ is the real part.
  • $\Im(z) = b$ is the imaginary part.

Complex Arithmetic

• For $z_1 = a + bi$ and $z_2 = c + di$:
  • Addition: $z_1 + z_2 = (a + c) + (b + d)i$
  • Subtraction: $z_1 - z_2 = (a - c) + (b - d)i$
  • Multiplication: $z_1 * z_2 = (ac - bd) + (ad + bc)i$
  • Division: $\frac{z_1}{z_2} = \frac{ac + bd}{c^2 + d^2} + \frac{bc - ad}{c^2 + d^2}i$

Complex Conjugate

• The complex conjugate of $z = a + bi$ is $\overline{z} = a - bi$.
  • $\Re(z) = \frac{z + \overline{z}}{2}$
  • $\Im(z) = \frac{z - \overline{z}}{2i}$
  • $z\overline{z} = a^2 + b^2$

Modulus

• The modulus of $z = a + bi$ is the distance from the origin to $(a, b)$.
• $|z| = \sqrt{a^2 + b^2} = \sqrt{z\overline{z}}$

Argument

• The argument of $z = a + bi$ is the angle $\theta$ between the positive real axis and the line connecting the origin to $(a, b)$.
• $\theta = arg(z) = tan^{-1}(\frac{b}{a})$

Polar Form

• $z = a + bi$ can be $z = r(cos(\theta) + isin(\theta))$
  • $r = |z| = \sqrt{a^2 + b^2}$
  • $\theta = arg(z) = tan^{-1}(\frac{b}{a})$

Euler's Formula

• Connects complex exponentials with trigonometric functions:
  • $e^{i\theta} = cos(\theta) + isin(\theta)$
  • $z = re^{i\theta}$

De Moivre's Theorem

• For $z = r(cos(\theta) + isin(\theta))$ and integer $n$:
  • $z^n = r^n(cos(n\theta) + isin(n\theta))$
  • $(cos(\theta) + isin(\theta))^n = cos(n\theta) + isin(n\theta)$

Roots of Complex Numbers

• To find the nth roots of $z = r(cos(\theta) + isin(\theta))$:
  • $z_k = \sqrt[n]{r}[cos(\frac{\theta + 2\pi k}{n}) + isin(\frac{\theta + 2\pi k}{n})]$, where $k = 0, 1, 2,..., n - 1$