Impressive improvements of efficiency and safety of vehicles have been achieved over the last decade, but increasing traffic density and drivers' age accentuate the need of further improvements. The contributions summarized in this chapter argue that a substantial additional fuel benefit can be achieved by extending the well introduced Adaptive Cruise Control in a predictive sense, e.g. taking into account a predicted behavior of other traffic components. This chapter starts by discussing results on the potential benefits in the ideal case (full information, no limits on computing power) and then examines how much of the potential benefits is retained if approximate solutions are used to cope with a realistic situation, with limited information and computing power. Two setups are considered: vehicles exchanging a small set of simple data over a V2V link and the case of mixed traffic, in which some vehicles will not provide any information, but the information must be obtained by a probabilistic estimator. The outcome of these considerations is that the approach is able to provide-statistically-a substantial fuel consumption benefit without affecting negatively the driveability or the driver comfort like other methods, e.g. platooning, would. © Springer International Publishing Switzerland 2014.