Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient ComputabilityOberseminar Discrete Optimization

by Thorben Tröbst (University of California, Irvine)

Monday Jan 6, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

Given a set of agents and an equally large set of goods where each agent 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 (envy-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 until Chen et al. (SODA 2022) showed it to be PPAD-hard.

In this talk, I will show that the problem of finding any envy-free and Pareto-optimal matching is by itself PPAD-hard via an interesting construction relying on key insights about such matchings. On the other hand, I will show that the Nash bargaining mechanism which was proposed by Hosseini and Vazirani (ITCS 2022) results in 2-approximately envy-free and Pareto-optimal matchings.

This talk is based on joint work with Vijay Vazirani (EC 2024)

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.