An official website of the United States government
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
Mechanism Design for Demand Management in Energy Communities
We consider a demand management problem in an energy community, in which several users obtain energy from an external organization such as an energy company and pay for the energy according to pre-specified prices that consist of a time-dependent price per unit of energy as well as a separate price for peak demand. Since users’ utilities are their private information, which they may not be willing to share, a mediator, known as the planner, is introduced to help optimize the overall satisfaction of the community (total utility minus total payments) by mechanism design. A mechanism consists of a message space, a tax/subsidy, and an allocation function for each user. Each user reports a message chosen from her own message space, then receives some amount of energy determined by the allocation function, and pays the tax specified by the tax function. A desirable mechanism induces a game, the Nash equilibria (NE), of which results in an allocation that coincides with the optimal allocation for the community. As a starting point, we design a mechanism for the energy community with desirable properties such as full implementation, strong budget balance and individual rationality for both users and the planner. We then modify this baseline mechanism for communities where message exchanges are allowed only within neighborhoods, and consequently, the tax/subsidy and allocation functions of each user are only determined by the messages from their neighbors. All of the desirable properties of the baseline mechanism are preserved in the distributed mechanism. Finally, we present a learning algorithm for the baseline mechanism, based on projected gradient descent, that is guaranteed to converge to the NE of the induced game.
more »
« less
- Award ID(s):
- 2015191
- PAR ID:
- 10289554
- Date Published:
- Journal Name:
- Games
- Volume:
- 12
- Issue:
- 3
- ISSN:
- 2073-4336
- Page Range / eLocation ID:
- 61
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the market structure for emerging distribution-level energy markets with high renewable energy penetration. Renewable generation is known to be uncertain and has a close-to-zero marginal cost. In this paper, we use solar energy as an example of such zero-marginal-cost resources for our focused study. We first show that, under high penetration of solar generation, the classical real-time market mechanism can either exhibit significant price-volatility (when each firm is not allowed to vary the supply quantity), or induce price-fixing (when each firm is allowed to vary the supply quantity), the latter of which leads to extreme unfairness of surplus division. To overcome these issues, we propose a new rental-market mechanism that trades the usage-right of solar panels instead of real-time solar energy. We show that the rental market produces a stable and unique price (therefore eliminating price-volatility), maintains positive surplus for both consumers and firms (therefore eliminating price-fixing), and achieves the same social welfare as the traditional real-time market. A key insight is that rental markets turn uncertainty of renewable generation from a detrimental factor (that leads to price-volatility in real-time markets) to a beneficial factor (that increases demand elasticity and contributes to the desirable rental-market outcomes).more » « less
-
This paper studies a satellite transponder’s communication channel, in which there exist multiple-user terminals, who compete for limited radio resources to meet their own data rate needs. Because inter-user interference limits on the satellite transponder’s performance, the transponder’s power-control system needs to coordinate all its users to reduce interference and maximizes overall performance. A non-cooperative Differential Game (DG) is set up to model the users’ competition in a transponder’s communication channel. Each user’s utility function is a trade-off between transmission data rate and power consumption. Nash Equilibrium (NE) is defined to be the solution of the DG model. The optimality condition of NE is derived to be a set of Differential Algebraic Equations (DAE). An algorithm based on minimizing Hamiltonians is developed to solve the DAE system. The numerical solution of the DG model provides the transponder’s power control system with each user’s power-control strategy at the equilibrium.more » « less
-
This paper studies controlling segregation in social networks via exogenous incentives. We construct an edge formation game on a directed graph. A user (node) chooses the probability with which it forms an inter- or intra- community edge based on a utility function that reflects the tradeoff between homophily (preference to connect with individuals that belong to the same group) and the preference to obtain an exogenous incentive. Decisions made by the users to connect with each other determine the evolution of the social network. We explore an algorithmic recommendation mechanism where the exogenous incentive in the utility function is based on weak ties which incentivizes users to connect across communities and mitigates the segregation. This setting leads to a submodular game with a unique Nash equilibrium. In numerical simulations, we explore how the proposed model can be useful in controlling segregation and echo chambers in social networks under various settings.more » « less
-
Traditional systems for allocating finite cluster resources among competing jobs have either aimed at providing fairness, relied on users to specify their resource requirements, or have estimated these requirements via surrogate metrics (e.g. CPU utilization). These approaches do not account for a job’s real world performance (e.g. P95 latency). Existing performance-aware systems use offline profiled data and/or are designed for specific allocation objectives. In this work, we argue that resource allocation systems should directly account for real-world performance and the varied allocation objectives of users. In this pursuit, we build Cilantro. At the core of Cilantro is an online learning mechanism which forms feedback loops with the jobs to estimate the resource to performance mappings and load shifts. This relieves users from the onerous task of job profiling and collects reliable real-time feedback. This is then used to achieve a variety of user-specified scheduling objectives. Cilantro handles the uncertainty in the learned models by adapting the underlying policy to work with confidence bounds. We demonstrate this in two settings. First, in a multi-tenant 1000 CPU cluster with 20 independent jobs, three of Cilantro’s policies outperform 9 other baselines on three different performance-aware scheduling objectives, improving user utilities by up to 1.2 − 3.7x. Second, in a microservices setting, where 160 CPUs must be distributed between 19 inter-dependent microservices, Cilantro outperforms 3 other baselines, reducing the end-to-end P99 latency to x0.57 the next best baseline.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3390/g12030061
