Cost-sharing in Parking Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912106184441856 |
|---|---|
| author | Elder, Jennifer Harris, Pamela E. Kretschmann, Jan Mori, J. Carlos Martínez |
| author_facet | Elder, Jennifer Harris, Pamela E. Kretschmann, Jan Mori, J. Carlos Martínez |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_12265 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cost-sharing in Parking Games Elder, Jennifer Harris, Pamela E. Kretschmann, Jan Mori, J. Carlos Martínez Combinatorics Discrete Mathematics Computer Science and Game Theory 05A05, 91A12, 91A46 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. |
| title | Cost-sharing in Parking Games |
| topic | Combinatorics Discrete Mathematics Computer Science and Game Theory 05A05, 91A12, 91A46 |
| url | https://arxiv.org/abs/2309.12265 |