Coding as Part of the Auction: Learning How Much Redundancy to Sell over Lossy Links

A server streaming images, video or sensor data over an unreliable network faces a choice long studied in coding theory. It can split the content into several independently decodable pieces, called "descriptions," so that any one piece gives a rough version and all of them together give a sharp version. This is multiple description coding. How much redundancy to build into those pieces is a tunable knob. More redundancy makes each piece better on its own, but it makes the full set worse for the same bandwidth.

Coding theory sets this knob to minimize expected distortion. When the link capacity is scarce and the pieces are sold to buyers who value quality differently, the same knob also sets what a seller can offer and charge. This note proposes treating the redundancy level as a parameter of the selling mechanism, and learning it from historical bids together with the prices, with no assumption that the bid distribution is known. The claim has two parts. First, the choice of code changes revenue and welfare by a measurable amount. Second, a revenue-maximizing seller will systematically choose less redundancy than a welfare-maximizing planner would. That second part is a concrete, testable "robustness distortion" caused by market power.

Core Claim

We model a server that can send at most $K$ descriptions per round across $n$ buyers. Each description is erased on buyer $i$'s link with a probability $p_i$ that the server observes from acknowledgments. Buyer $i$ has a private per-unit value $v_i$ for quality. The code has a redundancy parameter $\rho$, chosen from the achievable side/central distortion trade-off. Sending $k$ descriptions to buyer $i$ yields an expected quality $g_\rho(k; p_i)$, averaged over which subset of descriptions survives erasure. Buyer utility is $v_i\, g_\rho(k_i; p_i)$ minus payment.

Because $g_\rho$ is concave in $k$ for standard multiple description codes, this is a single-parameter environment. For a fixed $\rho$ and a known value distribution with virtual value $\phi$, Myerson's theory gives the expected revenue as

$$ R(\rho) \;=\; \mathbb{E}_{v}\Big[\max_{k_1+\dots+k_n \le K}\; \sum_{i=1}^n \phi(v_i)\, g_\rho(k_i; p_i)\Big]. $$

This maximum is attained by greedily awarding descriptions to the highest marginal virtual gains $\phi(v_i)[g_\rho(k_i{+}1)-g_\rho(k_i)]$. Replacing $\phi(v_i)$ with $v_i$ gives the welfare objective $W(\rho)$.

The comparative-statics prediction follows from what $\rho$ rewards. The planner serves many buyers, often with one description each, so it values good single-description (side) quality and favors high $\rho$. The seller excludes low-value buyers and concentrates descriptions on fewer buyers, so it values good full-set (central) quality and favors low $\rho$. The research question is whether a seller who knows only past bid samples can learn $(\rho, \text{prices})$ jointly with a sample complexity close to learning prices alone. We also ask whether the resulting gap in chosen $\rho$ is large enough to matter.

Relation to Prior Work

Three coding papers supply the knob and the quality curves.

All three treat the channel as non-strategic and optimize distortion alone. We keep their codes and change the objective.

On the mechanism side, four papers constrain the learning method and one sets the gap.

  • Learning Simple Auctions bounds sample complexity through pseudo-dimension. We need to show that adding a one-dimensional code parameter inflates this bound only mildly.
  • Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments regularizes empirical revenue maximization by rounding values to a grid.
  • Ironing in the Dark shows that overestimating ironing intervals is costly while underestimating them is cheap. It uses a pessimistic lower-confidence revenue curve. These two papers supply our learning method directly, and the asymmetry motivates a pessimistic rule for choosing $\rho$ as well.
  • Selling Data as a Digital Good with Scaling Valuations prices a non-rival scalar data volume under a known prior, delivered losslessly. We differ on each point: our goods are discrete overlapping descriptions, delivery is random, capacity is rival, and the prior is unknown.

Capacity rivalry is essential to the whole proposal, not incidental. With non-rival goods and zero marginal cost, a single-parameter buyer who is linear in quality is best served by one posted price for full quality. The code would then barely matter to revenue. We say this up front because it defines the regime where the claim can hold.

A second tension concerns concavity. A Theory of Data Acquisition and Pricing at Scale shows that non-smooth, approximate valuation rules break monotonicity and therefore truthfulness. In our setting, an empirically measured $g_\rho$ from a learned codec may be non-concave. The greedy allocation would then be non-monotone in bids and not truthful. We handle this by taking the concave hull of $g_\rho$ in the number of descriptions, which is ironing in quantity space rather than value space. We also measure the cost of doing so.

Research Program

The theory has three results.

The first is structural. We characterize the optimal truthful mechanism for fixed $\rho$ under capacity $K$ and heterogeneous public loss rates. We show that concave (or concavified) $g_\rho$ yields a monotone greedy allocation with threshold payments.

The second is statistical. We bound the pseudo-dimension of the joint class of rounded, pessimistically ironed mechanisms over a grid of $G$ redundancy values. The expected result is an additive $O(\log G)$ term over the price-only class. This form comes from a union bound over grid points, since each $\rho$ indexes a fixed class of known complexity. The practical meaning is that learning the code jointly costs almost nothing extra in samples.

