On the Efficiency of Nash Equilibria in Aggregative Charging Games

Several works have recently suggested to model the problem of coordinating the charging needs of a fleet of electric vehicles as a game, and have proposed distributed algorithms to coordinate the vehicles towards a Nash equilibrium of such game. However, Nash equilibria have been shown to posses desirable system-level properties only in simplified cases. In this letter, we use the concept of price of anarchy (PoA) to analyze the inefficiency of Nash equilibria when compared to the social optimum solution. More precisely, we show that: 1) for linear price functions depending on all the charging instants, the PoA converges to one as the population of vehicles grows; 2) for price functions that depend only on the instantaneous demand, the PoA converges to one if the price function takes the form of a positive pure monomial; and 3) for general classes of price functions, the asymptotic PoA can be bounded. For finite populations, we additionally provide a bound on the PoA as a function of the number vehicles in the system. We support the theoretical findings by means of numerical simulations.

I. Introduction

In the last decade we have witnessed a profound change in the way energy systems are operated. A new paradigm called demand response is emerging, according to which the energy requirements of a population of users are tuned, by means of incentives, to account for the operational needs of the power grid [1]. Previous works [2], [3] have suggested to model these demand response methods as a game. Therein each player represents a user that needs to optimize his energy consumption over a given period of time, with the objective of minimizing his electricity bill. What couples the users, and thus makes the charging problem a game, is the assumption that the energy price depends at every instant of time on the sum of the energy demand of the whole population. The seminal paper [2] shows that the (unique) Nash equilibrium of such game has desirable properties from the standpoint of the grid operator, in the case of large and homogeneous populations. Under these assumptions, [2] shows that the equilibrium is socially optimum in the sense that it minimizes the collective electricity bill (including the cost of both flexible and inflexible demand) and fills the overnight demand valley. As a result, a rich body of literature has focused on devising distributed and decentralized schemes that are numerically efficient, and can be used by the grid operator to coordinate the strategies of the agents to a Nash equilibrium [2]–[7]. Less attention has been devoted to verify whether the optimality statement made in [2] is still valid in the presence of more general cost functions, agents heterogeneity and realistic charging constraints (e.g., upper bounds on the instantaneous charging, different charging windows, ramping constraints). Nonetheless, this is a fundamental prerequisite for the applicability of the aforementioned coordination schemes.¹

While there are multiple factors impacting the choice of a control scheme, if the Nash equilibria do not posses desirable properties, the grid operator has limited incentive in coordinating the agents to such a strategy profile.