1,721,262 research outputs found
Non-atomic one-round walks in congestion games
No full textIn this paper we study the approximation ratio of the solutions achieved after an ε-approximate one-round walk in non-atomic congestion games. Prior to this work, the solution concept of one-round walks had been studied for atomic congestion games with linear latency functions only (Christodoulou et al. [1], Bilò et al. [2]). We give an explicit formula to determine the approximation ratio for non-atomic congestion games having general latency functions. In particular, we focus on polynomial latency functions, and, we prove that the approximation ratio is exactly ((1+ε)(p+1))p+1 for every polynomial of degree p. Then, we show that, by resorting to static (resp. dynamic) resource taxation, the approximation ratio can be lowered to (1+ε)p+1(p+1)p (resp. (1+ε)p+1(p+1)!)
Analisi delle murature storiche di Caltabellotta
No full textL’architettura storica di pregio, ed ancor più l’edilizia di base dei piccoli centri montani - caratterizzati da un isolamento che spesso rendeva difficoltoso non solo lo spostamento delle maestranze ma anche l’approvvigionamento di materie prime per la costruzione – sono generalmente connotate da specificità derivanti dalla disponibilità in situ di risorse e da consuetudini non codificate che trovano raramente riscontro puntuale nelle “regole dell’arte” riportate nella manualistica e nella trattatistica “ufficiale”.
Rappresentativo in tal senso è il caso di Caltabellotta; l’antico borgo sulla valle del Platani – che domina tre colli, il Monte San Pellegrino, il Monte Castello e il Monte Gogàla - si caratterizza da sempre per la sua posizione strategica che ha reso il centro protagonista della gestione del territori
On the impact of singleton strategies in congestion games (extended abstract)
No full textTo what extent the structure of the players' strategic space inuences the efficiency of decentralized solutions in congestion games? In this work, we investigate whether better performance are possible when restricting to load balancing games in which players can only choose among single resources. We consider three difierent 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)
On 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
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
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)
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
Enhancing the Efficiency of Altruism and Taxes in Affine Congestion Games through Signalling
No full textWe address the problem of improving the worst-case efficiency of pure Nash equilibria (aka, the price of anarchy) in affine congestion games, through a novel use of signalling. We assume that, for each player in the game, a most preferred strategy is publicly signalled. This can be done either distributedly by the players themselves, or be the outcome of some centralized algorithm. We apply this signalling scheme to two well-studied scenarios: games with partially altruistic players and games with resource taxation. We show a significant improvement in the price of anarchy of these games, whenever the aggregate signalled strategy profile is a good approximation of the game social optimum
Dynamic taxes for polynomial congestion games
No full textWe consider the efficiency of taxation in congestion games with polynomial latency functions along the line of research initiated by [Caragiannis et al., ACM Transactions on Algorithms, 2010] who focused on both pure and mixed Nash equilibria in games with affine latencies only. By exploiting the primal-dual method [Bilò, Proceedings of the 10th Workshop on Approximation and Online Algorithms, 2012], we obtain interesting upper bounds with respect to a variety of different solution concepts ranging from approximate pure Nash equilibria up to approximate coarse correlated equilibria, and including also approximate one-round walks starting from the empty state. Our findings show a high beneficial effect of taxation which increases more than linearly with the degree of the latency functions. In some cases, a tight relationship with some well-studied polynomials in Combinatorics and Number Theory, such as the Touchard and the Geometric polynomials, arises. In these cases we can also show matching lower bounds, albeit under mild assumptions; interestingly, our upper bounds are derived by exploiting the combinatorial definition of these polynomials, while our lower bounds are constructed by relying on their analytical characterization
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
- …
