Epistemic Pairwise Maximin Share
For researchers in fair division, this work advances understanding of PMMS by providing existence and computation results under epistemic relaxation, though the guarantees are weaker than full PMMS.
The paper introduces epistemic pairwise maximin share (EPMMS), a relaxation of PMMS for fair division of indivisible goods, and shows that 4/5-EPMMS allocations exist for additive valuations, EPMMS allocations exist for bivalued valuations and in settings where MMS allocations may not exist (three additive agents or two types of additive agents).
We introduce epistemic pairwise maximin share (EPMMS), a new fairness notion for fair division of indivisible goods. Two fundamental notions in this setting are envy-freeness up to any item (EFX) and pairwise maximin share (PMMS), with PMMS being stronger than EFX. While EFX has been extensively studied, far less is known about PMMS. Recent work shows that relaxing EFX via an epistemic perspective leads to substantial progress on the EFX problem, raising the question of whether a similar approach can advance our understanding of PMMS. Motivated by this, we initiate the study of EPMMS, the epistemic relaxation of PMMS. EPMMS is more challenging than EEFX: the key approaches underlying recent progress on epistemic EFX inherently fail to extend to EPMMS. We establish the following results. (1) For additive valuations, $4/5$-EPMMS allocations exist and can be efficiently computed. (2) For bivalued valuations, EPMMS allocations exist and can be efficiently computed; in fact, we obtain the stronger guarantee of epistemic groupwise maximin share (EGMMS), which also strengthens the existence of MMS allocations for this setting. (3) We prove that EPMMS allocations exist in two settings where MMS allocations need not exist: instances with three additive agents or two types of additive agents.