## The price of anarchy of finite congestion games Kapelushnik Lior | |

tarix | 20.05.2018 |

ölçüsü | 485 b. |

## The price of anarchy of finite congestion games## Kapelushnik Lior## Based on the articles:## “The price of anarchy of finite congestion games”## by Christodoulou & Koutsoupias## “the price of routing unsplittable flow”## by Awerbuch, Azar & Epstein
## Agenda## Congestion games description## Price of anarchy definitions## Linear latency functions PoA upper and lower bounds## Polynomial latency functions PoA upper and lower bounds
## Network congestion game## A directed graph G=(V,E)## For each edge exists a latency function## n users, user j have request## Request j assigned to path which is the strategy of player j## Users are none cooperative
## Network game example## Network game example agent paths (strategies)## Network congestion game## Consider a strategy profile## Denote Ne(A) as the load on e in A## Mark as the possible paths for user i## Player j cost is the total cost of it’s strategy path## Strategy A is a NE if no player has reason to deviate from his strategy
## Congestion game## More generalized than a network congestion game## N players, a set of facilities E## Each player i has a strategy chosen from several sets of facilities## Facility j have cost (latency) function
## Congestion game definitions## Symmetric game (single-commodity) – all players choose from the same strategies## Asymmetric game (multi-commodity) – different players may have different strategy options## Mixed strategy for player i – a probability distribution over
## Congestion game example## Congestion game example## Congestion game example## Congestion game example## Congestion games## Every network congestion game is a congestion game## Each edge will be represented by a facility## Each strategy path of a player will be replaced by the set of edges in the path
## Network to congestion game## Social cost## Two possible definitions## Definition 1:## Definition 2:## or for weighted requests## When considering PoA the social cost definition of sum is equivalent to average (just divide by n)
## Price of anarchy## The worst-case ratio between the social cost of a NE and the optimal social cost## Definition 1:## Definition 2:
## Linear latency function## If an equivalent problem can be described with function## Duplicate an edge times
## Avg. social cost PoA## Asymmetric case- Unweighted requests
- pure strategy
- Mixed strategy
- Weighted requests
- Pure + mixed strategies
## Symmetric case- Unweighed pure strategy
## Upper PoA bounds## Sketch of proof## Compare agent’s delay to the delay that would be encountered at the optimal path## Combine the bounds and transform to a relation between a total NE delay and the total optimal delay
## Upper bound unweighted requests, fe(x)=x## Lemma:## for a pair of nonnegative integers a,b
## Upper bound unweighted requests, fe(x)=x## In a NE A and an optimal P allocation## The inequality holds since moving from a NE does not decrease the cost## Summing for all players we get
## Upper bound unweighted requests, fe(x)=x cont’## Using the lemma we get## And thus## And the upper bound is proven
## Upper bound weighted requests## Notations:- J(e) – set of agents using e
- P – NE strategies profile
- Qj – request j path in P
- X* - value X in optimal state
- l – load vector of a system
## Upper bound weighted requests## Lemma 1: (follows from Cauchy-Schwartz inequality)## Lemma 2: for any
## Upper bound weighted requests## Upper bound weighted requests## Upper bound weighted requests## Lower bounds, unweighted requests, congestion game## Assume N≥3 agents, 2N facilities fe(x)=x## Facilities## Agent i strategies## Optimal allocation: each agent i chooses## Worst NE agent i choose## The cost for each agent is 2 in the optimal allocation and 5 in the NE, PoA is 5/2
## Lower bounds, unweighted requests, network game## Lower bounds, weighted requests, network game## Lower bounds, weighted requests, network game## Lower bounds, weighted requests, network game## Linear congestion symmetric games lower bound of PoA## The upper bound for asymmetric games with avg. social cost also holds for symmetric games## The lower bound both max and avg. social cost is (5N-2)/(2N+1)## Next is a game description which achieves this PoA for N players
## Lower bound game construction for symmetric games## The facilities will be in N sets of the same size P1,P2,…,Pn## Each Pi is a pure strategy and in optimal allocation each player i plays Pi## Each Pi contains facilities## At NE player i plays alone facilites of each Pj## At NE each pair of players play together facilities of each Pj
## Lower bound game construction for symmetric games cont’## At NE A,## We want that at NE no players will switch to Pj## For NE we need## Which proves the PoA of (5N-2)/(2N+1)
## Max social cost PoA## Unweighted pure strategy cases only## Symmetric case- Lower bound already shown
## Asymmetric case
## Asymmetric case upper bound## Let A be a NE, P optimal allocation, w.l.o.g Max(A)=c1(A), the NE imply## Denote the players in A that use facilities of P1## The avg. social cost lower bound showed
## Asymmetric case upper bound## Combining the last 2 inequalities## substitute in the first inequality
## Asymmetric case lower bound## Symmetric case upper bound## Let A be a NE, P optimal allocation, w.l.o.g Max(A)=c1(A), the NE imply## Summing for all possible j in P and using the lemma## Using the avg. social cost lower bound
## Polynomial latency function## The latency functions are polynomials of bounded degree p## The proofs for PoA of linear latency functions are quite similar to those of polynomial latencies
## Polynomial latencies cost PoA## For polynomials of degree p, nonnegative coefficients## Avg. social cost## weighted requests, unweighted requests, symmetric games, asymmetric games, pure strategies, mixed strategies## Max social cost- Pure strateties symmetric games
- Pure strateties asymmetric games
## Upper bound unweighted requests polynomial latencies## Instead of the lemma for linear functions## for a pair of nonnegative integers a,b## A new lemma is used, if f(x) polynomial in x with nonnegative coefficients, of degree p, for nonegative x and y## Where
## Upper bound unweighted requests polynomial latencies cont’## In a NE A and an optimal P allocation## The inequality holds since moving from a NE does not decrease the cost## Summing for all players we get
## Upper bound unweighted requests polynomial latencies cont’## Using the lemma we get## And thus## And the upper bound is proven
## Lower bound game construction for symmetric games## The facilities will be in N sets of the same size P1,P2,…,Pn## Each Pi is a pure strategy and in optimal allocation each player i plays Pi## Each Pj contains N facilities## At NE player i plays
## Lower bound game construction for symmetric games cont’## At NE A,## We want that at NE no players will switch to Pj## For NE we need to select N such that## For opt## The PoA is## Which proves the PoA of when choosing N that satisfies the equation
## Asymmetric case lower bound almost like in the linear case## Dostları ilə paylaş:©2018 Учебные документы Рады что Вы стали частью нашего образовательного сообщества. |
? |