| paper | d4-conf-wine-2024-0004 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given sellers \(K\), items \(J\) partitioned among them, \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), per-capita budgets \(b_t\), values \(v_{tj}\), per-capita supplies \(s_j\), and positive initial budget splits \(\beta^0_{tk}\), run the paper’s pacing-equilibrium process with mass-weighted feasibility \(\sum_t\mu_t x^r_{tj}=s_j\) and update \(\beta^{r+1}_{tk}=b_t u^r_{tk}/u^r_t\), where \(u^r_{tk}=\sum_{j\in J_k}v_{tj}x^r_{tj}\) and \(u^r_t=\sum_k u^r_{tk}\). Does this process converge to a continuum competitive equilibrium, and what bit-sensitive round and per-round computation bounds suffice to output a feasible average allocation \(\hat{x}\) with \(G^*-G(\hat{x})\le\epsilon\), where \(G(x)=\frac{\sum_t\mu_t b_t\log(\sum_jv_{tj}x_{tj})}{\sum_t\mu_t b_t}\) and \(G^*\) is its maximum over feasible allocations?
A finite-support society of advertiser types with rational mass \(\mu_t\), per-capita budgets and valuations, and per-capita item supplies. The decisions are type-level budget shares \(\beta_{tk}\) and per-capita allocations \(x_{tj}\), with aggregate feasibility weighted by \(\mu_t\); the objective is the mass-weighted Eisenberg–Gale objective. This is exactly representable as a finite Fisher market with \(\tau\) buyers of budgets \(\mu_t b_t\).
The type-mass market is exactly equivalent to a finite Fisher market with \(\tau\) buyers whose budgets are \(\mu_t b_t\), so the mirror adds no new algorithmic structure beyond applying Theorem 1 to a compressed high-multiplicity input.
fatal: False
The mirror covers Theorem 1’s fixed-point and convergence result and its averaged objective guarantee; it leaves the buyer-incentive result and the seller revenue, competition, and fairness results without continuous analogues.
The strongest positive case is a continuous-population version of the paper’s dynamics result.
The anchor is Theorem 1, proved in this paper: a competitive equilibrium is a fixed point of proportional dynamics, and the dynamics converges to a competitive equilibrium. The proof also gives an \(O(T^{-1})\) rate for the time-averaged Eisenberg–Gale objective gap after \(T\) rounds. This is an algorithmic convergence result, though not a formal claim that a problem is in P: the paper gives no named NP-hardness, FPT, or bit-complexity result. With no comparable hardness result in the paper, this is the useful lead.
A plausible regime is a large advertising market with many small advertiser accounts using a finite set of standardized campaign templates. A type is the complete per-account profile used by the model: its per-capita budget and its value for each item. The mass \(\mu_t\) of type \(t\) is its fraction of the advertiser population. The regime of interest has many accounts but moderate support size \(\tau\). To keep the market scale meaningful as the population grows, inventory supply scales with the population too; in normalized units, each item has a fixed supply per unit of population. Standardized budgets and campaign values make repeated types plausible, though only for a stylized market.
Here is the mirror I would hand to a prover: Continuum Proportional Dynamics for Linear Fisher Markets. An instance has a finite set of sellers \(K\), a finite set of items \(J\) partitioned among sellers, and \(\tau\) types with rational masses \(\mu_t>0\), where \(\sum_t\mu_t=1\). Each type has a rational per-capita budget \(b_t>0\) and rational values \(v_{tj}\ge 0\); each item \(j\) has rational per-capita supply \(s_j\). The instance also specifies a positive initial per-capita budget split \(\beta^0_{tk}\) for each type and seller, summing to \(b_t\).
In round \(r\), each seller runs the paper’s pacing-equilibrium auction on its items. Let \(x^r_{tj}\) be the per-capita allocation to type \(t\), with \(\sum_t\mu_t x^r_{tj}=s_j\), and let \(u^r_{tk}=\sum_{j\in J_k}v_{tj}x^r_{tj}\), \(u^r_t=\sum_k u^r_{tk}\). The type’s budget update is \(\beta^{r+1}_{tk}=b_tu^r_{tk}/u^r_t\). Ask whether this process converges to a continuum competitive equilibrium and, given \(\epsilon>0\), how many rounds suffice to compute an \(\epsilon\)-accurate equilibrium allocation. More precisely, with \(G(x)=\big(\sum_t\mu_tb_t\log(\sum_jv_{tj}x_{tj})\big)/\big(\sum_t\mu_tb_t\big)\), the computational output can be the feasible average allocation \(\hat{x}=T^{-1}\sum_{r=1}^T x^r\) satisfying \(G^*-G(\hat{x})\le\epsilon\), where \(G^*\) is the optimum over feasible allocations. The paper’s averaged-objective guarantee is the direct lead for this output; concavity makes the averaged allocation at least as good as the average objective value.
I expect this to be Class A, subject to proving a bit-sensitive bound. With \(\tau\) types, each round’s pacing-equilibrium computation is a market problem over the type support, and the paper’s potential argument appears to extend by replacing sums over buyers with mass-weighted sums over types. The questions for the prover are whether that extension holds for all admissible instances, and whether the round count and per-round computation are polynomial in the number of items, sellers, \(\tau\), input bit length, and \(1/\epsilon\). Further questions include the exact bit complexity of computing the limiting equilibrium and whether an EG objective guarantee also yields useful bounds on price or equilibrium residuals.
This mirror covers Theorem 1’s convergence and rate result. It does not claim to mirror the buyer-incentive or seller-competition results: those would need separate arguments about how deviations work when a type has positive mass. Nor is the mirror just about divisible outcomes or continuous time; it makes the buyer population continuous while keeping the dynamics’ rounds discrete.
The weak point is the regime. Advertisers often have distinct budgets and valuation profiles, and the paper itself studies finitely many buyers. Exact high multiplicity is most credible for standardized cohorts, not for every real advertising market. A second limitation is that Theorem 1 gives convergence in rounds, not a complexity bound in the continuous instance’s input size. That leaves real work for the mirror, but it also gives the work a clear target: determine whether the type-mass version is efficiently computable.
The strongest case against this mirror is that Theorem 1’s dynamics already runs on aggregate market quantities. In the proposed model, set \(y_{tj}=\mu_t x_{tj}\) and give type \(t\) a total budget \(\mu_t b_t\). Then \(y\) is exactly the allocation of a finite Fisher-market buyer with that budget. The Eisenberg–Gale objective changes only by the constant \(\sum_t \mu_t b_t\log\mu_t\), and the budget update becomes the paper’s update for that buyer. So the weighted type model is an exact re-encoding of a market with \(\tau\) buyers, not a new population-dependent algorithmic problem.
That matters because Theorem 1 is a convergence theorem, not a complexity classification. Its continuous-population version appears to follow by substituting weighted buyers into the same dynamics and potential argument. Asking for an \(\epsilon\)-round bound with explicit dependence on input bit length could be useful, but the paper’s \(O(T^{-1})\) objective guarantee already points directly to that analysis; it does not expose new combinatorial structure that population continuity could simplify. The items and allocations are already divisible, so the interesting continuity in this model is largely on the outcome side.
This is a case against spending ChoCo effort on this particular mirror, not a sound argument that no worthwhile mirror exists. The proposed advertising cohort is plausible, and the population model is well-defined. I cannot honestly defeat the anchor on the stronger universal standard: the remaining question about bit-sensitive computation is legitimate, even if its likely contribution is an explicit weighted restatement of the existing result.
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.