Assignments for Congestion-Averse Agents: Seeking Competitive and Envy-Free Solutions

Abstract

We investigate congested assignment problems where agents have preferences over both resources and their associated congestion levels. These agents are \emph{averse} towards congestion, i.e., consistently preferring lower congestion for identical resources. Such scenarios are ubiquitous across domains including traffic management and school choice, where fair resource allocation is essential. We focus on the concept of \emph{competitiveness}, recently introduced by Bogomolnaia and Moulin [6], and contribute a polynomial-time algorithm that determines competitiveness, resolving their open question. Additionally, we explore two optimization variants of congested assignments by examining the problem of finding envy-free or maximally competitive assignments that guarantee a certain amount of social welfare for every agent, termed \emph{top-guarantees} [6]. While we prove that both problems are NP-hard, we develop parameterized algorithms with respect to the number of agents or resources.