Search

We provide a unifying, black-box tool for establishing existence of approximate equilibria in weighted congestion games and, at the same time, bounding their Price of Stability. Our framework can handle resources with general costs—including, in particular, decreasing ones—and is formulated in terms of a set of parameters which are determined via elementary analytic properties of the cost functions. We demonstrate the power of our tool by applying it to recover the recent result of Caragiannis and Fanelli [ICALP'19] for polynomial congestion games; improve upon the bounds for fair cost sharing games by Chen and Roughgarden [Theory Comput. Syst., 2009]; and derive new bounds for nondecreasing concave costs. An interesting feature of our framework is that it can be readily applied to mixtures of different families of cost functions; for example, we provide bounds for games whose resources are conical combinations of polynomial and concave costs. In the core of our analysis lies the use of a unifying approximate potential function which is simple and general enough to be applicable to arbitrary congestion games, but at the same time powerful enough to produce state-of-the-art bounds across a range of different cost functions. [ABSTRACT FROM AUTHOR]

We consider a strategic game, called project game, where each agent has to choose a project among her own list of available projects. The model includes positive weights expressing the capacity of a given agent to contribute to a given project. The realization of a project produces some reward that has to be allocated to the agents. The reward of a realized project is fully allocated to its contributors according to a simple proportional rule. Existence and computational complexity of pure Nash equilibria is addressed and their efficiency is investigated according to both the utilitarian and the egalitarian social function. [ABSTRACT FROM AUTHOR]

We introduce the class of modified Schelling games in which there are different types of agents who occupy the nodes of a location graph; agents of the same type are friends, and agents of different types are enemies. Every agent is strategic and jumps to empty nodes of the graph aiming to maximize her utility, defined as the ratio of her friends in her neighborhood over the neighborhood size including herself. This is in contrast to the related literature on Schelling games which typically assumes that an agent is excluded from her neighborhood whilst computing its size. Our model enables the utility function to capture likely cases where agents would rather be around a lot of friends instead of just a few, an aspect that was partially ignored in previous work. We provide a thorough analysis of the (in)efficiency of equilibria that arise in such modified Schelling games, by bounding the price of anarchy and price of stability for both general graphs and interesting special cases. Most of our results are tight and exploit the structure of equilibria as well as sophisticated constructions. [ABSTRACT FROM AUTHOR]

We consider weighted congestion games with polynomial latency functions of maximum degree d ≥ 1. For these games, we investigate the existence and efficiency of approximate pure Nash equilibria which are obtained through sequences of unilateral improvement moves by the players. By exploiting a simple technique, we firstly show that these games admit an infinite set of d -approximate potential functions. This implies that there always exists a d -approximate pure Nash equilibrium which can be reached through any sequence of d -approximate improvement moves by the players. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, these games also admit a constant approximate potential function. Secondly, using a simple potential function argument, we are able to show that a (d + δ) -approximate pure Nash equilibrium of cost at most (d + 1) / (d + δ) times the cost of an optimal state always exists, for every δ ∈ [ 0 , 1 ]. [ABSTRACT FROM AUTHOR]

We consider graph-based hedonic games such as simple symmetric fractional hedonic games and social distance games, where a group of utility maximizing players have hedonic preferences over the players' set, and wish to be partitioned into clusters so that they are grouped together with players they prefer. The players are nodes in a connected graph and their preferences are defined so that shorter graph distance implies higher preference. We are interested in Nash equilibria of such games, where no player has an incentive to unilaterally deviate to another cluster, and we focus on the notion of the price of stability. We present new and improved bounds on the price of stability for several graph classes, as well as for a slightly modified utility function. [ABSTRACT FROM AUTHOR]

A treasure is placed in one of M boxes according to a known distribution and k searchers are searching for it in parallel during T rounds. How can one incentivize selfish players so that the probability that at least one player finds the treasure is maximized? We focus on congestion policies C (ℓ) specifying the reward a player receives being one of the ℓ players that (simultaneously) find the treasure first. We prove that the exclusive policy , in which C (1) = 1 and C (ℓ) = 0 for ℓ > 1 , yields a price of anarchy of (1 − (1 − 1 / k) k) − 1 , which is the best among all symmetric reward policies. We advocate the use of symmetric equilibria, and show that besides being fair, they are highly robust to crashes of players. Indeed, in many cases, if some small fraction of players crash, symmetric equilibria remain efficient in terms of their group performance while also serving as approximate equilibria. [ABSTRACT FROM AUTHOR]

• We study a load balancing game with uncertainty imposed by a randomizing scheduler. • We provide nearly tight upper bounds on PoAs when players follow the win-or-go-home and minimum-expected-cost principles. • The bottom-out principle is studied for the first time in load balancing games. • Non-optimal prices of stabilities exhibit a sharp contrast with the classical load balancing games. We study the efficiency of Nash equilibria for the load balancing game with a randomizing scheduler. In the game, we are given a set of facilities and a set of players along with a scheduler, where each facility is associated with a linear cost function, and the players are randomly ordered by the scheduler. Each player chooses exactly one of these facilities to fulfill his task, which incurs to him a cost depending on not only the cost function of the facility he chooses and the players who choose the same facility (as in a usual load balancing game), but also his uncertain position in the uniform random ordering. From an individual perspective, each player tries to choose a facility for optimizing his own objective that is determined by a certain decision-making principle. From a system perspective, it is desirable to minimize the maximum cost among all players, which is a commonly used criterion for load balancing. We estimate the price of anarchy and price of stability for this class of load balancing games under uncertainty, provided all players follow one of the four decision-making principles, namely the bottom-out, win-or-go-home, minimum-expected-cost, and minimax-regret principles. Our results show that the efficiency loss of Nash equilibria in these decentralized environments heavily rely on player's attitude toward the uncertainty. [ABSTRACT FROM AUTHOR]

We consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node s and the cost of each communication link is equally shared among the downstream receivers according to the Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in Anshelevich et al. (2008). Our result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution T ⁎ , is able to restore local similarity by exploiting cost differences between nearby players in T ⁎. [ABSTRACT FROM AUTHOR]

When a group of Mobile Users (MUs) equipped with multi-mode or multi-home terminals, like passengers on board a bus or a train or a car, moves from one wireless network (WN) to another WN within a heterogeneous wireless network (HWN) environment, request vertical handoffs simultaneously, a group vertical handoff (GVHO) occurs. In literature, the prevailing research work is mainly concerned for forced GVHO with network aspects like signal strength and bandwidth etc. while in reality the user initiated GVHO with the user aspects like price, power consumption and velocity etc. along with their respective user preferences is more important for performing vertical handoffs in HWNs. In user initiated GVHO, selection of the mutually best WN-MU pair which can maximise network revenue of constituent WN as well as user satisfaction of MU in a group while minimising the simultaneous selection of a WN by multiple MU of the group is a challenging problem. This paper proposes a GVHO decision model based on non-cooperative game which utilizes multiple handoff decision attributes and their respective user preferences calculated dynamically on real-time basis as the game strategies to select the best available WNs by group MUs at NASH equilibrium for vertical handoffs. The performance of the proposed model is evaluated in terms of number of GVHOs, price of anarchy and price of stability for both group of MUs and WNs. The simulation results show that the proposed model results in minimum number of GVHOs as compared to existing GVHO models and maximisation of user satisfaction and network revenue. [ABSTRACT FROM AUTHOR]

We consider a project scheduling environment in which the activities are partitioned among a set of agents. The owner of each activity can decide its length, which is linearly related to its cost within a minimum (crash) and a maximum (normal) length. For each day the project makespan is reduced with respect to its normal value, a reward is offered to the agents, and each agent receives a given ratio of the reward. As in classical game theory, we assume that the agents' parameters are common knowledge. We study the Nash equilibria of the corresponding non-cooperative game as a desired state where no agent is motivated to change his/her decision. Regarding project makespan as an overall measure of efficiency, here we consider the worst and the best Nash equilibria (i.e., for which makespan is maximum and, respectively, minimum among Nash equilibria). We show that the problem of finding the worst Nash equilibrium is NP-hard (finding the best Nash equilibrium is already known to be strongly NP-hard), and propose an ILP formulation for its computation. We then investigate the values of the price of anarchy and the price of stability in a large sample of realistic size problems and get useful insights for the project owner. [ABSTRACT FROM AUTHOR]

In a seminal paper, Chen, Roughgarden, and Valiant [SIAM J. Comput., 39 (5) (2010), pp. 1799-1832] studied cost sharing protocols for network design with the objective to implement a low-cost Steiner forest as a Nash equilibrium of an induced cost-sharing game. One of the most intriguing open problems to date is to understand the power of separable cost sharing protocols in order to induce low-cost Steiner forests. In this work, we focus on undirected networks and analyze topological properties of the underlying graph so that an optimal Steiner forest can be implemented as a Nash equilibrium (by some separable cost sharing protocol) independent of the edge costs. We term a graph efficient if the above stated property holds. As our main result, we give a complete characterization of efficient undirected graphs for two-player network design games: an undirected graph is efficient if and only if it does not contain (at least) one out of few forbidden subgraphs. Our characterization implies that several graph classes are efficient: generalized series-parallel graphs, fan and wheel graphs, and graphs with small cycles. [ABSTRACT FROM AUTHOR]

We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer d we construct rather simple games with cost functions of degree at most d which have a PoS of at least Ω (Φd)d+1, where Φd ~ d/ln d is the unique positive root of the equation xd+1 = (x + 1)d. This almost closes the huge gap between θ(d) and Φd+1d. Our bound extends also to network congestion games. We further show that the PoS remains exponential even for singleton games. More generally, we provide a lower bound of Ω ((1+1/α)d/d) on the PoS of α -approximate Nash equilibria for singleton games. All our lower bounds hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of α -approximate Nash equilibria, which is sensitive to the range W of the player weights and the approximation parameter α. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most (d+3)/2; the equilibrium's approximation parameter ranges from θ (1) to d+1 in a smooth way with respect to W. Second, we show that for unweighted congestion games, the PoS of α-approximate Nash equilibria is at most (d + 1)/α. [ABSTRACT FROM AUTHOR]

Abstract We introduce a new model of congestion games that captures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ ≥ 0 , while the system designer estimates that each player perceives the load of all others by an extent of σ ≥ 0. For specific choices of ρ and σ , we obtain extensions such as altruistic player behavior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should "design" the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ = 0.625 (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible. [ABSTRACT FROM AUTHOR]

Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable properties of a coordination mechanism includes simplicity in its definition and efficiency of the outcomes of the induced game. We present a broad class of coordination mechanisms for unrelated machine scheduling that are simple to define and we identify one of its members (mechanism DCOORD) that is superior to all known mechanisms. In particular, DCOORD induces potential games with logarithmic price of anarchy and only constant price of stability. Both bounds are almost optimal. [ABSTRACT FROM AUTHOR]

In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most Hn, the n-th harmonic number. This bound is tight for directed graphs.For undirected graphs, it has only recently been shown that the price of stability is at most Hn1-1Θ(n4), while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most Hn/2+ε for any ε starting from some suitable n≥n(ε).We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of 43 and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90-100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of 43, and provide an upper bound of 2619. To the end, we conjecture and argue that the right answer is 43. [ABSTRACT FROM AUTHOR]

Abstract We investigate opinion formation games with dynamic social influences, where opinion formation and social relationships co-evolve in a cross-influencing manner. We show that these games always admit an ordinal potential, and so, pure Nash equilibria, and we design a polynomial time algorithm for computing the set of all pure Nash equilibria and the set of all social optima of a given game. We also derive non-tight upper and lower bounds on the price of anarchy and stability which only depend on the players' stubbornness, that is, on the scaling factor used to counterbalance the cost that a player incurs for disagreeing with the society and the cost she incurs for breaking away from her innate beliefs. [ABSTRACT FROM AUTHOR]

We 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 p ≥ 2 and the priority-free scenario of p = 1. In fact, while in absence of priorities the worst-case prices of anarchy and stability of non-atomic games are lower than their counterparts in atomic ones, the two classes share the same bounds when p ≥ 2. Moreover, while the worst-case price of stability is lower than the worst-case price of anarchy in atomic games with no priorities, their values become equal when p ≥ 2. Said differently, the presence of priorities simultaneously irons out any combinatorial difference between atomic and non-atomic requests and among different pure Nash equilibria to produce a unique representative worst-case situation. Notably, our results keep holding 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 arise. [ABSTRACT FROM AUTHOR]

An active line of research has considered games played on networks in which payoffs depend on both a player's individual decision and the decisions of her neighbors. A basic question that has remained largely open is to consider games where the players' strategies come from a fixed, discrete set, and where players may have different preferences among the possible strategies. We develop a set of techniques for analyzing this class of games, which we refer to as discrete preference games . We parametrize the games by the relative extent to which a player takes into account the effect of her preferred strategy and the effect of her neighbors' strategies, allowing us to interpolate between network coordination games and unilateral decision-making. We focus on the efficiency of the best Nash equilibrium and provide conditions on when the optimal solution is also a Nash equilibrium. [ABSTRACT FROM AUTHOR]

We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k- equilibria respectively). We show that pure Nash equilibria and 2-equilibria exist, and give an example in which no 3-equilibrium exists. Moreover, we prove that strong equilibria exist for various special cases. We also study the price of anarchy (PoA) and price of stability (PoS) for these solution concepts. We show that the PoS for strong equilibria is 1 in almost all of the special cases for which we have proven strong equilibria to exist. The PoA for pure Nash equilbria turns out to be unbounded, even when we fix the graph on which the coordination game is to be played. For the PoA for k-equilibria, we show that the price of anarchy is between $$2(n-1)/(k-1) - 1$$ and $$2(n-1)/(k-1)$$ . The latter upper bound is tight for $$k=n$$ (i.e., strong equilibria). Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a k-equilibrium or strong equilibrium. We prove that, given a coordination game, a joint strategy s, and a number k as input, it is co-NP complete to determine whether s is a k-equilibrium. On the positive side, we give polynomial time algorithms to compute strong equilibria for various special cases. [ABSTRACT FROM AUTHOR]

We study the stable roommates problem in networks where players are embedded in a social context and may incorporate positive externalities into their decisions. Each player is a node in a social network and strives to form a good match with a neighboring player. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. We characterize prices of anarchy and stability, which capture the ratio of the total profit in the optimum matching over the total profit of the worst and best stable matching, respectively. When the benefit from a match (which we model by associating a reward with each edge) is the same for both players, we show that externalities can significantly improve the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the bound on the price of stability can be obtained in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different benefits from the match. For this more general case, we show that network externalities (i.e., 'caring about your friends') can make an even larger difference and greatly reduce the price of anarchy. We show a variety of existence results and present upper and lower bounds on the prices of anarchy and stability for various structures of matching benefits. All our results on stable matchings immediately extend to the more general case of fractional stable matchings. [ABSTRACT FROM AUTHOR]

We introduce a new class of games, called Network Movement Games , naturally related to the movement problems of [7] , which models the spontaneous creation of multi-hop communication networks by the distributed and uncoordinated movement of k selfish mobile devices placed on the nodes of an underlying graph. Devices are players aiming to find the final positions which achieve a global property of the induced subnetwork. We actually focus on solutions (i.e. Nash equilibria) connecting all the players while minimizing the distances from their home locations. We show that the game always admits a pure Nash equilibrium, and that the convergence after a finite number of improving moves is guaranteed only when players perform their best possible moves; in this case, we provide tight bounds on the speed of convergence to Nash equilibria, both when initial positions are arbitrary and when players start at their home positions. As for the Nash equilibria performances, we first prove that the price of stability is 1 (i.e., an optimal solution is also a Nash equilibrium). Furthermore, we provide tight bounds on the price of anarchy, also showing that better performances are obtained when players start at their home positions. Finally, through extensive experiments, we show that high bounds on the price of anarchy as well as high convergence time of best move dynamics to Nash equilibria are only due to pathological worst cases. Moreover, quite often improving move dynamics (i.e., where players do not necessarily perform a best possible move) converge to Nash equilibria on the tested instances even though the class of instances does not guarantee the convergence. [ABSTRACT FROM AUTHOR]

We study two scheduling games on parallel-batching machines with activation cost, where each game involves n jobs being processed on m parallel-batching identical machines. Each job, as an agent, selects a machine (more precisely, a batch on a machine) for processing to minimize his disutility. For the former game, on the basis of previous results, we find the conditions for the existence of Nash equilibrium, and present the parametric upper bounds of price of anarchy (PoA) and the price of stability (PoS) for the minimax and minisum objectives, and provide some mixed strategy Nash equilibria for two special cases. For the latter game, we first analyze the conditions for the nonexistence of Nash equilibrium, and provide tight approximate Nash equilibrium. Then, the conditions for the existence of Nash equilibrium are studied, and the constant-bounds of PoA and PoS for the minimax objective are given. [ABSTRACT FROM AUTHOR]

We study profit sharing games in which players select projects to participate in and share the reward resulting from that project equally. Unlike most existing work, in which it is assumed that the player utility is monotone in the number of participants working on their project, we consider non-monotone player utilities. Such utilities could result, for example, from 'threshold' or 'phase transition' effects, when the total benefit from a project improves slowly until the number of participants reaches some critical mass, then improves rapidly, and then slows again due to diminishing returns.Non-monotone player utilities result in a lot of instability: strong Nash equilibrium may no longer exist, and the quality of Nash equilibria may be far away from the centralized optimum. We show, however, that by adding additional requirements such as players needing permission to leave a project from the players currently on this project, or instead players needing permission to join a project from players on that project, we ensure that strong Nash equilibrium always exists. Moreover, just the addition of permission to leave already guarantees the existence of strong Nash equilibrium within a factor of 2 of the social optimum. In this paper, we provide results on the existence and quality of several different coalitional solution concepts, focusing especially on permission to leave and join projects, and show that such requirements result in the existence of good stable solutions even for the case when player utilities are non-monotone. [ABSTRACT FROM AUTHOR]

In this paper, we study the scheduling game with machine activation costs. A set of jobs is to be processed on parallel identical machines. The number of machines available is unlimited, and an activation cost is needed whenever a machine is activated in order to process jobs. Each job chooses a machine on which it wants to be processed. The cost of a job is the sum of the load of the machine it chooses and its shared activated cost. The social cost is the total cost of all jobs. Representing the Price of Anarchy (PoA) and Price of Stability (PoS) as functions of the number of jobs, we get the tight bounds of PoA and PoS. Representing PoA and PoS as functions of the smallest processing time of jobs, asymptotically tight bound of PoA and improved lower and upper bounds of PoS are also given. [ABSTRACT FROM AUTHOR]

We study a capacitated symmetric network design game, where each of n agents wishes to construct a path from a network's source to its sink, and the cost of each edge is shared equally among the agents using it. The uncapacitated version of this problem has been introduced by Anshelevich et al. () and has been extensively studied. We find that the consideration of edge capacities entails a significant effect on the quality of the obtained Nash equilibria (NE), under both the utilitarian and the egalitarian objective functions, as well as on the convergence rate to an equilibrium. The following results are established. First, we provide bounds for the price of anarchy (PoA) and the price of stability (PoS) measures with respect to the utilitarian (i.e., sum of costs) and egalitarian (i.e., maximum cost) objective functions. Our main result here is that unlike the uncapacitated version, the network topology is a crucial factor in the quality of NE. Specifically, a network topology has a bounded PoA if and only if it is series-parallel (SP), i.e., a network that is built inductively by series compositions and parallel compositions of SP networks. Second, we show that the convergence rate of best-response dynamics (BRD) may take Ω( n) steps. This is in contrast to the uncapacitated version, where convergence is guaranteed within at most n iterations. [ABSTRACT FROM AUTHOR]

In this paper, we investigate job scheduling games on uniform machines. Activating each machine incurs an activation cost in accordance with its speed. Jobs are self-decision-making players choosing machines with the objective of minimizing their own individual cost. Here, a job's individual cost is defined as the load of its chosen machine plus its activation cost, which is proportionally shared with respect to its size. We first propose an algorithm when there are m kinds of unlimited number of uniform machines, and it is proved to be a Nash Equilibrium (NE) algorithm by using the induction method. Because of equilibria always being far from optimal solutions, the inefficiency of pure NE is measured with the social objective of minimizing the maximum individual cost. Assuming that the longest job is α times as large as the unit activation cost, together with α ≥ a 2 , we obtain that both the Price of Anarchy (PoA) and Price of Stability (PoS) are equal to 1. Otherwise, they are bounded by ( α + 1 ) / 2 α . Finally, we provide an example to illustrate the tight bound. [ABSTRACT FROM AUTHOR]

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting network satisfies a given set of connectivity requirements and the cost of establishing the network links is as low as possible. The Minimum Spanning Tree problem, which is well-understood, is a nice example. In this paper, we consider the natural scenario in which the connectivity requirements are posed by selfish users who have agreed to share the cost of the network to be established according to a well-defined rule. The design proposed by the network designer should now be consistent not only with the connectivity requirements but also with the selfishness of the users. Essentially, the users are players in a so-called network design game and the network designer has to propose a design that is an equilibrium for this game. As it is usually the case when selfishness comes into play, such equilibria may be suboptimal. In this paper, we consider the following question: can the network designer enforce particular designs as equilibria or guarantee that efficient designs are consistent with users' selfishness by appropriately subsidizing some of the network links? In an attempt to understand this question, we formulate corresponding optimization problems and present positive and negative results. [ABSTRACT FROM AUTHOR]

In this article we show that the price of stability of Shapley network design games on undirected graphs with k players is at most k 3 ( k + 1 ) / 2 − k 2 1 + k 3 ( k + 1 ) / 2 − k 2 H k = ( 1 − Θ ( 1 / k 4 ) ) H k , where H k denotes the k -th harmonic number. This improves on the known upper bound of H k , which is also valid for directed graphs but for these, in contrast, is tight. Hence, we give the first non-trivial upper bound on the price of stability for undirected Shapley network design games that is valid for an arbitrary number of players. Our bound is proved by analyzing the price of stability restricted to Nash equilibria that minimize the potential function of the game. We also present a game with k = 3 players in which such a restricted price of stability is 1.634. This shows that the analysis of Bilò and Bove (2011) [3] is tight. In addition, we give an example for three players that improves the lower bound on the (unrestricted) price of stability to 1.571. [ABSTRACT FROM AUTHOR]

In this paper we study the network design game when the underlying network is a ring. In a network design game we have a set of players, each of them aims at connecting nodes in a network by installing links and equally sharing the cost of the installation with other users. The ring design game is the special case in which the potential links of the network form a ring. It is well known that in a ring design game the price of anarchy may be as large as the number of players. Our aim is to show that, despite the worst case, the ring design game always possesses good equilibria. In particular, we prove that the price of stability of the ring design game is at most 3/2, and such bound is tight. Moreover, we observe that the worst Nash equilibrium cannot cost more than 2 times the optimum if the price of stability is strictly larger than 1. We believe that our results might be useful for the analysis of more involved topologies of graphs, e.g., planar graphs. [ABSTRACT FROM AUTHOR]

We study asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of source-destination node-pairs over links with linear latencies. We show that there exists an optimal solution that is a 9-approximate Nash equilibrium, significantly improving the existing upper bound of 54 on the instability factor. We present fast implementation of the best response dynamics for computing a Nash equilibrium. Furthermore, we perform empirical study on the price of stability, narrowing the gap between the lower and upper bounds to 0.7436. [ABSTRACT FROM AUTHOR]

We consider a model of next-hop routing by self-interested agents. In this model, nodes in a graph (representing ISPs, Autonomous Systems, etc.) make pricing decisions of how much to charge for forwarding traffic from each of their upstream neighbors, and routing decisions of which downstream neighbors to forward traffic to (i.e., choosing the next hop). Traffic originates at a subset of these nodes that derive a utility when the traffic is routed to its destination node; the traffic demand is elastic and the utility derived from it can be different for different source nodes. Our next-hop routing and pricing model is in sharp contrast with the more common source routing and pricing models, in which the source of traffic determines the entire route from source to destination. For our model, we begin by showing sufficient conditions for prices to result in a Nash equilibrium, and in fact give an efficient algorithm to compute a Nash equilibrium which is as good as the centralized optimum, thus proving that the price of stability is 1. When only a single source node exists, then the price of anarchy is 1 as well, as long as some minor assumptions on player behavior is made. The above results hold for arbitrary convex pricing functions, but with the assumption that the utilities derived from getting traffic to its destination are linear. When utilities can be non-linear functions, we show that Nash equilibrium may not exist, even with simple discrete pricing models. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider undirected network design games with fair cost allocation. We introduce two concepts Potential-Optimal Price of Anarchy (POPoA) and Potential-Optimal Price of Stability (POPoS), where POPoA is the ratio between the worst cost of Nash equilibrium with optimal potential and the minimum social cost, and POPoS is the ratio between the best cost of Nash equilibrium with optimal potential and the minimum social cost, and show the following. [•] The POPoA and POPoS for undirected broadcast games with players are . [•] The POPoA and POPoS for undirected broadcast games with vertices are . [•] There exists an undirected broadcast game with players such that , . [•] There exists an undirected broadcast game with vertices such that . [Copyright &y& Elsevier]

We consider cut games where players want to cut themselves off from different parts of a network. These games arise when players want to secure themselves from areas of potential infection. For the game-theoretic version of Multiway Cut, we prove that the price of stability is 1, i.e., there exists a Nash equilibrium as good as the centralized optimum. For the game-theoretic version of Multicut, we show that there exists a 2-approximate equilibrium as good as the centralized optimum. We also give poly-time algorithms for finding exact and approximate equilibria in these games. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we address the selfish bin covering problem, which is greatly related both to the bin covering problem, and to the weighted majority game. What we are mainly concerned with is how much the lack of central coordination harms social welfare. Besides the standard PoA and PoS, which are based on Nash equilibrium, we also take into account the strong Nash equilibrium, and several new equilibrium concepts. For each equilibrium concept, the corresponding PoA and PoS are given, and the problems of computing an arbitrary equilibrium, as well as approximating the best one, are also considered. [Copyright &y& Elsevier]

We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it chooses, among its permissible servers, to run its job on the server having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness. We characterize almost completely the impact of selfishness and greediness in load balancing by presenting new and improved, tight or almost tight bounds on the price of anarchy of selfish load balancing as well as on the competitiveness of the greedy algorithm for online load balancing when the objective is to minimize the total latency of all clients on servers with linear latency functions. In addition, we prove a tight upper bound on the price of stability of linear congestion games. [ABSTRACT FROM AUTHOR]

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem. We then investigate the impact of the limited knowledge of the players on the performance of the game. More precisely, given a bound on the maximum degree of G, for the convergent cases we provide tight lower and upper bounds on the price of stability and asymptotically tight bounds on the price of anarchy. Such results are determined for four natural social cost functions: total and maximum presumed latencies, that is the ones the players believe to pay due to the fact that they are only aware of the existence of their neighbors, and total and maximum perceived latencies, i.e. actually experienced due to all (and not only the known) players using the same facilities. All the results are then extended to singleton congestion games. [ABSTRACT FROM AUTHOR]

Abstract: We consider a process called the Group Network Formation Game, which represents the scenario when strategic agents are building a network together. In our game, agents can have extremely varied connectivity requirements, and attempt to satisfy those requirements by purchasing links in the network. We show a variety of results about equilibrium properties in such games, including the fact that the price of stability is 1 when all nodes in the network are owned by players, and that doubling the number of players creates an equilibrium as good as the optimum centralized solution. For the general case, we show the existence of a 2-approximate Nash equilibrium that is as good as the centralized optimum solution, as well as how to compute good approximate equilibria in polynomial time. Our results essentially imply that for a variety of connectivity requirements, giving agents more freedom can paradoxically result in more efficient outcomes. [Copyright &y& Elsevier]

We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time $\widetilde{O}(n^{2}s^{\omega/2-1})$, where the input matrices have size n× n, the number of non-zero entries in the product matrix is at most s, ω is the exponent of the fast matrix multiplication and $\widetilde{O}(f(n))$ denotes O( f( n)log n) for some constant d. By the currently best bound on ω, its running time can be also expressed as $\widetilde{O}(n^{2}s^{0.188})$. Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n and it is never slower than the fast $\widetilde{O}(n^{\omega})$-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form $\widetilde{O}(n^{\omega(\frac{1}{2}\log_{n}s,1,1)})$, where ω( p, q, t) is the exponent of the fast multiplication of an n× n matrix by an n× n matrix. We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms. [ABSTRACT FROM AUTHOR]

We study the performance of approximate Nash equilibria for congestion games with polynomial latency functions. We consider how much the price of anarchy worsens and how much the price of stability improves as a function of the approximation factor ε. We give tight bounds for the price of anarchy of atomic and non-atomic congestion games and for the price of stability of non-atomic congestion games. For the price of stability of atomic congestion games we give non-tight bounds for linear latencies. Our results not only encompass and generalize the existing results of exact equilibria to ε-Nash equilibria, but they also provide a unified approach which reveals the common threads of the atomic and non-atomic price of anarchy results. By expanding the spectrum, we also cast the existing results in a new light. [ABSTRACT FROM AUTHOR]

In this paper we investigate the problem of partitioning an input string T in such a way that compressing individually its parts via a base-compressor C gets a compressed output that is shorter than applying C over the entire T at once. This problem was introduced in Buchsbaum et al. (Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, ; J. ACM 50(6):825-851, ) in the context of table compression, and then further elaborated and extended to strings and trees by Ferragina et al. (J. ACM 52:688-713, ; Proc. of 46th IEEE Symposium on Foundations of Computer Science, pp. 184-193, ) and Mäkinen and Navarro (Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, ). Unfortunately, the literature offers poor solutions: namely, we know either a cubic-time algorithm for computing the optimal partition based on dynamic programming (Buchsbaum et al. in J. ACM 50(6):825-851, ; Giancarlo and Sciortino in Proc. of 14th Symposium on Combinatorial Pattern Matching, pp. 129-143, ), or few heuristics that do not guarantee any bounds on the efficacy of their computed partition (Buchsbaum et al. in Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, ; J. ACM 50(6):825-851, ), or algorithms that are efficient but work in some specific scenarios (such as the Burrows-Wheeler Transform, see e.g. Ferragina et al. in J. ACM 52:688-713, ; Mäkinen and Navarro in Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, ) and achieve compression performance that might be worse than the optimal-partitioning by a Ω(log n/log log n) factor. Therefore, computing efficiently the optimal solution is still open (Buchsbaum and Giancarlo in Encyclopedia of Algorithms, pp. 939-942, ). In this paper we provide the first algorithm which computes in O( nlog n) time and O( n) space, a partition of T whose compressed output is guaranteed to be no more than (1+ ε)-worse the optimal one, where ε may be any positive constant fixed in advance. This result holds for any base-compressor C whose compression performance can be bounded in terms of the zero-th or the k-th order empirical entropy of the text T. We will also discuss extensions of our results to BWT-based compressors and to the compression booster of Ferragina et al. (J. ACM 52:688-713, ). [ABSTRACT FROM AUTHOR]

Abstract: We introduce a game theoretic model of network formation in an effort to understand the complex system of business relationships between various Internet entities (e.g., Autonomous Systems, enterprise networks, residential customers). In our model we are given a network topology of nodes and links where the nodes act as the players of the game, and links represent potential contracts. Nodes wish to satisfy their demands, which earn potential revenues, but may have to pay their neighbors for links incident to them. We incorporate some of the qualities of Internet business relationships, including customer–provider and peering contracts. We show that every Nash equilibrium can be represented by a circulation flow of utility with certain constraints. This allows us to prove bounds on the prices of anarchy and stability. We also focus on the quality of equilibria achievable through centralized incentives. [Copyright &y& Elsevier]

We study the survivable version of the game theoretic network formation model known as the Connection Game, originally introduced in Anshelevich et al. (Proc. 35th ACM Symposium on Theory of Computing, ). In this model, players attempt to connect to a common source node in a network by purchasing edges, and sharing their costs with other players. We introduce the survivable version of this game, where each player desires 2 edge-disjoint connections between her pair of nodes instead of just a single connecting path, and analyze the quality of exact and approximate Nash equilibria. This version is significantly different from the original Connection Game and have more complications than the existing literature on arbitrary cost-sharing games since we consider the formation of networks that involve many cycles. For the special case where each node represents a player, we show that Nash equilibria are guaranteed to exist and price of stability is 1, i.e., there always exists a stable solution that is as good as the centralized optimum. For the general version of the Survivable Connection Game, we show that there always exists a 2-approximate Nash equilibrium that is as good as the centralized optimum. To obtain the result, we use an approximation algorithm technique that compares the strategy of each player with only a carefully selected subset of her strategy space. Furthermore, if a player is only allowed to deviate by changing the payments on one of her connection paths at a time, instead of both of them at once, we prove that the price of stability is 1. We also discuss the time complexity issues. [ABSTRACT FROM AUTHOR]

After almost seven years from its definition,2 the price of stability of undirected network design games with fair cost allocation remains to be elusive. Its exact characterization has been achieved only for the basic case of two players2,7 and, as soon as the number of players increases, the gap between the known upper and lower bounds becomes super-constant, even in the special variants of multicast and broadcast games. Motivated by the intrinsic difficulties that seem to characterize this problem, we analyze the already challenging case of three players and provide either new or improved bounds. For broadcast games, we prove an upper bound of 1.485 which exactly matches a lower bound given in Ref. 4; for multicast games, we show new upper and lower bounds which confine the price of stability in the interval [1.524; 1.532]; while, for the general case, we give an improved upper bound of 1.634. The techniques exploited in this paper are a refinement of those used in Ref. 7 and can be easily adapted to deal with all the cases involving a small number of players. [ABSTRACT FROM AUTHOR]

Game theory has gained popularity as an approach to analysing and understanding distributed systems with self-interested agents. Central to game theory is the concept of Nash equilibrium as a stable state (solution) of the system, which comes with a price - the loss in efficiency. The quantification of the efficiency loss is one of the main research concerns. In this paper, we study the quality and computational characteristics of the best Nash equilibrium in two selfish scheduling models: the congestion model and the sequencing model. In particular, we present the following results: (1) In the congestion model: first, the best Nash equilibrium is socially optimum and consequently, computing the best Nash is NP-hard; second, any ℇ-approximation algorithm for finding the optimum can be transformed into an ℇ-approximation algorithm for the best Nash. (2) In sequencing model: for identical machines, we show that the best Nash is no better than the worst Nash and it is easy to compute; for related machines, we show that there is a gap between the worst and the best Nash equilibrium, and leave the analytical bound of this gap for future work. [ABSTRACT FROM AUTHOR]

We consider the problem of all-to-one selfish routing in the absence of a payment scheme in wireless sensor networks, where a natural model for cost is the power required to forward, referring to the resulting game as a Locally Minimum Cost Forwarding (LMCF). Our objective is to characterize equilibria and their global costs in terms of stretch and diameter, in particular finding incentive compatible algorithms that are also close to globally optimal. We find that although social costs for equilibria of LMCF exhibit arbitrarily bad worst-case bounds and computational infeasibility of reaching optimal equilibria, there exist greedy and local incentive compatible heuristics achieving near-optimal global costs. [ABSTRACT FROM AUTHOR]

We consider a model of game-theoretic network design initially studied by Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, ), where selfish players select paths in a network to minimize their cost, which is prescribed by Shapley cost shares. If all players are identical, the cost share incurred by a player for an edge in its path is the fixed cost of the edge divided by the number of players using it. In this special case, Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS), pp. 295–304, ) proved that pure-strategy Nash equilibria always exist and that the price of stability—the ratio between the cost of the best Nash equilibrium and that of an optimal solution—is Θ(log k), where k is the number of players. Little was known about the existence of equilibria or the price of stability in the general weighted version of the game. Here, each player i has a weight w i≥1, and its cost share of an edge in its path equals w i times the edge cost, divided by the total weight of the players using the edge. This paper presents the first general results on weighted Shapley network design games. First, we give a simple example with no pure-strategy Nash equilibrium. This motivates considering the price of stability with respect to α-approximate Nash equilibria—outcomes from which no player can decrease its cost by more than an α multiplicative factor. Our first positive result is that O(log wmax )-approximate Nash equilibria exist in all weighted Shapley network design games, where wmax is the maximum player weight. More generally, we establish the following trade-off between the two objectives of good stability and low cost: for every α=Ω(log wmax ), the price of stability with respect to O( α)-approximate Nash equilibria is O((log W)/ α), where W is the sum of the players’ weights. In particular, there is always an O(log W)-approximate Nash equilibrium with cost within a constant factor of optimal. Finally, we show that this trade-off curve is nearly optimal: we construct a family of networks without o(log wmax / log log wmax )-approximate Nash equilibria, and show that for all α=Ω(log wmax /log log wmax ), achieving a price of stability of O(log W/ α) requires relaxing equilibrium constraints by an Ω( α) factor. [ABSTRACT FROM AUTHOR]

