Fast Core Pricing for Rich Advertising Auctions

DOI10.1287/OPRE.2021.2104MaRDI QIDQ5031009zbMATH OpenOpenAlexFDO

Authors

Publication date 18 February 2022

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.03564

zbMATH Keywords

combinatorial auctioncore pricingGSP auctionrevenue management and market analyticssale of ad spacesponsored search auctionsVCG auction

Mathematics Subject Classification ID

Marketing, advertising (90B60) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) can yield unacceptably low revenue. We therefore study core selecting auctions, which boost revenue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinatorial algorithm that finds an approximate bidder optimal core point with almost linear number of calls to the welfare maximization oracle. Our algorithm is faster than previously-proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time sensitive practical use cases such as realtime auctions for online advertising and can yield more revenue. We justify this claim experimentally using the Microsoft Bing Ad Auction data, through which we show our core pricing algorithm generates almost 26% more revenue than VCG on average, about 9% more revenue than other core pricing rules known in the literature, and almost matches the revenue of the standard Generalized Second Price (GSP) auction.

Recommendations

• Pricing in position auctions and online advertising
• Optimal dynamic auctions for display advertising
• Optimal advertising of auctions
• Bidding on Configurations in Internet Ad Auctions
• Adaptive Incentive-Compatible Sponsored Search Auction
• Optimal dynamic pricing for sponsored search advertising
• On Revenue Maximization in Second-Price Ad Auctions
• A Pareto optimal mechanism for demand-side platforms in real time bidding advertising markets

Cites work

• A course in game theory.
• A new algorithm for minimizing convex functions over convex sets
• Algorithm for optimal winner determination in combinatorial auctions
• Autobidding with constraints
• Computationally feasible VCG mechanisms
• Convex optimization: algorithms and complexity
• Core-selecting package auctions
• Core-selecting package auctions: a comment on revenue-monotonicity
• Fair payments for efficient allocations in public sector combinatorial auctions
• Incentives in Teams
• Non-bidding equilibrium in an ascending core-selecting auction
• On the Implementation of a Primal-Dual Interior Point Method
• On the impossibility of core-selecting auctions
• Package Auctions and Exchanges
• Preprocessing for quadratic programming
• Quadratic core-selecting payment rules for combinatorial auctions
• Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions
• Solving large-scale linear programs by interior-point methods under the Matlab^∗Environment^†
• The ellipsoid method and its consequences in combinatorial optimization
• The Multiple-Choice Knapsack Problem
• Truthful mechanisms with implicit payment computation

Cited in

(3)

• Maximizing revenue for publishers using header bidding and ad exchange auctions
• Understanding the relationship between core constraints and core-selecting payment rules in combinatorial auctions
• On the strategyproof allocation of items under a budget constraint

Describes a project that uses

Uses Software

• LIPSOL
• QP

This page was built for publication: Fast Core Pricing for Rich Advertising Auctions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5031009)