【理论学习？】在线单物品拍卖的最优竞争系数到底是啥？

发表于 2023-10-17 分类于理论学习

single-item

问题就是上面这个问题里描述的这个东西，我们关注的是c题。（“竞拍者的私人估值是”，翻译错了）

我很快就做出了的方案，那就是首先查看前一半的报价（每个都拒绝），然后按照前一半中的最高报价作为接下来的标价，一旦有人高于标价，就卖给他，证明已经在【练习】Twenty Lectures on Algorithmic Game Theory | Home of Mr. 5给出。

但是这个是不是紧的呢？我不想重新发明轮子，也大概率没有发明的能力，所以去请教了别人。

TLAGT的作者Tim Roughgarden回复了我：
tim

我去看了这篇论文（忽略我狂暴的注释风格）：
ada

首先，非常明显的，这个问题和secretary problem、prophet inequality之类的东西差不多。事实上，任何一个secretary problem的方案都可以直接归约到这个在线单物品拍卖问题上。

这篇文献提到了很多种模型。比方说把单物品扩展到多物品、把bidder一个一个分立地到来扩展到每个bidder有自己的到达时间和离开时间且这些时间形成的区间可以相交。同时，还要考虑知不知道bid的分布、能否保证truthful bidding等等。

文章把之前提到的“查看前个bid，并取其中的最大值作为接下来的标价”的策略称为，那么的那个策略就是。

根据secretary problem里面的研究，这类方案能达到的最好的结果是，对应，这也就是很多科普up介绍过的法则。

在secretary problem中，这个结果不仅是所有类策略中最好的，它也是一切策略中最好的，是一个tight bound。

但是这个tight不能直接扩展到在线单物品拍卖中，原因如下：

low

第二个问题比较好解决，只要让最高bid与其他bid相比超出很多很多就可以了。

但是第一个问题似乎比较难搞（本质上是能不能通过得到的数值对一个未知的分布进行一定程度的猜测从而进行策略调整？）。这篇文献没有解决这个问题，而是给出了几个不紧的bound。

我试图进一步寻找给出了紧证明的文献，期间我发现了这个，Kleinberg等人2008年的作品：

tight

I mean, where is the proof?

我又翻了一堆文献，并没有找到他提到的这个optimal的证明。（不过期间还是发现了好多很有意思的结果，以后再写博客讲吧）

这个问题就先这样吧，我已经不关心了（悲