Jennifer Elder ; Pamela E. Harris ; Jan Kretschmann ; J. Carlos Martínez Mori - Cost-sharing in Parking Games

dmtcs:13113 - Discrete Mathematics & Theoretical Computer Science, November 4, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.13113
Cost-sharing in Parking GamesArticle

Authors: Jennifer Elder ; Pamela E. Harris ; Jan Kretschmann ; J. Carlos Martínez Mori

    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.


    Volume: vol. 26:3
    Section: Combinatorics
    Published on: November 4, 2024
    Accepted on: September 7, 2024
    Submitted on: February 25, 2024
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,Computer Science - Computer Science and Game Theory,05A05, 91A12, 91A46

    Classifications

    Consultation statistics

    This page has been seen 77 times.
    This article's PDF has been downloaded 31 times.