  A key obstacle to increasing renewable energy penetration in the power grid
is the lack of utility-scale storage capacity. Transportation electrification
has the potential to overcome this obstacle since Electric Vehicles (EVs) that
are not in transit can provide battery storage as a service to the grid. This
is referred to as EV-Power grid integration, and could potentially be a key
milestone in the pathway to decarbonize the electricity and the transportation
sectors. We first show that if EV-Power grid integration is not done carefully,
then contrary to improving the cost efficiency of operating the grid, it could
in fact be counterproductive to it. This fundamentally occurs due to two
phenomena operating in tandem - the randomness of EV usage patterns and the
possibility of strategic behavior by EV operators. We present a market-based
solution to address this issue. Specifically, we develop a mechanism for energy
storage markets using which the system operator can efficiently integrate a
fleet of strategic EVs with random usage patterns into the grid, utilize them
for storage, and satisfy the demand at minimum possible cost.
