When Privacy Moves ML-Mediated Decisions On Device: Information and Incentive Misalignment in Auctions

AI summary

Overview

Research area: Algorithmic game theory and auction design, specifically budget pacing and incentive compatibility in privacy-preserving, on-device ML-mediated advertising auctions.

Technical level: Advanced. The paper combines auction theory (dominant-strategy incentive compatibility, critical payments, Myerson's lemma), stochastic-process bounds, and an executable simulation harness in Rust and TypeScript. Readers without a game-theory or ad-auction background will need to work harder, though the central narrative is a fairly intuitive one about stale shared state.

Scope (one sentence): The paper formalises and empirically measures two distinct economic failures — one about stale shared budget accounting across devices, and one about a payment rule that charges the runner-up's paced score — in an auction-logic-faithful on-device simulation with 36 campaigns and 50 devices, using dimensionless score units and explicitly declining any currency claim.

What This Paper Is About

When privacy-preserving inference moves decision-making onto user devices, the economic decision moves there too. A local relevance model can decide which ad wins, but the shared campaign budget is only known through snapshots broadcast from a central service — so different devices act on mutually inconsistent accounting state. The paper asks what this information-structure failure costs in overspend, and separately asks whether the deployed score-space payment rule gives bidders an incentive to misreport.

Key Contributions

1. A formal model of accounting information misalignment. The paper models budget state replicated across autonomous clients that observe their own debits but not each other's, and derives a finite-window expected excess-debit bound from lag, arrival intensity, crossing campaigns, and conditional payment caps, evaluated with paired confidence intervals.

2. Pressure and enforceability evidence. A new 4 × 7 pressure–lag sweep shows long-lag excess debit persists at two-times as well as 20-times budget pressure, and a visible-balance no-sale guard is shown to eliminate the preventable zero-lag crossing debit but not stale cross-device spending.

3. A separate incentive-misalignment result. The paper characterises a canonical dominant report on rival auctions and gives an executable implementation-level counterexample isolating the runner-up's multiplier in the winner's price. Critical-base-bid payment is DSIC per-auction conditional on current multipliers, but neither proves dynamic truthfulness nor changes paced ranking.

4. An auction-logic-faithful economic audit. Thirty paired paths use frozen budgets, disjoint calibration seeds, deposited replicate rows, and a live TypeScript parity test with a fractional 27.9064-score vector so integer golden files cannot hide drift.

Main Findings

• Overspend rises sharply with sync lag. In the deterministic arm, Even pacing overspend rises from 0.5276% (95% CI half-width ± 0.0347) with shared accounting state to 17.7731% (± 0.8702) at one tick and 1669.3075% (± 3.8743) at 50 ticks. The calibrated-synthetic arm reaches 0.9983% at zero lag, 31.8700% at one tick, and 905.0317% at 50 ticks.

• The effect does not require severe budget pressure. Varying only the divisor used to freeze budgets, mean overspend at Δ = 50 is 106.95% (pressure 2), 367.37% (5), 801.41% (10), and 1669.31% (20).

• Device count and offered load both matter. At Δ = 1 with fixed aggregate load and the same frozen deterministic budget, Even overspend is about 13%, 18%, and 20% for N = 10, 50, and 200. Holding N = 50 and halving or doubling arrival load yields approximately 0%, 18%, and 47%. The paper labels these one-factor sensitivities, not a scale law.

• The lag effect survives bursty, heterogeneous demand. Under a declared two-state Markov burst process with a heterogeneous device mixture, mean overspend at Δ = 0, 1, 2, 5, 10, 25, 50 is 0.4861%, 39.5224%, 118.8324%, 241.8145%, 381.9290%, 1098.1294%, and 1573.1751%. Every paired lag-minus-zero 95% CI is positive, and 24 of 30 individual paths are themselves strictly increasing across all seven cells.

• A visible-balance guard fixes only the local problem. The guarded ablation produces exactly 0 excess debit at zero lag in all 30 replicates, but still overspends 11.8822% (± 1.1969) at one tick because other devices' unsynchronised debits remain invisible. Guard and standard means are equal only at Δ = 5 (both 189.9383%) and Δ = 10 (both 479.2772%).

• The expected bound contains the measured curve. The 12 corpus-derived vertical intensities sum to about 309.7 servable arrivals per tick; charge caps are 101–119 score units. Paired slack is positive in every cell, from 52.7024 [51.3435, 54.0613] at Δ = 1 to 688.5453 [684.7028, 692.3878] at Δ = 50. The paper notes this is consistency of estimated expectations, not a claim the bound holds on each finite replicate, and that the untruncated proxy arm lies outside the theorem's support premise.

• The deployed payment rule is not truthful. At deterministic Δ = 1, 98.23% of rival auctions admit a profitable deviation; including the outcome-invariant one-bidder branch, the rate is 96.97% of all sales. The highest-value admissible bidder differs from the winner in 51.63% of sales; zero-lag deterministic base-value ranking disagreement is 49.26%, which the paper does not label an inefficiency.

• Critical-base-bid payment separates incentives from ranking. With a 100-unit no-sale reserve, the harness finds no profitable per-auction deviation in any of 420 replicate cells, conditional on reali

Authors’ abstract

Moving ML-mediated decision making onto privacy-preserving clients decentralises the economic decision along with the inference. Shared budget constraints then depend on information that cannot be globally current, creating an information-structure failure that conventional pacing is not designed to solve. We study this information misalignment in an auction-logic-faithful on-device simulation with 36 campaigns and 50 devices. Accounting is in dimensionless integer score units; no currency semantics are claimed. Across 30 paired demand paths, proportional Even pacing overspends 17.77% after one tick of staleness and 1,669.31% after 50 ticks under the original 20-times budget pressure. The effect does not depend on that severe a budget: at two-times pressure, 50-tick overspend remains 106.95%. A visible-budget no-sale guard makes zero-lag compliance exact at this score-unit granularity, yet leaves 11.88% overspend at one tick because other devices' debits remain invisible. A declared bursty, heterogeneous-device sweep retains a strictly increasing mean lag curve. We derive a finite-window expected excess-debit bound under conditional charge caps and find positive paired slack in every bounded-value cell. A second, incentive misalignment arises when the ML/pacing score transformation is allowed to change payment units: 98.23% of rival auctions at one tick admit a profitable deviation. An executable implementation-level counterexample isolates the runner-up's multiplier in the winner's price. Critical-base-bid payment is per-auction DSIC conditional on current multipliers, but does not establish dynamic truthfulness and does not repair base-value ranking disagreement.