1,722,419 research outputs found
On stackelberg strategies in affine congestion games
No full textWe investigate the efficiency of some Stackelberg strategies in congestion games with affine latency functions. A Stackelberg strategy is an algorithm that chooses a subset of players and assigns them a prescribed strategy with the purpose of mitigating the detrimental effect that the selfish behavior of the remaining uncoordinated players may cause to the overall performance of the system. The efficiency of a Stackelberg strategy is measured in terms of the price of anarchy of the pure Nash equilibria they induce. Three Stackelberg strategies, namely Largest Latency First, Cover and Scale, were already considered in the literature and non-tight upper and lower bounds on their price of anarchy were given. We reconsider these strategies and provide the exact bound on the price of anarchy of both Largest Latency First and Cover and a better upper bound on the price of anarchy of Scale
The price of anarchy of affine congestion games with similar strategies
No full textAffine congestion games are a well-studied model for selfish behavior in distributed systems, such as transportation and communication networks. Seminal influential papers in Algorithmic Game Theory have bounded the worst-case inefficiency of Nash equilibria, termed as price of anarchy, in several variants of these games. In this work, we investigate to what extent these bounds depend on the similarities among the players' strategies. Our notion of similarity is modeled by assuming that, given a parameter θ ≥ 1, the costs of any two strategies available to a same player, when evaluated in absence of congestion, are within a factor θ one from the other. It turns out that, for the non-atomic case, better bounds can always be obtained for any finite value of θ. For the atomic case, instead, θ < 3/2 and θ < 2 are necessary and sufficient conditions to obtain better bounds in games played on general graph topologies and on parallel link graphs, respectively. It is worth noticing that small values of θ model the behavioral attitude of players who are partially oblivious to congestion and are not willing to significantly deviate from what is their best strategy in absence of congestion
Congestion Games with Priority-Based Scheduling
No full textWe reconsider atomic and non-atomic affine congestion games under the assumption that players are partitioned into p priority classes and resources schedule their users according to a priority-based policy, breaking ties uniformly at random. We derive tight bounds on both the price of anarchy and the price of stability as a function of p, revealing an interesting separation between the general case of and the priority-free scenario of. In fact, while non-atomic games are more efficient than atomic ones in absence of priorities, they share the same price of anarchy when. Moreover, while the price of stability is lower than the price of anarchy in atomic games with no priorities, the two metrics become equal when. Our results hold even under singleton strategies. Besides being of independent interest, priority-based scheduling shares tight connections with online load balancing and finds a natural application within the theory of coordination mechanisms and cost-sharing policies for congestion games. Under this perspective, a number of possible research directions also arises
Selected papers of ICTCS 2016 (The Italian Conference on Theoretical Computer Science (ICTCS)
No full textOn the stackelberg fuel pricing problem
No full textWe consider the Stackelberg fuel pricing problem in which a company has to decide the fuel selling price at each of its gas stations in order to maximize its revenue, assuming that the selling prices of the competitors and the customers' preferences are known in advance. We show that, even in the basic case in which the road network is modeled by an undirected planar graph and the competitors discriminate on two different selling prices only, the problem is APX-hard. On the positive side, we design a polynomial time algorithm for instances in which the number of gas stations owned by the company is constant, while, in the general case, we show that the single-price algorithm (which provides the best-known solutions for essentially all the Stackelberg pricing problems studied in the literature up to date) achieves an approximation ratio which is logarithmic in some parameters of the input instance. This result, in particular, is tight and holds for a much more general class of Stackelberg network pricing problems
On the impact of singleton strategies in congestion games
No full textTo what extent does the structure of the players' strategy space influence the efficiency of decentralized solutions in congestion gamesε In this work, we investigate whether better performance is possible when restricting to load balancing games in which players can only choose among single resources. We consider three different solutions concepts, namely, approximate pure Nash equilibria, approximate one-round walks generated by selfish players aiming at minimizing their personal cost and approximate one-round walks generated by cooperative players aiming at minimizing the marginal increase in the sum of the players' personal costs. The last two concepts can also be interpreted as solutions of simple greedy online algorithms for the related resource selection problem. Under fairly general latency functions on the resources, we show that, for all three types of solutions, better bounds cannot be achieved if players are either weighted or asymmetric. On the positive side, we prove that, under mild assumptions on the latency functions, improvements on the performance of approximate pure Nash equilibria are possible for load balancing games with weighted and symmetric players in the case of identical resources. We also design lower bounds on the performance of one-round walks in load balancing games with unweighted players and identical resources (in this case, solutions generated by selfish and cooperative players coincide)
- …
