Price of Stability - Assignment

Game Theory
Problem 2
Problem (a)
Price of stability (Pos) of a game is the ratio between the best values of the
objective function to the outcome of the optimal value.
PoS= value of best Nash equilibrium
value of optimal solution ,PoS ≥ 0
You are given a directed weight social network, that is G=(N,E)
Given E to be the resource value on the edge set of a graph with a directed
network.
An agent i ,an element of the total population of the sample N, has a source 0i∈N
and a destination.
Consider a game where;
 n is the number of agents
 Every agent aims to network Si to Sj on the graph G=(N,E)
 Some strategies are laid down such that an agent Pi constitutes a
combination of paths from Si to Sj in G.
 Ci, is the cost of each edge
There is an average cost allocation, when ne agents are to make a choice of
a path hence the cost dk(nk)= Ce
ne is divided equally among the students.
The total Cost of agents is Ci(s)= ∑
e ∈ Pi
Ce
ne
But the social cost of a strategy profile s is the weighted sum of costs;
SC(S)=∑
i
Ci ( s )=∑
e ∈S
ne Ce
ne = ∑
e ∈S
Ce
But OPT(G)=minSƹsC(S) is the optimum strategy profiles cost given by s ∈S
Therefore,
The Price Stability (PoS) of G is equal to the social cost of the best Nash equilibrium
from the optimal cost.
PoS(G)=minSɛne(G) Es ∂ ¿ ¿

As a result,the price stability is well defined.
PoS for a class G of games can be concluded to be the worst case, that is, the
maximum of the class.
PoS(G)=SupGƸǤPoS(G)
Problem b
Consider the potential function φ==∑
e
∑
i=1
ne ck
i
Supposing that there are only two constants,(N and E) in existence, then for each
strategy S,
N.SC(S)≤ φ ( S ) ≤ E . SC ( S )
Hence the price of stability less N
E
Proof
NE of φ is a Nash equilibrium,
Hence;
SC(NE)≤ 1
N . φ ( NE ) ≤ 1
N . φ (OPT ) ≤ E
N . SC ( OPT )
But,R
Social cost is equal to sum of costs over the paths.
As a result,
φ (S)=∑
e ∈s
∑
i=1
ne ce
i = ∑
e ∈S
CeHne ≤ ∑
e∈ S
CeHn=Hn . SC ( S )
¿ ¿
Trivially, we have,N=1 and this computes to E=Hn.Hence a tight bound.
Problem c
(i)
Price of Anarchy-is the worst possible ratio of the total latency of a Nash equilibrium
and the optimal fixation of the utility.
You are given students from two families=BUG.