Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions
成果类型：
Article
署名作者：
Fikioris, Giannis; Tardos, Eva
署名单位：
Cornell University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2023.0274
发表日期：
2025
关键词：
摘要：
We study the liquid welfare in sequential first-price auctions with budgeted buyers. We use a behavioral model for the buyers, assuming a learning style guarantee: the utility of each buyer is within a gamma factor (gamma >_ 1) of the utility achievable by shading their value with the same factor at each iteration. We show a gamma + 1/2 + O(1/gamma) price of anarchy for liquid welfare when valuations are additive. This is in stark contrast to sequential second-price auctions, where the resulting liquid welfare can be arbitrarily smaller than the maximum liquid welfare, even when gamma = 1. We prove a lower bound of gamma on the liquid welfare loss under the given assumption in first-price auctions. Our liquid welfare results extend when buyers have submodular valuations over the set of items they win across iterations with a slightly worse price of anarchy bound of gamma + 1 + O(1/gamma) compared with the guarantee for the additive case.
来源URL：