Collaborative Research: CIF: Medium: An Information-Theoretic Foundation for Adaptive Bidding in First-Price Auctions

随着电子商务的出现和日益巩固，数字广告最近取代传统广告成为经济中的主要营销力量。在过去两年中，数字广告行业的一个特别重要的发展是在线展示广告从第二价格拍卖转向第一价格拍卖。这种转变立即激发了如何在第一价格拍卖中出价的智力挑战问题，因为与第二价格拍卖不同，真实地出价一个人的私人价值不再是最佳的。此外，这种转变有两个独特的现代特征：1）拍卖以非常高的频率重复发生，投标决策必须在（毫秒）时间尺度上做出;第二，存在依赖于交易所的反馈信息，人们可以并且应该利用这些信息来告知自己的顺序投标决策。这两个特点暴露了现有的博弈理论方法的缺陷，并呼吁在顺序投标的新的和原则的发展。该项目中建立的方法和算法创新也可能帮助各种有广告需求的组织在新的和具有挑战性的展示广告竞标环境中导航。该项目的主要目标是开发一种方法框架，该方法框架智能地和自适应地利用过去的信息来构建计算和统计效率都高的竞标策略。这需要开发信息理论工具来理解第一价格拍卖中投标的基本学习限制，其中奖励函数既不是凸的也不是连续的，而是具有需要利用的特殊结构。此外，它需要为重复的第一价格拍卖开发计算效率高的投标和私人价值估计算法，以满足实时投标和大规模历史投标数据集的要求，以及学习-该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的学术价值和更广泛的影响审查标准。

With the advent and increasing consolidation of e-commerce, digital advertising has very recently replaced traditional advertising as the main marketing force in the economy. In the past two years, a particularly important development in the digital advertising industry is the shift from second-price auctions to first-price auctions for online display ads. This shift immediately motivated the intellectually challenging question of how to bid in first-price auctions, because unlike in second-price auctions, bidding one's private value truthfully is no longer optimal. Furthermore, this shift has two unique modern characteristics: 1) the auctions are occurring repeatedly at a very high frequency and the bidding decisions must be made on that (milliseconds) timescale; second, there is exchange-dependent feedback information that one can and should leverage to inform one's sequential bidding decisions. These two characteristics expose drawbacks in the existing game-theoretical approaches and call for novel and principled developments in sequential bidding. The methodological and algorithmic innovation established in this project could also potentially help various organizations with advertising needs to navigate in the new and challenging landscape of display ads bidding.The broad goal of this project is to develop a methodological framework that intelligently and adaptively leverages past information to construct bidding strategies that are both computationally and statistically efficient. This requires developing information-theoretic tools to understand the fundamental learning limits for bidding in first-price auctions, where the reward function is neither convex nor continuous but has a special structure of its own that needs to be exploited. Further, it requires developing computationally efficient bidding and private value estimation algorithms for repeated first-price auctions that could meet the demanding nature of real-time bidding and large-scale historical bidding dataset, as well as learning-theoretical tools that enable the analysis and rigorous characterization of the algorithms' performance.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.