The vertex cover game: Application to transport networks

Omega. 2020. Vol. 97. P. 102102.

Vasily V. Gusev

As communications are progressing, transport networks need to be monitored, more specifically, camera surveillance of violations is needed. Standards are being developed on how to install cameras, and the question of efficiently distributing surveillance devices across the road network ensue. This task is addressed in this paper by using the methods of the cooperative game theory. The vertex cover game is introduced, and its properties are studied. Since surveillance cameras are to cover all areas of the network, the characteristic function depends on the vertex covers of the graph. The Shapley–Shubik index is used as the measure of centrality. The Shapley–Shubik index is shown to be efficient in a vertex cover game for the allocation of cameras in a transport network. Proceeding from the Shapley–Shubik indices calculated in this study, recommendations were given for the allocation of surveillance cameras in a specific transport network in a district of the City of Petrozavodsk, Russia.

Keywords: индекс Шепли-Шубика, vertex cover, Shapley–Shubik index, Minimal winning coalitions, Simple cooperative games, вершинное покрытие, минимальные выигрывающие коалиции, простые кооперативные игры

Publication based on the results of: Allocation and social choice mechanisms: axioms, incentives, algorithms (2020)