Refine the Map Where the Budget Binds: Economically Adaptive Spatial Cells for Budgeted Auto-Bidding

Location-targeted advertising buys impressions region by region. An advertiser, or the automated bidder acting for it, sets one bid adjustment per geographic cell and spends against a hard campaign budget. The cell size is usually fixed: a city, a postal code, or a uniform hexagon. That choice is not neutral. If cells are coarse, a single bid has to cover locations that are worth very different amounts. If cells are fine, each one holds too few auctions to estimate what it is worth. This note proposes choosing the map adaptively using a signal from the budget itself. A cell should be split only where the advertiser's buy-or-skip decision is close to the margin set by the budget's shadow price, meaning the price of one more unit of spend. Everywhere else, cells should be merged.

The intuition comes from image segmentation. PointRend starts from a coarse 28×28 prediction grid and refines it only at points whose label probability is near 0.5. That gives sharp boundaries at about 30× less compute than a dense grid. A budget-constrained bidder has an analogous boundary. Locations whose value per unit cost sits well above the shadow price should always be bought. Locations well below it should never be bought. Resolution only matters in the band where value per cost is close to the shadow price. If that band is small, a partition built around it should reach nearly fine-grid efficiency with nearly coarse-grid sample sizes per cell.

Core Claim

Two existing ideas meet here, and to our knowledge nobody has put them together. The spatial-modeling literature already treats discretization as a trade-off between bias and variance. AdaSTEM builds randomized quadtrees whose cells shrink wherever there are many observations, which balances over-smoothing against over-fitting for bird distributions. It adapts to how much data a region has, not to how much the resolution matters for the decision being made. The auction literature already shows why coarseness is costly under budgets. Liaw, Mehta and Zhu prove that in deterministic first-price auctions, budget-constrained bidders hit an all-or-nothing trap: they must bid zero on queries that would exceed their remaining budget. As a result, the Price of Anarchy (the worst-case ratio of optimal welfare to equilibrium welfare) can grow linearly in the number of bidders. They also prove that uniform bid multipliers keep it at $n$. Within one cell, a single bid is exactly a uniform multiplier across heterogeneous locations. So spatial coarsening reproduces the uniform-bidding failure mode. No paper in our file links these two results or studies how cell granularity affects pacing or efficiency. BAT (BAT) treats its region IDs as flat categories.

We formalize the claim for one advertiser with budget $B$ and budget dual $\lambda \ge 0$, the shadow price on spending. When the advertiser can only bid one amount per cell $c$, the Lagrangian value it gives up is approximately

$$ \Delta(c) \approx \mathbb{E}_{x \in c}\big[\,(r(x) - (1+\lambda))^{+}\,\big] \;-\; \big(\bar r_c - (1+\lambda)\big)^{+}, $$

Here $r(x)$ is the value-per-cost ratio of impressions at location $x$, $\bar r_c$ is its cell average, and $(\cdot)^+$ is the positive part. This is a Jensen gap. It vanishes when $r$ lies entirely on one side of $1+\lambda$ within the cell, however much $r$ varies. Splitting cell $c$ is therefore worth it only when the estimated $\Delta(c)$ exceeds the estimation penalty. That penalty scales like $\sigma/\sqrt{n_c}$, because the per-child mean of $r$ is estimated from $n_c$ auctions. This split rule is new. Refinement follows the dual-adjusted decision margin, not data density (as in AdaSTEM) and not raw value heterogeneity. Because $\lambda$ rises as the budget tightens, the right map changes over the course of the campaign. Tight budgets push the margin into high-value zones and call for resolution there. Slack budgets call for resolution in low-value zones.

Research Program

The method has three parts. First, a hierarchical base tessellation: hexagonal cells as in Liu et al.'s ridesharing dispatcher, or quadtrees as in AdaSTEM. The base is fine enough to be over-resolved. Second, a pacing controller that maintains $\lambda$ online. We use a standard dual-gradient controller of the kind benchmarked in BAT. Third, a periodic repartition step. Each epoch, it evaluates the gap-minus-penalty criterion bottom-up and merges or splits nodes. Following AdaSTEM, it averages bids over a small ensemble of randomly shifted partitions to avoid hard cell-edge artifacts.

