Balanced EF1 and fPO Allocations

Does every instance of indivisible goods with additive valuations admit a balanced allocation (any two bundles differing in size by at most one) that is simultaneously envy-free up to one good (EF1) and fractionally Pareto optimal (fPO)? Kawase et al. established existence only for personalized bivalued valuations or at most two valuation types. Proved in general, via the Knaster-Kuratowski-Mazurkiewicz lemma applied to a weighted-welfare duality framework plus a new price interlacing lemma.

The paper records how the collaboration actually went: the authors first aimed at a counterexample showing EF1 and PO incompatible under matroid constraints, and when the model surfaced fundamental difficulties with that plan they redirected toward proving the positive result instead. The paper also extends the technique to category constraints and leaves a pseudopolynomial-time algorithm open.