Feedback Congestion Games and their Application to Charging Electric Vehicles

In classical congestion games the players (or consumers) pay for the resources they consume according to the congestion over the resources. A common scenario, in which consumers also sell resources, cannot be naturally modelled using classical congestion games. A generalization of congestion games, feedback congestion games (FCG), in which players play the role of both consumer and producer, is introduced. FCGs are proven to be exact potential games and therefore converge to a pure-strategy Nash equilibrium by an iterated better-response process. The implication of FCGs is demonstrated by an example of electric vehicles charging. The charging of grid-integrated vehicles, which can also discharge energy back to the grid, is a natural FCG application. A compact representation and an algorithm that enable efficient best-response search are presented. A detailed empirical evaluation assesses the performance of the iterated best-response process. The evaluation considers the quality of the resulting solutions and the rate of convergence to a stable state. The effect of allowing to also discharge batteries using FCG is compared to scenarios that only include charging and is found to dramatically improve the predictability of the achieved solutions as well as the balancing of load.