| paper | d4-conf-ijcai-2020-0821 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm P\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.2
Given a finite plot-graph template with rational per-capita plot supplies, rational masses over supported singleton and friend-pair types, and each type's complete valuation profile and friendship value, maximize total welfare (or decide whether it reaches a rational threshold) by assigning mass to feasible whole-bundle allocations. Each singleton unit receives one plot and each pair unit receives two distinct plots; type mass may split among bundles, but every unit receives an integral bundle.
A configuration LP over rational mass variables for singleton-to-plot and friend-pair-to-plot-pair assignments, with type-mass, plot-supply, and adjacency constraints defined by the finite plot-graph template; each configuration preserves the paper's integral bundle and friendship bonus.
The mirror still needs an explicit scalable plot-graph template that preserves conflicts among overlapping adjacencies; the proposed per-capita supplies do not yet specify one.
fatal: False
The mirror covers the complete-information welfare objective in Theorem 3.2's degree-one friendship regime, with binary valuations and uniform friendship value; it leaves the paper's other hardness results and its strategic mechanism results uncovered.
I would lead with Theorem 3.2, proved in this paper by reduction from the cited NP-hard problem Path Rainbow Matching. It says that deciding whether an allocation has social welfare at least a given threshold is NP-complete even when plot values are binary, friendship values are uniform, each agent has at most one friend, and the plot graph is one path plus isolated plots. That is the cleanest anchor because its degree-one restriction gives a natural way to describe repeated agents as friend-pair types. [The paper](https://people.scs.carleton.ca/~alantsang/files/landalloc20.pdf)
My proposed mirror is Mass-SW-Opt for Friend-Pair Land Allocation. Picture a large planned development with many buyers but relatively few recurring preference profiles: for example, many sibling or friend pairs with the same two plot-value profiles and the same friendship value. The population is a rational-mass distribution over singleton types and friend-pair types. A pair type records both members’ complete binary valuation profiles and their friendship value; its mass is the fraction of pair units of that type. The degree-one condition makes this representation exact: the friendship structure consists only of disjoint pairs and singletons.
The land supply scales with population. An instance gives a finite per-capita catalogue of plot types, their rational supplies, and the available adjacent-plot-pair supplies in the plot template. The supplies sum to the population mass, normalized to one. The template can be a path with isolated plot types, as in the theorem. An allocation assigns each singleton unit one whole plot and each pair unit two whole plots. A pair unit earns both members’ plot values and receives the friendship bonus if its plots are adjacent. The question is to maximize total welfare, or decide whether it reaches a rational threshold. Mass may split across assignments, but every unit of mass receives an integral bundle.
Concretely, let \(y_{a,p}\) be singleton mass of type \(a\) assigned a plot of type \(p\), and \(x_{d,p,q}\) be mass of pair type \(d\) whose first and second members receive plot types \(p\) and \(q\). The instance supplies rational type masses, plot supplies, and adjacency-pair supplies. The constraints require each agent type’s mass to be assigned, each plot supply to be used, and adjacent assignments to respect the available adjacent-pair supply. The objective is
\(\sum_{a,p}u_a(p)y_{a,p}+\sum_{d,p,q}\bigl(u_{d,1}(p)+u_{d,2}(q)+2\phi_d\mathbf{1}_{pq\text{ adjacent}}\bigr)x_{d,p,q}\).
This is a finite linear program: there are polynomially many singleton and pair configurations in the number of types and plot types. I expect this mirror to be Class A. It asks the same underlying question as SW-Opt—maximize land-allocation welfare with friendship externalities—and its expected tractability comes from assigning mass over whole configurations for disjoint friend pairs.
I think the authors could recognize this as their optimization problem in a high-multiplicity regime: preferences, friendship value, and the utility function are preserved, while repeated singleton and pair profiles have rational masses and plot supplies scale with the population. It covers Theorem 3.2’s SW-Opt result, not the paper’s strategic mechanism results.
The weak point is that Theorem 3.2’s reduction uses many color-specific valuation profiles, so its hard instances do not themselves demonstrate a large population over a small support. Also, summarizing land by per-capita plot and adjacency supplies may lose global constraints of a particular finite path unless the template encodes them. Those are substantive limits: the theorem motivates this question but proves neither hardness nor tractability for the mirror. The next questions are whether the LP remains faithful for more detailed path templates, how its solutions round to finite developments, and whether the continuous problem becomes hard when the friendship support or degree grows.
Theorem 3.2 is a real computational anchor: it proves NP-completeness for welfare maximization under substantial restrictions. My best case against a mirror is about the population regime, not the result. Here an agent’s complete type includes her values for every named plot; a friend-pair type must capture both agents’ full value profiles and their friendship weights. In the paper’s small village setting, those pairs and their site preferences are naturally individuated. As a development grows, the number of plot identities grows too. Grouping buyers by coarse features such as “prefers a view” may create repeated types, but it may also discard which specific plots they value and how those plots sit in the adjacency graph. The paper’s reduction uses color-specific profiles and does not itself supply a convincing large population with small support.
The proposed LP over plot and adjacency *types* also needs more detail to be faithful. On a path, edges share vertices; aggregate edge supplies alone do not record which adjacent assignments compete for the same plot. A repaired model can preserve every plot vertex and enumerate configurations: assign each singleton type to a plot, and each friend-pair type to an ordered pair of distinct plots, with capacities at every plot. Mass variables then give a finite LP, with size polynomial in the number of plots and supported types. That is a coherent continuous mirror, and it keeps each infinitesimal pair’s bundle integral.
That repair is also why the negative case is weak. A large development with many repeated full pair profiles and scaled plot supplies is conceivable, and its mass version asks the same welfare question. The paper does not establish that this is a compelling regime, but neither the location-specific geometry nor the NP-hardness result rules it out. I can make a case to defer this mirror until someone gives a concrete setting with repeated complete types and a faithful spatial model; I cannot honestly argue that no worthwhile scenario exists.
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.