Search

The goal in this article is to approximate the Price of Stability (PoS) in stochastic Nash games using stochastic approximation (SA) schemes. PoS is among the most popular metrics in game theory and provides an avenue for estimating the efficiency of Nash games. In particular, evaluating the PoS can help with designing efficient networked systems, including communication networks and power market mechanisms. Motivated by the absence of efficient methods for computing the PoS, first we consider stochastic optimization problems with a nonsmooth and merely convex objective function and a merely monotone stochastic variational inequality (SVI) constraint. This problem appears in the numerator of the PoS ratio. We develop a randomized block-coordinate stochastic extra-(sub)gradient method where we employ a novel iterative penalization scheme to account for the mapping of the SVI in each of the two gradient updates of the algorithm. We obtain an iteration complexity of the order ϵ -4 that appears to be best known result for this class of constrained stochastic optimization problems, where ϵ denotes an arbitrary bound on suitably defined infeasibility and suboptimality metrics. Second, we develop an SA-based scheme for approximating the PoS and derive lower and upper bounds on the approximation error. To validate the theoretical findings, we provide preliminary simulation results on a networked stochastic Nash Cournot competition. [ABSTRACT FROM AUTHOR]

We consider the question of whether and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games in which each player's weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge in distribution to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second setting, we consider an increasing number of players with a unit weight that participate in the game with a decreasingly small probability. In this case, the Nash equilibrium flows converge in total variation toward Poisson random variables whose expected values are Wardrop equilibria of a different nonatomic game with suitably defined costs. The latter can be viewed as symmetric equilibria in a Poisson game in the sense of Myerson, establishing a plausible connection between the Wardrop model for routing games and the stochastic fluctuations observed in real traffic. In both settings, we provide explicit approximation bounds, and we study the convergence of the price of anarchy. Beyond the case of congestion games, we prove a general result on the convergence of large games with random players toward Poisson games. Funding: R. Cominetti gratefully acknowledges the support of Proyecto Anillo [Grant ANID/PIA/ACT192094]. M. Scarsini's work was partially supported by the Gruppo Nazionale per l'Analisi Matematica, la Probabilità e le loro Applicazioni, Istituto Nazionale di Alta Matematica [Grant 2020 "Random walks on random games"] and the Progetti di Rilevante Interesse Nazionale 2017 [Grant "Algorithms, Games, and Digital Markets"]. This research also received partial support from the European Cooperation in Science and Technology [Action European Network for Game Theory]. [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 consider two classes of games in which players are the vertices of a directed graph. Initially, nature chooses one player according to some fixed distribution and gives the player a buck. This player passes the buck to one of the player's out-neighbors in the graph. The procedure is repeated indefinitely. In one class of games, each player wants to minimize the asymptotic expected frequency of times that the player receives the buck. In the other class of games, the player wants to maximize it. The PageRank game is a particular case of these maximizing games. We consider deterministic and stochastic versions of the game, depending on how players select the neighbor to which to pass the buck. In both cases, we prove the existence of pure equilibria that do not depend on the initial distribution; this is achieved by showing the existence of a generalized ordinal potential. If the graph on which the game is played admits a Hamiltonian cycle, then this is the outcome of prior-free Nash equilibrium in the minimizing game. For the minimizing game, we then use the price of anarchy and stability to measure fairness of these equilibria. [ABSTRACT FROM AUTHOR]

Optimization of the transmission power and rate allocation is a significant problem in wireless networks with mobile nodes. Due to mobility, the vehicles establishing wireless networks may exhibit severe fluctuations of their link quality, affecting their connection reliability and throughput. In Vehicular Ad-hoc Networks (VANETS), the IEEE 802.11p standard provides a practical metric for the Packet Reception Ratio (PRR), which is related with the transmission power and rate. Finding a global strategy for optimizing PRR for all mobile nodes can be treated as a potential game where each vehicle is considered as a selfish player, aiming to maximise its transmission reliability while rate constraints are satisfied. To this end, we propose a game-theoretic approach that converges to a Nash equilibrium. The main contributions of this work include: (i) identification of the best case equilibrium, for two cases of interference: diminished or kept stable, and (ii) verification of the equilibrium optimality, by showing that the value of stability is 1. Moreover, numerical results exhibiting the ease of the utility function calculation are provided, especially after an SINR level, whereby the utility function is concave and can be solved efficiently in polynomial time. [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]

