TY - GEN
T1 - Online Ad Allocation in Bounded-Degree Graphs
AU - Albers, Susanne
AU - Schubert, Sebastian
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - We study the AdWords problem defined by Mehta, Saberi, Vazirani and Vazirani [10]. A search engine company has a set of advertisers who wish to link ads to user queries and issue respective bids. The goal is to assign advertisers to queries so as to maximize the total revenue accrued. The problem can be formulated as a matching problem in a bipartite graph G. We assume that G is a (k, d)-graph, introduced by Naor and Wajc [11]. Such graphs model natural properties on the degrees of advertisers and queries. As a main result we present a deterministic online algorithm that achieves an optimal competitive ratio. The competitiveness tends to 1, for arbitrary k≥ d, using the standard small-bids assumption where the advertisers’ bids are small compared to their budgets. Hence, remarkably, nearly optimal ad allocations can be computed deterministically based on structural properties of the input. So far competitive ratios close to 1, for the AdWords problem, were only known in probabilistic input models.
AB - We study the AdWords problem defined by Mehta, Saberi, Vazirani and Vazirani [10]. A search engine company has a set of advertisers who wish to link ads to user queries and issue respective bids. The goal is to assign advertisers to queries so as to maximize the total revenue accrued. The problem can be formulated as a matching problem in a bipartite graph G. We assume that G is a (k, d)-graph, introduced by Naor and Wajc [11]. Such graphs model natural properties on the degrees of advertisers and queries. As a main result we present a deterministic online algorithm that achieves an optimal competitive ratio. The competitiveness tends to 1, for arbitrary k≥ d, using the standard small-bids assumption where the advertisers’ bids are small compared to their budgets. Hence, remarkably, nearly optimal ad allocations can be computed deterministically based on structural properties of the input. So far competitive ratios close to 1, for the AdWords problem, were only known in probabilistic input models.
KW - AdWords problem
KW - Deterministic algorithm
KW - Online ad allocation
KW - Targeted advertising
UR - http://www.scopus.com/inward/record.url?scp=85145254120&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-22832-2_4
DO - 10.1007/978-3-031-22832-2_4
M3 - Conference contribution
AN - SCOPUS:85145254120
SN - 9783031228315
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 60
EP - 77
BT - Web and Internet Economics - 18th International Conference, WINE 2022, Proceedings
A2 - Hansen, Kristoffer Arnsfelt
A2 - Liu, Tracy Xiao
A2 - Malekian, Azarakhsh
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th International Conference on Web and Internet Economics, WINE 2022
Y2 - 12 December 2022 through 15 December 2022
ER -