On the Efficiency of Nash Equilibria in Charging Games
We consider charging problems, where the goal is to coordinate the charge of a fleet of electric vehicles by means of a distributed algorithm. Several works have recently modelled the problem as a game, and thus proposed algorithms to coordinate the vehicles towards a Nash equilibrium. However, Nash equilibria have been shown to posses desirable system-level properties only in simplified cases, and it is unclear to what extent these results generalise. In this work, we use the game theoretic concept of price of anarchy to analyze the inefficiency of Nash equilibria when compared to the centralized social optimum solution. More precisely, we show that i) for linear price functions depending on all the charging instants, the price of anarchy always converges to one as the population of vehicles grows and ii) for price functions that depend only on the instantaneous demand, the price of anarchy converges to one if the price function takes the form of a positive pure monomial. For finite populations, iii) we provide a bound on the price of anarchy as a function of the number vehicles in the system. We support the theoretical findings by means of numerical simulations.
READ FULL TEXT