Search

We consider the classical machine scheduling, where n jobs need to be scheduled on m machines, and where job j scheduled on machine i contributes p ij ∈ R to the load of machine i, with the goal of minimizing the makespan, i.e., the maximum load of any machine in the schedule. We study the inefficiency of schedules that are obtained when jobs arrive sequentially one by one, and the jobs choose the machine on which they will be scheduled, aiming at being scheduled on a machine with a small load. We measure the inefficiency of a schedule as the ratio of the makespan obtained in the worst-case equilibrium schedule, and of the optimum makespan. This ratio is known as the sequential price of anarchy (SPoA). We also introduce two alternative inefficiency measures, which allow for a favorable choice of the order in which the jobs make their decisions. As our first result, we disprove the conjecture of Hassin and Yovel (Oper Res Lett 43(5):530–533, 2015) claiming that the sequential price of anarchy for m = 2 machines is at most 3. We show that the sequential price of anarchy grows at least linearly with the number n of players, assuming arbitrary tie-breaking rules. That is, we show SPoA ∈ Ω (n) . At the end of the paper, we show that if an authority can change the order of the jobs adaptively to the decisions made by the jobs so far (but cannot influence the decisions of the jobs), then there exists an adaptive ordering in which the jobs end up in an optimum schedule. [ABSTRACT FROM AUTHOR]

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]

Motivated by possible applications in fault-tolerant selfish routing, we introduce the notion of uniform mixed equilibrium in network congestion games with adversarial link failures, where agents need to route traffic from a source to a destination node. Given an integer ρ≥1 , a ρ-uniform mixed strategy is a mixed strategy in which an agent plays exactly ρ edge-disjoint paths with uniform probability; therefore, a ρ-uniform mixed equilibrium is a tuple of ρ-uniform mixed strategies, one for each agent, in which no agent can lower her cost by deviating to another ρ-uniform mixed strategy. For games with weighted agents and affine latency functions, we show the existence of ρ-uniform mixed equilibria and provide a tight characterization of their price of anarchy. For games with unweighted agents, we extend the existential guarantee to any class of latency functions, and restricted to games with affine latencies, we derive a tight characterization of the price of anarchy and the price of stability. Funding: This work was partially supported by the INdAM-GNCS and the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets." [ABSTRACT FROM AUTHOR]

The complex interaction of fixed incentives for multiple agents can lead to inefficient results. The Price of Anarchy (PoA) is a concept employed in economics and game theory to quantify how, in the worst-case scenario, a system's efficiency diminishes due to the selfish behavior of its actors. It evaluates the outcomes obtained by perfect coordination to that obtained by self-interested players in a Nash equilibrium.This paper investigates the PoA in mechanism design for Pareto-Bayesian-Markov (PBN) games in which the players privately know their information. Our approach is restricted to the development of algorithmic mechanisms. We consider an ergodic finite Markov chain in which players' transitions are independent and decisions are made across a finite number of periods. As a key outcome, we completely characterize the Pareto frontier and calculate an efficient, ex-post incentive-compatible technique. We employ Tikhonov's regularization technique, for assuring that the original problem's solution converges to a unique solution. The ratio equilibria of the PoA is found employing a projection-gradient method, which is our main result. We compute the PoA using an auxiliary variable and present the formulas for retrieving the variables of interest. We show that our theoretical conclusions ensure convergence and we provide a numerical example to demonstrate the method's utility. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a transportation game first introduced by Fotakis, Gourvès, and Monnot in 2017, where players want to be transported to a common destination as quickly as possible and, to achieve this goal, they have to choose one of the available buses. We introduce a sequential version of this game and provide bounds for the Sequential Price of Stability and the Sequential Price of Anarchy in both metric and non-metric instances, considering three social cost functions: the total traveled distance by all buses, the maximum distance traveled by a bus, and the sum of the distances traveled by all players (a new social cost function that we introduce). Finally, we analyze the Price of Stability and the Price of Anarchy for this new function in simultaneous transportation games. [ABSTRACT FROM AUTHOR]

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

Investors usually resort to financial advisors to improve their investment process until the point of complete delegation on investment decisions. Surely, financial advice is potentially a correcting factor in investment decisions but, in the past, the media and regulators blamed biased advisors for manipulating the expectations of naive investors. In order to give an analytic formulation of the problem, we present an Agent-Based Model formed by individual investors and a financial advisor. We parametrize the games by considering a compromise for the financial advisor (between a sufficient reward by bank and to keep her reputation), and a compromise for the customers (between the desired return and the proposed return by advisor), and incorporating the social psychological concepts of truthfulness and cognitive dissonance. Then we obtain the Nash equilibria and the best response functions of the resulting game. We also describe the parameter regions in which these points result acceptable equilibria. In this way, the greediness/naivety of the customers emerge naturally from the model. Finally, we focus on the efficiency of the best Nash equilibrium. [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 study the trade-off between the price of anarchy (PoA) and the price of stability (PoS) in mechanism design in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to these metrics and observe that two fundamental mechanisms, namely the first price (FP) and the second price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms S P α that lie exactly on this frontier. In particular, these mechanisms range smoothly with respect to parameter α ≥ 1 across the frontier, between the first price (S P 1 ) and second price (S P ∞ ) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether nontruthful mechanisms can provide better makespan guarantees in the equilibrium compared with truthful ones. We answer this question in the negative by proving that the price of anarchy of all scheduling mechanisms is at least n, where n is the number of machines. [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]

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]

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]

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

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.

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]

We consider a game where a finite number of retailers choose a location, given that their potential consumers are distributed on a network. Retailers do not compete on price but only on location, therefore each consumer shops at the closest store. We show that when the number of retailers is large enough, the game admits a pure Nash equilibrium and we construct it. We then compare the equilibrium cost borne by the consumers with the cost that could be achieved if the retailers followed the dictate of a benevolent planner. We perform this comparison in terms of the Price of Anarchy (i.e., the ratio of the worst equilibrium cost and the optimal cost) and the Price of Stability (i.e., the ratio of the best equilibrium cost and the optimal cost). We show that, asymptotically in the number of retailers, these ratios are bounded by two and one, respectively. [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 introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d+1 clusters C0,C1,…,Cd. Players in C0 have full information about all the other participants in the game, while players in Ci, for any 1≤i≤d, have full information only about the members of C0∪Ci 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 (ii) 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.

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 propose a model of discrete time dynamic congestion games with atomic players and a single source-destination pair. The latencies of edges are composed of freeflow transit times and possible queuing time due to capacity constraints.We give a precise description of the dynamics induced by the individual strategies of players and of the corresponding costs, either when the traffic is controlled by a planner, or when players act selfishly. In parallel networks, optimal and equilibrium behavior eventually coincide, but the selfish behavior of the initial players has consequences that cannot be undone and are paid by all future generations. In more general topologies, our main contributions are threefold. First, we illustrate a new dynamic version of Braess paradox: the presence of initial queues in the network may decrease the long-run costs in equilibrium. This paradox can arise in networks for which no Braess paradox was previously known. Second, we show that equilibria are not unique and can induce very different long-run costs. In particular, we give a sequence of networks such that the price of stability is equal to 1, and the price of anarchy is equal to n - 1, where n is the number of vertices. Third, we propose an extension to model seasonalities by assuming that departure flows fluctuate periodically over time. We introduce a measure that captures the queues induced by periodicity of inflows. For optimal and equilibrium flows in parallel networks this measure is the increase in cost compared to uniform departures. [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]