An official website of the United States government
Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives—instead of individual auctions—and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg–Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers, and regrets all have a positive association in statistical terms. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. Funding: D. Panigrahi was supported in part by the National Science Foundation [Awards CCF 1535972, CCF 1750140, and CCF 1955703]. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2022.4310 .
more »
« less
Effect of constant-DI pacing on single cell pacing dynamics
- Award ID(s):
- 1662250
- PAR ID:
- 10198685
- Publisher / Repository:
- American Institute of Physics
- Date Published:
- Journal Name:
- Chaos: An Interdisciplinary Journal of Nonlinear Science
- Volume:
- 30
- Issue:
- 10
- ISSN:
- 1054-1500
- Page Range / eLocation ID:
- Article No. 103122
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Previous studies have observed that TCP pacing evenly spacing out packets-minimizes traffic burstiness, reduces packet losses, and increases throughput. However, the main drawback of pacing is that the number of flows and the bottleneck link capacity must be known in advance. With this information, pacing is achieved by manually tuning sender nodes to send at rates that aggregate to the bottleneck capacity. This paper proposes a scheme based on programmable switches by which rates are dynamically adjusted. These switches store the network's state in the data plane and notify sender nodes to update their pacing rates when the network's state changes, e.g., a new flow joins or leaves the network. The scheme uses a custom protocol that is encapsulated inside the IP Options header field and thus is compatible with legacy switches (i.e., the scheme does not require all switches to be programmable). Furthermore, the processing overhead at programmable switches is minimal, as custom packets are only generated when a flow joins or leaves the network. Simulation results conducted in Mininet demonstrate that the proposed scheme is capable of dynamically notifying hosts to adapt the pacing rate with a minimum delay, increasing throughput, mitigating the TCP sawtooth behavior, and achieving better fairness among concurrent flows. The proposed scheme and preliminary results are particularly attractive to applications such as Science DMZ, where typically a small number of large flows must share the bandwidth capacity.more » « less
-
Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in this game is known as a pacing equilibrium. In this work, we show that the problem of finding an approximate pacing equilibrium is PPAD-complete for second-price auctions. This resolves an open question of Conitzer et al. [Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2022a) Multiplicative pacing equilibria in auction markets. Oper. Res. 70(2):963–989]. As a consequence of our hardness result, we show that the tâtonnement-style budget-management dynamics introduced by Borgs et al. [Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540] are unlikely to converge efficiently for repeated second-price auctions. This disproves a conjecture by Borgs et al. [Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web (ACM, New York), 531–540], under the assumption that the complexity class PPAD is not equal to P. Our hardness result also implies the existence of a refinement of supply-aware market equilibria which is hard to compute with simple linear utilities. Funding: This work was supported by National Science Foundation (CCF-1703925, IIS-1838154).more » « less
