We study the liquid welfare in repeated first-price auctions with budget limited buyers. We use a behavioral model for the buyers, assuming a learning style guarantee on the utility each achieves. We focus on first-price auctions, which are increasingly commonly used in many settings, and consider liquid welfare, a natural and well-studied generalization of social welfare for the case of budget-constrained buyers. We show a $\gamma+O(\sqrt{\gamma})$ price of anarchy for liquid welfare assuming buyers have additive valuations and the utility of each buyer is within a $\gamma$ factor of the utility achievable by shading her value with the same factor each iteration. This positive result is in stark contrast to repeated second-price auctions, where even with $\gamma=1$, the resulting liquid welfare can be arbitrarily smaller than the optimal one. We prove a lower bound of $\gamma$ on the liquid welfare loss under the above assumption, making our bound asymptotically tight. For the case when $\gamma = 1$ our theorem proves a price of anarchy upper bound that is about $3.18$; we prove a lower bound of $2$ for that case. We also offer a learning algorithm that achieves utility of at least a $\gamma = O(\log T)$ fraction of the optimal utility even when a buyer's values and the bids of the other buyers are chosen adversarially, offering a possible algorithm they can use to achieve the guarantee needed for our liquid welfare result. Finally, we extend our liquid welfare results for the case where buyers have submodular valuations with a slightly worse constant in the big $O(.)$ of the guarantee for the linear case.
翻译:我们在与预算有限的买主反复进行的首价拍卖中研究液体福利。 我们为买主使用一种行为模式, 假设每个买主都有添加值, 并且每个买主的效用都低于通过以同样的因子来掩盖其价值而实现的效用的$\gamma系数。 我们注重第一价拍卖, 在许多场合中, 并且考虑液体福利的自然和研究周全性, 对于预算限制的买主来说,这是对社会福利的任意概括。 我们证明,根据上述假设,对于液体福利的损失来说, 价格为$\gamma+O(sqrt69 gamma} 价格为零, 而对于每个买主来说, 价格为$\gamma=1美元, 效益的效用在价值上一个因子。 这个结果与重复的二价拍卖形成鲜明对比, 即使用$=1美元, 由此产生的液体福利可以任意地小于最佳的。 我们证明, 在以上假设的液体福利损失中, 价格为美元, 价格为我们的最佳保证。 当我们的钱=1美元时, 我们的货币价值为1美元, 我们的货币价值为10美元, 价格的购买者也能够取得一个价格上限。