【理论学习】Posted Price Mechanisms

发表于 2024-03-07 分类于理论学习

继续记录一些要用到的 prophet inequality 相关的结论。（对无相关了解者可读性低）

背景

拍卖是经济学中的重要研究对象。在最近二十多年，拍卖也得到了算法博弈论领域的重点关注。

一个重要的DSIC的拍卖形式为二价拍卖，它可以做到让每个参与者truthfully bid，也即报出自己对商品的真实value。

然而，二价拍卖在维护商品提供方的revenue上是很垃圾的（一个例子就是新西兰的频谱拍卖），因此常使用一种二价拍卖的变形，即带底价的二价拍卖。它表示为二价拍卖增加一个底价，二价竞拍的获胜者的报价至少要高于该底价，且至少要支付该底价，否则就不卖了。

通过一些计算便可证明，带底价的二价拍卖对于参与者value独立同分布的情形是最优的拍卖。（即能使供方期望收益最大化）

然而，如果不是独立同分布的，最优拍卖的形式会变得非常复杂且奇怪，在现实中难以操作。因此我们需要一些更简单的，但是又不会损失太多收益的拍卖机制。

现实中最常用的一种拍卖形式其实是Posted Price Mechanism，即给商品公布一个价格，谁愿意买就谁买（先到先得）。

我们会发现，这个形式和先知不等式中的最优停止问题非常相似。

事实上，考虑单物品、独立但不同分布的多竞拍者的情形，并假设我们期望的是社会福利最大化，那么这个问题就完全等价于上个blog里证明了竞争系数的情形。

可如果我们的需求是收益最大化，事情就不太一样了。因为我们获得的是所设定的价格带来的收益，也即，其中代表的概率，也即价格定为时成交的概率。而stopping game里获得的则直接是。

这直接导致了一个问题，那就是——标价机制（事实上是全体拍卖机制）都不存在general的先知不等式。

考虑下面这个单物品单顾客的情形：

，支撑集为。

可以发现，顾客value的数学期望为正无穷，而无论如何定价，期望收益都为。

因此，通常在研究拍卖机制时，我们的benchmark是Optimal Auction，而非最大的期望。（这几年也有一些benchmark采用的是ex ante机制，即只要求机制在期望意义上能够把商品分配给一个customer）。

2009年，Hartline 和 Roughgarden 的一项工作指出，以Optimal Auction为benchmark，带底价的二价拍卖的Revenue Gap位于区间。后续有许多相关工作进行改进，例如2015年Hartline等人的工作指出了下面的Revenue Gap族：

rev

而welfare方面，相关的进展也和prophet inequality方面的成果同步涌现，代表性的有Jose Correa等人确定了i.i.d情形下的最优定价机制等。