CS Paper Radar

Optimizing Multi-Tier Intermediation in Programmatic Advertising: A DAG-Based Mechanism for Supply Path Optimization

Amelia Bădică, Costin Bădică

cs.AI ·submitted 2026-11-08 22:16 UTC · v1
benchmark

Abstract

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 \texttt{schain} and \texttt{sellers.json} data to benchmark optimal Nash social welfare against current uncoordinated market outcomes.

Closest papers

Nearest neighbours by meaning across the whole index.

Nonuniform Buy-at-Bulk Network Design: Improved Approximation and LP Integrality Gap

cs.DS ·2026-11-04 ·Iman Gholami, MohammadTaghi Hajiaghayi
theory similarity 0.59
Abstract

In nonuniform buy-at-bulk network design, we are given an undirected graph and $h$ terminal pairs with positive demands, and we must route every demand at minimum total cost when each network resource has two independent parameters: a fixed buying price paid once if the resource is used, and a per-unit rental cost (or physical length) paid proportionally to the traffic it carries. Unlike the uniform-cost or single-sink variants, the general multicommodity problem allows unrelated buying and rental metrics across arbitrary source--sink pairs, arbitrary demands, and both edge and node resources. We give a deterministic polynomial-time $O(\log^2 h / (\log\log h)^2)$-approximation algorithm for undirected nonuniform buy-at-bulk network design. The guarantee holds for edge costs, node costs, and their combination, and applies to arbitrary positive rational demands with no dependence on the number of vertices or the numerical demand ratio. This improves upon the $O(\log^4 h)$ bound of Chekuri, Hajiaghayi, Kortsarz, and Salavatipour (2010) for unrestricted instances. Our result also establishes the same $O(\log^2 h / (\log\log h)^2)$ upper bound on the integrality gap of the natural affine multicommodity flow LP, bounding integral buying and rental costs separately against their fractional counterparts and preserving zero rental budgets exactly.

0.25

On inverse aggregate network assignment games

cs.GT econ.TH ·2026-11-02 ·Joseph Y. J. Chow
similarity 0.58
Abstract

To design platforms for multi-operator mobility markets coordinating their operations or infrastructure to support them, models are needed to understand the behavior of these operators and travelers in a shared network. Assignment games can prove useful, but operationalizing them requires adopting a more generalized aggregate assignment game framework that allows for identification and estimation. We extend such a framework to aggregate network assignment games, proposing a path-based formulation and a PURC-based formulation along with solution algorithms. An inverse optimization model is proposed for the link-based formulation. It is solved by a quadratic program that separates into a buyer block, which retains the node potentials and imposes every observed zero-flow cell, and a seller block. This estimator, introduced in the literature for uncapacitated route choice, is extended here to a capacitated two-sided market, with rationing prices supported on observed binding links and operator supply scales estimated by group. Computational tests with a toy network demonstrate the economic value of these models. A large-scale Long Island Rail Road network example (897 nodes, 671 census tracts, 123 LIRR stations, 8,320 directed links) is calibrated to 2026 fares, timetabled seat supply and National Transit Database operating costs. With 10-50% of links sampled, the misspecified inverse model fits oracle link flows with R^2>=96%. Held-out link error falls from 29% to 19%, correlations with the true rationing prices rise from 49% to 75%, and social optimal gross surplus is recovered within 6%. Deadweight loss is overestimated by 10-17%. Ablation tests show that ignoring the inactive cells more than doubles the held-out error and, at 30-50% sampling, roughly halves the correlation of the pricing wedge, while ignoring the rationing prices degrades every metric.

0.33

Single-level reformulations for network pricing under Wardrop equilibrium with separable affine costs

cs.GT math.OC ·2026-10-19 ·Miguel F. Anjos, José Neto
benchmarktheory similarity 0.56
Abstract

We consider the problem of setting tolls on a subset of the arcs of a congested network so as to maximize the revenue of a network authority, anticipating that users route according to a Wardrop equilibrium. This problem is naturally cast as a bilevel program in which the leader sets tolls while the followers respond by choosing an equilibrium routing. We focus on the important special case of separable affine arc cost functions. Under this assumption, Wardrop equilibria admit Beckmann's convex characterization, from which we derive three new single-level reformulations of the bilevel problem, exploiting both Beckmann's formulation and its dual: an arc-based formulation, which we solve exactly, and two path-based formulations, solved by column-and-constraint generation. Beyond the reformulations, we further derive from Beckmann's potential an upper bound on the optimal revenue that can be used to certify optimality gaps across all formulations. An extensive computational study on instances derived from the Sioux Falls and Eastern Massachusetts networks compares our formulations with the recent mixed-integer nonlinear formulation of Beck, Labbé and Schmidt. The arc-based formulation solves substantially more instances to proven optimality (within a time limit of 1800 s) than this formulation and, unlike it, returns a feasible solution on every instance. It remains effective on the largest, 74-node network, on which the formulation of Beck et al. solves none. The magnitude of the upper bounds on the tolls proves to be a major driver of tractability: the genuinely hard core of the benchmark emerges once the regulatory cap on tolls is removed. The two path-based formulations, used as heuristics, return a solution within one percent of the optimum on every instance whose optimal value is known, often in seconds where exact formulations reach the time limit.

0.24

Auction-based allocation of routes in capacity-constrained networks

