Towards Fair and Efficient Public Transportation: A Bus Stop Model

We consider a stylized formal model of public transportation, where a set of agents need to travel along a given road, and there is a bus that runs the length of this road. Each agent has a left terminal and a right terminal between which they wish to travel; they can walk all the way, or walk to/from the nearest stop and use the bus for the rest of their journey. The bus can make a fixed number of stops, and the planner needs to select locations for these stops. We study notions of efficiency and fairness for this setting. First, we give a polynomial-time algorithm for computing a solution that minimizes the total travel time; our approach can capture further extensions of the base model, such as more general cost functions or existing infrastructure. Second, we develop a polynomial-time algorithm that outputs solutions with provable fairness guarantees (such as a variant of the justified representation axiom or 2-approximate core). Our simulations indicate that our algorithm almost always outputs fair solutions, even for parameter regimes that do not admit theoretical guarantees.