| paper | d4-conf-ijcai-2018-0116 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.11
statement extracted from the paper’s text layer
Given a rational mass profile \(\mu\) over \(\tau\) complete valuation types, a cohort scale \(N\) with \(N\mu_t\in\mathbb{Z}\), and Robertson–Webb EVAL and CUT oracles for each type valuation \(v_t\), what is the optimal worst-case query complexity of returning a partition \((X_{t,j})\) of \([0,1]\) into one bundle for each of the \(N\mu_t\) agents of type \(t\), such that \(v_t(X_{t,j})\le 1/N\) for every agent?
Represent the society by complete additive, normalized valuation types \(t\) with masses \(\mu_t\), and retain a finite cohort scale \(N\) to express the per-agent bound. Each type has \(N\mu_t\) identical agents; the output is their individual pieces, which may also be recorded by a fractional type-level average. The objective is worst-case Robertson–Webb query complexity as a function of \(N\), \(\tau\), and input-description length.
The mirror covers Theorem 3.11’s proportional chore allocation query-complexity result. Theorem 3.6 remains a single-valuation search result, while the paper’s envy-free and cake-cutting discussion is not independently mirrored.
The strongest honest mirror is high-multiplicity proportional chore division in the Robertson–Webb query model. The paper already makes the chore divisible; the mirror’s new continuous object is the population, represented by masses of complete valuation types.
My lead anchor is Theorem 3.11, proved in this paper. It says that every Robertson–Webb protocol for proportional chore division has worst-case query complexity at least \(\Omega(n\log n)\). Here the protocol must partition \([0,1]\) among \(n\) players so that each player’s additive, normalized valuation of their piece is at most \(1/n\). A query is an EVAL or CUT query to a player’s valuation function.
Here is the corresponding problem. An instance has a finite support \(T\) of valuation types, rational masses \(\mu_t\) summing to \(1\), and a scale \(N\) such that \(N\mu_t\) is an integer for every \(t\). Type \(t\) is a complete additive, normalized cost function \(v_t\), accessible through EVAL and CUT queries; there are \(N\mu_t\) agents of that type. The task is to return a partition of the chore into pieces \(X_{t,j}\), one for each agent, with
\[
v_t(X_{t,j})\leq 1/N.
\]
The complexity question is the optimal query bound in \(N\), support size \(\tau=|T|\), and the input bit length, especially when \(\tau\ll N\). At the type level, the average bundle
\[
\frac{1}{N\mu_t}\sum_j \mathbf{1}_{X_{t,j}}
\]
can be fractional, but that average is only a record of the allocation: every agent still receives an actual piece, and all pieces must partition the chore.
A plausible regime is a large workforce assigned a common divisible job, where cost profiles depend on a modest number of training or role categories. Thousands of workers might share a few dozen profiles for how costly different parts of the job are. The type is the whole valuation function, so workers grouped together are genuinely indistinguishable for this problem. This is a high-multiplicity instance, not a claim that every chore-division setting has that structure.
I would expect the lower bound to change in this regime, and would initially pursue a Class A result: reuse queries to each of the \(\tau\) valuation oracles and seek an output-sensitive bound that improves on \(N\log N\). The theorem does not establish such a bound, but neither does it establish its own lower bound when \(\tau\ll N\). Its adversary starts from \(n\) arbitrary valuation functions, which may be all distinct. The central question is whether repeated types let a protocol avoid paying separately for each agent. A matching lower bound for fixed \(\tau\), if one exists, would instead expose a barrier specific to this mass-profile regime.
The authors should recognize this as their proportional-allocation problem: it preserves the same fairness requirement, valuation model, and query operations, while grouping indistinguishable agents by mass. It does not turn proportionality into an average-value guarantee. The paper’s Theorem 3.6, also proved here, supports the motivation: finding a heavy piece for an arbitrary positive \((0,2)\)-dense valuation function requires \(\Omega(\log n)\) queries. That single-function search is used in the proof of the allocation lower bound; it does not by itself settle the mass-profile allocation question.
The scope is deliberately narrow: proportional chore division and its query complexity. I am not mirroring the paper’s discussion of envy-freeness or cake cutting as separate results, and this is not a claim about NP-hardness or ordinary Turing-time complexity.
The weakest point is that the paper’s result counts oracle queries, while the ChoCo programme is chiefly interested in computational complexity and algorithms. Also, the discrete lower-bound construction may rely on valuation diversity that vanishes when the support is small. Those are reasons to treat the mirror as a research question, not reasons to dismiss it: the population distribution gives a concrete, testable way to ask exactly where the original bound does and does not survive.
Theorem 3.11 is a genuine computational result in the Robertson–Webb query model. I would not argue that the paper lacks a complexity theorem, or that query complexity is inherently outside computation. The obstacle is that the theorem’s fairness guarantee is attached to individual pieces: it asks for \(N\) bundles \(X_i\) satisfying \(v_i(X_i)\leq 1/N\). That individual requirement is also where the population size enters.
For \(N\) agents grouped into valuation types, the strongest aggregate formulation assigns each type \(t\) a region \(A_t\) and requires \(v_t(A_t)\leq\mu_t\). For any finite cohort, this is a sensible way to summarize the total burden: with the paper’s divisibility assumptions, \(A_t\) can be split among its \(N\mu_t\) members into pieces costing at most \(1/N\) each. But the aggregate allocation and the individual allocation are different computational outputs. The aggregate version omits the work of making those pieces.
That gap becomes stark at support size \(\tau=1\). The aggregate problem can assign the whole chore to the sole type, satisfying \(v_t(A_t)=\mu_t=1\). Yet for finite \(N\), the original guarantee still requires \(N\) individual pieces. In a literal atomless population, each individual has zero mass; an individual cost bound that shrinks as \(1/N\) no longer imposes a substantive constraint. Keeping the per-person pieces preserves the finite-\(N\) task, but also preserves the need to describe them. Thus the aggregate model removes the micro-allocation challenge, while a continuum of individually constrained agents makes that challenge degenerate.
The strongest rescue is the one the proponent proposes: retain finite \(N\), give each of \(\tau\) types mass \(\mu_t\), solve the type-level allocation, and refine it into individual pieces. That is a legitimate high-multiplicity research question, and the paper’s lower bound for \(N\) arbitrary valuation oracles does not settle it. But it is a question about query reuse in a finite population plus the cost of disaggregation; it does not yield a continuous population model that preserves Theorem 3.11’s individual-output problem. Whether the aggregate-query question is valuable to ChoCo is the negative case’s weakest point: it is well-posed, and the paper’s authors might recognize it as theirs.
Theorem 3.6 does not supply a separate population mirror. Its parameter \(n\) sets the scale of the heavy-piece target for a single valuation oracle; the result is a query lower bound for that search task, not a lower bound about a society of \(n\) agents. It motivates Theorem 3.11’s proof, but changing that search problem into a population problem would require adding a population axis that the theorem itself does not have.
So the best case against is narrow: an exact continuum limit seems unable to retain both the paper’s per-person guarantee and its finite individual bundles. The cohort-mass problem is the strongest alternative, but it moves the computational question to aggregate allocation and leaves individual refinement outside the limit. I cannot honestly claim this rules out every worthwhile high-multiplicity mirror; it does make the case against a faithful continuous mirror stronger than the case against asking the finite-\(N\), small-support query question.
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.