Interdependent Values without Single-Crossing
Interdependent Values without Single-Crossing
复制标题
无单交叉的相互依赖的值
DOI：
10.1145/3219166.3219173
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Kira Goldner
中科院分区：
文献类型：
--
作者：
Alon Eden;M. Feldman;A. Fiat;Kira Goldner
我们考虑一个拍卖商出售一个单一的项目，n个潜在的代理人相互依赖的价值。也就是说，每个代理都有自己的私人信号，每个代理的估值是所有n个私人信号的已知函数。这捕获了诸如石油钻探权、广播权、艺术品等的估值等设置。在相互依赖的值设置，所有以前的工作都假设了所谓的单交叉条件。单交叉意味着私人信号si对代理i估值的影响大于si对任何其他代理估值的影响。众所周知，如果没有单交叉条件，就不能获得有效的结果。我们要问的是，当估值不呈现单交叉时，可以获得什么样的最优社会福利近似。我们表明，一般来说，在没有单交叉条件的情况下，人们不可能希望比将物品分配给随机竞标者更好地近似最优社会福利。因此，我们考虑单交叉的放松版本，c-单交叉，其中某些参数c≥1，这意味着si对代理i的估值的影响至少是si对任何其他代理的估值的影响的1/ c倍（c =1是单交叉）。使用这个放松的概念，我们得到了一系列积极的结果。其中包括一个无先验的普遍真实的2-nc 3/2 -福利近似，和一个无先验的确定性的（n-1）c -福利近似。在适当的条件下，我们将其改进为一个无先验的普遍真实的2 c -近似福利以及普遍真实的O（c2）-近似最优收入。
We consider a setting where an auctioneer sells a single item to n potential agents with interdependent values. That is, each agent has her own private signal, and the valuation of each agent is a known function of all n private signals. This captures settings such as valuations for oil drilling rights, broadcast rights, pieces of art, and many more. In the interdependent value setting, all previous work has assumed a so-called single-crossing condition. Single-crossing means that the impact of a private signal, si , on the valuation of agent i , is greater than the impact of si on the valuation of any other agent. It is known that without the single-crossing condition, an efficient outcome cannot be obtained. We ask what approximation to the optimal social welfare can be obtained when valuations do not exhibit single-crossing. We show that, in general, without the single-crossing condition, one cannot hope to approximate the optimal social welfare any better than assigning the item to a random bidder. Consequently, we consider a relaxed version of single-crossing, c-single-crossing, with some parameter c≥1 , which means that the impact of si on the valuation of agent i is at least 1/ c times the impact of si on the valuation of any other agent ( c =1 is single-crossing). Using this relaxed notion, we obtain a host of positive results. These include a prior-free universally truthful 2√ nc3/2 -approximation to welfare, and a prior-free deterministic ( n -1) c -approximation to welfare. Under appropriate concavity conditions, we improve this to a prior-free universally truthful 2 c -approximation to welfare as well as a universally truthful O(c2)-approximation to the optimal revenue.