d4-conf-aaai-2017-0530

The strongest mirror is welfare maximizing envy-free pricing. Imagine a marketplace with many buyers but relatively few stable valuation profiles: thousands or millions of customers fall into a few hundred segments, and everyone in a segment has the same utility for each good. A type \(t\) is that complete utility vector \(v_t\in\mathbb{Q}_{\ge0}^k\); its mass \(\mu_t\) is the fraction of buyers in the segment, with \(\sum_t\mu_t=1\). If the paper has \(l\) copies of each good for \(n\) buyers, the continuous market has per-capita supply \(q=l/n\). A type’s mass may be divided among goods, while each individual still receives at most one good.

My lead anchor is Theorem 4.2, proved in this paper. It shows that, for every arbitrarily small constant \(\epsilon>0\), no streaming algorithm using \(o(l)\) space can \(\epsilon\)-approximate all the item prices of a social-welfare-maximizing price vector; the lower bound applies even with two item types. The paper summarizes the corresponding exact-price lower bound as Theorem 1.5. This is a space lower bound for the raw stream of buyer–good utilities, not an NP-hardness result.

The continuous problem I would hand to a prover is Continuous Envy-Free Welfare Pricing. Given \(k\) goods, a list of \(\tau\) rational utility vectors \(v_t\), rational masses \(\mu_t\), and per-capita supplies \(q\), find prices \(p_i\ge0\) and allocations \(x_{ti}\ge0\) maximizing
\[ \sum_{t,i} v_{ti}x_{ti}, \]
subject to \(\sum_i x_{ti}\le\mu_t\), \(\sum_t x_{ti}\le q\), and the envy-free condition that any mass assigned good \(i\) gets maximum nonnegative utility at prices \(p\). The output is both the prices and the type-level allocation.

I expect this problem to be tractable in \(\mathrm{poly}(k,\tau,L)\) time. The welfare-maximizing assignment is a capacitated matching LP; its dual supplies supporting item prices, and complementary slackness gives the envy-free allocation. So the continuous version has a direct optimization formulation, with type mass as the input representation. There is also a concrete reason the theorem’s hardness need not survive: its Disjointness construction distinguishes buyers through their edges in the stream. Once those buyers are aggregated into utility-vector types, the mass of the type that values both goods records the intersection directly. In the continuous input, the construction’s relevant information is present in the type distribution rather than hidden across an ordered stream.

A second, separate mirror is Continuous Envy-Free Revenue Pricing, anchored by Theorem 4.3, also proved here. It states that no streaming algorithm using \(o(l)\) memory can find a revenue-maximizing envy-free price vector; the introduction summarizes the result as Theorem 1.6 and notes it holds even for \(k=2\). The continuous problem uses the same type distribution, supplies, prices, and envy-free allocations, but maximizes \(\sum_i p_i\sum_t x_{ti}\). This is a genuine pricing question from the paper, and it is not just the welfare LP with a different objective: choosing prices changes which types demand which goods.

For unrestricted \((k,\tau)\), I would expect the revenue problem to retain hardness on instances where \(\tau\) is as large as the number of buyers. Each discrete buyer can be represented as a type of mass \(1/n\), with supplies scaled by \(1/n\); for any fixed prices, an integral allocation is available at an extreme point of the matching polytope. The paper itself cites hardness for offline revenue pricing, though Theorem 4.3 proves only a streaming-space lower bound. This does not settle the high-multiplicity regime \(\tau\ll n\): whether revenue pricing becomes tractable there, and how complexity depends on \(\tau\), are natural further questions. In particular, the theorem’s \(o(l)\)-space lower bound should not be presented as a continuous-complexity lower bound.

The welfare mirror is my strongest case: it preserves the market’s objective and exposes a tractable type-mass formulation. Revenue is worth asking as a second problem because it remains the same pricing objective, but its expected complexity is less clear in the regime where continuization may help.

The weakest point is also the main boundary: Theorem 4.2 is specifically about processing an arbitrary-order stream of individual utility edges. A pre-aggregated support list removes the arrival-order information and may require work outside the theorem’s streaming model to construct. This mirror therefore covers the paper’s welfare-pricing problem under a continuous-population input model; it does not claim to continue the paper’s stream-space lower bound.