BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Cardinal-Utility Matching Markets: The Quest for Envy-Freeness\, P
 areto-Optimality\, and Efficient Computability [Oberseminar Discrete Optim
 ization]
DTSTART:20250106T171500Z
DTEND:20250106T181500Z
DTSTAMP:20260415T095200Z
UID:indico-event-138@math-events.uni-bonn.de
DESCRIPTION:Speakers: Thorben Tröbst (University of California\, Irvine)\
 n\nGiven a set of agents and an equally large set of goods where each agen
 t has some non‑negative utility for each good\, is there a way to find a
  (fractional) perfect matching between agents and goods which is fair (env
 y-free) and efficient (Pareto-optimal)? This question was posed by Hylland
  and Zeckhauser (JPE 1979) who proved the existence of such matchings in a
  non-constructive way\, leaving computer scientists scrambling for decades
  to find a polynomial time implementation of this so-called HZ mechanism u
 ntil Chen et al. (SODA 2022) showed it to be PPAD-hard.\nIn this talk\, I
  will show that the problem of finding any envy-free and Pareto-optimal ma
 tching is by itself PPAD-hard via an interesting construction relying on k
 ey insights about such matchings. On the other hand\, I will show that the
  Nash bargaining mechanism which was proposed by Hosseini and Vazirani (IT
 CS 2022) results in 2-approximately envy-free and Pareto-optimal matchings
 .\nThis talk is based on joint work with Vijay Vazirani (EC 2024)\nThe Obe
 rseminar takes place in the Seminarraum\, 1st floor. Participants are invi
 ted to have coffee or tea in the lounge before.\n\nhttps://math-events.uni
 -bonn.de/event/138/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/138/
END:VEVENT
END:VCALENDAR