How Much Does Lying Pay When the Liar Cannot See the Market?

Many matching and allocation rules used in practice are not strategyproof. A rule is strategyproof when telling the truth about your preferences is always your best move. Theory measures how much lying can pay with the incentive ratio: the best utility a participant can get by misreporting, divided by the utility from reporting truthfully. Two examples are well established. The Probabilistic Serial rule, a fair lottery-based way to assign items, has a worst-case incentive ratio of 1.5. Round-Robin drafting of goods has a worst-case ratio of 2. Both bounds assume a manipulator who knows every other participant's exact report. Real participants never have that knowledge.

This note proposes measuring the degree of strategyproofness as a function of what the manipulator knows. The measurement is run on real human preference data from the Sushi dataset and PrefLib. It replaces a single worst-case number with a curve: how much a misreport is expected to gain, and how often it backfires, as the manipulator's knowledge of others shrinks from complete to population-level. The central question is whether the theoretical vulnerability of Probabilistic Serial and Round-Robin survives once the manipulator must pick a lie before seeing the market. If it does not, these rules are safer in deployment than either the worst-case theory or the existing complete-information simulations suggest.

Core Claim

Existing empirical work measures manipulability under the same complete-information assumption as the theory. Bounded Incentives in Manipulating the Probabilistic Serial Rule proves the 1.5 bound. It then brute-forces optimal manipulations on 10,000 synthetic uniform instances with 8 to 20 agents, reporting average incentive ratios of "approximately 1.02 to 1.06". The manipulator in those simulations still sees every competitor.

We claim that the quantity a designer needs is the gain of a misreport chosen under realistic uncertainty, evaluated on realistic preferences. Here "realistic uncertainty" means a posterior over others' reports learned from population data. We expect this quantity to differ from the complete-information average in a measurable way: smaller, and with a non-trivial probability of loss. We also expect the gap to depend on how correlated real preferences are, which uniform synthetic profiles cannot reveal.

Formally, let $\sigma_i$ be agent $i$'s true ranking and $u_i$ its cardinal utility. Let $M$ be the mechanism, $R_{-i}$ the others' reports, and $I_k$ what the manipulator knows: it observes $k$ of the other reports exactly and has a population model for the rest. We define the information-limited gain as

$$G(k) = \max_{\sigma'} \frac{\mathbb{E}[u_i(M(\sigma', R_{-i})) \mid I_k]}{\mathbb{E}[u_i(M(\sigma_i, R_{-i})) \mid I_k]}.$$

The best ex-ante lie $\sigma'$ is then scored ex post on the true $R_{-i}$. That gives two numbers: the realized ratio, and the backfire rate, defined as the fraction of instances where the realized ratio falls below 1. When $k$ covers all other agents, $G(k)$ reduces to the incentive ratio studied in theory. At $k=0$ the manipulator holds only population-level knowledge.

Research Program

Instances from real data. Instances come from two sources. The first is the Sushi data used in Gaussian Process Preference Elicitation: 5,000 users, 10 sushi types, item and user features. That paper fits population-structured utility models, which we reuse to give each agent cardinal utilities rather than inventing them. The second source is complete-ranking collections from PREFLIB, curated as described in Closing the Loop. That paper argues that worst-case social-choice phenomena rarely appear on such data but does not measure incentive ratios.

For each instance we draw small markets of $n$ agents and $m$ items. Real rankings carry no intensities, so on PrefLib we attach cardinal utilities through a small sensitivity family: linear, exponentially decaying, and top-heavy dichotomous. The dichotomous member matters because the Zero-One Principle of Wang et al. says worst-case manipulation of Probabilistic Serial occurs at 0/1 values. Synthetic baselines use impartial culture and the Polya-Eggenberger urn model as in An Empirical Study of Borda Manipulation. This keeps continuity with prior numbers and isolates the effect of real correlation.

Mechanisms. We study Probabilistic Serial and Round-Robin. Round-Robin's worst-case ratio is 2, from Fair and Almost Truthful Mechanisms for Additive Valuations and Beyond. That bound matches the factor-of-2 honesty gap for sequential drafts in Parameterized Complexity of Manipulating Sequential Allocation. Both papers are purely theoretical, so their bounds frame our measurements rather than supply methods.

Knowledge model and search. The manipulator's posterior over unseen reports is the fitted population model. On Sushi this is conditioned on the demographic features of the other agents. On PrefLib it is a Mallows/urn model fitted on held-out voters. Expectations are estimated by Monte Carlo with confidence intervals.

The best lie is found exactly by enumerating all rankings when $m \le 7$, which is 5,040 candidates. For larger $m$, we use local search seeded from adjacent-swap moves and report the remaining gap against exact search on overlapping sizes. Flammini and Gilbert's fixed-parameter results for correlated preferences suggest exact optimization is easier on real data, and we check this directly by timing it.

