How Many Prices Does a Correlated Buyer Need? Rank Dependence as the Control Knob for Menu Size

A seller of several goods can in principle offer a huge menu of bundles, prices and lotteries. In practice sellers offer a handful of tiers, and empirical work backs them up: internet carriers keep 90% to 95% of maximum profit with three or four price tiers (Valancius et al.). Theory gives two answers that cannot both describe real markets. When the buyer's values for different goods are independent, a constant number of prices is near-optimal (Cai and Daskalakis). When values may be correlated arbitrarily, every menu of bounded size can lose essentially all of the optimal revenue (Selling Multiple Correlated Goods). Real buyers fall between these extremes, and no existing result says where the boundary lies.

This note proposes measuring correlation with Kendall's tau, a rank correlation: the probability that two random buyers order a pair of goods the same way, minus the probability that they order them oppositely. We then ask how the revenue kept by the best $k$-item menu depends on it. Our hypothesis has two parts. The menu-size collapse comes from the shape of the dependence, not its strength. For buyers whose values come from a transelliptical model (an ordinary elliptical distribution such as a Gaussian or Student-t, with each coordinate passed through an unknown increasing function), small menus keep a constant share of optimal revenue whenever rank dependence is non-negative, and the guarantee degrades only as tau becomes strongly negative. Because tau ignores any increasing rescaling of values, a seller can estimate it from rankings or pairwise comparisons alone, without cardinal willingness-to-pay data. The seller can then decide how many tiers to offer before running any price experiments on the joint structure.

Core Claim

Fix $n$ goods, an additive buyer, and marginal value distributions $F_1,\dots,F_n$ satisfying the monotone hazard rate (MHR) condition. MHR is a light-tail regularity property under which the independent and correlation-robust positive results already hold. Let the joint distribution be transelliptical with latent correlation matrix $\Sigma$. By the invariance result of Transelliptical Graphical Models, $\Sigma$ is pinned down by pairwise Kendall's tau through $\Sigma_{jk}=\sin(\tfrac{\pi}{2}\tau_{jk})$, whatever the marginals and monotone transformations are. Define

$$\mathrm{GF}_k(\tau) = \inf \frac{\mathrm{Rev}_k(F_1,\dots,F_n,\Sigma)}{\mathrm{Rev}_\infty(F_1,\dots,F_n,\Sigma)},$$

where $\mathrm{Rev}_k$ is the best revenue from a menu with at most $k$ entries, $\mathrm{Rev}_\infty$ is the unrestricted optimum, and the infimum runs over MHR marginals and over all $\Sigma$ whose off-diagonal taus lie in a given set. The two endpoints are anchored. At $\tau=0$ the result of Cai and Daskalakis suggests $\mathrm{GF}_k$ is bounded below by a constant. At $\tau=1$, the comonotone case, the buyer is effectively single-dimensional, and a single bundle price is optimal by the one-dimensional theory.

We conjecture that $\mathrm{GF}_k$ stays bounded away from zero, uniformly in $n$, on the whole region $\tau_{jk}\ge 0$. We further conjecture that the zero-guarantee phenomenon of Selling Multiple Correlated Goods can appear inside the transelliptical family only as some $\tau_{jk}\to -1$. If the first conjecture fails, so that positively rank-dependent elliptical buyers can still defeat small menus, that is equally informative. It would mean the empirical success of three-tier pricing needs an explanation beyond dependence structure.

Relation to Prior Work

Three papers motivate the question by defining its two poles. Selling Multiple Correlated Goods introduces menu size as a complexity measure. It shows bounded menus have a zero guaranteed fraction under general correlation and polylogarithmic menu size when values lie in a bounded range $[L,H]$. Its bad instances are constructed for the proof, and it does not ask whether natural dependence families avoid them; we restrict to such a family. Cai and Daskalakis prove constant-price results under independence with MHR marginals, and we extend their regime along a rank-dependence axis. Escaping Cannibalization? treats correlation as an adversary. It shows that a single price equal to the largest item median achieves a 3.443 approximation of worst-case revenue for a unit-demand buyer with MHR marginals, and that approximating the robust optimum within $n^{1/2-\epsilon}$ is NP-hard in general. It deliberately never estimates the dependence. We ask how much revenue that caution gives up when dependence is measurable.

