d4-conf-aaai-2023-1763

My lead is a population mirror of Theorem 1, the paper’s result for linear Fisher markets. It is proved in this paper; the appendix gives its proof using earlier convergence machinery. In the paper’s notation, for an initial iterate \(x^0\), random item-block updates from Algorithm 1, and stepsizes \(\eta_j^0=1/L_j\), where \(L_j=\max_i B_i v_{ij}^2/u_i^2\) and \(L_{\max}=\max_j L_j\), the theorem states
\[ \mathbb{E}[F(x^{k+1})]-F^* \le (1-\rho)^k(F(x^0)-F^*), \qquad \rho=\min\!\left\{\frac{\mu}{mL_{\max}\theta^2(A,C)},\frac1m\right\}. \]
Here \(F\) is the EG objective with its feasibility constraints, \(\mu\) is the paper’s strong-convexity parameter, and \(\theta(A,C)\) is the Hoffman constant in the theorem. This is a linear convergence guarantee for computing equilibria—not a named P result or a hardness result.

A credible regime is a large platform market with many advertising campaigns, each buying from a fixed catalogue of ad-slot categories. Suppose campaigns use a few hundred or thousand standardized valuation templates and budget tiers, while there are hundreds of thousands or millions of campaigns. A type is the complete pair \((v_t,B_t)\): the exact value vector over the catalogue and the budget. Campaign names do not matter to the market problem once those agree. This is a deliberately standardized regime; it is not a claim that every consumer or advertiser market has few types.

Here is the question I would hand to a prover: Type-Mass Linear Fisher Equilibrium (TM-LFE). An instance has \(m\) items, \(\tau\) types, rational masses \(\mu_t>0\) summing to \(1\), rational per-capita budgets \(B_t>0\), rational linear valuations \(v_t\in\mathbb{Q}_{\ge0}^m\), rational per-capita supplies \(q_j>0\), and a rational accuracy \(\epsilon\in(0,1)\). For example, \(q_j=1\) means one unit of item \(j\) per unit of population. The task is to output prices \(p\ge0\) and a per-capita bundle \(x_t\ge0\) for each type. Count the output as an \(\epsilon\)-equilibrium when each type’s bundle is budget-feasible, \(p^\top x_t\le B_t\), and nearly utility-maximizing at those prices:
\[ v_t^\top x_t\ge(1-\epsilon) \max\{v_t^\top z:z\ge0,\ p^\top z\le B_t\}. \]
It must also satisfy aggregate supply feasibility and approximate complementary slackness:
\[ \sum_t\mu_t x_{tj}\le q_j, \qquad p_j\!\left(q_j-\sum_t\mu_t x_{tj}\right)\le\epsilon \quad\text{for each }j. \]
The mass \(\mu_t\) is the fraction of buyers of type \(t\); \(\mu_t x_t\) is that type’s aggregate consumption. The decision variables remain the allocation and prices of the underlying Fisher market.

This is recognizably the authors’ problem. Its EG objective is the mass-weighted version
\[ \max_x\sum_t\mu_t B_t\log(v_t^\top x_t) \quad\text{subject to}\quad \sum_t\mu_t x_{tj}\le q_j,\;x_t\ge0. \]
With \(z_{tj}=\mu_t x_{tj}\), it becomes an ordinary finite EG program with \(\tau\) rows, budgets \(\mu_tB_t\), valuations \(v_t/\mu_t\), and supplies \(q_j\). So identical buyers are aggregated exactly, while the population itself is represented by masses. Divisible items are already part of the paper’s model; the mirror’s continuous object is the buyer population. Scaling supplies per capita is the natural co-modification as the population grows.

I expect this approximation question to be Class A. The item-block method acts on \(\tau\)-dimensional allocation blocks, and each update reduces to a simplex projection. Theorem 1’s geometric rate suggests \(O(\rho^{-1}\log(\Delta/\epsilon))\) updates for an objective gap \(\epsilon\), with \(\Delta\) the starting gap; a direct projection implementation costs \(O(\tau\log\tau)\) per update. That is a route to an efficient approximation algorithm in \(m,\tau\), and the input bit lengths, with conditioning made explicit. It does not give a uniform polynomial bound in those parameters as printed: \(\rho\) depends on the conditioning constants, which can deteriorate for small masses or other ill-conditioned inputs. Nor does this paper supply a hardness anchor whose behavior in the continuum could be tested.

The soft spot is the regime. The paper’s examples do not demonstrate \(N\gg\tau\): a dataset of individual movie ratings, for instance, may have nearly as many distinct valuation vectors as buyers. If the intended market has mostly unique profiles, this mirror offers little aggregation. Its case is strongest for markets with genuinely repeated valuation-and-budget templates, where grouping preserves exactly the distinctions the Fisher problem uses.