We study network design games where n self-interested agents have to form a network by purchasing links from a given set of edges. We consider Shapley cost sharing mechanisms that split the cost of an edge in a fair manner among the agents using the edge. It is well known that the price of anarchy of these games is as high as n. Another line of research has focused on evaluating the price of stability, i.e., the cost of the best Nash equilibrium relative to the social optimum. In this paper we investigate to which extent coordination among agents can improve the quality of solutions. We resort to the concept of strong Nash equilibria, which were introduced by Aumann and are resilient to deviations by coalitions of agents. We analyze the price of anarchy of strong Nash equilibria and develop lower and upper bounds for unweighted and weighted games in both directed and undirected graphs. These bounds are tight or nearly tight for many scenarios. It shows that, by using coordination, the price of anarchy drops from linear to logarithmic bounds. We complement these results by also proving the first superconstant lower bound on the price of stability of standard equilibria (without coordination) in undirected graphs. More specifically, we show a lower bound of Ω(log W/log log W) for weighted games, where W is the total weight of all the agents. This almost matches the known upper bound of O(log W). Our results imply that, for most settings, the worst-case performance ratios of strong coordinated equilibria are essentially always as good as the performance ratios of the best equilibria achievable without coordination. These settings include unweighted games in directed graphs as well as weighted games in both directed and undirected graphs. [ABSTRACT FROM AUTHOR]

