| paper | A Polynomial-Time Algorithm for Fair and Efficient Allocation with a Fixed Number of Agents |
| authors | Ryoga Mahara |
| venue | WINE 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1.1
statement extracted from the paper’s text layer
Given fixed \(\tau\), rational type masses \(\mu_\theta\), additive values \(v_{\theta g}\), and rational per-capita supplies \(\sigma_g\) for indivisible good kinds, compute masses \(x_{\theta,b}\) over integral bundles \(b\in\mathbb{Z}_{\ge 0}^{m}\) satisfying \(\sum_b x_{\theta,b}=\mu_\theta\) and \(\sum_{\theta,b}b_gx_{\theta,b}\le\sigma_g\), such that every pair of supported cells satisfies \(v_\theta(b)\ge v_\theta(b')-\max(\{v_{\theta g}:b'_g>0\}\cup\{0\})\), and no feasible fractional reassignment weakly improves every positive-mass cell while strictly improving one.
A high-multiplicity indivisible-goods fair-division model with fixed complete valuation types \(\Theta\), population masses \(\mu\), per-capita supplies \(\sigma\), integral bundle configurations \(b\), mass variables \(x_{\theta,b}\), support-wise EF1, and cell-wise continuous fPO.
Theorem 1.1's proof relies on sequentially inserting named agents and an \(n\)-indexed potential, so it provides no polynomial bound for a mass allocation in which one type is split across many bundles; cell-wise EF1 and continuous fPO require genuinely new configuration-level arguments.
fatal: False
The mirror covers the EF1-and-fPO algorithmic result in Theorem 1.1 and the Nash-welfare approximation in Theorem 1.2. It leaves aside chores, unrestricted valuation classes, unrestricted numbers of types, and the paper's finite-agent error analysis.
The strongest positive case is a high-multiplicity fair-division mirror in which the population of agents becomes continuous, while each individual still receives an integral bundle of indivisible goods. The paper has no named NP-hardness theorem of its own: its remarks that Nash social welfare is NP-hard are literature claims, not numbered results proved here. I therefore use its two main algorithmic theorems as anchors.
Take a finite set of complete valuation types \(\Theta=\{\theta_1,\ldots,\theta_\tau\}\), with rational population masses \(\mu_\theta\ge 0\) summing to \(1\). Type \(\theta\) has additive values \(v_{\theta g}\) for good kinds \(g\in G=\{1,\ldots,m\}\). There are also rational per-capita supplies \(\sigma_g\): in a finite realization with population size \(N\), there are \(N\sigma_g\) indivisible copies of good kind \(g\). Each individual may receive an integral bundle \(B\subseteq G\), with value
\[ v_\theta(B)=\sum_{g\in B}v_{\theta g}. \]
The continuous allocation variable is \(x_{\theta,B}\), the mass of type-\(\theta\) agents receiving bundle \(B\). Thus
\[ \sum_{B\subseteq G}x_{\theta,B}=\mu_\theta \]
and
\[ \sum_{\theta}\sum_{B\ni g}x_{\theta,B}=\sigma_g. \]
The aggregate variables are fractional, but every unit of population mass receives an integral bundle. This is not divisible-goods fair division.
A direct population lift of EF1 requires that for every pair of supported cells \(x_{\theta,B}>0\) and \(x_{\theta',B'}>0\),
\[ v_\theta(B)\ge v_\theta(B')-\max_{g\in B'}v_{\theta g}. \]
Thus every represented individual is EF1 with respect to every other represented individual. Likewise, continuous fPO means that there is no fractional reassignment \(z_{\theta,B,g}\) which respects the aggregate supplies, weakly improves the utility of every positive-mass cell, and strictly improves at least one positive-mass cell. This is exactly the paper’s fPO definition after normalizing a finite repeated instance.
The regime is plausible in course allocation, staffing, or housing: perhaps \(N=10^5\) students but only \(\tau=20\) complete valuation/eligibility types, with course-seat capacities proportional to \(N\). A type includes every feature relevant to valuation and feasibility, so there is no hidden individual-specific price or budget. For rational data, choosing \(N\) to clear all denominators converts the mass instance into a finite instance with \(N\mu_\theta\) agents and \(N\sigma_g\) indivisible goods. Conversely, repeated finite agents normalize to such a distribution. This gives a genuine high-multiplicity dictionary rather than merely replacing integers by reals.
My lead anchor is Theorem 1.1, proved in the paper:
When each agent has an additive valuation function and the number of agents is fixed, an EF1 and fPO allocation can be computed in polynomial time.
The body proves correctness in Theorem 4.1 and termination and polynomial running time for fixed \(n\) in Theorem 4.5. The continuous problem I would hand to a prover is:
*Continuous Fixed-Type EF1-fPO Allocation.* Given \((\Theta,\mu,G,\sigma,V)\) as above, with \(\tau\) fixed, compute a mass allocation \(x_{\theta,B}\) whose bundles are integral, which satisfies the supply constraints, support-wise EF1, and continuous fPO.
The expected classification is Class A. The paper’s algorithm already identifies the relevant structure: prices, MBB edges, pEF1, and a Fisher-market certificate for fPO. In the mirror, the sequential insertion of named agents becomes the insertion of finitely many valuation types, while masses determine how much population is transferred along the resulting MBB structure. A configuration-LP or column-generation formulation can represent mixtures of integral bundles, and the fixed parameter should be \(\tau\), not the total population size \(N\). The important point is that the mirror retains the paper’s actual fairness and efficiency questions; it does not replace EF1 by an arbitrary average-utility condition or make each good divisible for each agent.
The main further questions are whether support-wise EF1 can be maintained while a type is split across several bundles, whether a polynomial-size mass representation always exists, and whether the price/MBB operations admit a separation oracle whose complexity is polynomial in \(m,\tau\), and the input bit length. If \(\tau\) is allowed to grow, the problem may instead become Class B or Class C.
A useful secondary anchor is Theorem 1.2, also proved in the paper, with its proof supplied in Appendix A:
When the number of agents is fixed and valuations are additive, there is a polynomial-time \(e^{1/e}\)-approximation algorithm for Nash social welfare. The resulting allocation also satisfies EF1 and fPO.
For the same continuous instance, define
\[ \operatorname{NSW}_\infty(x) = \exp\!\left( \sum_{\theta,B}x_{\theta,B}\log v_\theta(B) \right), \]
with value \(0\) when a positive-mass cell has zero utility. This is the exact continuum limit of the finite Nash social welfare: if \(Nx_{\theta,B}\) agents receive \(B\), then their contribution to the finite geometric mean is precisely the corresponding exponential term above.
The associated problem is:
*Continuous NSW-EF1-fPO Allocation.* Given \((\Theta,\mu,G,\sigma,V)\), compute an integral-bundle mass allocation \(x\) satisfying continuous EF1 and fPO such that
\[ \operatorname{NSW}_\infty(x) \ge e^{-1/e} \max_y \operatorname{NSW}_\infty(y), \]
where the maximum ranges over all feasible mass allocations into integral bundles.
I would also expect this version to be Class A in the repeated-copy regime. At the population level, mixtures of integral bundles remove the named-agent partition obstruction while preserving integral treatment of each individual. The continuous NSW objective has an exact finite-expansion interpretation, and the remaining algorithmic issue is a configuration or pricing problem rather than the identities of \(N\) separate agents. If one instead keeps all goods unique and does not scale supply with the population, the model ceases to be a convincing high-multiplicity regime and discrete NSW hardness may return.
The weakest point is that the paper fixes the total number of agents, whereas the mirror has many agents and fixes only the number of types. Replacing \(n\) by \(\tau\) is a natural high-multiplicity translation, but it is not a theorem in the paper. Moreover, support-wise EF1 is stronger than merely comparing type-average utilities, so the continuous algorithm is genuinely open rather than an immediate restatement.
Still, the mirror is credible: it preserves indivisible individual bundles, the paper’s EF1 definition, its fPO notion, and its Nash-welfare objective; only the repeated population is compressed into masses. It covers Theorems 1.1 and 1.2, not the paper’s results on chores, arbitrary valuation classes, or one-off finite-agent instances.
The strongest case against the proposed mirror is that neither theorem’s computational content is actually about population multiplicity. Theorem 1.1 is polynomial only because the number of named agents \(n\) is fixed. Its proof depends on inserting one agent at a time and on a potential vector with coordinates indexed by \(0,\ldots,n\). That structure does not survive replacing agents by valuation types.
In the proposed model, agents of one type may receive many different bundles. Exact EF1 therefore has to be imposed on allocation cells \((\theta,B)\), not merely on types:
\[ v_\theta(B)\ge v_\theta(B')-\max_{g\in B'}v_{\theta g} \]
whenever both cells have positive mass. The population masses \(\mu_\theta\) do not appear in this condition. If one aggregates all bundles received by a type and checks only its average utility, one has abandoned the paper’s EF1 notion. If one retains the bundle cells, there can be exponentially many of them, and a type cannot be inserted as a single “new agent” in the paper’s algorithm. Thus “replace fixed \(n\) by fixed \(\tau\)” is not a translation of Theorem 1.1; it is a new configuration-allocation problem.
The same issue affects fPO. In the finite paper, Pareto improvement may benefit one named agent. In an atomless society, that notion is either invisible if strict improvement is required only on a null set, or must be changed to require improvement on a positive-measure population. A cell-wise version can also conceal improvements to only a submass of a type. These are reasonable new definitions, but none is simply the paper’s fPO notion with \(n\) replaced by a real population. The continuous model must choose a welfare order that the paper never studies.
Theorem 1.2 is a weaker anchor. The continuum Nash-welfare expression
\[ \operatorname{NSW}_\infty(x) = \exp\!\left(\sum_{\theta,B}x_{\theta,B}\log v_\theta(B)\right) \]
is indeed the correct per-capita limit for repeated finite instances. But that only shows that a new optimization problem is well-defined. The paper’s approximation algorithm is inherited from its EF1-and-fPO construction; it gives no algorithm for the mass problem. Once agents and goods are repeated, the relevant pricing problem is over integral bundle configurations, with constraints coupling all positively supported cells. The fixed-agent proof supplies no separation oracle, no bounded-support theorem, and no reason that fixed \(\tau\) controls the resulting configuration complexity.
There is also a basic dichotomy. If the number of goods remains fixed while the population grows, most agents receive nothing and the limit becomes a degenerate abundance-of-agents problem. If goods are duplicated with per-capita supply, the resulting course-market or housing-market model is sensible, but it is no longer merely the paper’s allocation problem with a continuous population: both the resource side and the allocation state have been rebuilt. That may be a valuable research problem, but it is evidence for a new high-multiplicity fair-division programme, not for a mirror of this paper’s theorem.
This is the strongest negative case, but it is not decisive. The repeated-copy regime is a legitimate high-multiplicity scenario; identities are irrelevant once valuation types and allocation bundles are specified; EF1 does not automatically degenerate; and the Nash-welfare limit is mathematically natural. Consequently, I cannot honestly defeat the two anchors universally. The fair conclusion is that the paper does not itself provide a continuous mirror, but the proponent has identified a credible new one. The negative case should therefore be scored as a warning that the mirror is a substantial configuration-LP research problem, not as a convincing claim that it is unworthwhile.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.