Can network optimization improve the routes taken by online ads?

The problem: choosing a route through middlemen

Programmatic advertising automatically trades opportunities to display ads. Publishers supply the space, advertisers buy access, and intermediaries connect them. Each intermediary can retain a percentage of the payment, so successive fees reduce the amount reaching the publisher.

Supply Path Optimization means choosing among these trading routes. A short route might reduce fees or delays, but the authors ask a broader question: can a centralized calculation select routes and transaction prices that benefit the publisher, buyer and participating intermediaries while meeting a deadline?

The supplied paper is an arXiv preprint. Its findings and mathematical claims should be treated as provisional.

How the model works

The researchers represent the supply chain as a directed acyclic graph: a network of one-way connections without loops. Publishers, intermediaries and buyers are its nodes. For an individual transaction, the model selects a continuous route rather than splitting one advertising opportunity across competing buyers.

It combines yes-or-no routing choices with adjustable transaction prices. Intermediary percentage fees are supplied as inputs, and payments must cover those fees while leaving the publisher and buyer with positive benefits. The selected route must also stay within a total delay limit.

The objective is Nash social welfare, implemented as a sum of logarithms of participant utilities. Here, utility means a modeled financial benefit: publisher revenue above its reserve, buyer valuation minus payment, or intermediary fee income. Logarithms strongly penalize very small positive benefits. This is a particular allocation objective, not a direct measure of advertising effectiveness or proof of fairness.

To make the problem computationally manageable, the authors transform routing–price products into linear constraints and approximate logarithms with connected straight-line segments. The resulting mixed-integer linear program combines discrete choices and continuous quantities. They implement it using Pyomo and the CBC solver.

Real observations, reconstructed connections

The benchmark blends observations with substantial reconstruction. Browser automation collected auction responses from publishers using header-bidding software, which solicits competing bids in parallel. The observed network contained 506 nodes and 594 directed connections, with a maximum observed depth of two hops.

Public ads.txt and sellers.json registries supplied additional declared business relationships. These describe potential relationships, not necessarily executed transactions. The researchers joined the datasets, removed loops and pruned the network.

Some connections to buyers were algorithmically assigned, including fallback assignments when no identifying match existed. Publisher reserve prices were synthesized, intermediary fees were assumed and varied, and missing numerical values were replaced with network averages. Browser response times supplied latency information, but do not establish separately measured delays for every reconstructed server-side hop.

The resulting evaluation graphs contained 552–820 nodes. They are semi-synthetic test environments, not complete recordings of real advertising transactions.

What the comparisons showed

The main routing comparison used one highly connected publisher–buyer pair. Under uniform baseline fees, the optimizer and a fewest-hops rule selected four-hop routes with identical reported financial performance: about 65% of buyer expenditure reached the publisher, while intermediaries retained about 35%.

A greedy decentralized baseline performed worse as the available network expanded. It exceeded one tested delay limit and found no route in the most expanded scenario. That demonstrates a weakness of this simulated rule, not that decentralized advertising markets generally collapse.

Reported solver times stayed below ten seconds in the two more constrained scenarios and exceeded 70 seconds in one expanded-network configuration. These times support offline analysis, not per-impression execution. The authors propose periodically generating routing allow-lists, then using a faster path-search heuristic online.

A separate fee experiment examined 50 publisher–buyer pairs. Raising a selected hub’s fee from 10% to 20% caused bypassing in 45 cases; one hub was bypassed at 40%, while four remained selected through the tested maximum of 60%. Because fees increased in ten-percentage-point steps, these are coarse switching thresholds, not precise universal fee caps.

Why the conclusions need restraint

The experimental delay limits were 3,000–3,800 milliseconds, much looser than the roughly 150–300-millisecond auction windows discussed elsewhere in the paper. The model also evaluates sequential route delay, not the completion time of parallel auctions.

The claimed four-hop guidance is not a proven network-wide limit: despite a preprocessing parameter of four, the reported graphs contained paths as long as 74 hops. Likewise, the assertion that shortest-path routing starves intermediaries is not demonstrated by the uniform-fee comparison, where both methods matched.

Finally, negative sums of logarithms do not mean participants suffered financial losses. The paper’s welfare ratio becomes problematic when its denominator is negative or undefined; the greedy baseline is not a demonstrated strategic equilibrium.

The defensible takeaway is narrower: centralized optimization can explore fee–routing trade-offs in this constructed benchmark. Establishing benefits in operating advertising markets requires stronger transaction-level evidence and broader, realistic comparisons.