| paper | d4-conf-aaai-2015-0113 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Positive-threshold feasibility is in \(\mathrm{P}\): every valid instance with \(q>0\) is infeasible. For every encoded society and every \(N\ge 2\), \(g_N(T,\mu,f)=0\). Hence \(\liminf_{N\to\infty}g_N(T,\mu,f)=0\), and its infimum over all such societies is \(0\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Corollary 1(b)
statement extracted from the paper’s text layer
Given finitely encoded valuation types \(T\) with rational masses \(\mu_t\), and square land whose area scales with household count \(N\), compute envy-free allocations of non-overlapping whole square plots to households, maximizing the minimum type utility relative to per-capita cake value; determine the limiting guarantee as \(N\) grows.
A high-multiplicity housing allocation with type masses \(\mu_t\), per-capita-scaled square land, mass assignments of whole square plots, geometric non-overlap, and a maximin envy-free utility objective.
On a fixed finite cake, uncountably many households cannot receive disjoint positive-area plots, and shrinking plots drives the paper's absolutely continuous utilities toward zero; the proponent mentions scaling land but does not specify the packing-limit model.
fatal: False
The mirror extends Corollary 1(b)'s two-agent guarantee to a high-multiplicity population; it does not cover the three-agent \(1/10\) result, the unbounded-plane result, or the general knife-function bounds.
I can make a plausible case that large land-allocation problems are a natural high-multiplicity setting: types would be complete valuation measures \(V_t\), mass \(\mu_t\) the share of households with each valuation, and utility from a plot \(P\) would remain \(V_t^\square(P)=\sup_{s\subseteq P,\ s\text{ square}}V_t(s)\). One could ask for an envy-free assignment of usable plots that maximizes the least utility across types. The authors might recognize that as a worthwhile extension.
But I can’t honestly make it a mirror anchored in this paper’s qualifying results. The paper has named constructive guarantees, but no named result asserting a computational complexity classification. Its nearest anchors are:
These are geometric fairness guarantees, not results that a problem is in P, hard, FPT, or similar. The paper also gives no finite input model or running-time analysis; its three-agent construction is explicitly an infinite procedure. So none can serve as a valid anchor under the requested rule, and there is no honest “one continuous problem per anchor” to state.
The weakness of the positive case is therefore fundamental: the paper’s continuity lies in land and valuation measures, while its population consists of exactly two or three agents. Replacing those agents with a distribution over household types changes the allocation problem and requires a model for how land supply scales and how a continuum of households receives usable plots. That could be a promising new question, but the paper’s results do not establish it as their continuous mirror.
The strongest case against a mirror is that the paper has no result at ChoCo’s computational level. Its population size is fixed at \(n=2\) or \(n=3\); the results concern geometric fairness guarantees for particular procedures. None classifies a computational problem by running time, hardness, or approximability, and the paper gives no finite input model for its valuation measures. A new complexity problem might be inspired by the paper, but it would not mirror one of its computational results.
Each proposed anchor has that limitation. Claim 2 bounds the utility guaranteed by a knife procedure in terms of geometric loss. Its proof uses continuity and the intermediate value theorem; it provides no representation of valuations or running-time bound. Corollary 1(b) gives the exact \(1/4\) guarantee for two agents, with the upper bound coming from earlier work. It is a geometric fairness result, not a complexity result. Corollary 2(c) gives a \(1/10\) guarantee for three agents. The associated three-knife procedure is explicitly infinite, so it supplies no finite algorithm whose complexity could be continuized.
The best proposed mirror is a large housing allocation problem: households fall into valuation types, land supply grows with population, and each household receives a square plot. That scenario is imaginable, but it runs into a deeper mismatch with the paper’s allocation model. Each named agent receives a positive-area piece of a shared Euclidean cake. A continuum of agents cannot each receive a positive-area plot from a measurable shared region of the plane: there can be only countably many pairwise disjoint positive-area pieces. If plots shrink as the population grows, the paper’s absolute-continuity assumption makes their utility vanish. Rescaling values to avoid that collapse, or letting agents receive lotteries or fractional claims on plots, changes the fairness object; in particular, the square utility \(V_t^\square(P)=\sup_{s\subseteq P,\ s\text{ square}}V_t(s)\) does not turn a fractional average of parcels into an individual usable square.
The programme permits co-modifications such as per-capita supply and fractional type averages, so those choices alone do not invalidate the proposal. The difficulty is that this case needs a new account of how a continuum of households can receive non-overlapping, individually usable plots while retaining the paper’s envy-free criterion. The paper’s two- and three-agent guarantees do not supply that account. I can’t prove that no continuous-population spatial-allocation problem could be worthwhile; the universal claim is too broad to establish from this paper. The strongest honest negative conclusion is narrower: none of the three anchors survives as a ChoCo computational mirror, and the most plausible population extension requires a new allocation model before it becomes a mirror at all.
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.