Revenue Maximization and Ex-Post Budget Constraints
Revenue Maximization and Ex-Post Budget Constraints
复制标题
收入最大化和事后预算约束
DOI：
10.1145/2764468.2764521
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. M. Weinberg
中科院分区：
文献类型：
--
作者：
C. Daskalakis;Nikhil R. Devanur;S. M. Weinberg
我们认为，如果卖方对竞标者的价值和预算有一些先前的分配，则将收入最大化卖方的卖方最大化卖方的卖方出售。先验可以在同一出价者的项目和预算之间关联，但假定在竞标者之间独立。我们以贝叶斯激励兼容为目标的机制，但符合个人理性和事后预算。几乎没有知道满足所有这些条件并保证任何收入近似的机制，即使只有一个项目。我们提供了一种计算有效的机制，该机制是所有BIC，前局部IR和前预算尊重机制的3个同样的机制。请注意，即使在先验是点质量的情况下，问题的近似值比16/15的倍数（Chakrabarty and Goel，2010年）。我们进一步表征了这种情况下的最佳机制，表明它可以解释为虚拟福利最大化器的分布。我们通过利用[Cai等人开发的从机制到算法设计的黑框减少。 2013]。我们的主要技术贡献是一种用于算法问题的计算有效的3-辅助算法，该算法是通过将其框架应用于此问题而导致的。算法问题具有混合符号目标，并且是确切优化的NP-硬化，因此令人惊讶的是，完全可以进行计算有效的近似值。在单个项目的情况下（M = 1），可以通过详尽的搜索准确地解决算法问题，从而导致计算有效的精确算法，并将最佳机制作为虚拟值最大化器的分布进行更强的表征。
We consider the problem of a revenue-maximizing seller with $m$ items for sale to $n$ additive bidders with hard budget constraints, assuming that the seller has some prior distribution over bidder values and budgets. The prior may be correlated across items and budgets of the same bidder, but is assumed independent across bidders. We target mechanisms that are Bayesian Incentive Compatible, but that are ex-post Individually Rational and ex-post budget respecting. Virtually no such mechanisms are known that satisfy all these conditions and guarantee any revenue approximation, even with just a single item. We provide a computationally efficient mechanism that is a 3-approximation with respect to all BIC, ex-post IR, and ex-post budget respecting mechanisms. Note that the problem is NP-hard to approximate better than a factor of 16/15, even in the case where the prior is a point mass [Chakrabarty and Goel 2010]. We further characterize the optimal mechanism in this setting, showing that it can be interpreted as a distribution over virtual welfare maximizers. We prove our results by making use of a black-box reduction from mechanism to algorithm design developed by [Cai et al. 2013]. Our main technical contribution is a computationally efficient 3-approximation algorithm for the algorithmic problem that results by an application of their framework to this problem. The algorithmic problem has a mixed-sign objective and is NP-hard to optimize exactly, so it is surprising that a computationally efficient approximation is possible at all. In the case of a single item (m=1), the algorithmic problem can be solved exactly via exhaustive search, leading to a computationally efficient exact algorithm and a stronger characterization of the optimal mechanism as a distribution over virtual value maximizers.