Outputs. The program produces three things. The first is curves of realized ratio and backfire rate against $k$, per mechanism and dataset. The second is a comparison of real-data and synthetic complete-information ratios. The third is a released audit tool with fixed instance splits, so later bounds work has a common empirical reference. That reference is the missing testbed named in the evaluation-gap direction.

Baselines

Naive reference: worst-case theory. The do-nothing reference is to report the worst-case bounds, 1.5 for Probabilistic Serial and 2 for Round-Robin, as the vulnerability estimate. Beating it is easy. The point is to quantify how far realistic gains sit below it.

Strongest existing method: complete-information brute force. The strongest competitor is the complete-information brute-force evaluation of Wang et al., which reported average ratios of about 1.02 to 1.06 on synthetic uniform profiles. It is the only prior empirical measurement of incentive ratios for these rules. We rerun it on the same real-data instances, with the same utility completions and the same exact or local search, as the $k = n-1$ end of our curve. Compute is identical by construction. Matching their reported synthetic range on uniform profiles validates our implementation.

Our approach beats this baseline if either of two things holds. One is that the information-limited realized ratio is significantly lower than the complete-information ratio, with confidence intervals excluding overlap. The other is that the real-data complete-information ratio differs from the synthetic ratio enough to change a designer's conclusion.

Black-box estimator. The second competitor is Regret-UCB from Online Learning for Measuring Incentive Compatibility in Ad Auctions?. It estimates incentive-compatibility regret against a stationary distribution of opponents by allocating queries across candidate misreports, with error shrinking as $O(1/\sqrt{nT})$. That paper reports only this rate and qualitative wins over Random-Bids and ε-greedy, with no absolute error figure. We adapt it to ordinal reports by treating candidate rankings as arms and sampled markets as auctions. We then compare its query budget against plain Monte Carlo at equal sample counts, using estimation error of $G(k)$ against exact enumeration on small $m$ as the metric.

Ablation of the key ingredient. The ablation replaces the learned population model with an uninformed one. At $k=0$ the manipulator assumes impartial culture for unseen agents. If realized gains and backfire rates do not change, the population model is not doing the work and the claim narrows accordingly. A second ablation restricts the manipulator to adjacent swaps. This asks empirically whether the quadratic local-to-global loss proven tight in Local Sufficiency for Partial Strategyproofness ever bites on real profiles.

Why not just…?

Why not just rerun Wang et al.'s brute force on PrefLib and Sushi? This is the obvious study and a real threat. If complete-information gains on real data are already around 1%, the information axis adds little. We include it as one arm, so the study cannot do worse than this alternative. The added value depends on the gap between the $k=n-1$ and $k=0$ ends being large, which the decisive check below measures. If the gap is small, we report the real-data table as the main finding and drop the information-curve claim.

Why not just trust the worst-case bounds, or rely on manipulation being NP-hard? Wang et al.'s own simulations already show averages far below 1.5. Davies et al. showed hardness is no shield in practice, with a greedy heuristic finding optimal Borda manipulations in 99% of uniform and 99.7% of urn elections. Our timing of exact search on correlated real profiles tests the analogous claim for Round-Robin drafts.

Why not just use Regret-UCB as is? It measures gain under a known stationary opponent distribution, which is close to our $k=0$ quantity. We use it as an estimator baseline. However, it does not ask how gains scale with the manipulator's knowledge, and it has only been run on synthetic auctions. If it matches Monte Carlo at a fraction of the samples, we adopt it as our estimator rather than competing with it.

Proposed Experiments

Calibration. The first experiment reproduces Wang et al.'s synthetic setting (uniform profiles, $n$ from 8 to 20, complete information) and must land inside their 1.02 to 1.06 range before anything else is trusted.

Main measurement. The main experiment sweeps $k$ from $n-1$ down to 0 on Sushi and PrefLib markets for both mechanisms and all utility completions. For each setting it reports mean realized ratio, its 95th percentile, and backfire rate. We expect the realized ratio to fall toward 1 as $k$ shrinks and the backfire rate to rise. We further expect this decline to be steeper on correlated real data than under impartial culture, because correlation makes others' reports predictable, which could even keep gains high. Both directions are informative.

Decisive check. The decisive check is the gap between $k=n-1$ and $k=0$ on real data, under the dichotomous completion, where theory says gains are largest. If the 95th-percentile realized ratio at $k=0$ stays above 1.1, a designer should take Probabilistic Serial's manipulability seriously even without well-informed manipulators. If it falls within the confidence interval of 1, the 1.5 bound is practically irrelevant for these populations.

Secondary checks. The adjacent-swap ablation reports what fraction of the optimal gain local lies capture. The comparison across utility completions shows how much the conclusions depend on unobserved preference intensities, the quantity Mennle and Seuken's partial strategyproofness parameter is built on but which no prior work has measured empirically.