<div class="csl-bib-body">
<div class="csl-entry">Chen, J. (2024, December 11). <i>Fairness in Assignments with Congestion-Averse Agents: Concepts, Algorithms, and Complexity</i> [Presentation]. Algorithmics of Fair Division and Social Choice Workshop on Voting, Matching, and Preference Aggregation, Singapore. http://hdl.handle.net/20.500.12708/210387</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/210387
-
dc.description.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.
en
dc.language.iso
en
-
dc.subject
Social Choice
en
dc.subject
Competitiveness
en
dc.subject
Envy-freeness
en
dc.title
Fairness in Assignments with Congestion-Averse Agents: Concepts, Algorithms, and Complexity
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.type.category
Presentation
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.author.orcid
0000-0002-8163-1327
-
tuw.event.name
Algorithmics of Fair Division and Social Choice Workshop on Voting, Matching, and Preference Aggregation
en
tuw.event.startdate
09-12-2024
-
tuw.event.enddate
13-12-2024
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.country
SG
-
tuw.event.presenter
Chen, Jiehua
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairecristype
http://purl.org/coar/resource_type/R60J-J5BD
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.fulltext
no Fulltext
-
item.openairetype
conference presentation
-
item.grantfulltext
none
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