Transelliptical Graphical Models supplies the method. It contributes the sine identity linking tau to latent correlation, its validity across heavy-tailed elliptical cores where Spearman's rho fails, and an estimation rate of $O(\sqrt{\log d/n})$. That paper concerns graph recovery and never touches revenue. The empirical tiering papers (Valancius et al.; Equilibrium Pricing in Data Markets, where sellers "rarely need more than two shards") document the low-cardinality regularity we try to explain. The step-function results of Learning to Price Homogeneous Data and the binary-fee result of Iyer et al. show structural collapse in single-good or single-outcome settings and carry no correlation parameter.

Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing constrains our design choices. It learns correlated demand through singular value decomposition of raw demand and optimizes continuous prices. We instead target discrete menus and a scale-free dependence statistic, and we do not claim to beat it at its own continuous task.

Research Program

The program has three parts. The first is computational mapping. For two and three goods, we discretize values on a fine grid. We solve the linear program for the unrestricted optimal mechanism, which allows lotteries, and a mixed-integer program for the best menu of size $k\in\{1,2,3,4,6\}$. We do this for Gaussian, Student-t and Cauchy copulas over a grid of tau from $-0.95$ to $0.95$, paired with exponential, uniform and truncated-normal marginals, all of which are MHR. This produces empirical curves of $\mathrm{GF}_k(\tau)$. It also searches adversarially, by local optimization over marginals for fixed $\Sigma$, for the worst instance at each tau. The search is aimed at whether near-zero fractions occur at non-negative tau.

The second part is theory, guided by the maps. The planned route to a lower bound at $\tau\ge 0$ is a coupling argument. Under non-negative elliptical dependence, the latent vector decomposes into a common factor plus an independent-like residual. One menu entry serves as the grand bundle, priced against the common factor, and the remaining $k-1$ entries are priced separately against the residuals. The existing independent-case and single-dimensional bounds then combine. For negative tau we will try to embed a curve-supported construction like the one in Selling Multiple Correlated Goods into a limit of transelliptical distributions. We frame both directions as conjectures to settle.

The third part is an estimation pipeline built on the invariance. The seller learns each marginal $F_j$ from single-item posted-price tests, a standard one-dimensional problem. It estimates tau from ordinal data such as rankings or pairwise preferences over goods, then plugs $\hat\Sigma=\sin(\tfrac{\pi}{2}\hat\tau)$ into a Gaussian or t copula to simulate buyers and select a $k$-menu. The same $\hat\tau$ also gives a rule for how many tiers to offer: choose the smallest $k$ whose predicted $\mathrm{GF}_k(\hat\tau)$ exceeds a target such as 0.9. The 0.9 target matches the 90% to 95% regime reported by Valancius et al.. The rankings are assumed to come from the same buyers' latent values, possibly observed with noise. We will measure how sensitive the method is to rank noise. Tied rankings will be handled with the tie-adjusted (tau-b) variant.

Baselines

The naive reference point is a single bundle price, or separate per-item pricing that ignores dependence. Both are what a seller does without modeling. Any proposed menu must beat them, and they cost nothing to compute on identical simulated buyers.

The independence baseline designs the $k$-menu as if values were independent, using the true marginals and an independent copula. This is the Cai and Daskalakis regime. It isolates the revenue gained by knowing tau at all.

The correlation-robust baseline is the single max-median price of Escaping Cannibalization?, together with its additive analogue under worst-case coupling. Its reported result is a proven 3.443 worst-case approximation factor for MHR unit-demand buyers. No reported empirical revenue for it on Lacuna was found. We evaluate it on the same copula instances, with buyers set to unit demand when comparing to it directly. Our tau-calibrated menu beats it if it keeps a materially larger share of optimal revenue at a matched menu size, while losing no more than a few percent on adversarially chosen marginals at the estimated tau.