cs.GT econ.THecon.GN ·2026-10-14 ·Gergely Csáji, Dávid Csercsik
similarity 0.56
Abstract

We study the route-set allocation problem between end nodes in capacity-constrained flow networks with transfer costs. We introduce an origin--destination (OD) bidding language, in which a participant bids for bounded conic combinations of inlet--outlet--quantity licences and the mechanism performs the routing through a network-flow optimising winner-determination problem. We then study payment rules for the OD mechanism. Under a restricted model with openly and uniformly priced sources and bidders who are indifferent to the source of the gas, the Vickrey--Clarke--Groves (VCG) payment is core-stable; the key structural fact is that in this regime some optimal aggregate flows never use a physical pipe in both directions, so the winner-determination problem reduces to a single-commodity network flow whose value is submodular in the set of active bidders. If source access is allowed to depend on the individual consumer -- a realistic feature, e.g. when gas deals are embedded in bilateral political bargaining -- the reduction fails and VCG payments may lie strictly outside the core. For this general model we propose a dual (nodal) pricing rule derived from the shadow prices of the flow-conservation constraints, and prove it is always core-stable, at the cost of dominant-strategy incentive compatibility. Illustrative examples accompany each result.

0.26

Finding Competitive Equilibria in Online Marketplaces with Platform Fees, Taxes, and Subsidies

cs.GT econ.TH ·2026-10-29 ·Taihei Oki, Ryosuke Sato
similarity 0.55
Abstract

We study equilibrium computation in multi-unit trading networks with valuations satisfying generalized full substitutes and agent- and transaction-specific piecewise-linear transfer functions. These transfers model platform fees, taxes, subsidies, and membership discounts in online marketplaces. Our ascending procedure raises prices at different rates and reaches the minimum equilibrium price vector in finitely many iterations, each implementable in strongly polynomial time under our oracle and arithmetic models. An equilibrium allocation can then be recovered efficiently. The method extends primal-dual techniques developed for ascending auctions to handle complementarities between purchases and sales through a submodular flow formulation. In single-seller markets with substitutes and complements, our framework also extends the double-track auctions of Sun and Yang (2009) and Shioura and Yang (2015) to bidder- and good-specific transfers.

0.16

Mixed-integer programming formulations for optimal reconfiguration of supply chains

eess.SY math.OC ·2026-08-18 ·Lavinia M. P. Ghilardi, Olga Walz, Steffen Klosterhalfen, Calvin Tsay
published similarity 0.55
Abstract · Accepted to IFAC World Congress 2026

Supply chains are interconnected networks of processes and operations producing and delivering high-value products. These chains are increasingly subjected to structural changes from the energy transition and other external factors. To address this, this work develops mixed-integer programming formulations to identify optimal reconfigurations that preserve industrial operations and profitability. We propose products and spatial neighborhoods to restrict the feasible search space and enable fast heuristic solutions. Furthermore, this restriction combines structural and product-based information, thus allowing to explore and define multiple reconfiguration scenarios. We demonstrate the approach using an agricultural waste case study, showing its ability to quickly produce good quality solutions.

0.54

Scalable Exact Path Selection via Structure-Aware Search for Virtual Payment Channels

cs.DC ·2026-08-23 ·Jiangnan Luo, Zhebei Shen, Yuan Zhang, Sheng Zhong
published similarity 0.53
Abstract · 10 pages, 9 figures. To appear in the Proceedings of the 55th International Conference on Parallel Processing (ICPP 2026)

Virtual Payment Channels (VPCs) enable efficient off-chain transactions in Payment Channel Networks (PCNs), but their performance depends on selecting high-quality underlying paths. Existing approaches either rely on simplified metrics or incur high computational cost. We study VPC path selection under generalized monotone metrics and propose a structure-aware exact solver based on quadtree search. By exploiting monotonicity and distance plateau properties, our method prunes large regions of the capacity-constrained search space while preserving optimality, significantly reducing the number of shortest-path computations. We further instantiate the framework with a composite metric that integrates economic cost and security risk, enabling flexible trade-offs across application scenarios. Experiments on synthetic graphs and real-world Lightning Network topologies (up to 12,552 nodes) show 2--5 orders of magnitude speedup over prior work, with consistent sub-100ms latency.

0.63

Network Design against the Bullwhip Effect in Complex Supply Chains

eess.SY ·2026-09-23 ·Lauren Bogo, Dominic Liao-McPherson
unusual similarity 0.53
Abstract · 11 pages, 10 figures

This paper studies the bullwhip effect, the amplification of demand fluctuations into larger order fluctuations upstream, in supply chain networks where each firm orders from several suppliers over routes with different lead times. We show that on a directed acyclic network every response from demand to orders is a sum over paths of products of nodal responses, so that the stability and stability margins of the network are determined by those of its individual nodes, and that a node which splits its orders across routes of different lengths gains margin it can spend on a higher gain and a faster response. We then minimize the worst-case amplification of the network by choosing how each firm splits its orders among its suppliers, which route lead times to shorten, and each firm's ordering gain, with gradients from one adjoint pass per demand node and frequency. On a 14-city network the optimized design amplifies 20~dB less than cost-minimal routing and 17~dB less than a design that shortens the longest routes with the same budget, and is better connected than either. Amplification is therefore a property of routing and delay, not only of the ordering policy, and designing against it also makes the network more robust to a lost route.

0.28