Research map / Learning theory and algorithms / Submodular and game algorithms

Epistemic Pairwise Maximin Share

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Fair division of indivisible goods · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Initiates the study of epistemic pairwise maximin share (EPMMS), proving 4/5-EPMMS existence for additive valuations, exact EPMMS for bivalued (via EGMMS), three additive agents, and two agent types.

Problem

Fair division of indivisible goods: existence of PMMS (and its epistemic relaxation) allocations, which is open for arbitrary additive agents, while EFX and MMS may fail or are hard in general.

Approach

Defines epistemic PMMS, where each agent only needs a hypothetical repartition of others' items (keeping its own bundle) that certifies PMMS. Shows 4/5-EPMMS for additive valuations via envy-cycle elimination on identical rankings with a careful analysis, and extends bivalued MMS algorithms with leximin partitions to obtain EGMMS.

Key results

• Every additive instance admits a 4/5-EPMMS allocation, computable in polynomial time.
• Every bivalued instance admits an EGMMS (hence EPMMS) allocation computable in polynomial time.
• EPMMS exists for three additive agents (simultaneously with IMMP) and for instances with two additive agent types.

Surprising findings

• The envy-cycle elimination analysis of prior work for 4/5-PMMS has gaps; a single envy-cycle step can only guarantee 2/3-PMMS from an exact PMMS allocation in general.
• Even PMMS and MMS simultaneously do not imply EGMMS under identical additive valuations.

Limitations

• Exact EPMMS for general additive valuations (even four agents) remains open.
• The 4/5-EPMMS result requires non-degenerate valuations in the identical-rankings analysis.
• Bivalued and few-agent/few-type results are restricted settings.

Experimental setup

Metrics: approximation factor of EPMMS existence of EPMMS/EGMMS allocations

Baselines: EEFX 0.781-PMMS 0.618-PMMS MMS

Builds on: EEFX envy cycle elimination PMMS GMMS PMMS-feasibility

Closest papers by meaning

• Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.94)
• Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.93)
• On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.91)
• Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.90)
• (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.90)
• The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)