Geodesic
Cost-sharing in Parking Games
Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 3.

Voir la notice de l'article provenant de la source Episciences

In this paper, we study the total displacement statistic of parking functions from the perspective of cooperative game theory. We introduce parking games, which are coalitional cost-sharing games in characteristic function form derived from the total displacement statistic. We show that parking games are supermodular cost-sharing games, indicating that cooperation is difficult (i.e., their core is empty). Next, we study their Shapley value, which formalizes a notion of "fair" cost-sharing and amounts to charging each car for its expected marginal displacement under a random arrival order. Our main contribution is a polynomial-time algorithm to compute the Shapley value of parking games, in contrast with known hardness results on computing the Shapley value of arbitrary games. The algorithm leverages the permutation-invariance of total displacement, combinatorial enumeration, and dynamic programming. We conclude with open questions around an alternative solution concept for supermodular cost-sharing games and connections to other areas in combinatorics.
DOI : 10.46298/dmtcs.13113
Classification : 05A05, 91A12, 91A46 
@article{DMTCS_2024_26_3_a3,
     author = {Elder, Jennifer and Harris, Pamela E. and Kretschmann, Jan and Mori, J. Carlos Mart{\'\i}nez},
     title = {Cost-sharing in {Parking} {Games}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2024},
     doi = {10.46298/dmtcs.13113},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13113/}
}
TY  - JOUR
AU  - Elder, Jennifer
AU  - Harris, Pamela E.
AU  - Kretschmann, Jan
AU  - Mori, J. Carlos Martínez
TI  - Cost-sharing in Parking Games
JO  - Discrete mathematics & theoretical computer science
PY  - 2024
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13113/
DO  - 10.46298/dmtcs.13113
LA  - en
ID  - DMTCS_2024_26_3_a3
ER  - 
%0 Journal Article
%A Elder, Jennifer
%A Harris, Pamela E.
%A Kretschmann, Jan
%A Mori, J. Carlos Martínez
%T Cost-sharing in Parking Games
%J Discrete mathematics & theoretical computer science
%D 2024
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13113/
%R 10.46298/dmtcs.13113
%G en
%F DMTCS_2024_26_3_a3
Elder, Jennifer; Harris, Pamela E.; Kretschmann, Jan; Mori, J. Carlos Martínez. Cost-sharing in Parking Games. Discrete mathematics & theoretical computer science, Tome 26 (2024) no. 3. doi : 10.46298/dmtcs.13113. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.13113/

Cité par Sources :