| paper | d4-conf-ijcai-2011-0129 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 1 is a named computational result, but its proposed continuation replaces atomic Nash equilibrium with Wardrop equilibrium. With shared strictly increasing delays, every Wardrop allocation already rules out positive-mass weakly improving deviations, so the social-network condition contributes nothing. That leaves a different problem from the one Theorem 1 establishes.
fails bit b-changes — the continuum limit changes the question
The proposed formulation targets Theorem 1 alone; it does not cover Theorem 2 or Proposition 1.
The strongest case is a narrow mirror of Theorem 1, proved in Section 3 of this paper. It says that every resource selection game with strictly increasing delays and any associated social network has a state that is both a Nash equilibrium and a considerate equilibrium, and that such a state can be computed in polynomial time. The paper proves this result; it is not merely citing an algorithm. The paper offers no comparable named hardness result, so this algorithmic theorem is the right anchor.
A plausible high multiplicity regime is a large routing or service platform whose users choose among congestible resources and belong to a small number of recurring social-network roles. Many users might share a role’s preferences and the same pattern of ties to other roles. The population could be enormous while the number \(\tau\) of such roles remains modest. This is a particular instance regime, not a claim that arbitrary social networks compress well.
Here is the mirror I would put to a prover: Continuous Considerate RSG Equilibrium. An instance has a finite resource set \(R\), a finite set of types \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), a symmetric matrix \(H\in\{0,1\}^{T\times T}\), and rational strictly increasing piecewise-linear delay functions \(D_r:[0,1]\to\mathbb{Q}_{\ge 0}\). Type means a complete *pre-action* description: common resource options, delay preferences, and network role. \(H_{tt'}=1\) means that members of those types are tied; \(H_{tt}=1\) means that any two distinct members of type \(t\) are tied. The population is atomless, and the matrix describes its block social network.
An allocation is \(x_{tr}\ge 0\), where \(x_{tr}\) is the mass of type \(t\) assigned to resource \(r\), with \(\sum_r x_{tr}=\mu_t\). Each agent still chooses one resource; \(x\) records how the mass is distributed, not a fractional bundle for an individual. Resource load is \(\ell_r=\sum_t x_{tr}\), and an agent using \(r\) incurs cost \(D_r(\ell_r)\).
The requested output is an allocation \(x\) that is both a Wardrop equilibrium and a considerate equilibrium. Wardrop means that if \(x_{tr}>0\), then \(D_r(\ell_r)\le D_q(\ell_q)\) for every resource \(q\). Considerate equilibrium means there is no positive-mass weak considerate deviation: a coalition drawn from types whose \(H\)-entries make them pairwise adjacent cannot reassign its selected mass so that every coalition member weakly lowers their cost, every neighbor outside the coalition weakly lowers theirs, and a positive mass of coalition members strictly lowers its cost. The computational question is whether every such instance admits this allocation and whether one can find it in time polynomial in \(m=|R|\), \(\tau=|T|\), and the input bit length \(L\). There is no scalar objective to minimize; the output is a stable allocation.
This keeps the paper’s underlying question: resource choice under congestion, clique-restricted coordination, and the requirement that a deviation not harm neighbors. The mass-level delays and allocations are the necessary co-modification when the population becomes continuous. A finite population split into many members of each role, with the same role-to-role tie pattern, gives the natural high-multiplicity bridge to the paper’s RSGs. It is plausible that the authors would recognize this as their equilibrium problem in a continuum population regime, though it deliberately covers role-symmetric networks rather than every graph.
I would tentatively expect Class A: tractable. The outcome depends on finitely many type-resource masses and aggregate loads, which puts a continuous potential or stability formulation within reach. But Theorem 1 does not establish this extension. Its proof uses individual moves, integer occupancy counts, and a finite descent argument. In the continuum, mass can move in arbitrarily small amounts, and the proof’s counting inequalities may no longer apply. A key follow-up is whether the type-level clique-deviation condition has an efficient separation method, or whether it creates continuum-specific hardness. Another is whether limits of finite equilibria are exact continuous equilibria or only approximate ones.
The weakest point is that the mirror changes both the population and the congestion scale: individuals become negligible, costs depend on population shares, and the theorem’s discrete termination argument may disappear. Also, few-type block networks are a restricted scenario. Those are real limits, but they do not make the question a different equilibrium problem: its actions, congestion effects, social ties, and considerate stability condition all remain intact. This case covers Theorem 1 alone; it does not mirror Theorem 2’s infinite dynamics construction or Proposition 1’s partition special case.
Theorem 1 is the right anchor, and the platform scenario is plausible: many users could share a small set of social roles. The problem is what the equilibrium condition becomes once those users are a nonatomic population.
In the proposed model, every user who chooses a resource at a Wardrop equilibrium pays the same minimum delay, say \(\lambda\). For each resource \(r\), let \(b_r\) be the largest load at which \(D_r(b_r)\le\lambda\), with \(b_r=0\) if even an empty resource costs more than \(\lambda\). Strictly increasing delays imply that an occupied resource is at exactly its capacity \(b_r\); an unoccupied resource has capacity zero. Thus \(\sum_r b_r=1\).
Now consider any positive-mass deviation whose members all weakly improve. They started at cost \(\lambda\), so no resource they move onto can end above its capacity \(b_r\). A resource they do not enter cannot gain load, and therefore also cannot exceed its capacity. The deviated loads sum to one, so every resource must remain exactly at capacity. No delay changes, and no member strictly improves. This rules out every weakly improving coalition, whether or not it is a clique and whatever the social network \(H\). The considerate condition therefore adds nothing at a Wardrop allocation.
A Wardrop allocation can be found by minimizing the usual separable congestion potential,
\[
\Phi(\ell)=\sum_{r\in R}\int_0^{\ell_r}D_r(z)\,dz
\quad\text{subject to}\quad
\sum_r\ell_r=1,\ \ell_r\ge0.
\]
With the proposed piecewise-linear delays, this is a finite convex optimization problem. The resulting continuous question has lost the feature that makes Theorem 1 a result about social networks: the network no longer constrains which equilibria qualify. Requiring only a considerate equilibrium does not rescue it, since the Wardrop solution already supplies one. The finite proof’s individual moves and occupancy counts have disappeared with the individual’s nonzero effect on congestion.
There are ways to recover strategic effects, but they change the model. If each type’s entire mass must move as one indivisible bloc, the agents are weighted atomic players; outcomes then depend on how one partitions a type into blocs. If types instead have different delay functions or resource options, the common-delay argument can fail, but the result is no longer about the paper’s symmetric RSGs with a delay \(d_r(\ell_r)\) shared by all players. That could be a worthwhile extension, and the authors might recognize it as a new problem. It does not rescue the faithful continuous mirror proposed here. So the negative case is strong against this anchor in its stated symmetric setting, but it cannot honestly establish that no enriched, heterogeneous version could be worthwhile.
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.