Existence Questions in Discrete Allocation and Data ExchangeLecture

by Dr Hannaneh Akrami

Tuesday Nov 3, 2026, 8:15 AM → 9:00 AM Europe/Berlin

Endenicher Allee 60/1-016 - Lipschitzsaal (Mathezentrum)

Existence questions are central to mathematical economics and theoretical computer science: given desirable properties, is there always an outcome satisfying all of them? This talk presents one negative and one positive answer.

First, we settle the central open problem in fair division of indivisible goods. When m items are divided among n agents with monotone valuations, must there be an EFX allocation, one in which no agent envies another’s bundle after removing any single item from it? We show that the answer is no. For n ≥ 3 and m ≥ n + 5, there are submodular instances with no EFX allocation. The proof reduces the question to Boolean satisfiability, and the same reduction proves existence for n = 3 and m = 7.

Second, we study the exchange of data, which, unlike classical goods, can be copied at no cost. We prove that reciprocal and core-stable exchanges always exist for monotone continuous utilities. The feasible set is not convex, so standard fixed-point theorems do not apply directly. Instead, we construct a homeomorphism onto a convex compact set, apply Brouwer’s theorem, and pass to a limit.