
Electric vehicles (EVs) are expected to be a major component of the smart
grid. The rapid proliferation of EVs will introduce an unprecedented load on
the existing electric grid due to the charging/discharging behavior of the EVs,
thus motivating the need for novel approaches for routing EVs across the grid.
In this paper, a novel gametheoretic framework for smart routing of EVs within
the smart grid is proposed. The goal of this framework is to balance the
electricity load across the grid while taking into account the traffic
congestion and the waiting time at charging stations. The EV routing problem is
formulated as a noncooperative game. For this game, it is shown that selfish
behavior of EVs will result in a purestrategy Nash equilibrium with the price
of anarchy upper bounded by the variance of the ground load induced by the
residential, industrial, or commercial users. Moreover, the results are
extended to capture the stochastic nature of induced ground load as well as the
subjective behavior of the owners of EVs as captured by using notions from the
behavioral framework of prospect theory. Simulation results provide new
insights on more efficient energy pricing at charging stations and under more
realistic grid conditions.

Motivated by emerging resource allocation and data placement problems such as
web caches and peertopeer systems, we consider and study a class of resource
allocation problems over a network of agents (nodes). In this model, nodes can
store only a limited number of resources while accessing the remaining ones
through their closest neighbors. We consider this problem under both
optimization and gametheoretic frameworks. In the case of optimal resource
allocation we will first show that when there are only k=2 resources, the
optimal allocation can be found efficiently in O(n^2\log n) steps, where n
denotes the total number of nodes. However, for k>2 this problem becomes
NPhard with no polynomial time approximation algorithm with a performance
guarantee better than 1+1/102k^2, even under metric access costs. We then
provide a 3approximation algorithm for the optimal resource allocation which
runs only in linear time O(n). Subsequently, we look at this problem under a
selfish setting formulated as a noncooperative game and provide a
3approximation algorithm for obtaining its pure Nash equilibria under metric
access costs. We then establish an equivalence between the set of pure Nash
equilibria and flipoptimal solutions of the MaxkCut problem over a specific
weighted complete graph. Using this reduction, we show that finding the
lexicographically smallest Nash equilibrium for k> 2 is NPhard, and provide an
algorithm to find it in O(n^3 2^n) steps. While the reduction to weighted
MaxkCut suggests that finding a pure Nash equilibrium using best response
dynamics might be PLShard, it allows us to use tools from quadratic
programming to devise more systematic algorithms towards obtaining Nash
equilibrium points.

In this paper, the problem of energy trading between smart grid prosumers,
who can simultaneously consume and produce energy, and a grid power company is
studied. The problem is formulated as a singleleader, multiplefollower
Stackelberg game between the power company and multiple prosumers. In this
game, the power company acts as a leader who determines the pricing strategy
that maximizes its profits, while the prosumers act as followers who react by
choosing the amount of energy to buy or sell so as to optimize their current
and future profits. The proposed game accounts for each prosumer's subjective
decision when faced with the uncertainty of profits, induced by the random
future price. In particular, the framing effect, from the framework of prospect
theory (PT), is used to account for each prosumer's valuation of its gains and
losses with respect to an individual utility reference point. The reference
point changes between prosumers and stems from their past experience and future
aspirations of profits. The followers' noncooperative game is shown to admit a
unique purestrategy Nash equilibrium (NE) under classical game theory (CGT)
which is obtained using a fully distributed algorithm. The results are extended
to account for the case of PT using algorithmic solutions that can achieve an
NE under certain conditions. Simulation results show that the total grid load
varies significantly with the prosumers' reference point and their
lossaversion level. In addition, it is shown that the power company's profits
considerably decrease when it fails to account for the prosumers' subjective
perceptions under PT.