| paper | Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio |
| authors | Bo Li, Zihao Li, Shengxin Liu, Zekai Wu |
| venue | IJCAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
Given rational type masses \(\mu_\theta\) summing to \(1\), population scale \(q\), item classes \(G\) with \(q b_g\) identical indivisible copies, divisible supply \(q b_C\), and additive values \(v_{\theta g},v_{\theta C}\), let \(p_\theta=\sum_{g\in G}b_gv_{\theta g}+b_Cv_{\theta C}\) and \(\alpha_\theta=\sum_g b_gv_{\theta g}/p_\theta\). Find a finite-support mass distribution \(x_{\theta,B,z}\) over integral bundles \(B\in\mathbb{Z}_{\ge0}^{G}\) and divisible quantities \(z\ge0\), with type marginals \(\mu_\theta\), average supply constraints \(\sum xB_g\le b_g\) and \(\sum xz\le b_C\), and every supported configuration satisfying \(v_\theta(B,z)+\alpha_\theta h_\theta(B)\ge p_\theta\), where \(h_\theta(B)=\max\{v_{\theta g}:B_g<qb_g\}\) and the empty maximum is \(0\). Decide whether this construction is solvable in time polynomial in \(\tau\), \(|G|\), \(\log q\), and the input bit length; when masses are multiples of \(1/q\), it must recover the corresponding finite-clone allocation.
A high-multiplicity mixed-goods allocation with \(\tau\) agent types of masses \(\mu_\theta\), \(q b_g\) identical copies of each indivisible item class, and \(q b_C\) divisible supply. Decision variables are masses assigned to integral bundle configurations and divisible quantities, subject to per-capita supplies and type-wise \(\mathrm{PROP}_\alpha\); indivisible goods themselves are never fractionalized.
The scaled item classes and configuration distribution change the resource side of the instance, so the theorem supplies no polynomial-in-\(\log q\) compression and the mirror may have a genuinely new configuration-pricing difficulty.
fatal: False
The mirror covers the constructive \(\mathrm{PROP}_\alpha\) result of Theorem 4.1; it leaves Theorem 3.1, the EF existence and impossibility results, the PROP lower bound, MNW/PO results, and the relation theorems unaddressed.
The strongest case is a population-scaled mirror of the paper’s constructive PROP result.
The named anchor is Theorem 4.1, proved in this paper: “For any number of agents, Algorithm 1 returns a PROP\({}_\alpha\) allocation in polynomial time.” I would use this as the sole anchor. The other main theorems are primarily existence or structural statements, so adding them would weaken the case.
A credible regime is a large public-allocation market: \(q\) households receive a mixture of indivisible apartment, vehicle, or equipment units and divisible relocation assistance. Households fall into a small number \(\Theta\) of administrative types: two households have the same type exactly when they have the same valuation for every item class and the divisible resource, and the same relevant parameters. Thus \(|\Theta|=\tau\ll q\). Item supplies also scale with the population: there are \(q b_g\) copies of each indivisible item class \(g\), and \(q b_C\) units of divisible assistance. This scaling is essential; keeping a fixed number of houses while \(q\) grows would make the fairness question degenerate.
Here is the continuous problem I would propose.
HM-\(\mathrm{PROP}_\alpha\)-MixedGoods\(_\infty\) — Given a finite type set \(\Theta\), rational masses \(\mu_\theta\ge 0\) with \(\sum_\theta\mu_\theta=1\), a population scale \(q\), item classes \(G\), per-capita supplies \(b_g\) and \(b_C\), and rational additive valuations \(v_{\theta g}\) and \(v_{\theta C}\), define
\[ p_\theta=\sum_{g\in G}b_gv_{\theta g}+b_Cv_{\theta C} \]
and
\[ \alpha_\theta= \frac{\sum_{g\in G}b_gv_{\theta g}}{p_\theta}. \]
A solution is a finite-support family \(x_{\theta,B,z}\ge 0\), where \(B\in\mathbb Z_{\ge0}^{G}\) is an integral bundle of indivisible goods and \(z\in\mathbb Q_{\ge0}\) is divisible assistance, satisfying
\[ \sum_{B,z}x_{\theta,B,z}=\mu_\theta, \]
\[ \sum_{\theta,B,z}x_{\theta,B,z}B_g\le b_g \quad\text{for every }g\in G, \]
and
\[ \sum_{\theta,B,z}x_{\theta,B,z}z\le b_C. \]
Every configuration in the support of type \(\theta\) must satisfy
\[ \sum_{g\in G}v_{\theta g}B_g+v_{\theta C}z +\alpha_\theta h_{\theta,q}(B) \ge p_\theta, \]
where
\[ h_{\theta,q}(B)= \max\{v_{\theta g}:B_g<qb_g\}, \]
with \(h_{\theta,q}(B)=0\) if the set is empty. The task is to output such a family, or report that none exists.
This is directly recognizable as PROP\({}_\alpha\). If \(q\mu_\theta\) and \(qb_g\) are integers and every \(x_{\theta,B,z}\) is a multiple of \(1/q\), it is exactly an allocation of \(q\mu_\theta\) cloned agents and \(qb_g\) indivisible goods. Normalizing each type’s total utility to \(1\) turns the displayed condition into the paper’s
\[ u_i(A_i)+\alpha_i u_i(o)\ge \frac1q. \]
The indivisibility has not been fractionalized: every individual receives an integral bundle \(B\). Only the mass of agents receiving a given integral bundle is continuous. This is precisely the high-multiplicity move. The cake is inherited from the paper’s model; it is not the source of the proposed continuity.
The expected complexity question is whether this problem can be solved in time polynomial in
\[ \tau,\ |G|,\ \log q,\ \text{and the input bit length}, \]
rather than in \(q\). I expect the homogeneous-cake version to be Class A. Algorithm 1 already alternates between bag-filling with indivisible goods and moving-knife allocation of divisible goods. With finitely many types, identical agents can plausibly be processed in batches rather than one at a time, and the relevant threshold events are determined by type/item-class pairs. A configuration-LP formulation may have exponentially many integral bundles, but the paper’s structural argument suggests that one should be able to avoid enumerating them or solve the associated pricing problem efficiently.
That is a real computational question: the explicit-agent theorem does not automatically yield a \(\log q\)-time high-multiplicity algorithm. The continuous problem asks whether the theorem’s combinatorial process compresses from \(q\) agents to \(\tau\) types. If arbitrary heterogeneous cake valuations or unrestricted item-class structure make the pricing problem hard, that would be a meaningful Class C boundary rather than evidence that the mirror is artificial.
The mirror is therefore author-recognizable: same mixed goods, same additive utilities, same personalized indivisibility ratio, same PROP\({}_\alpha\) predicate, and the same bag-filling/moving-knife mechanism. The only substantive change is that repeated agents and repeated goods are represented by masses and supplies.
The weakest point is the required supply scaling. If one insists on a literal continuum of agents facing the paper’s fixed finite set of goods, indivisible items become negligible and the \(1/n\) PROP threshold collapses. My formulation avoids that pathology by taking the meaningful high-multiplicity regime in which both population and repeated resource classes scale. That makes it an extension rather than a purely literal restatement, but it is the natural regime for the paper’s problem.
This mirror also raises worthwhile follow-up questions: can the result survive heterogeneous cakes in the Robertson–Webb model; can a PROP\({}_\alpha\) allocation also be Pareto-optimal in the compressed setting; and how can a continuous solution be rounded back to \(q\) discrete agents with a controlled fairness loss?
The strongest negative case is that the proponent’s model is not a continuization of Theorem 4.1, but a new high-multiplicity resource-allocation problem.
Theorem 4.1 itself is a legitimate computational anchor, so the “no named result” objection is unavailable. The difficulty is the limit. If the paper’s finite set \(M\) of indivisible goods is held fixed while the number of agents \(q\) grows, the mixed-goods problem degenerates. The PROP\({}_\alpha\) threshold becomes \(1/q\). For any unserved agent with \(\alpha_i u_i(o)>0\) for some outside good \(o\), the relaxation is eventually satisfied without giving that agent anything, since \(\alpha_i u_i(o)\) is fixed while \(1/q\to 0\). Only finitely many agents can receive the finitely many indivisible goods; the cake can be divided among the rest. Thus the paper’s central tension between indivisibility and proportionality disappears.
The proposed repair—\(q\) agents together with \(qb_g\) copies of every item class—is mathematically coherent, but it changes the object being studied. The paper has a finite collection of individually specified indivisible goods. The proposed problem replaces it by a capacitated supply of homogeneous item classes and asks for a distribution over integral bundles. That is a sensible extension, but not a population-only mirror of the stated theorem. The continuous object is now jointly the population and the resource inventory, and the new combinatorial object is the configuration family \(B\), not the population distribution alone.
The claimed finite-clone correspondence does not rescue this distinction. Clearing denominators does show that rational \(x_{\theta,B,z}\) can describe a finite allocation with repeated goods. It does not show that Theorem 4.1’s algorithm compresses to a procedure polynomial in \(\tau\) and \(\log q\). Algorithm 1 processes indivisible goods sequentially and may give identical types different integral bundles. After aggregation, the residual state consists of item counts and a potentially large collection of bundle patterns. A configuration formulation therefore introduces a separate succinct-generation or separation problem. That problem is not supplied by the theorem, and its complexity comes from repeated-resource bundle selection rather than from continuizing the society.
One can make the mirror more faithful by retaining integral bundles, homogeneous cake, support-wise PROP\({}_\alpha\), rational supplies, and exact finite-clone fidelity. That removes the obvious objections about fractionalizing indivisible goods or losing individual fairness. It also makes the proposal a plausible high-multiplicity extension for recurring public-allocation markets. But precisely because that repaired version survives all of those tests, the universal negative cannot honestly be maintained.
So the defensible opposition is narrow: reject the proposed formulation as a direct mirror of Theorem 4.1, since fixed-supply continuization is vacuous and supply scaling creates a new configuration problem. The stronger claim that no worthwhile continuous mirror exists in any scenario is weak. The repaired model is author-recognizable and computationally worthwhile, even though it should be labelled an extension rather than an automatic consequence of the paper.
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.