Load Balancing Games: Identical Machines

Remainder of the Braess Paradox

Load Balancing Games

• Focus on scenarios where multiple players aim to distribute load to minimize their individual costs.

Identical Machines

• Deals with load balancing across machines with equal capabilities.

Theorem 1

• Price of Anarchy (PoA) for load balancing games with identical machines is at most 2.

Proof

• MAKESPAN objective: $MS(s) = max_{i \in [m]} L_i(s)$, where $L_i(s)$ is the load on machine $i$.
• $s$: equilibrium state; $s^*$: social optimum state.
• Job $j$: last job scheduled on the machine defining makespan in equilibrium $s$.
• $MS(s) = L_{i(j)}(s) = l_j + \sum_{k \neq j: s_k = i(j)} l_k$, where $i(j)$ is the machine job $j$ is scheduled on.
• Job $j$ prefers machine $i(j)$ over any other machine in equilibrium $s$.
• $l_j + \sum_{k \neq j: s_k = i(j)} l_k \leq l_j + L_{i(j)}(s^*)$
• Summing over all jobs: $\sum_i L_i(s^*) = \sum_j l_j$
• In optimum, there exists a machine $i$ with $L_i(s^*) \leq \frac{\sum_j l_j}{m}$
• $MS(s) \leq l_j + L_{i(j)}(s^) \leq MS(s^) + \frac{\sum_j l_j}{m}$
• $MS(s) \leq 2MS(s^)$, since $MS(s^) \geq \frac{\sum_j l_j}{m}$

Theorem 2

• A bound of 2 for identical machines is tight and cannot be improved.

Proof

• Specific Example:
• $m$ machines
• $m^2$ jobs of size 1
• 1 job of size $m$
• Social Optimum: Job of size $m$ on one machine, $m$ jobs of size 1 on each of the others, makespan is $m$.
• Equilibrium: Job of size $m$ on one machine, $m-1$ machines have $m$ jobs of size 1, one machine has $m$ jobs of size 1 and job of size $m$, makespan is $2m - 1$.
• As $m$ approaches infinity, the ratio of equilibrium makespan to social optimum makespan approaches 2.

Related Machines

• Considers machines with different processing speeds.
• Machine $i$ has speed $v_i$, and $v_1 \geq v_2 \geq... \geq v_m$.
• The cost to job $j$ if scheduled on machine $i$ is $l_j/v_i$.

Theorem 3

• PoA for load balancing games with related machines is unbounded.

Proof

• Illustrative Example:
• 2 machines
• $v_1 = 1, v_2 = \epsilon$
• 1 job of size 1
• Social Optimum: Schedule job on machine 1, makespan is 1.
• Equilibrium: Schedule job on machine 2, makespan is $1/\epsilon$.
• As $\epsilon$ approaches 0, the ratio of equilibrium makespan to social optimum makespan approaches infinity.

Selfish Routing

• Focuses on network traffic routing, where each player aims to minimize their path cost.

The Model

• A network has $n$ players routing from a source $s_i$ to a target $t_i$.
• Player $i$ routes $r_i$ units of flow.
• Each edge $e$ has a cost function $c_e(x)$, depending on the amount of traffic $x$.
• Player $i$'s cost: sum of edge costs on their path.
• Social cost: sum of costs for all players.
• Assumed cost functions are non-decreasing.

Wardrop Equilibrium

• $f_e$ is flow on edge $e$.
• A Wardrop equilibrium is such that for every $s_i-t_i$ pair, all flow travels on paths with minimum cost.
• All flow travels on shortest paths.

Proposition 4

• Wardrop equilibrium is a Nash equilibrium.

Proof

• Changing to a path with lower cost improves cost for some player, high cost flow would move to low cost path until costs are equal.

Fact 5

• A Wardrop equilibrium exists for any network setup.

The Price of Anarchy

• Focuses on the efficiency loss due to selfish routing.

Definition 6

• Social cost of flow $f$: $C(f) = \sum_{e \in E} f_e c_e(f_e)$

Definition 7

• Price of anarchy (PoA) is the ratio of the worst-case Nash equilibrium social cost to the social optimum social cost: $PoA = \frac{C(f)}{min_g C(g)}$ where $f$ is Wardrop equilibrium, $g$ is the optimal flow.

Exercices d'Algèbre Linéaire

Exercice 1

• Given matrix $A = \begin{bmatrix} 1 & 2 \ 2 & 1 \end{bmatrix} \in M_2(\mathbb{R})$.

1. Determine the eigenvalues of A.
2. Determine a base of eigenvectors of A.
3. Determine if A is diagonalizable. If so, provide an invertible matrix P and a diagonal matrix D such that $A = PDP^{-1}$.

Exercice 2

• Given matrix $A = \begin{bmatrix} 1 & -1 & 0 \ 0 & 1 & -1 \ 0 & 0 & 1 \end{bmatrix} \in M_3(\mathbb{R})$.

1. Determine the eigenvalues of A.
2. Determine a base of eigenvectors of A.
3. Determine if A is diagonalizable.

Exercice 3

• Given $f \in \mathcal{L}(\mathbb{R}^3)$ with the matrix in the standard basis as $A = \begin{bmatrix} 5 & -3 & 2 \ 6 & -4 & 4 \ 4 & -4 & 5 \end{bmatrix}$.

1. Determine the eigenvalues of A.
2. Determine a base of eigenvectors of A.
3. Determine if A is diagonalizable. If so, provide a base that turns the matrix for f into diagonal form.

Exercice 4

• Given matrices: $A = \begin{bmatrix} 1 & 2 & -1 \ 1 & 0 & 1 \ 1 & 2 & -1 \end{bmatrix}$, $B = \begin{bmatrix} 1 & 2 & 3 \ 0 & 1 & 2 \ 0 & 0 & 1 \end{bmatrix}$, $C = \begin{bmatrix} 1 & 3 & 1 \ 0 & 1 & 2 \ 0 & 0 & 2 \end{bmatrix}$

1. Calculate the characteristic polynomial for each matrix.
2. Calculate the eigenvalues for each matrix.
3. Determine if the matrices are diagonalizable.