Problem $3(20$ points$).$ Consider the following scheduling game: We are given a set

of jobs $N=[n]$ that need to be processed on a set of machines $M=[m].$ Every job

jinN has a processing time $p_j>0,$ which defines the amount of time that $j$ needs to

be processed. A schedule $x=(x_1,$dots,$x_n)in{M}^n$ assigns each job jinN to a machine

$x_j$inM on which it is processed. The load $L_i(x)$ of a machine iinM with respect to a

given schedule $x$ is defined as the total processing time of all jobs that are assigned

to $i,$ i$.$e$.,$

$L_i(x)={\displaystyle \underset{\text{j}\text{i}\text{n}\text{N}\text{:}{x}_j=i}{\overset{?}{}}}{p}_j$

Here, the interpretation is that each job jinN corresponds to a player who chooses

a machine $x_j$inM to minimize their completion time. The completion time $C_j(x)$

of player jinN with respect to a given schedule $x$ is defined as the load of the

machine to which player $j$ is assigned, i$.$e$.,C_j(x)=L_i(x)$ with $i=x_j.$ We define the

social cost $SC(x)$ of a schedule $x$ as the maximum load of a machine, i$.$e$.,SC(x)=$

$ma{x}_{\text{i}\text{i}\text{n}\text{M}}{L}_i(x).$ A social optimum is a schedule that minimizes the social cost.

$($a$)$ Consider a scheduling game with $m=2$ machines and $n=4$ jobs. Let $p_1=$

$p_2=2$ and $p_3=p_4=1.$ Determine the price of anarchy of this instance.

$($b$)$ Generalize the example in $($a$)$ to show that for every $m2$ there is a schedul$-$

ing game whose price of anarchy is at least $2\frac{m}{m+1}.$

$($c$)$ Show that the price of anarchy for scheduling games is at most $2.($Hint: Prove

and exploit that for an optimal schedule $x^{*}$ we have

$SC(x^{*})$max$\{p_{\text{m}\text{a}\text{x}},\frac{1}{m}{\displaystyle \underset{\text{j}\text{i}\text{n}\text{N}}{\overset{?}{}}}{p}_j\}$

where $p_{\text{m}\text{a}\text{x}}$ denotes the maximum processing time of a job.$)$