|
The price of anarchy of finite congestion games Kapelushnik Lior
|
tarix | 20.05.2018 | ölçüsü | 485 b. | | #50880 |
|
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 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 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
Asymmetric case - Unweighted requests
- pure strategy
- Mixed strategy
- Weighted requests
Symmetric case
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
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
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
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ş: |
|
|