EconCS Seminar

 

Lecturer: 

Tomasz Ponitka (TAU)

Title: 

Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

Abstract: 

We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of EFX. Our first result constructs a three-agent instance with two monotone valuations and one additive valuation in which no PMMS allocation exists. Since EFX allocations are known to exist under these assumptions, this establishes a formal separation between EFX and PMMS. 

We prove the existence of fair allocations for three important special cases. We show that EFX allocations exist for personalized bivalued valuations, where for each agent i there exist values a_i>b_i such that agent i assigns value vi({g})∈{a_i,b_i} to each good g. We establish an analogous existence result for PMMS allocations when a_i is divisible by b_i. We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations, where each bundle S has value v_i(S)∈{0,1}. Notably, this result holds even without assuming monotonicity of valuations and thus applies to the fair division of chores and mixed manna. Finally, we study a class of valuations called pair-demand valuations, which extend the well-studied unit-demand valuations to the case where each agent derives value from at most two items, and we show that PMMS allocations exist in this setting. Our proofs are constructive, and we provide polynomial-time algorithms for all three existence results.

 

Authors: Jarosław Byrka, Franciszek Malinka, Tomasz Ponitka

Arxiv link: https://arxiv.org/pdf/2507.14957

Venue: AAAI 2026

 

Location: 

Room 130, Feldman Building, Edmond J. Safra Campus.

Click here to add the EconCS Seminar to your Google Calendar