Digital programmatic advertising operates through complex, multi-hop supply chains. The opacity of these intermediary networks leads to significant efficiency losses, often referred to as the ``ad-tech tax.'' While current industry practices utilize heuristic Supply Path Optimization (SPO) to trim inefficient routes, they fail to optimize the equilibrium of the entire network. This paper extends previous work on Directed Acyclic Graph (DAG) intermediation models by applying them to traceable programmatic supply chains mapped via the OpenRTB SupplyChain object. We introduce multi-attribute utility functions and Mixed-Integer Linear Programming (MILP) to account for substitutable routing (OR nodes) and percentage-based fee structures. Furthermore, we outline a computational methodology and experimental framework using public schain and sellers.json data to benchmark optimal Nash social welfare against current uncoordinated market outcomes.
Figures & tables
Figure 1: A multi-tier OpenRTB supply chain mapped as a DAG. Arrows indicate the flow of the ad impression from the seller ( s ) through intermediaries ( I ) to the buyers ( b ).
Metric
F3000
F3500
F3800
Structural Properties
Total Nodes ( ∣VF∣ )
552
689
820
Total Directed Arcs ( ∣AF∣ )
754
1,513
2,854
Publisher Nodes (Sources)
361
376
385
Buyer Nodes (Sinks)
58
58
58
Intermediary Nodes
133
255
377
Table 1: Topological and Combinatorial Characteristics of the Evaluation Graphs at k=4
Figure 2: MILP Execution Time vs. SOS2 Grid Density ( K ) across different latency bounds ( Tmax ).
Figure 3: Nash Social Welfare (NSW) optimization comparison.
Figure 4: Supply Path Efficiency (SPE) comparison between MILP and baseline heuristics.
Figure 5: Total Tech Tax extracted by intermediaries across routing algorithms.
Figure 6: Path Depth (Hops) selected by MILP and baselines.
Figure 7: End-to-End Latency measured across the generated supply paths.
Metric
Tmax=3000 ms
Tmax=3500 ms
Tmax=3800 ms
MILP NSW
1.23
1.23
1.23
DEC NSW
1.23
-0.67
Undefined (No Path)
POA Ratio
1.00
Undefined
Undefined
Table 2: Price of Anarchy (POA) Degradation Across Latency Thresholds
Exclusion Threshold ( γ )
Frequency (Pairs)
Proportion
20.0%
45
90.0%
40.0%
1
2.0%
Never Excluded (Monopoly)
4
8.0%
Average Threshold (excluding ’Never’)
20.4%
Table 3: Distribution of Hub Exclusion Thresholds ( γ ) across 50 Optimal Routing Pairs.
Online advertising studies how digital ads are targeted, ranked, priced, measured, and delivered while balancing budgets, business goals, and user interests.
Real-time bidding (RTB) ad exchanges typically forward nearly all incoming requests to demand-side platforms (DSPs), even though only a small fraction receive bids. This over-distribution weakens auction outcomes: DSPs throttle participation under compute and budget constraints, reducing the effective use of limited bidding capacity. We present a competition-aware request dispatch framework that uses distributional bid prediction and probabilistic forwarding to decide whether each request should be sent to each DSP. The system adapts per-DSP thresholds over time through lightweight policy optimization to track non-stationary market conditions. We evaluate the framework through four sequential online experiments on a production platform serving over 20 billion daily requests. A full multi-DSP deployment reduces DSP request volume under the policy by 34.2% while increasing net revenue by 4.6% (p<0.001) in a recent 14-day window after an initial DSP adaptation period. Further analysis highlights strong heterogeneity across traffic segments and reveals that aggregate metrics can be misleading. Segment-level and per-DSP analyses suggest that the policy surfaces comparative advantages among DSPs, improving monetized outcomes without increasing overall request volume.
Jonaid Shianifar, Blaz Mramor, Fangda Zou +5
Huawei Ireland Research Center, Dublin, Ireland · Huawei, Nanjing, China
Generative AI assistants are becoming an advertising medium, embedding sponsored content in their answers. This setting departs from classical position auctions in two ways: an ad's click-through rate depends on the passage that hosts it, and because users stop at their first click, earlier ads take clicks from later ones. This competition for clicks makes truthfulness delicate: a higher bid can reshape the allocation and put a competitor ahead of the bidder, reducing the bidder's clicks. Existing mechanisms either attain a constant fraction of the optimal welfare (advertisers' total click value) but are not known to be truthful, or are truthful but their welfare guarantee degrades as the number of passages grows. We achieve both even when the answer and its editorial order are fixed before bidding. Assuming each ad's click-through rate when reached is known and unaffected by omitting other ads, we give a computationally efficient mechanism that is truthful in expectation and attains at least half the optimal welfare under free reordering. Our key idea, click thinning, omits ads at random, showing earlier ads less often so that each ad's overall click probability no longer depends on the order of the ads. Welfare maximization then reduces to a tractable matching problem, and solving it exactly with VCG-style payments makes truthful bidding optimal in expectation. Characterizing the click probabilities that omission can achieve sharpens the approximation factor from 2 to 2−(1−δ)K−1 when at most K ads are shown and each click-through rate is at most δ. This factor is the best possible for any order-preserving rule, even one that ignores incentives and computation, so truthfulness and computational efficiency incur no additional worst-case loss.
Junhua Liu, Zhicheng Liang, Zejun Zhang +2
University of Southern California, Los Angeles, USA · The Chinese University of Hong Kong, Shenzhen, Shenzhen, China · University of Illinois Chicago, Chicago, USA
The rise of automated bidding strategies in online advertising presents new challenges in designing and analyzing efficient auction mechanisms. In this paper, we focus on proportional mechanisms within the context of auto-bidding and study the efficiency of pure Nash equilibria, specifically the price of anarchy (PoA), under the liquid welfare objective. We first establish a tight PoA bound of 2 for the standard proportional mechanism. Next, we introduce a modified version with an alternative payment scheme that achieves a PoA bound of 1+n−1O(1) where n≥2 denotes the number of bidding agents. This improvement surpasses the existing PoA barrier of 2 and approaches full efficiency as the number of agents increases. Our methodology leverages duality and the Karush-Kuhn-Tucker (KKT) conditions from linear and convex programming. Due to its conceptual simplicity, our approach may offer broader applications for establishing PoA bounds.
Nguyen Kim Thang
LIG, Grenoble INP, University Grenoble-Alpes, France