text: ABSTRACTIn many ‘smart city’ applications, congestion arises in part due to the nature of signals received by individuals from a central authority. In the model of , each agent uses one out of multiple resources at each time instant. The per-use cost of a resource depends on the number of concurrent users. A central authority has up-to-date knowledge of the congestion across all resources and uses randomisation to provide a scalar or an interval for each resource at each time. In this paper, the interval to broadcast per resource is obtained by taking the minima and maxima of costs observed within a time window of length r, rather than by randomisation. We show that the resulting distribution of agents across resources also converges in distribution, under plausible assumptions about the evolution of the population over time.
  @cite_35: In many settings there exists a set of potential participants, but the set of participants who are actually active in the system, and in particular their number, is unknown. This topic has been first analyzed by Ashlagi, Monderer, and Tennenholtz [AMT] in the context of simple routing games, where the network consists of a set of parallel links, and the agents can not split their jobs among different paths. AMT used the model of pre-Bayesian games, and the concept of safety-level equilibrium for the analysis of these games. In this paper we extend the work by AMT. We deal with splitable routing games, where each player can split his job among paths in a given network. In this context we generalize the analysis to all two-node networks, in which paths may intersect in unrestricted manner. We characterize the relationships between the number of potential participants and the number of active participants under which ignorance is beneficial to each of the active participants.
  @cite_38: 
  @cite_26: In this work, we study the degree to which small fluctuations in costs in well-studied potential games can impact the result of natural best-response and improved-response dynamics. We call this the Price of Uncertainty and study it in a wide variety of potential games including fair cost-sharing games, set-cover games, routing games, and job-scheduling games. We show that in certain cases, even extremely small fluctuations can have the ability to cause these dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large degrees of fluctuation. We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show again a contrast between different games. In certain cases (e.g., fair cost-sharing, set-cover, job-scheduling) even a single Byzantine player can cause best-response dynamics to transition from low-cost states to states of substantially higher cost, whereas in others (e.g., the class of β-nice games, which includes routing, market-sharing and many others) these dynamics are much more resilient. Overall, our work can be viewed as analyzing the inherent resilience or safety of games to different kinds of imperfections in player behavior, player information, or in modeling assumptions made.
  @cite_4: We study a setting where a set of players simultaneously invest in a shared resource. The resource has a probability of failure and a return on investment, both of which are functions of the total investment by all players. We use a simple reference dependent preference model to capture players with heterogeneous risk attitudes (risk seeking, risk neutral and risk averse). We show the existence and uniqueness of a pure strategy Nash equilibrium in this setting and examine the effect of different risk attitudes on players' strategies in the presence of uncertainty. In particular, we show that at the equilibrium, risk averse players are pushed out of the resource by risk seeking players. We compare the failure probabilities in the decentralized (game-theoretic) and centralized settings, and show that our proposed game belongs to the class of best response potential games, for which there are simple dynamics that allow all players to converge to the equilibrium.
  @cite_18: In game theory, the price of anarchy framework studies efficiency loss in decentralized environments. Optimization and decision theory, on the other hand, explore tradeoffs between optimality and robustness in the case of single-agent decision making under uncertainty. What happens when we combine both approaches? We examine connections between the efficiency loss due to decentralization and the efficiency loss due to uncertainty and establish tight performance guarantees for distributed systems in uncertain environments. We present applications based on novel variants of atomic congestion games with uncertain costs, for which we provide tight performance bounds under a wide range of risk attitudes. Our results establish that the individual’s attitude toward uncertainty has a critical effect on system performance and therefore should be a subject of close and systematic investigation.
  @cite_41: We analyze 2-terminal routing games with linear cost functions and with unknown number of active players. We deal with both splittable and unsplittable models. We prove the existence and uniqueness of a symmetric safety-level equilibrium in such games and show that in many cases every player benefits from the common ignorance about the number of players. Furthermore, we prove new theorems on existence and uniqueness of equilibrium in 2-terminal convex routing games with complete information.
  @cite_56: 
  @cite_24: In this paper we characterize the “price of anarchy”, i.e., the inefficiency between user and system optimal solutions, when costs are non-separable, asymmetric and nonlinear, generalizing earlier work that has addressed “the price of anarchy” under separable costs. This generalization models traffic equilibria, competitive multi-period pricing and competitive supply chains. The bounds established in this paper are tight and explicitly account for the degree of asymmetry and nonlinearity of the cost function. We introduce an alternate proof method for providing bounds that uses ideas from semidefinite optimization. Finally, in the context of multi-period pricing our analysis establishes that user and system optimal solutions coincide.
  @cite_27: We propose a natural model for agent failures in congestion games. In our model, each of the agents may fail to participate in the game, introducing uncertainty regarding the set of active agents. We examine how such uncertainty may change the Nash equilibria (NE) of the game. We prove that although the perturbed game induced by the failure model is not always a congestion game, it still admits at least one pure Nash equilibrium. Then, we turn to examine the effect of failures on the maximal social cost in any NE of the perturbed game. We show that in the limit case where failure probability is negligible new equilibria never emerge, and that the social cost may decrease but it never increases. For the case of nonnegligible failure probabilities, we provide a full characterization of the maximal impact of failures on the social cost under worst-case equilibrium outcomes.
  @cite_2: We present a short geometric proof for the price of anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks. This novel proof also facilitates two new types of results: On the one hand, we give pseudo-approximation results that depend on the class of allowable cost functions. On the other hand, we derive improved bounds on the inefficiency of Nash equilibria for situations in which the equilibrium travel times are within reasonable limits of the free-flow travel times. These tighter bounds help to explain empirical observations in vehicular traffic networks. Our analysis holds in the more general context of congestion games, which provides the framework in which we describe this work.
  @cite_46: We show how giving partial or no information to players about the number of other players may yield higher social welfare in games.
  @cite_20: Traditionally, traffic assignment models, both for within-day static and dynamic demand, have been formulated following an equilibrium approach in which a state ensuring internal consistency between demand (flows) and costs is sought. However, equilibrium analysis is significant under some assumptions on its “representativeness” (coincidence or closeness with the actual attractor of the system) and analytical properties, such as existence, uniqueness, and stability. Moreover, transients due to modifications of demand and or supply cannot be simulated through equilibrium models, nor can a statistical description of the state of the system, i.e. means, modes, moments and, more generally, frequency distributions of flows over time be obtained. In this paper, interperiodic (day-to-day) dynamic modeling of transportation networks is addressed following two different approaches, namely deterministic and stochastic processes. In both cases several theoretical results are shown by making use of a formal framework covering most models discussed in the literature as well as some possible extensions. Most of the results reported can be extended to cover within-day dynamic models but these models are not explicitly dealt with. Within the framework of deterministic processes the relevance of day-to-day dynamic models for demand supply interaction in comparison with the traditional user equilibrium approach is discussed, and conditions for coincidence of fixed-point attractors and equilibrium states are stated. Conditions for existence and uniqueness of fixed-point attractors are proposed, generalizing and extending those presented in the literature for user equilibrium. Conditions for stability of both fixed-points and equilibrium states were formulated by making use of results from non-linear dynamic system theory. Moreover, it is possible to devise a new family of “dynamic” algorithms which simulate the system convergence to a fixed-point in order to obtain an equivalent equilibrium state, as opposed to conventional “optimisation” algorithms. In this case the fixed-point stability analysis can be viewed as a convergence analysis for the algorithms specified this way. Conditions for stochastic process regularity are proposed ensuring, among other things, existence and uniqueness of a stationary probability distribution of system states. These conditions generalize and extend results presented in the literature to a wider class of possible dynamic models. Relationships between a deterministic process, together with corresponding fixed-points or equilibrium states, and stochastic probability distribution are also briefly addressed. Finally, some numerical examples confirming theoretical results are reported for a small test network.
  @cite_13: We define a new class of games, congestion games with load-dependent failures (CGLFs). In a CGLF each player can choose a subset of a set of available resources in order to try and perform his task. We assume that the resources are identical but that players' benefits from successful completion of their tasks may differ. Each resource is associated with a cost of use and a failure probability which are load-dependent. Although CGLFs in general do not have a pure strategy Nash equilibrium, we prove the existence of a pure strategy Nash equilibrium in every CGLF with nondecreasing cost functions. Moreover, we present a polynomial time algorithm for computing such an equilibrium.
  @cite_25: We study the quality of equilibrium in atomic splittable routing games. We show that in single-source single-sink games on series-parallel graphs, the price of collusion — the ratio of the total delay of atomic Nash equilibrium to the Wardrop equilibrium — is at most 1. This proves that the existing bounds on the price of anarchy for Wardrop equilibria carry over to atomic splittable routing games in this setting.
  @cite_12: We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times---the total latency---is minimized.In many settings, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance.In this article, we quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4 3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and nondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulated selfish network users may be arbitrarily larger than the minimum possible total latency; however, we prove that it is no more than the total latency incurred by optimally routing twice as much traffic.
  @cite_17: Uncertainty is present in different guises in many settings, in particular in environments with strategic interactions. However, most game-theoretic models assume that players can accurately observe interactions and their own costs. In this paper we quantify the effect on social costs of two different types of uncertainty: adversarial perturbations of small magnitude to costs (effect called the Price of Uncertainty (PoU) [3]) and the presence of several players with Byzantine, i.e. arbitrary, behavior (effect we call the Price of Byzantine behavior (PoB)). We provide lower and upper bounds on PoU and PoB in two well-studied classes of potential games: consensus games and set-covering games.
summary: Within game theory, the social cost is the metric of a number of studies @cite_12 @cite_24 @cite_2 @cite_25 , which show that, even when agents have full information, a natural equilibrium outcome can incur much higher total congestion than a socially optimal outcome. This is known as the price of anarchy. Particularly interesting are studies of the Nash equilibria in connection with ignorance @cite_26 @cite_56 @cite_17 , often concerning the number of players @cite_35 @cite_41 @cite_46 , failures of agents @cite_27 , failures of resources @cite_13 @cite_38 , or stratified and risk-averse populations @cite_4 @cite_18 . Indeed, our work can be seen as showing the benefits of ignorance to a stratified and risk-averse population, albeit over the long run. We can hence describe the attractor, whose existence is often moot in the studies of Nash equilibria. See @cite_20 for further well-developed arguments why considering the fixed-points of a dynamical system is preferable to the study of the Nash equilibrium.