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

We investigate congested assignment problems where agents have preferences over both resources and their associated congestion levels. These agents are 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 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 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.