| paper | d4-conf-ecai-2024-0492 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Under the supplied exact equivalence and Robertson–Webb query model, decision and construction query complexities are both \(\Theta(\tau 2^\tau)\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4.7
statement extracted from the paper’s text layer
Given \(\tau\) types of equal mass \(\mu_t=1/\tau\), each with a normalized nonatomic valuation \(V_t\) available through eval and right-mark queries, decide whether the interval can be partitioned into one contiguous interval \(I_t\) per type with \(V_t(I_t)>\mu_t\) for every \(t\), and compute such a partition if it exists.
The society is a distribution over \(\tau\) complete valuation types with masses \(\mu_t=1/\tau\). Choose an ordering and cut points that give each type one interval \(I_t\); the decision condition is \(V_t(I_t)>\mu_t\). In a finite realization with \(K\) members per type, divide each type’s interval into \(K\) contiguous equal-value pieces.
The type-block oracle problem is formally identical to the paper’s finite-agent problem after treating each type as an agent with entitlement equal to its mass, so the paper itself already supplies the query-complexity answer.
fatal: False
The mirror covers existence and computation of connected strong-proportional allocations for equal-mass cohorts on an interval, and exact-query impossibility for cohorts on a pie. It does not claim a matching bound for arbitrary rational masses, cover the stronger-surplus result, or address allocations where one type’s members receive separated blocks.
The paper’s named complexity results are in the Robertson–Webb query model, not in a conventional bit model such as P or NP-hardness. The strongest honest mirror is therefore about the number of valuation queries needed when a large population has few distinct valuation types.
Consider a shared facility whose resource is time on a line: many users, but only \(\tau\) distinct complete valuation types. Type \(t\) has mass \(\mu_t\), and every member of that type has the same normalized, nonatomic valuation \(V_t\). In the regime I would defend, each type receives one contiguous block of time, which is then divided among its members. For a finite realization with \(N\mu_t\) members of type \(t\), the block \(I_t\) is fair to that cohort exactly when \(V_t(I_t)>\mu_t\): divide the block into \(N\mu_t\) equal-value contiguous pieces, and each member gets value
\[
\frac{V_t(I_t)}{N\mu_t}>\frac{\mu_t}{N\mu_t}=\frac1N.
\]
Thus each individual still receives an integral, connected interval; the type-level value is an average over a large cohort. The population is represented by the rational distribution \(\mu\), with \(N\gg\tau\).
Lead mirror — Type-Block Strong Proportionality on an interval. For the anchored regime, take \(\mu_t=1/\tau\). The input is the \(\tau\) type valuations, accessible by eval and right-mark queries. Decide whether the interval can be partitioned into \(\tau\) disjoint intervals \(I_t\), one per type, such that \(V_t(I_t)>1/\tau\) for every type. A solution is the type order and the cuts defining those intervals.
The anchor is Theorem 4.7, proved in this paper. It states that for \(n\) agents, the number of queries required either to decide whether a connected strongly-proportional allocation exists or to compute one if it does is \(\Theta(n2^n)\), even when entitlements are equal. In the mirror, set \(n=\tau\): the cohort-block decision problem has the same \(\Theta(\tau2^\tau)\) query complexity. This is my strongest anchor because it covers general, not necessarily hungry, valuations and directly concerns existence of the paper’s allocation. Its expected classification is hardness transfers, in the exact-query sense: the \(\tau\) type blocks are the paper’s \(\tau\) equal-entitlement agents. This is not a claim of NP-hardness in a finite encoding.
A second, distinct mirror is Type-Block Strong Proportionality on a pie. Use the same equal-mass cohorts and valuations, but let the resource be circular and ask for a partition into connected arcs \(I_t\) with \(V_t(I_t)>1/\tau\) for every type. A solution is the cyclic order and arc boundaries. In a finite population with \(N=K\tau\), each cohort’s arc can be cut into \(K\) equal-value subarcs, so each member gets more than \(1/N\).
Its anchor, Theorem 6.1, is also proved here: no finite algorithm can decide whether a connected strongly-proportional allocation of a pie exists, even for hungry agents with equal entitlements. The expected direction is again hardness transfers, now as impossibility of a finite exact query protocol for arbitrary valuation oracles. Whether useful finite protocols become possible under restricted valuation representations, or for approximate decisions, is a natural follow-up.
These mirrors cover connected strong proportionality and its existence and computation questions, in the equal-mass cohort regime. They do not make the resource continuous as their contribution: the resource is already a cake or pie in the paper. The new modeling choice is the society, represented by masses over complete types. Unequal rational cohort masses would be a natural extension, but these two anchors establish the stated bounds only in the equal-mass regime.
The weakest point is the cohort-block condition. It is sensible when a policy schedules repeated users in coordinated blocks, and the subdivision argument shows that members can still receive individual connected pieces. But it restricts the paper’s allocations: members of the same type must be adjacent in the allocation order. The paper does not show that arbitrary feasible allocations can be rearranged this way. Also, its query bounds concern oracle access to valuations; they do not settle ordinary bit-complexity questions.
The strongest case against both anchors is that the proposed cohort models are the paper’s finite-agent models under a change of labels. Given types \(t\) with masses \(\mu_t>0\) and valuations \(V_t\), make one paper-agent per type and set that agent’s entitlement to \(w_t=\mu_t\). Then the Type-Block condition is exactly the paper’s condition: partition the cake into intervals \(I_t\) such that \(V_t(I_t)>w_t\). The valuation oracles are the same too.
So Theorem 4.7 gives the stated \(\Theta(\tau 2^\tau)\) bound for the equal-mass mirror directly. For arbitrary masses, the paper’s characterization and algorithm in Theorems 4.4–4.5 already cover the corresponding entitlement problem. The finite-cohort subdivision is valid, but it adds no computational parameter: the number of people per type disappears, while mass becomes entitlement. This is not an objection based on the cake already being divisible; it is an identity between the proposed population model and the paper’s allocation model.
The pie anchor has the same issue. For equal masses, Theorem 6.1 is already the exact finite-query question for \(\tau\) pie-cutting agents. Calling them cohorts does not create a distinct population-complexity question.
A stronger mirror could drop the requirement that members of each type occupy one block. But if it retains a connected piece for every individual, the literal continuum limit degenerates: each person’s entitlement tends to zero, while strict positive value requires a positive-length interval. A line or circle cannot be partitioned into uncountably many disjoint positive-length intervals. If instead each type receives an aggregate, possibly fragmented share, individual connectedness has been dropped; that is a different allocation problem, not a continuation of these anchors.
That leaves a real limit to the negative case: an interleaved, finite-cohort problem parameterized by both population size and number of types could be worth studying. But it is a different mirror, and the appended case does not establish that it has a continuous-population limit or a worthwhile complexity question. For the two anchors actually offered, the paper already contains the computational models they describe.
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.