Introduction
Billboard providers face a significant financial challenge in balancing advertiser demand with inventory supply. Under-delivering on promised views leads to partial payments and penalties, while over-delivering results in wasted inventory that could have been sold to other clients. This paper formalizes this dual-sided loss as "Regret" and introduces efficient algorithms to minimize it by optimizing digital billboard slot allocation.
The Problem of Regret
In digital outdoor advertising, influence providers are paid based on the number of "views" (influence) their ads generate. The provider faces two primary risks:
- Under-delivery: If the influence provided is less than the advertiser's demand, the provider receives only a partial payment.
- Over-delivery: If the influence exceeds the demand, the provider receives no extra incentive, and those excess views represent wasted slots.
Optimizing slot allocation across multiple advertisers to minimize total regret is a combinatorial optimization problem classified as NP-Hard, necessitating the use of clever heuristics for practical application.
Proposed Methodology
The authors propose two primary strategies designed to run in polynomial time:
- Effective Allocation (EA): A greedy-style heuristic that sorts advertisers based on their budget-to-demand ratio and evaluates billboard slots based on payment per unit influence. It allocates slots to satisfy demand while avoiding over-supply. If slots are scarce, it strategically removes the least budget-effective advertisers to ensure others are fully satisfied.
- Effective Local Search (ELS): A refinement step that iteratively looks for opportunities to swap allocated slots for unallocated ones. If a swap decreases an advertiser's regret, the algorithm performs it, continuing until no further improvements are possible.
Experimental Evaluation
The researchers evaluated their algorithms using the NYC Trajectory Dataset and the LAMAR Billboard Dataset, focusing on specific geographic contexts such as "Park" and "Mall" locations. The proposed methods were compared against existing baselines: G-Global, G-Order, and ALS.
Key Results
Experimental results comparing Regret across different algorithms and scenarios. Orange bars represent the unsatisfied penalty, while green bars represent excessive regret (wasted inventory). Source, p. 2
As shown in the experimental simulations, EA and ELS consistently demonstrate lower total regret than the baseline methods. In scenarios with high global demand, the proposed algorithms significantly reduce both the "unsatisfied penalty" (orange bars) and "excessive regret" (green bars). The authors note that their methods provide these improvements with reasonable computational requirements, outperforming the state-of-the-art ALS method across various demand-supply scenarios.
Future Work
While the current model provides a robust framework for regret minimization, future research could explore dynamic traffic patterns (as influence probabilities currently assume static conditions), real-time bidding environments where prices fluctuate, and the scalability of these algorithms to city-scale networks managing tens of thousands of billboards simultaneously.
Summary updated