Please click here if you are unable to view this page.
TOPIC:
FAIR CONGESTION
ABSTRACT
We initiate a normative approach to a common congestion problem where agents must be assigned, fairly and efficiently, to heterogenous public items subject to congestion. Examples include distributing messages between multiple congested carriers, workers in crowded office spaces, jobs to busy servers, or students to heterogenous team projects.
We study two symmetric models where congestion is either unanimously bad or unanimously good: it can slow down the carriers, or protect them from potential dangers. In each case a participant selects a menu of acceptable congestion levels over the different items (maximal level in the former case, minimal in the latter). Ex ante fairness is captured by a canonical Fair Share guarantee.
Ex post fairness strengthens the Fair Share: it is defined as an ad hoc version of Envy Freeness. When congestion is bad, it singles out a unique fractional/randomised congestion profile, approximated up to one unit of congestion by deterministic assignments.
If congestion is good, Envy Free assignments--whether fractional or deterministic--always exist but they often allow multiple congestion profiles and must be refined, for instance by an egalitarian selection.