d4-conf-sagt-2023-0003

The strongest clean anchor is Proposition 2, proved in this paper. For \(n\) agents with cost utilities and \(n+2\) indivisible goods, it gives a picking sequence for Sequential Allocation that is strategyproof and returns a Pareto-efficient MMS allocation. Goods are ordered by cost. If \(c(g_4)>c(g_2)+c(g_3)\), the sequence is \(1,2,\ldots,n-1,n,n,n\); otherwise it is \(1,2,\ldots,n-1,n,n,n-1\). The paper presents this as a polynomial-time algorithm. The proposition’s contribution is the joint guarantee of strategyproofness, Pareto efficiency, and every agent receiving their maximin fair share in that \(n+2\)-good setting.

A plausible high-multiplicity setting is a large region allocating standardized, indivisible benefit vouchers to residents. Voucher categories have public costs; each resident either finds a category useful or does not. Millions of residents may fall into a small number \(\tau\) of approval types, while the number \(N\) of residents is large. Voucher stock scales with the population. In the regime of Proposition 2, there are \(N+2\) vouchers, so supply approaches one voucher per resident. This is a co-modification of the model forced by continuizing the population: the supply must scale too. Each resident still receives an integral bundle; only the distribution of bundles across a type’s mass can be fractional.

Here is the corresponding prover-ready question.

Unit-Supply High-Multiplicity MMS Mechanism. An instance specifies a finite set \(J\) of voucher categories, nonnegative rational costs \(c_j\), a finite report domain \(\mathcal T\) of approval sets, and a rational population distribution \(\mu\) over \(\mathcal T\), with support size \(\tau\). The per-capita supply vector \(b\) is rational and satisfies \(\sum_{j\in J} b_j=1\), representing limits of \(N+2\) indivisible vouchers for \(N\) residents. A resident of true type \(t\) values an integral bundle \(z\in\mathbb Z_{\ge0}^{J}\) at
\[ u_t(z)=\sum_{j\in t} c_jz_j. \]

Define the continuous MMS benchmark \(M_t(b,c)\) as the largest \(v\) for which there is a distribution \(\pi\) over integral bundles with \(\mathbb E_\pi[z_j]=b_j\) for every \(j\), and \(\pi\)-almost every bundle has \(u_t(z)\ge v\). It is the limiting version of partitioning the scaled stock into one bundle per resident and maximizing the least-valued bundle for type \(t\).

The question is whether there is a polynomial-time direct mechanism which, for every rational \(\mu\), returns a menu of bundle distributions \((\pi_r^\mu)_{r\in\mathcal T}\) such that:

• under truthful reports, aggregate use is feasible and each type-\(t\) resident receives a bundle worth at least \(M_t(b,c)\) with probability one;
• the resulting allocation is Pareto efficient among feasible measurable assignments of integral bundles; and
• truthful reporting is dominant: for every pair of types \(t,r\), \(\mathbb E_{\pi_t^\mu}[u_t(z)]\ge \mathbb E_{\pi_r^\mu}[u_t(z)]\).

A single resident has zero mass, so a unilateral report changes their own menu choice while leaving the population distribution \(\mu\) unchanged. That makes the incentive condition meaningful at the individual level. The question does not impose strategyproofness against a positive-mass coalition.

I would initially expect this full mirror to be continuum-specifically hard (Class C). The continuous allocation side has a natural configuration formulation over integral bundles, but simultaneously satisfying MMS, Pareto efficiency, and incentive constraints across reports may create its own obstruction. A solution could instead uncover a tractable configuration or column-generation method, especially for fixed \(J\) and \(\mathcal T\). That is an open classification question, not a complexity conclusion from Proposition 2.

The paper’s Theorem 2 supports the plausibility of this domain: it proves that MMS allocations always exist for cost utilities with laminar approval sets, for any number of agents. It is proved here, but it asserts existence rather than a complexity class, so I would not use it as a computational anchor. The paper’s numbered results also include Proposition 3, which proves that for \(n=2,m=5\) there is an instance with cost utilities for which no strategyproof mechanism can guarantee a Pareto-efficient MMS allocation. That is a significant strategic impossibility, though it is not an NP-hardness result and I would not count it as a second computational anchor. The paper’s NP-hard MMS-value statement appears in the prose, not as a numbered hardness theorem.

The mirror covers Proposition 2’s combined strategic and fairness guarantee in its high-multiplicity regime. It does not extend the paper’s three-agent theorem or laminar-approval existence theorem to all continuous societies, and it does not continuize the outcome space: bundles remain indivisible. Its intended question is whether the per-capita society admits a strategyproof, Pareto-efficient MMS mechanism.

The weakest point is the anchor’s reliance on a finite picking order and exactly two extra goods. In the proposed limit, those two goods vanish per capita, and the priority order becomes continuous. The paper’s mechanism therefore does not establish the mirror or its polynomial-time solvability. The authors would still recognize the question’s underlying problem—cost-utility allocation with MMS, Pareto efficiency, and strategyproofness—but the continuous problem tests whether their guarantee survives after the resource slack and priority structure change.