论文标题
在部分信息拍卖中无需重新学习
No-Regret Learning in Partially-Informed Auctions
论文作者
论文摘要
有关项目的部分信息的拍卖广泛用于现实世界应用中，但是基本机制的理论支持有限。在这项工作中，我们研究了这些类型的机制的机器学习公式，从买家的角度提出了算法，这些算法是没有重新格雷的。具体来说，希望最大化其公用事业的买家与一系列$ t $回合的平台反复互动。在每个回合中，都从未知的分布中汲取新项目，并且该平台以不完整的“掩盖”信息发布了价格。然后，买家决定是否购买该商品。我们将这个问题正式化为在线学习任务，其目标是对近视甲骨文的遗憾，该甲骨文对物品的分布和卖方的掩盖功能具有完美的了解。当买家知道项目上的分布和蒙版是一个simhash函数映射$ \ mathbb {r}^d $ to $ \ {0,1 \}^{\ ell} $时，我们的算法很遗憾$ \ tilde o（（td \ ell）^{1/2}）$。在完全不可知的设置中，当掩码是任意函数映射到一组$ n $并且价格随机的映射时，我们的算法很遗憾$ \ tilde o（（TN）^{1/2}）$。
Auctions with partially-revealed information about items are broadly employed in real-world applications, but the underlying mechanisms have limited theoretical support. In this work, we study a machine learning formulation of these types of mechanisms, presenting algorithms that are no-regret from the buyer's perspective. Specifically, a buyer who wishes to maximize his utility interacts repeatedly with a platform over a series of $T$ rounds. In each round, a new item is drawn from an unknown distribution and the platform publishes a price together with incomplete, "masked" information about the item. The buyer then decides whether to purchase the item. We formalize this problem as an online learning task where the goal is to have low regret with respect to a myopic oracle that has perfect knowledge of the distribution over items and the seller's masking function. When the distribution over items is known to the buyer and the mask is a SimHash function mapping $\mathbb{R}^d$ to $\{0,1\}^{\ell}$, our algorithm has regret $\tilde O((Td\ell)^{1/2})$. In a fully agnostic setting when the mask is an arbitrary function mapping to a set of size $n$ and the prices are stochastic, our algorithm has regret $\tilde O((Tn)^{1/2})$.
