skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Social Cost Analysis of Shared/Buy-in Computing Systems
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
Award ID(s):
1908087
PAR ID:
10496686
Author(s) / Creator(s):
; ;
Publisher / Repository:
IEEE
Date Published:
Journal Name:
ACM Transactions on Economics and Computation
Volume:
11
Issue:
3-4
ISSN:
2167-8375
Page Range / eLocation ID:
1 to 36
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, ArXivorg)
    We develop a probabilistic approach to continuous-time finite state mean field games. Based on an alternative description of continuous-time Markov chain by means of semimartingale and the weak formulation of stochastic optimal control, our approach not only allows us to tackle the mean field of states and the mean field of control in the same time, but also extend the strategy set of players from Markov strategies to closed-loop strategies. We show the existence and uniqueness of Nash equilibrium for the mean field game, as well as how the equilibrium of mean field game consists of an approximative Nash equilibrium for the game with finite number of players under different assumptions of structure and regularity on the cost functions and transition rate between states. 
    more » « less
  2. ; ; ; (, IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS))
    In UAV communication with a ground control station, mission success requires maintaining the freshness of the received information, especially when the communication faces hostile interference. We model this problem as a game between a UAV transmitter and an adversarial interferer. We prove that in contrast with the Nash equilibrium, multiple Stackelberg equilibria could arise. This allows us to show that reducing interference activity in the Stackelberg game is achieved by higher sensitivity of the transmitter in the Stackelberg equilibrium strategy to network parameters relative to the Nash equilibrium strategy. All the strategies are derived in closed form and we establish the condition for when multiple strategies arise. 
    more » « less
  3. ; ; ; ; (, Proceedings of the ACM on Measurement and Analysis of Computing Systems)
    Automated marker makers (AMMs) are decentralized exchanges that enable the automated trading of digital assets. Liquidity providers (LPs) deposit digital tokens, which can be used by traders to execute trades, which generate fees for the investing LPs. In AMMs, trade prices are determined algorithmically, unlike classical limit order books. Concentrated liquidity market makers (CLMMs) are a major class of AMMs that offer liquidity providers flexibility to decide not onlyhow muchliquidity to provide, butin what ranges of pricesthey want the liquidity to be used. This flexibility can complicate strategic planning, since fee rewards are shared among LPs. We formulate and analyze a game theoretic model to study the incentives of LPs in CLMMs. Our main results show that while our original formulation admits multiple Nash equilibria and has complexity quadratic in the number of price ticks in the contract, it can be reduced to a game with a unique Nash equilibrium whose complexity is only linear. We further show that the Nash equilibrium of this simplified game follows a waterfilling strategy, in which low-budget LPs use up their full budget, but rich LPs do not. Finally, by fitting our game model to real-world CLMMs, we observe that in liquidity pools with risky assets, LPs adopt investment strategies far from the Nash equilibrium. Under price uncertainty, they generally invest in fewer and wider price ranges than our analysis suggests, with lower-frequency liquidity updates. In such risky pools, by updating their strategy to more closely match the Nash equilibrium of our game, LPs can improve their median daily returns by $116, which corresponds to an increase of 0.009% in median daily return on investment (ROI). At maximum, LPs can improve daily ROI by 0.855% when they reach Nash equilibrium. In contrast, in stable pools (e.g., of only stablecoins), LPs already adopt strategies that more closely resemble the Nash equilibrium of our game. 
    more » « less
  4. ; (, Mathematics of Operations Research)
    null (Ed.)
    We develop a probabilistic approach to continuous-time finite state mean field games. Based on an alternative description of continuous-time Markov chains by means of semimartingales and the weak formulation of stochastic optimal control, our approach not only allows us to tackle the mean field of states and the mean field of control at the same time, but also extends the strategy set of players from Markov strategies to closed-loop strategies. We show the existence and uniqueness of Nash equilibrium for the mean field game as well as how the equilibrium of a mean field game consists of an approximative Nash equilibrium for the game with a finite number of players under different assumptions of structure and regularity on the cost functions and transition rate between states. 
    more » « less
  5. ; ; ; ; (, IEEE Transactions on Control of Network Systems)
    In this paper, we develop distributed computation algorithms for Nash equilibriums of linear quadratic network games with proven differential privacy guarantees. In a network game with each player's payoff being a quadratic function, the dependencies of the decisions in the payoff function naturally encode a network structure governing the players' inter-personal influences. Such social influence structure and the individual marginal payoffs of the players indicate economic spillovers and individual preferences, and thus they are subject to privacy concerns. For distributed computing of the Nash equilibrium, the players are interconnected by a public communication graph, over which dynamical states are shared among neighboring nodes. When the players' marginal payoffs are considered to be private knowledge, we propose a distributed randomized gradient descent algorithm, in which each player adds a Laplacian random noise to her marginal payoff in the recursive updates. It is proven that the algorithm can guarantee differential privacy and convergence in expectation to the Nash equilibrium of the network game at each player's state. Moreover, the mean-square error between the players' states and the Nash equilibrium is shown to be bounded by a constant related to the differential privacy level. Next, when both the players' marginal payoffs and the influence graph are private information, we propose two distributed algorithms by randomized communication and randomized projection, respectively, for privacy preservation. The differential privacy and convergence guarantees are also established for such algorithms. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email