Network design is a fundamental problem for which it is important to understand the effects of strategic behavior. Given a collection of self-interested agents who want to form a network connecting certain endpoints, the set of stable solutions-the Nash equilibria-may look quite different from the centrally enforced optimum. We study the quality of the best Nash equilibrium, and refer to the ratio of its cost to the optimum network cost as the price of stability. The best Nash equilibrium solution has a natural meaning of stability in this context-it is the optimal solution that can be proposed from which no user will defect. We consider the price of stability for network design with respect to one of the most widely studied protocols for network cost allocation, in which the cost of each edge is divided equally between users whose connections make use of it; this fair-division scheme can be derived from the Shapley value and has a number of basic economic motivations. We show that the price of stability for network design with respect to this fair cost allocation is O(log k), where k is the number of users, and that a good Nash equilibrium can be achieved via best-response dynamics in which users iteratively defect from a starting solution. This establishes that the fair cost allocation protocol is in fact a useful mechanism for inducing strategic behavior to form near-optimal equilibria. We discuss connections to the class of potential games defined by Monderer and Shapley, and extend our results to cases in which users are seeking to balance network design costs with latencies in the constructed network, with stronger results when the network has only delays and no construction costs. We also present bounds on the convergence time of best-response dynamics, and discuss extensions to a weighted game. [ABSTRACT FROM AUTHOR]

