GPT 6 Astra Ultra attempt on Econ-400

PMMS for MMS-feasible pair-demand valuations: a research attempt

Target and outcome

Status: unresolved. The general existence of complete PMMS allocations for MMS-feasible, non-additive pair-demand valuations is not proved here. This attempt gives a four-item witness theorem that makes MMS-feasibility checkable in polynomial time from the singleton/pair table, a bottleneck formula for checking PMMS, two exact existence subcases, and an explicit obstruction to extending a partial allocation.

The source's Definition 2.8 uses additive values for the best two goods, whereas its Open Problem 5 asks about the broader non-additive class in this catalogue [pmms]. The distinction is essential. This attempt does not treat the source's positive result for additive top-two values as a solution to the broader question.

Finite representation and two-way maximin shares

Let $m=|M|$. Store $v(\emptyset)=0$, all $m$ singleton values, and all $\binom m2$ pair values, with nonnegative rational values and $v(\{g,h\})\geq\max(v(\{g\}),v(\{h\}))$. Extend to all bundles by the maximum over subsets of size at most two. This defines exactly a normalized monotone pair-demand valuation with those table entries.

Write $\mathcal W(S)=\{U\subseteq S:|U|\leq2\}$. Empty witnesses are included. Then \[ \mu^2(S)= \max_{\substack{U,V\in\mathcal W(S)\\U\cap V=\emptyset}} \min\{v(U),v(V)\}. \]

Consequently a proposed allocation can be checked for PMMS using $O(n^2m^4)$ rational comparisons, up to polynomial encoding factors. One need not enumerate the exponentially many bipartitions of each union. This verification result by itself does not produce an allocation.

Every failure of MMS-feasibility has at most four items

There are $O(m^4)$ such subsets, and each has at most sixteen ordered bipartitions. Checking every ordered pair of their bipartitions therefore takes $O(m^4)$ comparisons with a constant independent of $m$. For general explicit rational tables, this is a polynomial-time membership test for the promised valuation class. It also supplies a compact certificate when a proposed computational counterexample fails the hypothesis.

Threshold graphs explain the restriction

Fix a level $t\geq0$ and retain only goods with $v(\{g\})\leq t$. Join two retained goods when $v(\{g,h\})>t$. A low-valued bundle is exactly an independent set in this graph. A violation at level $t$ therefore consists of a bipartite induced subgraph with two disjoint edges: its two color classes are low, while the two edges form disjoint high witnesses.

It is enough to inspect the four endpoints of those edges. On four vertices, a bipartite graph with a matching of size two contains, as its whole induced graph, two disjoint edges, a four-vertex path, or a four-cycle. Conversely each of these three patterns admits a split into two independent sets and two disjoint high edges, producing a violation. Thus MMS-feasibility is equivalent to forbidding those patterns in every such level graph. A high singleton cannot occur in a violating subset because whichever part contains it is already high.

Only finitely many levels between table values matter. The direct four-item algorithm avoids discretizing levels and uses strict comparisons exactly. This graph characterization does not impose a common vertex ordering across levels; assuming one without proof would add an unstated restriction.

For example, take four goods with all singleton values zero, pair values one on $12$ and $34$, and zero on every other pair. The partition $(12,34)$ has minimum one, while $(13,24)$ has maximum zero. This natural complementary-pairs construction is pair-demand but is not MMS-feasible, so it cannot disprove the problem.

Two existence subcases

For two agents, let agent 1 choose a bipartition attaining her two-way maximin share, and let agent 2 take a highest-valued part. Agent 1 receives at least her share whichever part remains. MMS-feasibility of agent 2 implies that the larger value of this particular partition is at least her maximum possible partition minimum. Both agents therefore satisfy PMMS, and every good is assigned. This proof needs MMS-feasibility only for the chooser, and makes no additive assumption.

For any number of agents with an identical valuation $v$, choose a complete allocation maximizing the sorted vector of bundle values lexicographically, from smallest to largest. Such an allocation exists because there are finitely many complete allocations. If an agent had $v(A_i)<\mu^2(A_i\cup A_j)$, repartition that union into two bundles each worth at least the latter threshold. Both new values exceed the smaller old value. In the sorted list, no value below that smaller old value changes, and the number of occurrences of it decreases; thus the lexicographic objective improves, a contradiction. This proves PMMS for identical valuations, even without pair demand or MMS-feasibility. Positive agent-specific rescalings of the same valuation inherit this argument after normalization.

Why completing a partial solution remains difficult

The empty allocation is partial PMMS, but arbitrary completion can break it. With two agents having identical additive-top-two unit values on two goods, allocating both goods to agent 1 leaves agent 2 with zero although her two-way share of their union is one. Splitting them works, but the example shows that monotonicity of own-bundle values does not protect pairwise fairness when another bundle expands.

For a computational search, first generate valid singleton/pair tables, apply the four-item hypothesis check to every agent, and then enumerate all $n^m$ complete allocations, using the disjoint-witness formula to test each. A negative instance must retain the full tables and certify failure of every allocation; a positive finite search does not imply general existence. The algorithms here are exact finite procedures and structural reductions, not a claim that exhaustive enumeration is efficient in the number of goods.

The remaining step is a constructive argument coupling the different agents' level graphs through all thresholds, or a certified counterexample satisfying every four-item test. Neither two-agent cut-and-choose nor the identical-valuation lexicographic potential supplies that coupling. The full conjecture remains unresolved by this attempt.

Completion Estimate

46%

This is a post hoc, heuristic estimate for the full catalogue target. Disjoint small witnesses and forbidden threshold graphs give a polynomial feasibility test, while cut-and-choose and leximin prove complete PMMS for restricted agent profiles. Heterogeneous many-agent valuations still require a simultaneous allocation construction or an admissible counterexample to settle the full existence question.

References

• [pmms] J. Byrka, F. Malinka and T. Ponitka (2025), Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division, arXiv:2507.14957v2. Primary text inspected: Definitions 2.6 and 2.8, Section 6, and Open Problem 5. https://arxiv.org/html/2507.14957v2.