Future low-carbon societies will need to store vast amounts of electricity to stabilize electricity grids and to power electric vehicles. Vehicle-to-grid allows vehicle owners and grid operators to share the costs of electricity storage by making the batteries of electric vehicles available to the grid. In practice, vehicle owners decide when to reserve their cars for driving and when to make them available for grid services. Vehicle aggregators then decide how to commit the vehicles to grid services. For vehicle-to-grid to succeed, both vehicle owners and grid operators must be able to trust aggregators, i.e., vehicles should be available for driving and for grid services when the aggregators promise they will be. In this thesis, we solve a decision-making problem that ensures reliable commitments by vehicle aggregators for a particular grid service known as primary frequency regulation, considered one of the most profitable applications of vehicle-to-grid. Mathematically, we first formulate a robust optimization problem with functional uncertainties that maximizes the expected profit from selling primary frequency regulation to grid operators and guarantees that vehicle owners can meet their market commitments for all frequency deviation trajectories in an uncertainty set that encodes applicable European Union regulations. Functional uncertainties ensure that vehicle owners and grid operators can trust the decisions of aggregators at all times. Faithfully modeling the energy conversion losses during battery charging and discharging renders the optimization problem nonconvex. By exploiting a total unimodularity property of the proposed uncertainty sets and an exact linear decision rule reformulation, we prove that the nonconvex robust optimization problem with functional uncertainties is equivalent to a tractable linear program. Somewhat counterintuitively, the underlying deterministic problem for a known frequency deviation trajectory does not reduce to a linear program but results in a large-scale mixed-integer linear program, even if time is discretized. We believe that we have thus discovered the first practically interesting class of optimization problems that become dramatically easier through robustification. Through extensive numerical experiments using real-world data, we quantify the economic value of vehicle-to-grid and elucidate the financial incentives of vehicle owners, aggregators, equipment manufacturers, and regulators. In particular, we find that the prevailing penalties for non-delivery of promised regulation power are too low to incentivize aggregators to honor their promises toward grid operators. For general electricity storage devices, we then solve a simplified version of the decision-making problem analytically to understand how the optimal frequency regulation commitments depend on the roundtrip efficiency of the storage device, the dispersion of the frequency deviations, and the EU delivery guarantee. We show how the marginal cost of frequency regulation decreases with roundtrip efficiency and increases with frequency deviation dispersion. For energy-constrained storage devices, we find that the profits from frequency regulation are inversely proportional to the length of time for which storage operators commit regulation power. Establishing an intra-day market for frequency regulation would thus make electricity storage devices more competitive with other regulation providers, such as thermal power plants.