In an anti$-$coordination game we are given a connected $($undi$-$

rected$)$ graph $G=(N,E)$ with $n$:$=|N|2$ nodes and a non$-$negative weight

$w_{e}0$ for every edge einE. Each node iinN corresponds to a player who has to

choose between two colors, say red $($r$)$ and blue $($b$),$ i$.$e$.,$ the set of strategies of player

$i$ is $x_i=\{r,b\}.$ The goal of player $i$ is to choose a color $x_{i}in{x}_i$ such that the total

weight of edges to neighbors having a different color is maximized. More formally,

given a strategy profile xinx$={?}_{\text{i}\text{i}\text{n}[n]}{x}_i,$ the utility $u_i(x)$ of player $i$ is defined as

$u_i(x)={\displaystyle \underset{e=\{i)}{\overset{?}{}}},$jinE:$x_i{x}_j{w}_e$

Define the social welfare of a strategy profile $x$ as $SW(x)={\displaystyle \underset{\text{i}\text{i}\text{n}\text{N}}{\overset{?}{}}}{u}_i(x).$ Let $x^{*}$ denote a strategy profile of maximum social welfare.

$($a$)$ Consider the instance of an anti$-$coordination

game depicted on the right with $n=4$ play$-$

ers, where the edges are labeled with their re$-$

spective weights. Identify all pure Nash equi$-$

libria and determine the price of anarchy of

this instance.

$($b$)$ Prove that anti$-$coordination games have the finite improvement property.

$($c$)$ Derive a tight bound on the price of anarchy for anti$-$coordination games.