The third is a comparative-statics theorem for the Gaussian family. We give conditions on $K/n$, the loss rates, and the value distribution under which $\arg\max R(\rho) < \arg\max W(\rho)$, and we quantify the welfare lost to the seller's choice of $\rho$.

The empirical work builds three families of quality curves. The first comes analytically from the Gaussian multiple description region. The second comes from single-decoder learned codecs in the style of Kurka and Gündüz, trained on CIFAR-10 at five or more redundancy levels, with Kodak PSNR mapped to quality. The third comes from graded quantization at several bit-split ratios, with scene recognition accuracy on the BMW database as a task-level quality measure.

These curves are paired with three kinds of buyer value distributions: truncated Gaussians like those in A Robust Multi-Item Auction Design with Statistical Learning, bimodal irregular mixtures that force ironing, and a heavy-tailed but truncated family. Erasures are generated both independently and in bursts from a two-state Markov process, since bursts are exactly where Yun Ye et al. report that forward error correction fails. Mechanisms are learned from $m$ samples, with $m$ swept from $10^2$ to $10^5$, and evaluated on fresh buyers.

Baselines

The naive reference point is a fixed engineering code with a single posted price. The code's redundancy minimizes expected distortion at the observed loss rates, and every served buyer receives all descriptions at an empirically revenue-maximizing price. It shows what a practitioner gets by ignoring both screening and code choice.

The strongest competitor is separation: a distortion-optimal code followed by the best learned single-parameter auction on top of it. The auction uses Gonczarowski–Nisan value rounding combined with Roughgarden–Schrijvers pessimistic ironing. This is the right competitor because it already contains everything the mechanism literature offers. The only thing it lacks is joint choice of $\rho$. For fairness, both methods see identical sample sets and identical $g_\rho$ curves and receive the same rounding-grid and confidence-level tuning budget. The separation baseline is also given the $\rho$ grid for its distortion optimization.

No reported result was found on Lacuna for revenue of any learned auction selling multiple descriptions. The nearest reported figure is from Han and Dai's truncated Gaussian environment, with regret below 25 against a benchmark revenue of 543. We will reproduce that environment to calibrate our implementation before adding codes. On the coding side, the strongest reported robustness figure is from graded quantization on BMW at 10% packet loss: 61.88% recognition accuracy versus 54.38% for measurement splitting. This anchors the quality curves.

Joint learning counts as beating separation if it achieves at least 3% higher out-of-sample revenue with non-overlapping 95% intervals across 20 seeds in some substantial region of $(K/n, p)$, while staying within a small fraction of the known-prior optimum.

Two ablations isolate the key ingredients. The first uses joint learning without pessimistic ironing, which tests whether the Roughgarden–Schrijvers asymmetry carries over to code selection. The second uses joint learning without concavifying $g_\rho$, which tests whether non-monotone learned quality curves create exploitable misreporting. This second ablation is measured by the best-response utility gain of a simulated deviating bidder.

Why not just…?

Why not just use layered (successive-refinement) coding and sell quality tiers? Layered coding is more rate-efficient for ordered tiers, and at low loss it may well beat multiple description coding. This is a real threat. Under erasure, however, an enhancement layer is worthless when its base layer is lost, so the realized quality of a tier becomes a steep lottery. We will run the full pipeline with a layered Gaussian code alongside the multiple description code and report the loss rate at which the ranking flips. The claim is restricted to the regime where multiple description coding wins.

Why not just fix the code for robustness and learn the auction separately? This is the separation baseline, and it is the alternative most likely to hold. If $R(\rho)$ is flat near the distortion-optimal $\rho$, the idea fails, and our experiments would show exactly that. The comparative-statics theorem predicts where the curve should not be flat: tight capacity and skewed values. A null result there would falsify the proposal, not merely weaken it.

Why not just sell each description as a separate item with item prices? Descriptions are complements with engineered redundancy between them. Pricing them independently ignores the diminishing marginal value of each additional description. Unifying and Optimizing Data Values for Selection via Sequential Decision-Making shows that independent valuation of redundant components suffers a quadratic $(1-c)^2$ penalty, where $c$ measures redundancy, with 8.39% to 23.76% gaps to optimal selection. We will include anonymous item pricing, whose sample complexity is bounded in Morgenstern and Roughgarden, as a baseline and measure its revenue gap directly.

Decisive Checks

The proposal stands or falls on three measurements. First, the fraction of the $(K/n, p, F)$ grid where joint learning beats separation by the stated margin. Second, the measured gap between revenue-optimal and welfare-optimal $\rho$ on the analytic Gaussian curves and on the learned-codec curves; the prediction is that the gap is positive and grows as capacity tightens. Third, the empirical sample-complexity curve, where joint learning should need no more than a small constant factor more samples than price-only learning to reach the same revenue. If the redundancy gap vanishes on learned codecs, or if separation matches joint learning everywhere, we will report that codes and markets can be designed separately. That would itself be a useful negative result for anyone pricing network-delivered content.