| paper | d4-conf-ijcai-2021-0351 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 6.9
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a base rectangular estate \(L\), one integrable density \(f_t\) per type, and a fixed separation distance \(s\), consider each integer scale \(q\ge2\) for which \(q\mu_t\) is integral. Scale the estate to \(L_q=\sqrt q\,L\), extend each density by \(f_{t,q}(x,y)=f_t(x/\sqrt q,y/\sqrt q)\), and set \(m_q=\lceil h^{-1}(17\cdot2^{q-3})\rceil\), where \(h(m)=m/\log_2(2m)\). Can one compute \(q\mu_t\) axis-parallel rectangles for each type \(t\), all pairwise \(s\)-separated, such that each type-\(t\) household receives value at least \(\mathrm{MMS}^{m_q,s}_{t,q}-\varepsilon\), where \(\mathrm{MMS}^{m_q,s}_{t,q}\) is that type’s \(1\)-out-of-\(m_q\) maximin share on \(L_q\)?
Households are grouped into complete valuation types with masses \(\mu_t\); at scale \(q\), type \(t\) has \(q\mu_t\) households and the rectangular land supply scales as \(L_q=\sqrt q\,L\). The decision is the placement and dimensions of one integral plot per household, subject to pairwise separation and the type-specific MMS threshold; the task is to find a feasible allocation.
With the proposed scaling, the benchmark parameter \(m_q\) grows exponentially, so bounded per-area densities can make the guaranteed value per household tend to zero; the proponent notes the rapid growth but does not address this loss in substantive fairness.
fatal: False
The mirror covers the arbitrary-rectangle \(s\)-separated MMS allocation guarantee of Corollary 6.9 for a scaled population; it leaves the paper’s fat-rectangle and square bounds, impossibility results, and other allocation and query-complexity results aside.
The best mirror I see is a high multiplicity land allocation problem. A type is an agent’s complete valuation profile: here, their density function, usable shape family, and separation requirements. The mass \(\mu_t\) is the fraction of households with that profile. This fits a plausible setting such as a large development or land portfolio serving many households from a small set of recurring valuation classes. The land supply must grow with the population: take a base rectangular estate \(L\), and at population scale \(q\) use the rectangle \(L_q=\sqrt q\,L\), keeping physical separation \(s\) fixed. This keeps land per capita stable. The density for type \(t\) can be lifted from \(L\) to \(L_q\) by scaling its coordinates, so value per unit of physical area stays stable too.
My anchor is Corollary 6.9, proved in this paper. Define \(h(m)=m/\log_2(2m)\). For a constant number \(n\ge2\) of agents, the authors prove that, for every \(\varepsilon>0\), one can compute an \(s\)-separated allocation of a rectangular estate into axis-parallel rectangles in which each agent \(i\) receives value at least \(\mathrm{MMS}^{m,s}_i-\varepsilon\), where \(m=\lceil h^{-1}(17\cdot 2^{n-3})\rceil\). The computation is polynomial in \(\log(1/\varepsilon)\) in the paper’s Cut/Eval query model. This is an algorithmic anchor; the paper gives no named NP-hardness result to anchor on. Its bound uses the authors’ guillotine-partition algorithm and geometric separation results, rather than a hardness classification.
Here is the corresponding question, which I would call Typed Separated MMS Allocation at Scale. An instance consists of a finite type set \(T\), binary-rational masses \(\mu_t>0\) summing to \(1\), a base rectangular estate and one integrable density \(f_t\) per type, a separation distance \(s\), an admissible population scale \(q\) for which \(q\mu_t\) is integral, and an error tolerance \(\varepsilon>0\). The estate and densities are scaled to \(L_q\) as above. Let \(m_q=\lceil h^{-1}(17\cdot 2^{q-3})\rceil\), and let \(\mathrm{MMS}^{m_q,s}_{t,q}\) be the type’s \(1\)-out-of-\(m_q\) maximin share on \(L_q\), using axis-parallel rectangles. Find \(q\mu_t\) rectangles for each type \(t\), with all chosen rectangles pairwise \(s\)-separated, such that every type-\(t\) household receives value at least \(\mathrm{MMS}^{m_q,s}_{t,q}-\varepsilon\). The input society is specified by masses rather than a list of named agents; the solution still gives every household one integral plot.
I expect this problem to be continuum-specifically hard, with low confidence. The combinatorics may remain in the geometry of packing separated rectangles even when the number of types is small. The anchor establishes an algorithm for each fixed \(q\), but it does not give a uniform polynomial-time bound as \(q\) grows: the result assumes \(n\) constant, and its guarantee parameter grows rapidly with \(n\). So the continuous version asks whether the fixed-population algorithmic picture survives in a high-multiplicity regime; the paper does not answer that. Useful follow-up questions are whether fixed support \(\tau=|T|\) helps, whether square or fat-rectangle restrictions yield a uniform algorithm, and whether any hardness comes from geometric packing even with one type.
The authors should recognize this as a high-multiplicity version of their allocation problem: it preserves each type’s valuation, the separation rule, rectangular plots, and the ordinal MMS benchmark. The weakest point is that a literal continuum of agents cannot each receive a separated plot inside a bounded estate when \(s>0\). The scaling regime is therefore essential, and it makes this an asymptotic family of finite allocations represented by \(\mu\), rather than a one-shot allocation to uncountably many agents. I think that co-modification is defensible here, but it is the main reason this is a promising mirror rather than an unambiguous one.
Corollary 6.9 is a genuine computational anchor, so the negative case cannot rest on the paper having no algorithmic result. The problem is that its algorithm is stated for constant \(n\), and its exponent depends on \(k=\lceil h^{-1}(17\cdot 2^{n-3})\rceil\). Taking \(n=q\) therefore gives no uniform complexity bound for a growing population. Its particular benchmark also weakens sharply under the proposed scaling: with bounded value density on an estate of area \(q\), total value is \(O(q)\), while \(m_q\) grows exponentially, so \(\mathrm{MMS}^{m_q,s}\le O(q/m_q)\). The guarantee tends to zero.
A stronger mirror would use the paper’s square or fat-rectangle result, where the benchmark parameter is linear in the number of agents. That avoids the vanishing-guarantee problem, but it does not resolve the deeper mismatch: the output is a set of physically separated plots. In a bounded region with fixed \(s>0\), choosing one point from each nonempty plot gives points that are pairwise at least \(s\) apart. There can be only finitely many such points. Thus a positive mass of agents cannot each receive an exclusive plot in a fixed estate while preserving the paper’s separation constraint.
Scaling the estate by \(\sqrt q\) makes \(q\) finite allocations possible, but after normalizing the estate back to fixed size, the separation becomes \(s/\sqrt q\) and vanishes in the limit. Keeping a positive normalized separation instead prevents the number of plots from growing with \(q\). An expanding-space limit might preserve physical spacing, but then the population is represented by a spatial packing or point process as well as type proportions; \(\mu\) alone does not describe a feasible allocation. Representing outcomes as type-level averages loses the pairwise geometric constraint, while listing the plots retains a growing finite configuration.
So the proposed scaled problem is defensible as a high-multiplicity family of finite packing problems, but I would not count that alone as a continuous mirror of Corollary 6.9: the theorem supplies no uniform algorithm for that family, and the aggregate type-mass model cannot retain its defining spatial constraint on a fixed domain. The weakness in this negative case is real, though: an authors-recognizable thermodynamic or spatial high-multiplicity model could still be worthwhile. I cannot honestly rule out every such scenario; the case against a continuous mirror is strongest against the proposed type-mass formulation, not against the entire research direction.
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.