| paper | d4-conf-wine-2024-0008 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 7
Given item classes \(J=[d]\) with rational per-capita supplies \(q_j\ge 0\), a finite set of additive valuation types \(T\) with rational masses \(\mu_t\) summing to one, and comparison-oracle access to each type’s valuation \(v_t\), compute a finite-support rational assignment \(x_{t,b}\ge 0\) over integral bundles \(b\in\mathbb{Z}_{\ge 0}^d\). Require \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_j=q_j\) for every class \(j\); every bundle with positive assigned mass must satisfy \(v_t\cdot(b+e_j)\ge v_t\cdot q\) for some class with positive supply, and \(v_t\cdot b\ge\frac12\mathrm{MMS}_t(q)\). Here \(\mathrm{MMS}_t(q)\) is the maximum \(z\) for which a distribution over integral bundles has expectation \(q\) and every bundle in its support has value at least \(z\) under \(v_t\). Determine the comparison-query and running-time complexity in \(d\), \(|T|\), and the input bit length.
A continuous population has type masses \(\mu_t\), per-capita supplies \(q_j\), and hidden additive valuations accessible by bundle comparisons. The decision variables \(x_{t,b}\) assign mass of each type to integral personal bundles, conserving each type’s mass and each class’s supply; every assigned bundle must meet that type’s PROP1 and \(\frac12\)-MMS thresholds.
The lead mirror covers Theorem 7’s PROP1 and \(\frac12\)-MMS allocation guarantee. Theorem 1 supplies a separate, tentative query-lower-bound question; the paper’s standalone PROP1 and EF1 results are not covered by the lead mirror.
The strongest honest case is a mirror of the paper’s main allocation result, with a narrower query lower-bound question as a second anchor. The society is the continuous object; goods remain indivisible for each person.
A plausible setting is a large benefits or equipment programme. There are many recipients but relatively few complete preference types: people of the same type have the same additive values, prices, and other relevant attributes. Inventory scales with the population. A type’s mass is its share of recipients, and a type may receive different integral bundles across that mass. This preserves individual fairness: it does not ask only that the type’s *average* bundle be fair.
Lead problem: Mass-PROP1-\(\frac12\)-MMS Allocation. Let \(J=[d]\) be item classes, with \(q_j\in\mathbb{Q}_{\ge0}\) copies of class \(j\) per person. Let \(T\) be a finite set of valuation types with rational masses \(\mu_t\) summing to one. Type \(t\) has a hidden additive valuation \(v_t\), accessed through the paper’s comparison oracle: a query presents two integral bundles \(b,b'\in\mathbb{Z}_{\ge0}^d\), and the oracle says which type \(t\) prefers. Find a finite-support, rational mass assignment \(x_{t,b}\ge0\). It must satisfy \(\sum_b x_{t,b}=\mu_t\) for each type and \(\sum_{t,b}x_{t,b}b_j=q_j\) for each item class, so every person receives an integral bundle and the population uses the per-capita supply.
For this question, define the continuous maximin share of type \(t\) as the greatest \(z\) for which there is a distribution \(\pi\) over integral bundles with expected bundle \(q\) and every bundle in its support valued at least \(z\) by \(t\). Thus \(\mathrm{MMS}_t(q)=\max_{\pi:\,\mathbb{E}_{\pi}[b]=q}\operatorname*{ess\,inf}_{b\sim\pi}v_t\cdot b\). Require every bundle with \(x_{t,b}>0\) to meet both fairness conditions: it is PROP1, meaning \(v_t\cdot(b+e_j)\ge v_t\cdot q\) for some available item class \(j\), and it satisfies \(v_t\cdot b\ge\frac12\mathrm{MMS}_t(q)\). The computational question is to determine the comparison-query and running-time complexity in \(d\), \(|T|\), and the input bit length, and whether it can be polynomial in those compressed parameters.
The anchor is Theorem 7 (the result labeled thm:prop1_mms_general), proved in this paper: for additive valuations, a deterministic algorithm finds an allocation that is both PROP1 and \(\frac12\)-MMS using \(O(n^4\log m)\) comparison queries and running time. In the mirror, \(n\) named recipients are replaced by a mass distribution over complete valuation types, while individual bundles and each person’s fairness test remain intact. Clearing denominators in \(\mu\) and \(q\) yields finite replicated instances; aggregating a finite allocation gives a mass assignment. That makes this a recognizable high-multiplicity version of the authors’ problem, not merely a fractional-outcome variant.
I would provisionally expect a Class A result for fixed \(d\) and \(|T|\): splitting type mass turns the final assignment step into a fractional allocation problem. The paper’s theorem establishes the corresponding finite-population guarantee, but does not establish that the type-compressed algorithm is efficient. The open technical question is whether the integral bundle patterns and the type-specific MMS thresholds admit an efficient pricing or separation method.
A second, more tentative question is One-Type Binary Query Complexity. Take one type of mass \(1\), \(d\) item classes, and per-capita supply \(q_j=1/N\) for every class. Its hidden additive valuation is binary and values exactly \(N+1\) classes at one and all others at zero. Ask for a mass assignment of integral bundles that satisfies a fixed \(\alpha\)-MMS guarantee, for \(\alpha>0\), using as few comparison queries as possible. The continuous object is the mass assignment; \(N\) records the scale of the finite replicas, not a finite population in the target model.
The anchor is Theorem 1, proved here using a construction similar to Oh et al.’s Theorem 5.5. It states that computing a PROP1, EF1, or \(\alpha\)-MMS allocation requires \(\Omega(\log m)\) comparison queries even with a constant number of agents and identical valuations, for every \(\alpha\in(0,1]\). The theorem’s proof uses binary valuations with \(n+1\) valued goods among \(m\), and gives the adversary bound \(\log(m/(2n))\) before specializing to constant \(n\). I would ask whether an analogous \(\Omega(\log(d/N))\) lower bound persists as \(N\) grows and \(d/N\) becomes large. If it does, this is a query-complexity hardness transfer: fractional type masses do not remove the need to discover enough about which item classes are valuable. The fixed-\(n\) theorem statement does not prove that growing-\(N\) claim, so it is a concrete follow-up question, not a result to attribute to the paper.
My weakest point is the main mirror’s complexity model. In the paper, the allocation algorithm operates on named agents and makes \(O(n^4\log m)\) queries; its theorem does not show that those queries or its matching steps compress to a number of valuation types. Also, the mass-level MMS definition must be accepted as the limit of the finite partition benchmark. The mirror remains worth asking because it keeps each person’s bundle integral, preserves type-by-type fairness, and has a direct finite-replication dictionary. I would limit the claim to PROP1 plus \(\frac12\)-MMS and the specialized one-type query question; the paper’s other EF1 and PROP1 query bounds are not automatically covered.
The strongest negative case is about payoff, not fidelity. Theorem 7 has a credible mirror: a large benefits programme could have many recipients in a small number of complete valuation types, repeated item classes, and integral bundles for each recipient. With rational masses and per-capita supplies, clearing denominators gives a finite clone instance. The proposed type-level MMS also has a natural interpretation as the best minimum bundle value over replicated partitions. I don’t see a sound objection based simply on indivisibility, identity, or the required supply scaling.
The concern is that this mirror changes the *representation* without yet showing a new computational phenomenon. The paper’s query bounds are driven by the goods and comparison oracle; after grouping identical recipients, queries can be asked of type representatives. A polynomial algorithm in the compressed input would be a meaningful result, but the paper’s theorem does not provide one: clearing binary-encoded denominators can produce a very large clone instance. That leaves a real algorithmic question, though it may be a high-multiplicity fair-division problem more than a continuization-specific one. And if inventory does not scale with population, per-capita supply can vanish and the fairness benchmark can become trivial. The programme explicitly permits supply to co-scale, so this is a limitation of the mirror’s natural settings, not a decisive refutation.
The query lower-bound anchor is weaker as a separate target. Its proposed one-type instance fixes the population mass at \(\mu=1\); the varying parameter \(N\) appears in the per-capita supplies and goods classes. The paper’s Theorem 1 proof already gives the discrete adversary bound \(\log(m/(2n))\), beyond the constant-\(n\) theorem statement. Thus the proposed \(\Omega(\log(d/N))\) question is close to a variable-\(n\) extension of an argument already in the paper. Fractional mass assignments might evade that adversary, so the extension still needs proof, but it looks like a narrow query-bound question rather than a strong independent mirror.
That leaves a credible main mirror and a secondary question whose likely lower bound is already suggested by the source proof. I can make a case to prioritize the main mirror and treat the lower-bound question cautiously. I cannot honestly defend the stronger claim that no worthwhile continuous mirror exists: the main result survives the strongest objections available here.
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.