In cost-sharing games with delays, a set of agents jointly uses a subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A separable cost-sharing protocol determines cost shares that are budget-balanced, separable, and guarantee existence of pure Nash equilibria (PNE). We provide black-box reductions reducing the design of such a protocol to the design of an approximation algorithm for the underlying cost-minimization problem. In this way, we obtain separable cost-sharing protocols in matroid games, single-source connection games, and connection games on n-series-parallel graphs. All these reductions are efficiently computable - given an initial allocation profile, we obtain a cheaper profile and separable cost shares turning the profile into a PNE. Hence, in these domains, any approximation algorithm yields a separable cost-sharing protocol with price of stability bounded by the approximation factor. [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]

Copyright of Ordnance Industry Automation is the property of Editorial Board for Ordnance Industry Automation and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. In this paper we assume that for each couple of agents (i, j), weight w i , j = w j , i reflects how much agents i and j benefit from belonging to the same coalition. We consider the (symmetric) modified fractional hedonic game, that is a coalition formation game in which agents' utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of w i , j over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0–1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i.e., including herself. [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 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.

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]

We study a game theoretical model of multistage interval scheduling problems in which each job consists of exactly one task (interval) for each of t stages (machines). In the game theoretical model, the machine of each stage is controlled by a different selfish player who wants to maximize her total profit, where the profit for scheduling the task of a job j is a fraction of the weight of the job that is determined by the set of players that also schedule their corresponding task of job j. We provide criteria for the existence of pure Nash equilibria and prove bounds on the Price of Anarchy and the Price of Stability for different social welfare functions. [ABSTRACT FROM AUTHOR]

This paper deals with decentralized decision-making situations in which firms outsource production orders to multiple identical suppliers. Each firm aims to minimize the sum of its completion times. We study whether a central authority can install a mechanism such that strategic interaction leads to a socially optimal schedule. For the case of single demand the shortest-first mechanism implements optimal schedules in Nash equilibrium. We show that for the general case there exists no anonymous mechanism that implements optimal schedules in correlated equilibrium. [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]

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 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]

We consider the infinite-horizon multiple retailer joint replenishment problem with first-order interaction. In this model, the joint setup cost incurred by a group of retailers placing an order simultaneously consists of a group-independent major setup cost and retailer-specific minor setup costs. The goal is to determine an inventory replenishment policy that minimizes the long-run average system-wide cost. In this paper, we adopt a noncooperative approach to study the joint replenishment game. We consider the allocation rule in which the major setup cost is split equally among the retailers who place an order together, and each retailer pays his own holding and minor setup costs. Given the preannounced allocation rule, each retailer determines his replenishment policy to minimize his own cost anticipating the other retailers' strategy. We show that a payoff dominant Nash equilibrium exists, and quantify the efficiency loss of the noncooperative outcome relative to the social optimum. Although the worst-case ratio between the best decentralized outcome and the social optimum is O((ln n)1/2), where n is the number of retailers, numerical results suggest that the best equilibrium is near optimal. The online appendix is available at . [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 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]

We consider network design games with weighted players and uniform edge capacities and study their Nash equilibria. In these games, each player has to choose a path from her source to her sink through a network subject to the constraint that the total weight of all players using an edge within their chosen path does not exceed the capacity of the edge. The fixed cost of each edge that is used by some player is shared among the players using the edge by charging each player a fraction of the edge's cost equal to the ratio of her weight to the total weight of all players using the edge. We show that there exist instances of capacitated network design games with weighted players and uniform capacities that do not admit a Nash equilibrium even in the case that all players share the same source and sink. Moreover, we show that it is strongly [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]

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]