d4-conf-wine-2020-0010

The strongest mirror is the positive-bid part of the paper. It has a direct population interpretation: a type is a valuation vector \(b\in\{0,\ldots,M\}^n\) for the \(n\) goods, describing a unit-demand consumer who chooses one good or rejects. The mass \(\mu_b\) is the fraction of consumers of that type, with \(\sum_b\mu_b=1\). At prices \(p\), each type chooses a maximizer of \(b_i-p_i\), including the reject option \(b_0=p_0=0\); the oracle returns the population’s aggregate demand,
\[ x_\mu(p)=\sum_b\mu_b e^{i_b(p)}. \]
Each consumer still receives an integral bundle, while aggregate per-capita demand can be fractional.

A plausible regime is a large buyer consolidating many standardized liquidity needs: perhaps millions of positions, but only a modest number \(\tau\) of repeated valuation schedules arising from contract or eligibility templates. Its pricing system reports total demand at a queried price vector. This is not just a story attached to the paper: the authors explicitly identify a positive bid with a unit-demand consumer and positive bid lists with collections of such consumers. That makes the positive-bid subproblem unusually recognizable as a population problem. [Paper PDF](https://arxiv.org/pdf/2005.01496)

Lead — Continuous Positive-Atom Recovery. The instance is \(n\), a bound \(M\), a support bound \(\tau\), a bit-length bound \(L\), and exact oracle access to a residual population measure \(\mu\) with at most \(\tau\) positive-mass types. The oracle is queried at generic prices, so each type has a unique choice, and returns the exact aggregate bundle. The task is to output one remaining type \(b\) and its exact mass \(\mu_b\); the solution is that type–mass pair.

The anchor is Theorem 4.4, proved in this paper: Algorithm 1 returns the vector and weight of a positive bid using \(O(n\log M)\) demand queries. Applied to the residual measure, the corresponding continuous question should have the same query bound for recovering one atom, with arithmetic cost polynomial in \(L\). The paper’s proof locates the bid coordinates by binary search and obtains its weight from demand changes. In the mass version, those changes return rational mass rather than an integer weight; the same positive-difference logic appears to apply. Repeating atom recovery gives an expected \(O(n\tau\log M)\) query bound for the full support. The rational-mass extension is an inference from the paper’s algorithm, not a theorem it proves.

Continuous Positive-Population Identification asks for that full-support version directly: given the same oracle and promise, return the complete list \(\{(b,\mu_b)\}\), exactly. Its anchor is Theorem 6.1, also proved here: any algorithm for learning bid lists requires \(\Omega(B\log M)\) queries. The theorem’s lower-bound construction uses \(B\) positive bids at distinct positions on one coordinate axis. In the mass mirror, take the corresponding \(\tau=B\) types to have mass \(1/B\). Exact aggregate answers are then the original integer counts scaled by \(1/B\), so the same restricted family remains distinguishable only through demand queries. The lower-bound family can also represent a much larger population by taking many identical copies of each type before normalizing.

For this full-recovery problem, I expect tractability: the adapted upper bound is \(O(n\tau\log M)\), and the Theorem 6.1 family gives an \(\Omega(\tau\log M)\) query lower bound. The lower bound is a polynomial query cost, not an NP-hardness result; it shows the problem cannot generally ignore support size or valuation range. Together the two anchors give a useful algorithm-and-limit picture, though they do not establish a tight bound in \(n\).

This mirror covers the paper’s positive-only learning results, including Theorems 4.4 and 6.1. It does not cover the general positive-and-negative bid case. Negative bid coefficients can cancel demand facets; they are not population masses, so the island-gadget lower bounds cannot honestly be read as population-complexity results without a separate model. The valuation-oracle simulation and the cited validity test are likewise outside this mirror.

Further questions are whether exact recovery with arbitrary rational masses has the stated query bound uniformly in \(L\), whether the \(n\) factor is necessary, and what remains learnable with noisy answers or a small number of negative bids.

The weakest point is the restriction to positive bids and an exact oracle. The paper’s broader strong-substitutes model does not itself become a population distribution just by replacing signed weights with real numbers. Within the positive-bid regime, however, the authors already use the unit-demand population interpretation and aggregate demand queries, so the proposed mirror preserves the problem they study while making population mass continuous.