The theoretical work proves a single-bidder regret bound for the criterion under a smoothness assumption on $r$. This should show that loss scales with the measure of the near-margin band, not the full domain. We then ask how cell resolution enters the Price-of-Anarchy bounds of Liaw et al. Our conjecture is that coarsening hurts deterministic first-price auctions much more than their randomized or quasi-proportional variants, which already smooth the budget cliff.

Baselines

The naive reference point is a single global bid multiplier with dual pacing and no spatial structure at all. The strongest practical competitor is a static uniform hexagonal grid whose resolution is tuned by held-out search. It gets the same total tuning budget, measured in validation simulations, as our method's penalty constant. If one well-chosen static resolution matches us, the adaptivity claim fails. The strongest adaptive competitor is an AdaSTEM-style density quadtree, which splits by impression count. It uses the identical tessellation, pacing controller and ensemble averaging, so it differs from ours only in the split signal. That makes it the key ablation isolating the economic ingredient.

A second ablation splits on value heterogeneity alone, with $\lambda$ fixed at 0. It tests whether budget-awareness, rather than variance-awareness, drives any gains. For pacing references, we run the BAT controllers (Mystique, TA-PID, M-PID) on the coarsest partition. BAT reports that Mystique achieves the lowest pacing error, TA-PID and ALM the most clicks, and M-PID the best cost-per-click compliance, but no numeric values for any of these were found on Lacuna. On iPinYou, the file reports that at 1/32 of budget a linear bidder won 1,594 clicks versus 242 for constant bidding (iPinYou benchmarking). That gives a sanity anchor for the size of budget-constrained gains. Beating the baselines means a statistically significant improvement in clicks or value won at matched budget spend and matched cost-per-click violation rate over the tuned static grid. The improvement should be largest under tight budgets.

Why not just…?

Why not just tune one static hexagon resolution? This is a real threat. If the near-margin band is spread evenly across the city, a single resolution is nearly optimal. Our criterion predicts the opposite whenever value concentrates in a few districts. That is plausible given that Liu et al. found fixed partitions lose profit on 3.5 million Beijing rides and that BAT documents strong regional heterogeneity. The tuned-grid baseline, run separately for each budget level, settles it. If its best resolution does not shift with budget tightness, our dual-driven story is wrong.

Why not just use AdaSTEM's density-driven splitting? Density is a proxy for estimation variance, not for decision relevance. A dense downtown cell where every impression is clearly worth buying gains nothing from splitting. A sparse suburban cell straddling the margin gains a lot. The density-quadtree ablation directly measures how much this matters.

Why not skip discretization and bid per impression from a smooth location model? If the bidding interface accepted per-impression bids from a continuous value model, partitioning would only matter through estimation. In that setting this proposal reduces to deciding where to spend model capacity. We include this "continuous oracle-interface" bidder, which uses kernel smoothing over coordinates. It serves as an upper reference rather than a competitor. Our claim is scoped to region-level bid interfaces, which are what BAT's region identifiers reflect.

Why not just randomize the auction, as Liaw et al. recommend? Randomized first-price auctions soften the all-or-nothing trap and might make coarseness harmless. We treat this as a condition of the experiment rather than a rival. We will run every partition method under deterministic and quasi-proportional first-price rules. The interaction effect, whether adaptive refinement helps less under randomization, is itself a prediction of the theory.

Proposed Experiments

BAT's region IDs are coarse and fixed, so on BAT we can only test the merging direction. We use its 10 million first-price and 1 million VCG auctions, with real budgets and the 30× peak-to-off-peak traffic swing. The hierarchy has BAT's regions as leaves, and we ask whether economically guided merging beats merging by density or by administrative grouping.

Splitting needs fine coordinates. For that we build a semi-synthetic simulator: impression locations are NYC Uber pickups (Liu & Xu), and traffic is reshaped to BAT's hourly profile. Advertisers have planted spatial value fields with controllable margin-band width, and budgets are swept from 1/32 to 1 of uncapped spend. We report value won, budget pacing error, cost-per-click violation, cells used, and empirical efficiency against the offline optimum. The offline optimum is computed by LP on subsamples, since full min-cost-flow solutions are impractical at scale per Liu & Xu.

The decisive checks are three. Adaptive gains should grow as the planted margin band narrows. The learned partition should migrate toward high-value zones as budgets tighten. Gains over the tuned static grid should be larger under deterministic first-price than under quasi-proportional first-price. If none of the three holds, the economic split signal adds nothing beyond density.