| paper | d4-conf-atal-2015-0049 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: A deterministic protocol exists with \(O(\tau 2^\tau)\) Robertson–Webb queries. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite support \(T\) of valuation types, rational masses \(\mu_t>0\) summing to \(1\), and normalized atomless valuation oracles \(V_t\), can a query protocol whose query count is bounded as a function of \(\tau=|T|\) find pairwise-disjoint connected intervals \(P_t\), with free disposal, such that \(V_t(P_t)\ge V_t(P_s)\) for all \(t,s\) and \(V_t(P_t)>0\) for every type?
A society consists of mass-bearing valuation cohorts; each cohort is a collective claimant receiving one shared connected parcel \(P_t\). The parcels are disjoint, the remainder may be discarded, envy-freeness is checked across cohorts, and \(\mu_t\) records population share and weights aggregate welfare.
The mirror covers Theorem 1's positive envy-free guarantee for any \(\tau\), including its proportionality bound of \(1/2^{\tau-1}\), and Theorems 2 and 3's sharper guarantees for \(\tau=3\) and \(\tau=4\). It does not establish polynomial-time complexity in \(\tau\), optimize mass-weighted welfare, or guarantee separate exclusive parcels to every individual.
The strongest positive case I believe is a type-cohort commons mirror: a large population is divided into a few preference cohorts, and each cohort receives a connected parcel for shared use. For example, a municipality might allocate public land among a few large neighborhood associations whose members share the same valuation of the land. Each member of a cohort values its parcel per capita; the cohort’s mass \(\mu_t\) is its share of the population. This is a plausible high-multiplicity regime: many residents, few distinct valuation types.
Here is the corresponding problem. An instance consists of a finite support \(T\), \(\tau=|T|\), rational masses \(\mu_t>0\) summing to \(1\), and a normalized, atomless valuation \(V_t\) for each type, accessed through the cake-cutting query interface. Find pairwise-disjoint connected intervals \(P_t\), with the remainder left unallocated, such that
\[
V_t(P_t)\ge V_t(P_s)\quad\text{for all }t,s,
\qquad
\min_{t\in T}V_t(P_t)>0.
\]
The allocation is the solution; its per-capita egalitarian value is \(\min_t V_t(P_t)\), and its population-weighted value is \(\sum_t\mu_tV_t(P_t)\). The question is whether a query protocol can produce such an allocation with its number of queries bounded by a function of \(\tau\).
My lead anchor is Theorem 1, proved in this paper. It states that, with free disposal, for any number \(n\) of agents there is a bounded-time protocol that gives each agent one connected piece of positive value in an envy-free allocation, using a number of queries that is only a function of \(n\). The theorem’s general-protocol analysis also gives a proportionality guarantee of at least \(1/2^{n-1}\). Its cohort mirror asks the same question with \(n\) replaced by the support size \(\tau\): can the protocol allocate one connected shared parcel per preference cohort, envy-free across cohorts, with positive value for every cohort? Expected direction: yes, in the paper’s bounded-query sense, by running the protocol on one representative of each type. This is the broadest anchor.
Two special cases make that mirror concrete. Theorem 2, also proved here, states that for three agents a bounded-query protocol with free disposal gives each agent a connected piece worth at least \(1/3\) in an envy-free allocation; the paper says this bound is best possible in general. The corresponding Three-Type \(1/3\) Cohort Allocation problem asks for the same type-level allocation above with \(\tau=3\) and \(V_t(P_t)\ge 1/3\) for every type. Expected direction: yes, by the three-agent protocol. Theorem 3, proved here as well, states that for four agents a bounded-query protocol with free disposal gives each agent a connected envy-free piece worth at least \(1/7\). The corresponding Four-Type \(1/7\) Cohort Allocation problem asks for \(\tau=4\) and \(V_t(P_t)\ge 1/7\) for every type. Expected direction: yes, by that protocol.
For these questions, the paper’s protocol is an unusually close anchor: cohort members share all valuation-relevant features, so one type representative supplies the relevant cut and comparison information. The population masses then give a natural aggregate interpretation of the result: Theorem 2’s guarantee implies weighted value at least \(1/3\), and Theorem 3’s implies at least \(1/7\). The paper’s theorems concern query-bounded protocols, though; they do not establish a running time polynomial in \(\tau\) and the bit length of the masses. The general bound may grow quickly with \(\tau\). I would classify this as tractable in the bounded-query sense, while leaving standard polynomial-time tractability open.
The weakness is the cohort interpretation itself. Each cohort shares a parcel as a public-use resource; members do not each receive a separate, exclusive piece. That makes the land-use scenario credible, but it changes the allocation unit. If the authors require a separate exclusive connected piece for every individual in a continuum population, this mirror does not answer their question: masses cannot simply be handed individual parcels from a single finite cake while preserving the paper’s positive-value guarantee. Also, \(\mu_t\) weights aggregate welfare but does not affect the envy constraints or the protocol. The case survives if the authors accept large groups as the claimants; it weakens sharply if they require individual-level cake division.
This paper’s numbered results offer algorithmic protocol anchors, not a hardness result whose population-driven combinatorics might disappear under continuization. The mirror therefore speaks to the programme’s computational scope through oracle query complexity. It covers Theorems 1–3’s connected, envy-free allocations with free disposal; it does not extend their claims to polynomial-time complexity, or to the paper’s cited impossibility results for other cake-cutting variants. Further questions include whether mass-weighted welfare can be optimized subject to cohort envy-freeness, whether protocols can scale polynomially with \(\tau\), and how the answer changes if cohorts must receive individual rather than shared parcels.
The strongest negative case is a mismatch between the paper’s recipients and the continuous population. Theorems 1–3 are genuine computational results: they give bounded-query protocols. But each protocol allocates a separate, exclusive connected interval to every agent. In a nonatomic population, that promise cannot survive. Since each valuation is absolutely continuous with respect to length, any piece with positive value has positive length. Only countably many pairwise-disjoint pieces can have positive length, so almost every individual in a continuum population would receive value zero. Theorem 1’s positivity guarantee and Theorems 2 and 3’s \(1/3\) and \(1/7\) guarantees would collapse; allowing everyone zero value makes envy-freeness trivial. Fractional or lottery allocations could change this, but they change the resource allocation model.
The cohort-commons version is the best rescue, and it also shows the limitation. If each type is a collective claimant that receives one shared parcel, the problem is exactly the paper’s finite-agent problem with \(n=\tau\). Run the existing protocol on one representative valuation per type: Theorem 1 covers any \(\tau\), while Theorems 2 and 3 cover \(\tau=3\) and \(\tau=4\). The masses \(\mu_t\) affect neither envy constraints nor the protocol; they appear only in a later weighted-welfare calculation. So this is a coherent group-allocation problem, but it adds mass labels to a finite query problem rather than opening a continuous-population complexity question. It gives no mass-sensitive algorithmic landscape or bit-complexity question in \(L\).
The same fork defeats all three anchors. For Theorem 1, individual positive shares are impossible in the limit, while type-level shared parcels reproduce the finite theorem. The \(1/3\) and \(1/7\) mirrors face the same fork at fixed support sizes three and four. Making mass consequential—for example, by modeling congestion on shared land, or by requiring a per-capita share inside each cohort—would introduce a new utility or allocation model. Those may be worthwhile problems, but they no longer ask the theorems’ question about envy-free allocations of exclusive connected pieces.
This case has a real weak point: a municipality allocating parcels among a few large, homogeneous neighborhood associations is plausible, and those associations could be treated as the claimants. If the authors accept that as a continuous-population mirror and value its query complexity, the cohort question survives. My objection is narrower: the proposed mirror either fails for individual recipients or reduces to applying the paper’s own finite-agent protocols to the types. That makes it a poor fit for ChoCo’s goal of charting computational questions created by a continuous society.
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.