Online Billboard Auction With Social Welfare Maximization

Outdoor billboard advertising has proven effective for commercial promotions, attracting potential customers, and boosting product sales. Auction serves as a popular method for leasing billboard usage rights, enabling a seller to rent billboards to winning users for predefined periods according to their bids. An effective auction algorithm is of great significance to maximize the efficiency of the billboard ecosystem. In contrast to a rich literature on Internet advertising auctions, well-crafted algorithms tailored for outdoor billboard auctions remain rare. In this work, we investigate the problem of outdoor billboard auctions, in the practical setting where bids are received and processed on the fly. Our goal is to maximize social welfare, namely the total benefits of auction participants, including the billboard service provider and the bidding users. To this end, we first formulate the billboard social welfare maximization problem into an Integer Linear Problem (ILP), and then reformulate the ILP into a compact form with a reduced size of constraints (at the cost of involving exponentially many primal variables), based on which we derive the dual problem. Furthermore, we design a dual oracle to handle the exponentially many dual constraints, avoiding exhaustive enumeration. We present a primal-dual online algorithm with an incentive-compatible pricing mechanism. Theoretical analysis proves the individual rationality, incentive compatibility, and computational efficiency of our online algorithm. Extensive experimental results show that the online algorithm is both effective and efficient, and achieves a good competitive ratio.