| paper | d4-conf-sagt-2011-0013 |
| 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: The bound \(\operatorname{PoA}\leq 1+2(m-1)\gamma_m^*\) holds for every stated nonatomic instance. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
Given rational type masses and a symmetric binary affinity matrix, compute the worst welfare ratio between any feasible allocation and a two-sided exchange-stable mass allocation, or decide for rational \(R\) whether that ratio exceeds \(R\). In particular, determine whether the ratio is at most \(1+2(m-1)\gamma_m^*\), the analogue of Theorem 5’s bound.
Use \(m\) houses, a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), common house values \(D_h\), and symmetric binary affinities \(K_{tr}\). Each house has capacity \(1/m\). An allocation \(x_{th}\geq 0\) satisfies \(\sum_h x_{th}=\mu_t\) and \(\sum_t x_{th}=1/m\). Type \(t\)’s per-capita utility in house \(h\) is \(\widehat U_t(h;x)=D_h+\sum_r K_{tr}x_{rh}\), and normalized welfare is \(W(x)=\sum_{t,h}x_{th}D_h+\sum_h\sum_{t,r}K_{tr}x_{th}x_{rh}\). Call \(x\) exchange-stable when no infinitesimal members of types \(t,u\), present in different houses \(h,g\), both weakly gain by exchanging houses with at least one strict gain, with gains evaluated in the aggregate field \(x\). Define \(\gamma_m^*=\max_{z}\frac{\sum_h\sum_{t,r}K_{tr}z_{th}z_{rh}}{\sum_{t,r}\mu_t\mu_rK_{tr}}\), taking the zero-affinity case separately. This is a cohort-level limit of the paper’s one-sided housing market; matching its per-capita utilities corresponds to scaling house values with cohort size.
After per-capita normalization, the affinity between the two swapped individuals vanishes, while Theorem 5 also relies on integral utility differences; the atomless stability test and bound need a fresh proof.
fatal: False
The mirror covers Theorem 5’s welfare guarantee, and thus Greedy’s implied competitive ratio, in the one-sided setting with binary affinities and equal house capacities. It leaves Theorem 6’s more general bound, the two-sided existence results, and the simulations aside.
There is a limit to the positive case: the paper has no named theorem classifying a problem as NP-hard, polynomial-time solvable, FPT, or similar. Its named results are about existence and welfare guarantees. So there is no strict complexity anchor here, and I would not present one as though the paper had proved a complexity classification.
The strongest nearby anchor is Theorem 5, proved in this paper (with details in Appendix B.1). In the one-sided market, with full quotas, students sharing the same house desirabilities, unweighted friendship edges \(w(s,t)\in\{0,1\}\), and \(q_h\ge 2\), it proves that if all house quotas are equal and/or all house desirabilities are equal, then
\[
\min_{\mu\ \text{stable}} W(\mu)
\ \ge\
\frac{\max_\mu W(\mu)}{1+2(m-1)\gamma_m^*}.
\]
Equivalently, it upper-bounds the price of anarchy. The theorem’s assumptions matter: the price-of-anarchy analysis is for students only, with houses having no utility of their own.
A credible high-multiplicity regime is a large housing or team-assignment cohort where students fall into a moderate number \(\tau\) of affinity groups. Members of a type have the same house valuations and the same affinity to every group; the \(N\) students may number in the thousands while \(\tau\) remains small. This is a meaningful restriction of the paper’s social network model: it describes group-level affinity or block homophily, rather than arbitrary friendships between named individuals.
Here is the continuous mirror I would put to a prover. An instance has \(m\) houses, types \(T\), rational type masses \(\mu_t\) summing to one, common house desirabilities \(D_h\), and a symmetric binary affinity matrix \(K_{tr}\). House capacities are equal, with mass \(1/m\) each. The decision variable is \(x_{th}\), the mass of type \(t\) assigned to house \(h\), subject to \(\sum_h x_{th}=\mu_t\) and \(\sum_t x_{th}=1/m\). A type-\(t\) resident’s utility in house \(h\) is
\[
\widehat U_t(h;x)=D_h+\sum_r K_{tr}x_{rh},
\]
and normalized social welfare is
\[
W(x)=\sum_{t,h}x_{th}D_h+
\sum_h\sum_{t,r}K_{tr}x_{th}x_{rh}.
\]
Call \(x\) exchange-stable if there are no types \(t,u\) with positive mass in different houses \(h,g\) such that both gain weakly by exchanging houses and at least one gains strictly. This preserves the paper’s peer effects, exchange-stability, and welfare objective; the population, rather than the outcome space, is what has become continuous.
The computational question is: given this instance and a rational threshold \(R\), is
\[
\sup_{x\ \mathrm{feasible},\,y\ \mathrm{exchange\text{-}stable}}
\frac{W(x)}{W(y)}>R?
\]
Assume the denominator is bounded away from zero. The \(\sup\) handles the possibility that the stable allocations are not a closed set. The optimization version asks for the supremal ratio and the allocations, or limiting sequence, that approach it. The natural continuous analogue of Theorem 5 is whether this ratio is bounded by \(1+2(m-1)\gamma_m^*\), with \(\gamma_m^*\) defined as the maximum fraction of total affinity mass placed within houses.
For this exact computation problem, my tentative expectation is hardness transfers (Class B): replication makes large discrete cohorts approximate the same type-mass allocations, while the combinatorics in the house and type interactions remain. That is a prediction, not a result of this paper; a reduction would have to address fractional allocations and stability at ties. The first follow-up question is whether Theorem 5’s bound survives this atomless model, including at such boundary cases. Others are whether the bound is tight for continuous instances and whether the exact ratio admits algorithms parameterized by \(m\) or \(\tau\).
The weakest point is the block-affinity assumption. In the paper, a student’s friends are individual vertices; here, students of one type interact identically with every member of each type. Many real friendship networks will not fit that model. The mirror is strongest for markets whose peer effects are genuinely cohort-level, and it covers only the paper’s one-sided welfare-efficiency result—not its general two-sided existence theorem or its matching algorithms.
The strongest case against starts with the paper’s results: it contains no named theorem classifying a computational problem as tractable, hard, or parameterized. Theorem 2 proves existence through a potential function; Theorem 4 relates welfare maxima to stability; Theorems 5 and 6 give price-of-anarchy bounds. The greedy and MCMC procedures are described, but the paper gives no running-time guarantee for them. So there is no computational classification here for a continuous version to preserve.
Theorem 5 is the closest anchor, but it is a structural inequality, not an algorithmic result. Its natural continuous analogue is whether the same bound holds for a mass-allocation model. The proponent instead proposes a new decision problem: compute the worst welfare ratio over all stable allocations. That could be a computational question, but the paper neither poses it nor establishes that computing this ratio is a computational bottleneck. Adding a threshold \(R\) makes the question formally decidable; it does not make it a computational mirror of Theorem 5.
There is also a substantive change inside that proposed mirror. The theorem concerns a graph of named students and uses binary edges; its proof exploits integrality, for example when \(\alpha<1\) implies \(\alpha\leq0\). The proposed model replaces those edges with type-level affinities and fractional house populations. Its stability test treats a swap between two infinitesimal students as meaningful, even though that swap changes no type masses. Meanwhile, the finite model’s direct friendship between the two students who swap disappears under the normalized mass formulation. This is a reasonable mean-field model of group affinity, but it changes the peer interactions that govern exchange stability. The original bound does not simply carry over.
The best version of the mirror would make the block structure explicit: large cohorts with common house values and affinities to each cohort, assigned to a small number of houses. That is a plausible high-multiplicity regime, and it respects the programme’s focus on the population. But it is a restriction to a graphon-like interaction model, not a continuum treatment of the paper’s arbitrary friendship graph. Preserving the finite model’s individual ties instead makes type descriptions depend on particular neighbors, generally defeating the small-support premise. The block model may still be a worthwhile new study; the paper alone gives little reason to treat it as a computational mirror of its results.
So the negative case is strongest on the absence of a computational anchor and the change in what stability measures. It is not airtight: a large, repeated cohort with genuine group-level affinities is credible, and asking whether Theorem 5’s bound survives that limit is well-posed. I would resist claiming that no worthwhile mirror exists in any scenario; the honest objection is that the proponent has identified a plausible adjacent model, not a computational result of this paper that continuization directly takes up.
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.