In hedonic games, coalitions are created as a result of the strategic interaction of independent players. In particular, in additively separable hedonic games, every player has valuations for all other ones, and the utility for belonging to a coalition is given by the sum of the valuations for all other players belonging to it. So far, non-cooperative hedonic games have been considered in the literature only with respect to totally selfish players. Starting from the fundamental class of additively separable hedonic games, we define and study a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context additively separable hedonic games (SCASHGs). We focus on the fundamental stability notion of Nash equilibrium, and study the existence, convergence and performance of stable outcomes (with respect to the classical notions of price of anarchy and price of stability) in SCASHGs. In particular, we show that SCASHGs are potential games, and therefore Nash equilibria always exist and can be reached after a sequence of Nash moves of the players. Finally, we provide tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCASHGs. [ABSTRACT FROM AUTHOR]

We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d + 1 clusters C 0 , C 1 , ... , C d . Players in C 0 have full information about all the other participants in the game, while players in C i , for any 1 ≤ i ≤ d , have full information only about the members of C 0 ∪ C i and are unaware of all the others. This model has at least two interesting applications: (i) it is a special case of graphical congestion games induced by an undirected social knowledge graph with independence number equal to d, and (i i) it represents scenarios in which players have a type and the level of competition they experience on a resource depends on their type and on the types of the other players using it. We focus on the case in which the cost function associated with each resource is affine and bound the price of anarchy and stability as a function of d with respect to two meaningful social cost functions and for both weighted and unweighted players. We also provide refined bounds for the special case of d = 2 in presence of unweighted players. [ABSTRACT FROM AUTHOR]