Chen, J. (2024, December 11). Fairness in Assignments with Congestion-Averse Agents: Concepts, Algorithms, and Complexity [Presentation]. Algorithmics of Fair Division and Social Choice Workshop on Voting, Matching, and Preference Aggregation, Singapore. http://hdl.handle.net/20.500.12708/210387
E192-01 - Forschungsbereich Algorithms and Complexity
-
Date (published):
11-Dec-2024
-
Event name:
Algorithmics of Fair Division and Social Choice Workshop on Voting, Matching, and Preference Aggregation
en
Event date:
9-Dec-2024 - 13-Dec-2024
-
Event place:
Singapore
-
Keywords:
Social Choice; Competitiveness; Envy-freeness
en
Abstract:
The congested assignment problem is concerned with assigning agents to posts where agents care about both the posts and their congestion levels. Here, agents are averse to congestion, consistently preferring lower over higher congestion for the same resource. Such scenarios are prevalent across many domains, including traffic management and school choice, where fair resource allocation is crucial. Congested assignment can be considered as a restricted variant of the Group Activity Selection problem, introduced by Darmann et al. Additionally, it is related to many-to-one matching in matching under preferences.
In this talk, I will explore one ex-ante fairness concept, top-fairness, and two ex-post fairness concepts, envy-freeness and competitiveness. The top-fairness and competitiveness concepts were recently introduced by Bogomolnaia and Moulin. While a top-fair or envy-free assignment always exists and can be found easily, competitive assignments do not always exist. The talk will cover the following key points:
1. An efficient method to determine the existence of competitive or maximally competitive assignments for a given congestion profile.
2. Two optimization variants of congested assignments and their computational complexity: a) Finding a top-fair assignment that is envy-free b) Finding a top-fair assignment that is maximally competitive. Both variants are NP-hard, unfortunately.
3. Parameterized algorithms for these NP-hard problems.