| paper | Truthful Fair Mechanisms for Allocating Mixed Divisible and Indivisible Goods |
| authors | Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results construct and certify mechanisms, but none asserts the complexity of a computational problem, such as polynomial-time solvability, hardness, FPT, or approximation. The proposed repeated-market \(\mu\)-model is a plausible population continuization, but plausibility cannot cure the missing computational anchor. Therefore the paper is red under the stated rule.
fails bit a — no named computational result to mirror
The proposed mirror covers Theorem 4.1 directly in spirit and Theorem 5.4 tentatively; it leaves Theorem 3.1, Corollary 3.2, Theorem 5.3, and the MNW impossibility unaddressed.
The strongest positive case is narrow but credible, and it is anchored by Theorem 4.1. I would not pretend that this paper contains a conventional complexity theorem: no named result here says “in P”, “NP-hard”, “FPT”, or similar. Theorem 4.1 is instead an explicit constructive algorithmic result. If “computational result” is read strictly as a complexity-class statement, this paper has no eligible anchor. Under the broader and more natural reading for mechanism design, Theorem 4.1 is a good anchor.
My lead mirror is Continuum Water-Filling Mixed Allocation.
The intended regime is a large course-allocation or resource-allocation market. There are many students or users, but only a small number of distinct valuation types: students of the same programme, cohort, or preference pattern value the same course seats in the same binary way. Let \(G\) be a finite set of indivisible-good categories, let \(T\) be a finite set of types, and let \(\mu_t\) be the fraction of the population of type \(t\). A type \(t\) is identified by a subset \(S_t\subseteq G\): it values one copy of \(g\) at \(1\) if \(g\in S_t\), and at \(0\) otherwise. All agents have the same public value \(u>0\) for one homogeneous divisible resource, such as money or compute credits.
To keep the indivisibility genuine, \(G\) denotes categories of individually indivisible copies, not fractions of goods. A scale-\(N\) discrete realization has \(N\mu_t\) agents of type \(t\), \(Nq_g\) copies of each indivisible good \(g\), and \(Nq_d\) units of the divisible resource. The continuous object is the population distribution \(\mu\); the supplies merely scale with the size of the market. This is a sensible high-multiplicity setting for course seats or repeated resource licences, and has \(N\gg |T|\).
A type-level allocation is a distribution over integral bundles and divisible-resource quantities. Write \(\lambda_{t,B,x}\) for the mass of type-\(t\) agents receiving indivisible bundle \(B\in\mathbb Z_{\ge0}^{G}\) and divisible amount \(x\ge0\). It must satisfy \( \sum_{B,x}\lambda_{t,B,x}=\mu_t \), \( \sum_{t,B,x}\lambda_{t,B,x}B_g\le q_g \) for every \(g\), and \( \sum_{t,B,x}\lambda_{t,B,x}x\le q_d \). An agent of type \(t\) has utility \(v_t(B,x)=\sum_{g\in S_t}B_g+ux\).
The continuous problem is:
Given \(G,T,\mu,(q_g)_{g\in G},q_d\), and \(u\), construct a succinct direct-revelation mechanism whose high-multiplicity allocation is EFM\(^{\ge0}\), truthful, and Lorenz-maximal in the resulting utility distribution. Equivalently, on every finite integer expansion, it must be truthful, EFM\(^{\ge0}\), leximin, and MNW, while its normalized allocation has the stated type-level limit.
EFM\(^{\ge0}\) is imposed pairwise on positive-mass allocation cells. If a type-\(t\) agent receives \((B,x)\) and another agent receives \((B',x')\), then, when \(x'=0\) and \(B'\neq\varnothing\), there must be a copy \(g\) in \(B'\) such that \(v_t(B,x)\ge v_t(B'-e_g,x')\); otherwise \(v_t(B,x)\ge v_t(B',x')\).
Truthfulness should be defined through the finite expansions, rather than through a literal unilateral deviation by a measure-zero point in an atomless society. Thus the compressed mechanism is correct if, for every sufficiently large \(N\), its expansion to \(N\mu_t\) labelled agents is dominant-strategy truthful. This preserves the strategic content of the paper while using \(\mu\) as the computational input.
The intended algorithm is exactly the structure of Mechanism 1: first compute a high-multiplicity MNWtie/leximin allocation of the indivisible copies, then water-fill the divisible resource among the agents with minimum current utility. The continuous water-filling step is especially natural: it raises the bottom utility level of a positive-mass cohort until either that cohort catches the next utility level or the resource is exhausted.
This mirrors Theorem 4.1, proved in this paper. The theorem states that Mechanism 1 is EFM\(^{\ge0}\) and truthful, and that its output is both leximin and MNW. Its proof uses Theorem 2.6, which is cited from Halpern et al. (2020), and Proposition 4.6, cited from Babaioff et al. (2021). The continuous question preserves every substantive feature of the theorem: binary valuations on indivisible goods, one common divisible resource, EFM fairness, truthfulness, and the leximin/MNW objective. Only named-agent multiplicity is replaced by a distribution of repeated types.
I expect this mirror to be Class A, although the paper itself does not prove that complexity classification. The water-filling part is one-dimensional and type-compressible. The remaining computation is a high-multiplicity binary fair-allocation problem, plausibly expressible through a flow or configuration LP whose size depends on \(m\), \(|T|\), and the encoding length of \(\mu\) and the supplies, rather than on \(N\). The real technical question is whether the MNW/leximin phase admits an efficient separation or pricing procedure over integral bundles. If it does, this becomes a clean continuous-optimization result. If that indivisible phase is hard, the hardness would more likely be inherited from the underlying discrete allocation problem than caused by population continuity.
This mirror covers Theorem 4.1, but not the paper’s impossibility result Theorem 3.1. I would not use Theorem 3.1 as a positive anchor: with one globally fixed indivisible good and an atomless population, the allocation problem degenerates, while scaling the supply produces a different and more useful regime. Theorem 5.4 is a promising second mirror, but its equal-share proof depends more delicately on the finite-agent bound that each minimum-utility agent receives at most one unit of the divisible good.
The weakest point is therefore the supply scaling. A referee could say that a market with \(N\) copies of every indivisible good and \(Nq_d\) divisible units is not the paper’s literal one-copy instance. That objection is real. The answer is that the programme asks whether the problem has a sensible high-multiplicity regime, not whether every finite instance has a nondegenerate continuum limit. Large course-seat markets and repeated resource allocations provide that regime, while each individual copy remains indivisible and the paper’s EFM and truthfulness requirements remain intact. The mirror is consequently a genuine population continuization of the authors’ mixed-goods problem, though not a claim that the fixed-two-agent impossibility instance itself becomes meaningful at continuum scale.
The decisive negative point is that this paper has no eligible ChoCo anchor under the programme’s own standard. Theorem 4.1 is a correctness theorem about a mechanism: Mechanism 1 is truthful, EFM\(^{\ge 0}\), leximin, and MNW. It does not assert a complexity bound, characterize an optimization problem, or study an input distribution over voter or agent types. The same is true of Theorems 5.3 and 5.4. Theorem 3.1 and Corollary 3.2 are impossibility results about mechanism properties, not computational complexity results. Thus the paper supplies no named result whose continuous computational analogue belongs to the proposed Class A/B/C landscape.
The proposed Theorem 4.1 mirror is nevertheless the strongest possible rescue, and it exposes a second difficulty. With the paper’s literal resource supply—one copy of each indivisible good and one unit of the divisible good—letting the number of agents grow makes the divisible allocation vanish per agent, while only finitely many agents can receive an indivisible good. The recipients of those goods have zero population mass. The water-filling and EFM guarantees therefore lose their substantive continuum content.
The proponent correctly tries to repair this by scaling supplies with \(N\). But that creates a repeated-market problem rather than a limit of the theorem’s stated setting: there are now \(N\) copies of each indivisible good and \(N\) units of the divisible resource. This may be a sensible high-multiplicity fair-division problem, but it is not the computational question posed or answered by Theorem 4.1. In particular, EF1’s “remove one good” clause, the MNW allocation, and the proof’s finite-agent comparisons all acquire a new per-capita interpretation. That interpretation may be worth studying, but it is a new model.
Truthfulness makes the mismatch more fundamental. A distribution \(\mu\) does not record the identity of an individual agent. A unilateral report changes \(\mu\) by zero in an atomless society, so truthfulness becomes vacuous. The proposed repair—requiring the compressed rule to expand truthfully for every finite \(N\)—is coherent, but it is a uniform family of labelled finite mechanisms, not a truthfulness property of the continuous object itself. If reports instead change type masses directly, the deviation is a coalition deviation and no longer mirrors the paper’s dominant-strategy notion.
Theorem 5.4 does not escape this problem. With one divisible good, its equal-share step gives each member of the minimum-utility set \(1/|T|\). In a large population this either tends to zero when \(T\) has positive mass or is received only by a zero-mass exceptional set when \(T\) remains finite. Scaling the divisible supply again produces a different per-capita market. Theorem 3.1 is even less suitable: its obstruction is intrinsically a two-agent, one-indivisible-good comparison, and fixed resources make its continuum limit degenerate while replicated resources change the problem.
I would not claim that repeated course-allocation markets are implausible, nor would I misuse existing high-multiplicity work as a novelty objection. The proponent’s \(\lambda_{t,B,x}\) formulation is a legitimate new research direction. But it is a compressed fair-division mechanism-design problem inspired by this paper, not a continuous computational mirror of one of its named results. Consequently, under the programme’s strict anchor requirement the paper should receive no; under the broader interpretation that admits new mechanism-design questions, the negative case is materially weaker and cannot honestly support the universal claim.
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.