| paper | d4-conf-wine-2019-0024 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Recognition is in \(\mathrm{P}\), and exact rational breakpoint values can be computed in \((L+m\tau)^{O(1)}\) bit operations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(m\) goods, per-capita supplies \(s_j\), finitely many route types \(t\in T\) with positive rational masses \(\mu_t\) summing to \(1\), and a per-person bundle \(x_t\) for each type satisfying route proportions and \(\sum_t \mu_t x_{tj}\le s_j\), decide whether common continuous strictly increasing curves \(f_j\), with \(f_j(0)=0\), make each type’s bundle affordable at unit budget and utility-maximizing for \(u_t(z)=\min_{j\in R_t}z_j\). If so, compute the curve values at the allocated-quantity breakpoints.
A continuum of users represented by finitely many route types \(t\), each with mass \(\mu_t\) and a common per-person bundle \(x_t\). The shared price curves charge each user according to their individual bundle, while masses determine aggregate demand against per-capita supplies.
The mirror covers support recognition and price-curve construction from Theorem 2 for type-homogeneous allocations. It leaves the CES welfare results, weakly increasing price curves, and the other supplementary results unaddressed.
The strongest honest mirror is a finite-support, nonatomic version of the paper’s bandwidth allocation setting. It keeps the paper’s divisible goods, Leontief route preferences and common price curves; it changes the society from finitely many named agents to a distribution over agent types.
My anchor is Theorem 2, proved in this paper. Given agents, goods and an allocation \(x\), the authors build an agent-order matrix \(A\) and solve the LP that maximizes \(\eta\), subject to \(A\mathbf y=0\), \(y_k\ge\eta\) for every coordinate \(k\), and \(y_{-1}=1\). Its optimum is strictly positive if and only if strictly increasing price curves support \(x\); a feasible \(\mathbf y\) encodes the price increases between successive allocated quantities, which can be joined into curves. The paper presents this as a polynomial-time way to find supporting curves or report that none exist. It contains no comparable hardness result, so this is an algorithmic anchor, not a case about hardness dissolving.
Call the mirror Type-Compressed Strict-Price Support. An instance has \(m\) goods, per-capita supplies \(s_j\), and \(\tau\) types with positive rational masses \(\mu_t\) summing to one. In the bandwidth setting, type \(t\) is a fixed route \(R_t\subseteq M\), with utility \(u_t(z)=\min_{j\in R_t}z_j\); everyone has the same unit budget. The input also gives a rational per-person bundle \(x_t\) for each type, in route proportions, with aggregate feasibility \(\sum_t\mu_t x_{tj}\le s_j\) for every good. The question is whether there are common, continuous, strictly increasing price curves \(f_j\), normalized by \(f_j(0)=0\), such that every person of type \(t\) receives a utility-maximizing bundle \(x_t\) affordable at budget one. A solution is the curves, represented by their values at the finitely many allocated-quantity breakpoints and a piecewise-linear interpolation; otherwise the answer is no. This is a feasibility problem, so it has no separate welfare objective.
The population regime is many network users sharing a small number of fixed routes and budgets: for example, a large user base using a modest set of paths through a network. The type is the complete route-and-budget description; mass is the fraction of users on that route. The continuous society’s total demand is \(\sum_t\mu_t x_t\), compared with per-capita capacity. This is a natural version of the bandwidth setting the authors already discuss, and they should recognize support by price curves as their problem. It also keeps the change in the population: divisible goods were already in the paper.
The expected answer is tractable. For a type-homogeneous allocation, the support constraints need one row per type, while the distinct quantity breakpoints number at most \(m\tau\). The paper’s LP therefore gives the natural finite-support algorithm, polynomial in \(m,\tau\) and the rational input bit length \(L\). The masses enter aggregate supply feasibility; once the per-type bundles are fixed, the budget and demand constraints are imposed type by type. Further questions include whether the paper’s CES support result extends directly to mass-weighted welfare \(\big(\sum_t\mu_t u_t^\rho\big)^{1/\rho}\), and how support changes when type masses or allocations vary.
The soft spot is that Theorem 2 is already polynomial in the number of named agents, and compressing identical agents into \(\tau\) types may look like a clean high-multiplicity extension rather than a new complexity boundary. Also, after feasibility is checked, mass has little role in finding the curves. That limits the computational novelty, but not the legitimacy of the mirror: it asks the paper’s actual support question for a genuinely continuous population in a scenario its bandwidth model naturally admits.
The strongest case against is about the scale of the contribution. For the proposed bandwidth mirror, Theorem 2’s pricing LP can be built with one row per route type and breakpoints from the per-person bundles. Its pricing constraints do not depend on the type masses; the masses enter only when checking aggregate supply. With finite support, that gives a direct algorithm polynomial in \(m\), \(\tau\), and the input bit length. The population is genuinely continuous, but the theorem’s pricing computation sees a type-compressed instance of the paper’s finite-agent problem.
The more ambitious CES mirror looks similarly close. Maximize \(\sum_t \mu_t u_t^\rho\) subject to \(\sum_t \mu_t x_{tj}\le s_j\). In the KKT conditions, the mass \(\mu_t\) appears in both welfare and supply terms and cancels, yielding the same per-person price-curve form \(f_j(x)=q_jx^{1-\rho}\). This suggests a finite-support convex program and a direct extension of the paper’s support argument, rather than a new pricing method.
That makes the best negative case one of research priority: these mirrors may be routine type-compressed extensions, with little new complexity structure to uncover. But it does not defeat the anchor. Theorem 2 is an explicit computational result, and the proposed society of many users on a small number of routes is a sensible high-multiplicity regime. Under the programme’s stated criteria, my honest negative case is weak: the mirror is well-posed, and the fact that its answer may follow directly from the paper’s machinery is not enough to rule it out.
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.