| paper | Multi-unit assignment under dichotomous preferences |
| authors | J. Ortega |
| venue | MSS 2020 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proponent gives a credible high-multiplicity analogue of the assignment model, but neither named anchor has computational character under the programme’s strict test. Theorem 1 is a fairness characterization and Theorem 3 is a strategic property; the paper’s remark that an algorithm is lacking does not constitute a computational result.
fails bit a — no named computational result to mirror
The proposed mirror covers continuous versions of egalitarian assignment and potentially CCE, IPO, and strategy-proofness questions, but it does not mirror a computational result proved by the paper.
The paper has a serious positive model-level mirror, but it fails the programme’s strict anchor test: it contains no named computational-complexity result. The numbered results concern fairness, existence, and strategy-proofness. Nothing states that a problem is in \(P\), NP-hard, FPT, or even gives a computational formulation that the paper solves. Thus the case below is a conditional one: a strong continuous mirror of the paper’s central assignment problem, but not a mirror anchored in an existing complexity theorem.
The most convincing mirror is a high-multiplicity egalitarian assignment problem for a large clearinghouse allocating interviews, appointments, or compatible job slots. Let \(M\) be the objects. A type \(t\) is an acceptable set \(A_t\subseteq M\), since dichotomous preferences are completely described by that set. The society is a distribution \(\mu\) over finitely many types, where \(\mu_t\) is the fraction of agents of type \(t\). Object \(k\) has per-capita supply \(s_k\), corresponding in a finite election or assignment instance to \(s_k=q_k/n\).
The regime is many agents but relatively few distinct eligibility profiles: for example, millions of applicants grouped into cohorts with the same qualification, location, schedule, and set of acceptable interviews. Within a type, agents are indistinguishable for every feature used by the model. This is exactly the high-multiplicity interpretation, not an artificial removal of individual prices.
Each individual still receives an integral bundle \(B\subseteq A_t\), with at most one unit of each object. Let \(\lambda_{t,B}\) be the mass of type \(t\) receiving bundle \(B\). Then \(\sum_{B\subseteq A_t}\lambda_{t,B}=\mu_t\), and efficient assignments satisfy \(\sum_{t,B:k\in B}\lambda_{t,B}=s_k\). The type’s utility is \(u_t=\mu_t^{-1}\sum_B |B|\lambda_{t,B}\). Equivalently, one can use the aggregate variables \(x_{t,k}=\sum_{B:k\in B}\lambda_{t,B}\), since the paper’s per-object feasibility constraints permit decomposition into integral bundles. The continuous object is therefore the population mass \(\mu\), not fractional consumption by an individual.
The strongest named anchor is Theorem 1, proved in this paper, although its proof invokes Dutta and Ray’s cited Lorenz-dominance theorem. Its full content is: for every multi-unit assignment problem \((R,q)\), the Egalitarian Solution, defined as the leximin-maximal efficient utility profile, is Lorenz dominant among all efficient utility profiles. Thus, after sorting utilities increasingly, its cumulative utility is at least that of every other efficient profile at every prefix, with strict improvement somewhere unless the profiles coincide.
This gives the following precise continuous problem.
Continuous Egalitarian Assignment\(_\infty\). Given rational \(M\), a finite explicit type set \(T\), rational masses \(\mu_t\), rational supplies \(s_k\), and acceptance sets \(A_t\), output an efficient mass assignment \(x\) and its type-utility profile \(u\) such that the utility distribution carrying mass \(\mu_t\) at value \(u_t\) Lorenz dominates the utility distribution of every other efficient mass assignment.
I would expect this problem to be Class A. With explicit type support, the feasible \(x\)-vectors form a transportation polytope, and weighted leximin/Lorenz optimization should be implementable by a polynomial sequence of linear programs. The main work would be proving exact rational bit-complexity bounds and formalizing the weighted Lorenz objective. For rational \(\mu_t=n_t/n\) and \(s_k=q_k/n\), the result has an exact high-multiplicity dictionary with the discrete problem: scaling the masses by \(n\) recovers the corresponding cohort instance, while an exact continuous solution gives a discrete randomized assignment or an additive rounding scheme.
This is a very plausible analogue of the authors’ problem. It preserves the same objects, capacities, individual rationality, dichotomous utilities, efficiency notion, and egalitarian objective. Theorem 3 also supports the interpretation: it states, again as a result proved in the paper, that ES is group strategy-proof whereas CCE is not. The paper’s Example 3 can be lifted directly to a continuous society by replacing each named agent with a positive-mass cohort of identical agents; the price-zero manipulation of perfect objects remains meaningful.
The weakest point is decisive under the programme’s rubric: the paper itself does not establish a computational anchor. The proposed problem is a new complexity question about the continuous version of the authors’ assignment model, rather than a continuization of a complexity result they proved. There is also a smaller modelling vulnerability: because the paper already uses random-assignment matrices, an opponent could say the construction merely renames fractional outcomes. The integral-bundle formulation above answers that objection, but the absence of a named computational theorem remains.
So my honest verdict is: a convincing continuous population mirror exists, centred on Theorem 1 and likely tractable by LP, but this paper is not a qualifying computational-complexity anchor for the ChoCo programme.
The decisive objection is categorical: this paper contains no computational-complexity result to continuize. Theorem 1 is a Lorenz-dominance characterization; Theorem 2 concerns existence and disjointness; Theorem 3 concerns group strategy-proofness. None specifies an input problem, algorithm, complexity class, or hardness result. The prose remark that “we lack an algorithm” is not a computational theorem. Thus any LP for a continuous version would be a new computational project inspired by the paper, not a mirror of one of its named computational results.
The proposed Theorem 1 mirror is nevertheless mathematically plausible, but it is not quite the stated theorem’s limit. The paper’s egalitarian solution orders the utilities of all named agents. The proposed model instead places mass \(\mu_t\) at the type-average utility \(u_t\). Those differ: if half of a type receives utility \(0\) and half utility \(2\), the paper sees a utility distribution with two values, whereas the proposed mirror sees mass at \(1\). An exact continuization must retain the within-type distribution of individual utilities, or impose symmetric lotteries for each type and prove that this restriction preserves the egalitarian solution. Both are repairable modelling choices, but neither supplies the missing computational anchor.
Theorem 3 does not rescue the case. Cohort replication can preserve the example in which agents manipulate by making objects perfect, so I would not object that high multiplicity is inherently nonsensical here. But individual strategy-proofness becomes vacuous for measure-zero agents, while meaningful group strategy-proofness requires a new definition for positive-mass coalitions and type-distribution changes. That is a legitimate continuous question, not a computational result from the paper.
Accordingly, the strongest negative verdict is: this paper should not qualify as a ChoCo mirror source under the programme’s strict anchor rule. I would not honestly claim that no worthwhile continuous assignment model exists. The proponent’s high-multiplicity course, interview, or scheduling scenario is sensible, and could motivate new computational work. The negative case defeats the paper’s eligibility as a computational anchor, not the broader claim that continuous population assignment is worth studying.
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.