Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Before we begin we will introduce the notion of Price of Stability (PoS). Let NE to be the set of all the equilibrium states, and
Before we begin we will introduce the notion of Price of Stability (PoS). Let NE to be the set of all the equilibrium states, and sOPT to be the state with the optimal Social Cost (SC). Then, the Price of Stability is defined as PoS=minsNESC(sOPT)SC(s), i.e., the ratio between the smallest Social Cost at an equilibrium state, and the optimal Social Cost. Now, consider the following function ()=rRi=1#(r,)cr(i), where is a strategy profile (1,,n),rR is a resource, cr is the cost function of resource r and \# (r,) is the number of players using resource r in profile . This is a potential function and it is called Rosenthal's potential. Now consider a congestion game for which we have the following guarantee: The cost functions cr are such that no resource is ever used by more than players. Use Rosenthal's potential to show that the Price of Stability of such a game is at most . Hint: Try to use the observation that by starting from a state that produces the optimal social cost, in case this state is not a Nash equilibrium, then there is at least one player that by deviating can decrease the potential function
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started