More Like this

1. PRICE OF ANARCHY FOR MEAN FIELD GAMES

   Carmona, Rene; Graves, Christy V.; Tan, Zongjun (February 2019, ESAIM. Proceedings and surveys)

   The price of anarchy, originally introduced to quantify the inefficiency of selfish behavior in routing games, is extended to mean field games. The price of anarchy is defined as the ratio of a worst case social cost computed for a mean field game equilibrium to the optimal social cost as computed by a central planner. We illustrate properties of such a price of anarchy on linear quadratic extended mean field games, for which explicit computations are possible. A sufficient and necessary condition to have no price of anarchy is presented . Various asymptotic behaviors of the price of anarchy are proved for limiting behaviors of the coefficients in the model and numerics are presented . 

   more » « less
2. A Library for Algorithmic Game Theory in Ssreflect/Coq

   https://doi.org/10.6092/issn.1972-5787/7235  

   Bagnall, Alexander; Merten, Samuel; Stewart, Gordon (December 2017, Journal of Formalized Reasoning)

   We report on the formalization in Ssreflect/Coq of a number of concepts and results from algorithmic game theory, including potential games, smooth games, solution concepts such as Pure and Mixed Nash Equilibria, Coarse Correlated Equilibria, epsilon-approximate equilibria, and behavioral models of games such as best-response dynamics. We apply the formalization to prove Price of Stability bounds for, and convergence under best-response dynamics of, the Atomic Routing game, which has applications in computer networking. Our second application proves that Affine Congestion games are (5/3, 1/3)-smooth, and therefore have Price of Anarchy 5/2. Our formalization is available online. 

   more » « less
3. Social Cost Analysis of Shared/Buy-in Computing Systems

   https://doi.org/10.1145/3624355  

   Shi, Zhenpeng; Starobinski, David; Orda, Ariel (December 2023, ACM Transactions on Economics and Computation)

   Shared/buy-in computing systems offer users the option to select between buy-in and shared services. In such systems, idle buy-in resources are made available to other users for sharing. With strategic users, resource purchase and allocation in such systems can be cast as a non-cooperative game, whose corresponding Nash equilibrium does not necessarily result in the optimal social cost. In this study, we first derive the optimal social cost of the game in closed form, by casting it as a convex optimization problem and establishing related properties. Next, we derive a closed-form expression for the social cost at the Nash equilibrium, and show that it can be computed in linear time. We further show that the strategy profiles of users at the optimum and the Nash equilibrium are directly proportional. We measure the inefficiency of the Nash equilibrium through the price of anarchy, and show that it can be quite large in certain cases, e.g., when the operating expense ratio is low or when the distribution of user workloads is relatively homogeneous. To improve the efficiency of the system, we propose and analyze two subsidy policies, which are shown to converge using best-response dynamics. 

   more » « less
4. On the Performance of Nash Equilibria for Data Preservation in Base Station-less Sensor Networks

   https://doi.org/10.1109/MASS58611.2023.00038  

   Rivera, Giovanni; Chen, Yutian; Tang, Bin (September 2023, the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2023))

   Base station-less sensor networks (BSNs) refer to emerging sensing applications deployed in challenging environments (e.g., underwater exploration). As installing a base station in such an environment is not feasible, data generated in the BSN will be preserved in the network before being collected by the uploading opportunities. This process is called data preservation in the BSN. Considering that sensor nodes are intelligent and selfish, this paper studies the Nash Equilibrium (NE) for data preservation in BSNs. We design a suite of data preservation algorithms, examine whether they achieve NEs, and rigorously analyze the performance of the NEs using existing (i.e., price of anarchy and price of stability) and our own designed metrics (i.e., rate of efficiency loss). We find that a minimum cost flow-based algorithm produces a NE that achieves the social optimal with minimum energy consumption in the data preservation process. We show the NE from one of our straightforwardly designed greedy algorithms achieves a price of anarchy of 3. On the other hand, we prove that a greedy algorithm always exists (although non-straightforward), achieving the socially optimal NE. Finally, we conduct extensive simulations to investigate the performances of various data preservation NEs and validate our theoretical results under different network parameters. 

   more » « less
5. A Game-Theoretic Approach for Optimal Dispatch of Building Thermal Loads Subject to Linear-Plus-Exponential Marginal Price

   Jiang, Zhimin; Cai, Jie (December 2023, 2023 62nd IEEE Conference on Decision and Control (CDC))

   This paper introduces a game-theoretical strategy for optimal dispatch of building thermal loads, based on a marginal price model derived from an actual dispatch curve. A non-cooperative game is formulated, and the existence and uniqueness of the Nash equilibrium solution are proved aided by the variational inequality theory. A game solution algorithm is presented in this paper to solve the control problem with guaranteed convergence. The proposed game-theoretical control technique was evaluated against a baseline energy minimization strategy and a socially optimal solution, through a simulation test of a virtual market comprised of six buildings. The results show that the proposed game-theoretical strategy could achieve performance very close to the social optimum with a Price of Anarchy of 1.0041 and a 24% cost reduction compared to the baseline energy-priority strategy. 

   more » « less