What is it about?
This paper is ultimately about modelling a certain type of "contract management" problem where you need to participate in a sequential auction (the auction is repeated rapidly) on behalf of a number of counter-parties. You need to find a bidding strategy that satisfies the constraints of the contract, and minimizes your costs. The problem arises in computational advertising, but is technically very closely related to a production-transportation problem (how to transport goods through a network, while also choosing how much of those goods to produce), and may inspire other applications.
Featured Image
Photo by Mari Helin on Unsplash
Why is it important?
Aside from the applicability of the actual problem being studied (and that the algorithm should be almost directly applicable with few modifications in practice), there are at least two more broad technical aspects which may be of interest: (1) There is a very natural and intuitive transformation of variables involving certain functions involved in auction theory that can be used to exploit convexity (many other tractable problems of interest can likely be formulated using these ideas) and (2) the problem analyzed in the paper may have pedagogical value as it illustrates a striking transformation of variables and analyzes the consequences of convex duality in infinite dimensions.
Perspectives
The "natural" formulation of the problem is as a monotone optimization problem (the objective and constraints are monotone functions) and I spent many months, with limited success, trying to exploit these properties to obtain a solution. The key insight is the transformation of variables (which makes the problem convex and easily tractable) where you instead optimize the "rate of acquisition" rather than the actual auction bids directly. To me, it is a striking illustration of how convexity arises in many, often surprising, ways -- look for it in your own problems.
Ryan Kinnear
University of Waterloo
Read the Original
This page is a summary of: Real-time Bidding for Time Constrained Impression Contracts in First and Second Price Auctions - Theory and Algorithms, Proceedings of the ACM on Measurement and Analysis of Computing Systems, December 2021, ACM (Association for Computing Machinery),
DOI: 10.1145/3491049.
You can read the full text:
Contributors
The following have contributed to this page
