| paper | d4-conf-wine-2024-0015 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.3
Given item types \(G\), an independence-system oracle \(\mathcal F\), strict rankings for \(\tau\) agent types with rational masses \(\mu_t\) summing to \(1\), and rational per-capita supplies \(b_g\), find a polynomial-bit rational assignment \(x_{t,S}\geq 0\), or certify none exists. Require \(\sum_{S\in\mathcal F}x_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x_{t,S}\leq b_g\), so each agent receives a whole feasible bundle. Every pair of bundles assigned positive mass must satisfy EF1 under the first bundle’s type ranking; the assignment must also admit no feasible reassignment of the same agents that weakly improves every agent and strictly improves a positive mass. Is this solvable in time and oracle calls polynomial in \(m,\tau,L\)?
A distribution over integral feasible bundles for each ranking type, constrained by per-capita supplies; EF1 is checked across bundles in the assignment’s support, and PO rules out a feasible reassignment that improves a positive mass without harming anyone.
The mirror covers Theorem 4.3 and Algorithm 2’s lexicographic EF1 and PO guarantee. It leaves the paper’s Max-NSW guarantees and additive-valuation results aside.
The strongest computational anchor is Theorem 4.3, proved in this paper. It says that, for lexicographic preferences under an independence-system constraint, Algorithm 2’s round-robin allocation is exactly EF1 and Pareto optimal. The algorithm skips an agent when adding any remaining item would violate feasibility. Its loops give a polynomial number of independence-oracle calls in the finite instance size, though the theorem does not state a runtime bound. I find no named hardness result in the paper; its headline Max-NSW theorems concern fairness guarantees for optimal allocations, not an algorithm for computing them. [Theorem 4.3 and Algorithm 2](https://arxiv.org/html/2411.01462)
A concrete mirror is Continuous Lexicographic EF1–PO Allocation. Let \(G\) be \(m\) item types, \(\mathcal F\) a common independence system given by an oracle, and \(T\) a list of \(\tau\) strict rankings of \(G\), with rational masses \(\mu_t\) summing to one. Give each item type \(g\) a rational per-capita supply \(b_g\). A feasible solution is a mass assignment \(x_{t,S}\geq 0\) to integral bundles \(S\in\mathcal F\), satisfying \(\sum_{S\in\mathcal F}x_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x_{t,S}\leq b_g\). Thus \(x_{t,S}\) is the fraction of type \(t\) receiving the whole bundle \(S\), not a fractional bundle for an individual.
Ask for such an assignment where every positive-mass pair \((t,S)\), \((u,S')\) satisfies exact EF1: there is a \(Z\subseteq S'\), \(|Z|\leq 1\), such that \(S\succeq_t S'\setminus Z\). Also require Pareto optimality: there is no feasible reassignment of the same agents that weakly improves every agent’s ranking and strictly improves a positive mass. There is no scalar objective here; as in Theorem 4.3, the task is to construct any allocation meeting both criteria. The computational question is whether a sparse rational solution can be produced in \(\mathrm{poly}(m,\tau,L)\) time and oracle calls, where \(L\) is the input bit length.
A plausible regime is a large course-allocation market: a very large cohort has relatively few complete course rankings, common course-combination constraints, and seat supplies that scale with cohort size. Each student still receives an integral set of courses; only the aggregate assignment is described by masses. This makes high multiplicity plausible, and the mirror changes the population while keeping the paper’s lexicographic preferences, bundle feasibility, EF1, and PO.
I would expect the mirror’s computational problem to be Class A, with medium confidence: the paper gives a constructive finite algorithm, and a type-compressed version may avoid dependence on the cohort size. The mirror covers Theorem 4.3 only; it does not claim a continuous Max-NSW result or cover the paper’s additive-valuation guarantees.
The weak point is that round-robin uses a finite sequence of individual turns and removes actual items as it proceeds. In a continuum, one infinitesimal agent’s turn consumes zero supply. A batch or type-compressed procedure is needed, and the paper does not provide one. The key open questions are whether exact EF1 and PO survive that batching, and whether the resulting assignment can have a polynomial-size representation in \((m,\tau,L)\).
The only anchor raised is Theorem 4.3 and Algorithm 2. The theorem guarantees that the algorithm’s output is EF1 and Pareto optimal, but it does not state a running-time bound. That makes it a weaker computational anchor than a theorem about complexity. Still, the algorithm itself is constructive and its round-robin loops can be bounded polynomially in the finite instance size and independence-oracle calls, so this objection does not dispose of it.
There is a real problem with the literal limit: the paper has \(m\) physical items. If the population grows while those items remain fixed, the mass receiving any item tends to zero. The EF1 condition can then become uninformative. But the proposed course-market version repairs this by scaling seat supply with the cohort, which is an allowed co-modification. A cohort with repeated preference rankings and common course constraints is a plausible high-multiplicity regime. Since each person still receives an integral bundle, the mass assignment preserves the paper’s object of study. EF1 can compare bundles held by positive-mass groups, and Pareto efficiency can rule out improvements to a positive mass of students.
The stronger mirror therefore survives the objections I can support. The paper’s round-robin order does not itself give an algorithm for that mass-allocation problem; finding one, or showing it hard, would be a genuine computational question. Calling that gap evidence against the mirror would confuse “the paper does not already solve the continuous version” with “the continuous version is not worth asking.” Nor can I argue that the mirror is merely about fractional outcomes: the population is continuous, while bundles remain integral.
So the negative case is weak. The fixed-stock limit degenerates, and the theorem is not formally stated as a complexity result, but both points leave a plausible, author-recognizable continuous version of the lexicographic EF1–PO problem. I cannot honestly make the universal case that no worthwhile mirror exists.
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.