| paper | d4-conf-sigecom-2005-0019 |
| 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: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Lemma 1
statement extracted from the paper’s text layer
Given types \(t\) with rational masses \(\mu_t\), machine classes \(j\) with per-population supplies \(q_j\), weights \(w_{tj}\), and integer parallelism caps \(k_t\), find the maximum welfare and an optimal assignment of mass to integral bundles. For bundle \(a\in\mathbb Z_{\ge 0}^{J}\), let \(y_{t,a}\) be the mass of type \(t\) receiving it; solve \(\max_{y\ge 0}\sum_{t,a} y_{t,a}\sum_j a_jw_{tj}\), subject to \(\sum_a y_{t,a}=\mu_t\) for each \(t\), \(\sum_{t,a}a_jy_{t,a}\le q_j\) for each \(j\), and \(y_{t,a}=0\) whenever \(\sum_j a_j>k_t\).
The society is a distribution over workload types. Each unit of mass receives an integral bundle of machine units, respecting its type’s parallelism cap; machine supply scales with population. The objective is total welfare, and the decision variables are the masses assigned to each type-and-bundle pair.
The mirror covers Lemma 1’s finite-parallelism social-optimum benchmark. It leaves Theorems 1–3 on equilibrium existence and performance, the best-response analysis, and the convergence, efficiency, and fairness results aside.
The strongest honest case is a narrow one: the finite-parallelism social optimum has a natural high-multiplicity mirror. It does not extend the paper’s central analysis of strategic equilibrium.
The anchor is Lemma 1, proved here. It says that in the finite-parallelism model the social optimum equals a maximum-weight matching: make one left-side vertex \(u_{i\ell}\) for each user \(i\) and each of their \(k_i\) machine slots, one right-side vertex for each machine \(j\), and give edge \((u_{i\ell},v_j)\) weight \(w_{ij}\). A maximum-weight matching gives the optimal allocation. The paper then computes this benchmark using a polynomial-time matching algorithm, specifically the Hungarian algorithm. This is the paper’s clearest named computational anchor; it offers no comparable named hardness result. Theorems 1–3 concern equilibrium existence and performance bounds, rather than computational complexity.
A continuous version would have many users but few workload types. A type \(t\) specifies the complete information this welfare problem uses: its preference weights \(w_{tj}\) for machine classes and its parallelism cap \(k_t\). Let \(\mu_t\) be its population mass, with \(\sum_t\mu_t=1\). The regime might be a large cloud or cluster with many repeated jobs from a small set of application classes, where jobs in a class have the same machine preferences and parallelism. To keep the allocation meaningful as the population grows, specify \(q_j\), the supply of machine units of class \(j\) per population member. This scaling of cluster capacity with workload is part of the proposed mirror.
Here is the problem I would hand to a prover: given rational \(\mu_t,q_j,w_{tj}\) and integer \(k_t\), find an optimal distribution of each type’s mass over integral machine bundles. Let \(a\in\mathbb Z_{\ge0}^n\) denote a bundle, with \(\sum_j a_j\le k_t\), and let \(y_{t,a}\) be the mass of type \(t\) receiving that bundle. Solve
\(\displaystyle \max_{y\ge0}\ \sum_{t,a} y_{t,a}\sum_j a_jw_{tj} \quad\text{subject to}\quad \sum_a y_{t,a}=\mu_t\ \ (\forall t),\qquad \sum_{t,a}a_jy_{t,a}\le q_j\ \ (\forall j).\)
The solution is the optimal welfare and a sparse list of type-and-bundle masses attaining it. Each agent’s bundle remains integral and respects their parallelism cap; only the mass assigned to bundles is fractional. Budgets do not appear because Lemma 1’s social optimum does not use them. For a finite cluster with \(N\) users and \(M_j\) copies of class \(j\), the correspondence is \(\mu_t=N_t/N\) and \(q_j=M_j/N\); the finite matching benchmark is recovered after scaling by \(N\).
I expect this problem to be Class A, tractable. Its configuration LP has potentially many bundle variables, but the pricing question is simple: for a type, choose up to \(k_t\) machine units with the best positive reduced values. That can be done by sorting the available values, so the usual LP separation machinery gives a plausible exact algorithm polynomial in the support size, machine-class count, and input bit length. This is the same computational shape as the paper’s anchor: make the allocation problem explicit, then control the matching or pricing step.
I would expect the authors to recognize this as a continuous analogue of Lemma 1’s welfare benchmark: it preserves their preferences, per-agent parallelism, and aggregate welfare objective, while replacing repeated named users with masses of indistinguishable users. It does not claim that their fixed-budget price-anticipating game has thereby become a tractable continuum game. Further questions include whether the discrete matching optima converge to this LP under high multiplicity, and what equilibrium, efficiency, and fairness questions remain after introducing a suitable continuum notion of strategic behavior.
The weak point is the scope: the paper’s main contribution is about Nash equilibria of a price-anticipating mechanism, while Lemma 1 supplies only the finite-parallelism social-optimum comparator. This mirror covers that comparator, not the equilibrium theorems, best-response analysis, or fairness results. The case survives as a precise mirror of a real, named optimization result, but it is not a continuous version of the paper as a whole.
The strongest negative case is that the proposed mirror drops the paper’s distinctive problem. The paper studies whether strategic users with fixed budgets reach a stable allocation, and what efficiency and fairness that equilibrium has. The proposed LP removes bids, budgets and strategic behavior; it computes the central planner’s welfare benchmark. A continuous model of the price-anticipating game would need to say how agents’ influence on prices behaves as their mass vanishes. That is a genuine modeling choice, and the resulting market may not preserve the strategic question the paper asks.
But that does not defeat the anchor the other analyst chose. Lemma 1 is a named computational result: it reduces the finite-parallelism social optimum to maximum-weight matching. Repeated workload classes with shared preferences and parallelism limits are plausible types, and scaling machine supply per person is a coherent co-modification. The mass distribution over integral bundles preserves the matching interpretation. A simple algorithmic answer would not make the question unworthy, and a narrow mirror of one result is allowed.
So I can argue that the mirror is modest: it continuizes the welfare benchmark, not the paper’s equilibrium analysis. I cannot honestly argue that it is not a worthwhile continuous mirror in any scenario. The anchor survives the strongest objection I can support.
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.