The strongest competitor is sample average approximation: draw $n$ cardinal value vectors from the true distribution and pick the empirical-revenue-maximizing $k$-menu by mixed-integer search. This seller has strictly more information than ours, namely cardinal joint samples rather than marginals plus rankings. We give both methods the same number of buyers $n$ and the same solver time. We count our method as successful if it matches sample average approximation within a few percent of optimal revenue at small $n$, and beats it under heavy-tailed cores, where empirical revenue from few samples is noisy. No reported number for this baseline was found on Lacuna.

The key ablation replaces the tau-based $\hat\Sigma$ with Pearson correlation computed on cardinal samples, holding everything else fixed. Transelliptical Graphical Models reports Pearson degrading on its Cauchy, t and monotone-transformed schemes while matching tau in the Gaussian case. That paper gives no quantitative figure, so we expect the same pattern here and will measure it in revenue.

Why not just…?

Why not just run sample average approximation on purchase data and skip the rank statistics? When cardinal joint samples are plentiful and light-tailed, this is a real threat, and we expect it to win on revenue. The proposal's claims sit elsewhere. The first is the structural map of $\mathrm{GF}_k(\tau)$, which sample average approximation cannot provide. The second is the regime where a unit-demand or menu-facing buyer reveals only which option they chose, so joint cardinal values are never observed. Rankings and marginal demand curves are, however, often available in that regime. The head-to-head comparison at matched $n$, run with and without heavy tails, settles where the crossover lies.

Why not just use Pearson correlation or a low-rank factorization of demand, as in Low-Rank Bandit Methods? Pearson correlation depends on the marginal scales, so it cannot be computed from ordinal data at all. It is also unstable under heavy tails, which the transelliptical simulations of Liu et al. illustrate. On Gaussian cores we expect no gap, and the Pearson ablation above will show whether any revenue difference survives outside that case.

Why not just use the correlation-robust single price? Its 3.443 factor from Escaping Cannibalization? is a worst-case guarantee and assumes nothing about dependence. If the computational maps show that tau-calibrated menus keep close to the full optimum at non-negative tau, then robust pricing gives up a measurable, quantifiable amount of revenue in exactly the regime real markets seem to occupy. If the maps show that small menus perform no better than the robust price, robust pricing is vindicated and our estimation arm is unnecessary.

Proposed Experiments

The decisive check is the computational map. Across Gaussian, t and Cauchy copulas with MHR marginals, we test whether the worst-case fraction kept by the best two- or three-entry menu stays bounded away from zero for all non-negative tau, and whether it falls sharply only as tau approaches $-1$. We will report adversarial-search minima, not averages. A near-zero fraction found at positive tau falsifies the main conjecture.

The second check is the estimation pipeline on the four simulation schemes of Transelliptical Graphical Models: Gaussian, multivariate Cauchy, multivariate t, and monotone-transformed t. These are reused as buyer-value generators with 5 to 50 goods. We vary the number of ranked responses, add rank noise, and compare revenue against all baselines. We also measure how well the tier-count rule predicts the smallest $k$ that reaches 90% of optimum.

For a realism check on which tau regime markets occupy, we compute pairwise Kendall's tau across product demand series in the public Grupo Bimbo data used by Low-Rank Bandit Methods. That paper reports that three singular vectors capture 99.9% of demand variation, which hints at strong positive co-movement. We will report the share of product pairs with negative tau. Demand co-movement is only a proxy for value dependence, so this check informs the regime, not the revenue claims.

The NetFlow data of Valancius et al. are not available to us. We will instead reproduce their constant-elasticity setting synthetically, adding a tunable copula, to see whether their 90% to 95% at three or four tiers corresponds to the positive-tau region of our map.