Answer: polynomial-time solvable
Corollary 6.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any instance with pair-demand valuations, a PMMS allocation can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given complete pair-demand types \(T\), rational type masses \(\mu_t\), item-category supplies \(\rho_g\) with \(\sum_g \rho_g=2\), and weights \(w_{t,g}\), find masses \(\pi_{t,B}\) over integral two-item multisets \(B\) satisfying \(\sum_B \pi_{t,B}=\mu_t\) and \(\sum_{t,B}\pi_{t,B}n_g(B)=\rho_g\), such that every positive-support pair \( (t,B),(u,D) \) satisfies \(v_t(B)\ge \max_{A\uplus A'=B\uplus D}\min\{v_t(A),v_t(A')\}\).
Let \(T\) and \(G\) be finite, explicitly listed sets of types and item categories. The input gives rational masses \(\mu_t\geq 0\) with \(\sum_t\mu_t=1\), rational supplies \(\rho_g\geq 0\) with \(\sum_g\rho_g=2\), and a nonnegative rational weight \(w_{t,g}\) for every type and category. For a multiset \(S\), let \(v_t(S)=\max_{A\subseteq S,\ |A|\leq 2}\sum_{g\in A}w_{t,g}\), counting repeated items separately.
Find nonnegative rational masses \(\pi_{t,B}\) over two-item multisets \(B\) such that \(\sum_B\pi_{t,B}=\mu_t\) and \(\sum_{t,B}\pi_{t,B}n_g(B)=\rho_g\). Require that every two positive-support pairs \((t,B)\) and \((u,D)\) satisfy \(v_t(B)\geq\max_{A\uplus A'=B\uplus D}\min\{v_t(A),v_t(A')\}\), where the maximum ranges over all partitions of the four-item multiset.
Is this continuous allocation problem solvable in polynomial time, or is it NP-hard?
For a finite list of agents with pair-demand valuations, a PMMS allocation can be computed in polynomial time. No complexity result for the exact mass allocation problem above was verified.
The problem is polynomial-time solvable. Every valid input admits an exact rational allocation satisfying the stated support condition. The algorithm below produces at most \(|T|+|G|-1\) positive entries.
The construction compresses the forward-then-reverse picking procedure used for finite pair-demand instances in [Algorithm 3 of *Probing EFX via PMMS*](https://ojs.aaai.org/index.php/AAAI/article/download/38716/42678). We prove both fairness and polynomial-time compression explicitly.
1. A four-item lemma. Fix a type, and write the weights of two bundles as \(B=(a,b)\) and \(D=(c,d)\), with \(a\ge b\ge0\) and \(c\ge d\ge0\). Then
\( v(B)<\max_{A\uplus A'=B\uplus D}\min\{v(A),v(A')\} \quad\Longleftrightarrow\quad c>a\ \text{and}\ d>b. \)
Here and throughout, repeated items are treated as separate occurrences.
To prove this, first observe that it suffices to consider partitions into two pairs. A partition into an empty set and four items has minimum value zero. For a partition into a singleton and a triple, move a lowest-weight item of the triple to the singleton. The triple’s value is unchanged because the valuation counts only its two highest weights; the singleton’s value cannot decrease because weights are nonnegative.
There are three partitions into pairs. The original partition cannot give both parts value strictly greater than \(a+b\). The partition \((a,d),(b,c)\) gives both parts value strictly greater than \(a+b\) exactly when \(d>b\) and \(c>a\). Finally, if the partition \((a,c),(b,d)\) gives both parts value strictly greater than \(a+b\), then \(b+d>a+b\), so \(d>a\). Consequently \(c\ge d>a\) and \(d>b\). This proves the equivalence.
Thus, writing \(M_t(B)\) and \(m_t(B)\) for the larger and smaller item weights in \(B\), respectively, the required inequality for the ordered comparison of \(B\) against \(D\) holds exactly when
\( M_t(B)\ge M_t(D) \quad\text{or}\quad m_t(B)\ge m_t(D). \)
2. Fairness of the finite picking procedure. Consider any finite list of \(N\) agents and exactly \(2N\) item occurrences. Fix an agent order and deterministic rules for breaking ties between categories.
First, agents pick a highest-weight remaining item in forward order. Then they pick a highest-weight remaining item in reverse order. Let agent \(i\)’s first and second picks be \(g_i\) and \(h_i\), so its bundle is \(B_i=\{g_i,h_i\}\).
Fix agents \(i<j\).
For the comparison evaluated by agent \(i\), both occurrences assigned to \(j\) were available when \(i\) chose \(g_i\). Therefore
\( w_{i,g_i}\ge\max\{w_{i,g_j},w_{i,h_j}\}, \)
and hence \(M_i(B_i)\ge M_i(B_j)\). The lemma proves the required inequality for \(i\).
For the comparison evaluated by agent \(j\), the occurrence eventually chosen as \(h_i\) was available at both of \(j\)’s picks: all first picks precede all second picks, and the second round runs in reverse order. Therefore
\( w_{j,g_j}\ge w_{j,h_i} \quad\text{and}\quad w_{j,h_j}\ge w_{j,h_i}. \)
Consequently,
\( m_j(B_j)\ge w_{j,h_i}\ge m_j(B_i), \)
so the lemma proves the required inequality for \(j\).
This covers both directions for every pair of distinct agents. Comparing a bundle with itself also satisfies the lemma.
3. Exact implementation with compressed multiplicities. Discard zero-mass types and zero-supply categories temporarily. Let their remaining numbers be \(n\) and \(m\).
Choose a positive integer \(Q\) divisible by every denominator appearing in the masses and supplies; their product suffices. Define integer counts
\( N_t=Q\mu_t,\qquad C_g=Q\rho_g. \)
Then \(\sum_tN_t=Q\) and \(\sum_gC_g=2Q\). Conceptually, create \(N_t\) agents of each type and \(C_g\) occurrences of each category. Order the agents in consecutive type blocks.
We never explicitly create this potentially enormous instance. Instead, simulate the procedure using integer counts.
For the first round, initialize residual supplies \(R_g=C_g\). Process the types in their fixed order. For a type \(t\), let \(r=N_t\) be its number of agents still awaiting their first pick. While \(r>0\):
This record represents \(c\) consecutive agents of type \(t\), all receiving category \(g\) as their first item.
For the second round, process these records in reverse order. For each record \((t,g,c)\), let \(r=c\). While \(r>0\):
Initialize all allocation entries to zero, and interpret \(\{g,h\}\) as a multiset, including when \(g=h\).
These batches reproduce the finite picking procedure exactly. Within a first-round batch, the same type repeatedly picks the same highest-weight category until either that category is exhausted or the type block ends. Reversing the record list reverses the order of those consecutive agent blocks. Within each such block, all agents have the same type and first item, so second-round choices can likewise be batched until the block or the selected category is exhausted.
4. Verification of every allocation requirement. The first round allocates exactly \(Q\) item occurrences, leaving exactly \(Q\) for the second round. Thus a positive residual supply always exists whenever a pick remains to be made.
Each first-round record of size \(c\) produces second-round batches whose sizes sum to \(c\). Since the records for type \(t\) have total size \(N_t\),
\( \sum_B\pi_{t,B}=\frac{N_t}{Q}=\mu_t. \)
Both rounds together exhaust every category’s count. A batch with bundle \(\{g,h\}\) accounts for one occurrence from each round, including two occurrences of the same category if \(g=h\). Therefore
\( \sum_{t,B}\pi_{t,B}n_g(B)=\frac{C_g}{Q}=\rho_g. \)
All output masses are nonnegative rationals.
Now consider any two positive-support pairs \((t,B)\) and \((u,D)\). Each occurs among the agents of the conceptual finite allocation. If the pairs are distinct, their occurrences belong to distinct agents, and Section 2 proves the required ordered comparison. If the pairs coincide, the self-comparison follows directly from the four-item lemma. Hence the condition holds across the entire support, including between different bundles assigned positive mass to the same type.
5. Polynomial running time and output size. Let \(q_1\) be the number of categories exhausted during the first round, and let \(K\) be the number of first-round records.
Every first-round iteration finishes a type block or exhausts a category, possibly both. Hence
\( K\le n+q_1. \)
Exactly \(q_2=m-q_1\) categories remain positive for the second round. Every second-round iteration finishes a record or exhausts a category. Its last iteration necessarily does both, since all records and all residual supplies finish together. Thus the number \(L\) of second-round batches satisfies
\( L\le K+q_2-1 \le n+q_1+q_2-1 =n+m-1. \)
Merging batches with identical type and bundle can only reduce the support size.
A direct implementation scans the categories at each iteration, using \(O(m(n+m))\) weight comparisons and polynomially many integer operations.
Finally, although \(Q\) may be exponentially large in numerical value, its binary length is at most the sum of the binary lengths of the input denominators. Every count manipulated by the algorithm is an integer between zero and \(2Q\), and every output mass has denominator \(Q\) before reduction. All arithmetic and rational weight comparisons therefore have polynomial bit complexity.
This proves exact polynomial-time solvability in the binary encoding of the given input.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes exact polynomial-time solvability of the stated rational mass allocation problem, including the condition on every ordered pair of positive-support entries. No major or minor issues were found.
The reduction to partitions into two pairs is valid. Moving a lowest-weight occurrence from a triple to a singleton preserves the triple’s pair-demand value and cannot decrease the singleton’s value. An empty part gives minimum value zero and cannot witness a strict violation.
The three pair partitions exhaust the possibilities, including repeated categories because occurrences are distinguished. The calculations are correct:
Negating the resulting strict-violation criterion gives precisely the stated disjunction involving \(M_t\) and \(m_t\). Ties and zero weights are handled correctly.
For \(i<j\), both of agent \(j\)’s eventual item occurrences remain available at agent \(i\)’s first pick. Thus the claimed maximum-weight inequality holds, regardless of ties.
Conversely, agent \(i\)’s second occurrence remains available at both of agent \(j\)’s picks. Both of agent \(j\)’s item weights therefore dominate that occurrence’s weight, establishing the claimed minimum-weight inequality.
These arguments evaluate each comparison using the evaluating agent’s own weights, as required. They cover all distinct-agent comparisons. The lemma also covers self-comparisons.
The chosen \(Q\) makes all \(N_t\) and \(C_g\) integers, with totals \(Q\) and \(2Q\). The potentially large number of conceptual agents is never enumerated.
Each first-round batch is a consecutive block of identical-type agents selecting the same category under the fixed category tie-breaking rule. Processing records in reverse order reproduces the second-round order. Within a record, agents have identical types and first categories, so batching second picks preserves the resulting allocation.
Each batch has positive integer size. The total residual supply guarantees that a category is available whenever an iteration requires a pick.
The record totals establish the type-mass equalities exactly. Exhaustion of category counts establishes the supply equalities, with repeated-category bundles correctly consuming two occurrences.
Every positive output entry has a conceptual-agent witness. Distinct support pairs necessarily have distinct witnesses, including when their types coincide but their bundles differ. The finite fairness argument therefore transfers to every required ordered comparison. Coincident support pairs satisfy the lemma directly.
Discarded zero-mass types and zero-supply categories receive only zero entries, consistent with the initialization. The normalization assumptions ensure that at least one positive type and category remain.
Every first-round iteration completes a type block or exhausts a category, giving \(K\le n+q_1\).
Every second-round iteration completes a record or exhausts a remaining category. Its last iteration does both: all remaining demand and supply terminate together. Consequently,
\(L\le K+q_2-1\le n+m-1\).
Merging identical entries cannot increase support. Since \(n\le |T|\) and \(m\le |G|\), the advertised bound of \(|T|+|G|-1\) follows.
The product of the input denominators has polynomial binary length. The counts are bounded by \(2Q\), so their representation lengths remain polynomial throughout.
The iteration bounds justify the stated \(O(m(n+m))\) weight comparisons. Comparisons of input rational weights and arithmetic on the counts have polynomial bit complexity. Accumulating allocation numerators over the common denominator \(Q\) also preserves polynomial representation length.
Thus the compression addresses the essential obstacle: running time does not depend polynomially on the numerical value of \(Q\).
The cited Algorithm 3 does use forward picks followed by reverse picks; its input requirement is satisfied by the conceptual instance with exactly twice as many items as agents. [Probing EFX via PMMS, Algorithm 3](https://ojs.aaai.org/index.php/AAAI/article/download/38716/42678)
More importantly, the submitted argument proves the relevant fairness property and the compression itself. Its complexity conclusion does not rely on transferring a finite-instance running-time bound to exponentially many agents.
Required clarification or repair: none.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.