Cost allocations in Shortest Path games

Publisher's full text
Mark Voorneveld
Sofia Grahn

A class of cooperative games arising from shortest path problems is defined. These shortest path games are totally balanced and allow a population-monotonic allocation scheme. Possible methods for obtaining core elements are indicated; first, by relating to the allocation rules in taxation and bankruptcy problems, second, by constructing an explicit rule that takes opportunity costs into account by considering the costs of the second best alternative and that rewards players who are crucial to the construction of the shortest path. The core and the bargaining sets of Davis-Maschler and Mas-Colell are shown to coincide. Finally, noncooperative games arising from shortest path problems are introduced, in which players make bids or claims on paths. The core allocations of the cooperative shortest path game coincide with the payoff vectors in the strong Nash equilibria of the associated noncooperative shortest path game.

LATEST NEWS


2017-11-30

Millions for research into maritime transport and the environment

Maritime transport is a major source of emissions of harmful air pollutants and carbon dioxide. In a new project, a research team from the Swedish National Road and Transport Research Institute (VTI) and the University of Gothenburg has received SEK 6.4...


2017-11-30

New research programme for more efficient travel

The Swedish National Road and Transport Research Institute (VTI) is playing an important role in a major new research programme to find radical solutions leading to fewer trips and more efficient travel, along with tools to enable better use of roads and...


2017-11-30

Simulator used to practice emergency responses safely

Emergency responses of the police, ambulance, and rescue services are associated with a high risk of accidents, but practicing them in real traffic is neither safe nor permissible. A simulator-based method developed by the Swedish National Road and Transport...


2017-10-26

Simulation of cut-in by manually driven vehicles in platooning scenarios

A study in a VTI-driving simulator has showed that a platoon will be able to handle a cut in from a manually driven car. The results of this study have recently been presented at two conferences in Japan.


2017-10-16

ERPUG Forum

The five-year anniversary of European Road Profile Users' Group (ERPUG) Forum will take place at Ramboll head quarter, Copenhagen, Denmark October 19-20, 2017.


2017-09-29

Self-driving buses in Sweden next year?

A self-driving, fossil-free bus. This idea might become reality through a forthcoming collaborative project involving the Swedish National Road and Transport Research Institute (VTI), Linköping University and several other participants. The project group aim...