
arXiv: 2309.12265
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.
FOS: Computer and information sciences, computer science - computer science and game theory, Discrete Mathematics (cs.DM), mathematics - combinatorics, Exact enumeration problems, generating functions, cooperative games, computer science - discrete mathematics, Cooperative games, 05a05, 91a12, 91a46, Computer Science - Computer Science and Game Theory, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Shapley value, Combinatorics (math.CO), parking functions, 05A05, 91A12, 91A46, Mathematics, Computer Science - Discrete Mathematics, Computer Science and Game Theory (cs.GT)
FOS: Computer and information sciences, computer science - computer science and game theory, Discrete Mathematics (cs.DM), mathematics - combinatorics, Exact enumeration problems, generating functions, cooperative games, computer science - discrete mathematics, Cooperative games, 05a05, 91a12, 91a46, Computer Science - Computer Science and Game Theory, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Shapley value, Combinatorics (math.CO), parking functions, 05A05, 91A12, 91A46, Mathematics, Computer Science - Discrete Mathematics, Computer Science and Game Theory (cs.GT)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
