# Fair Ride Allocation on a Line

arXiv: https://arxiv.org/abs/2007.08045 · HTML: https://mlsanity.com/paper/2007.08045/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 1 of 1)

- [Data-Driven Methods for Balancing Fairness and Efficiency in Ride-Pooling](https://mlsanity.com/paper/2110.03524/) (2021)

## Abstract (arXiv)

The airport game is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This paper extends it to the so-called assignment setting, that is, for multiple facilities and agents, each agent chooses a facility to use and shares the cost with the other agents. Such a situation can be often seen in sharing economy, such as sharing fees for office desks among workers, taxis among customers of possibly different destinations on a line, and so on. Our model is regarded as a coalition formation game based on the fair cost-sharing of the airport game; we call our model a fair ride allocation on a line. As criteria of solution concepts, we incorporate Nash stability and envy-freeness into our setting. We show that a Nash-stable feasible allocation that minimizes the social cost of agents can be computed efficiently if a feasible allocation exists. For envy-freeness, we provide several structural properties of envy-free allocations. Based on these, we design efficient algorithms for finding an envy-free allocation when at least one of (1) the number of facilities, (2) the capacity of facilities, and (3) the number of agent types, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show the NP-hardness of determining the existence of an allocation under two relaxed envy-free concepts.