Revenue Maximizing Envy-Free Fixed-Price Auctions with Budgets
Revenue Maximizing Envy-Free Fixed-Price Auctions with Budgets
复制标题
通过预算实现收入最大化的无羡慕固定价格拍卖
DOI：
10.1007/978-3-319-13129-0_18
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Qiang Zhang
中科院分区：
文献类型：
--
作者：
Riccardo Colini;S. Leonardi;P. Sankowski;Qiang Zhang
传统的激励相容拍卖[6，16]用于向无约束和预算的投标人出售多个商品，可以通过以不同的价格出售相同的商品来区分投标人。出于这个原因，Feldman等人[7]放弃了激励相容性，并将注意力转向收入最大化预算投标人的无嫉妒项目定价分配。经典论文[9，15]提出了无嫉妒分配。这种分配的关键属性是没有人羡慕分配和向其他人收取的价格。在本文中，我们考虑这个经典的概念，嫉妒免费和研究固定价格机制，使用非歧视性的统一价格的所有商品。Feldman等人[7]给出了一种物品定价机制，该机制可以获得相同商品的任何无嫉妒固定价格机制所获得收入的1/2。我们改进了这个结果，提出了一个FPTAS的问题，返回一个（1-ε）-近似的收入所获得的任何无嫉妒的固定价格机制，任何ε> 0，并运行在多项式时间内的投标者的数量snand 1/ε，即使是指数供应的商品sm。接下来，我们考虑预算投标人对商品集合具有匹配型偏好的情况，即，每个投标人对每个项目的估价为0或0。在这种更一般的情况下，我们证明了对于任何ε> 0，除非P =NP，不可能在O（min（n，m）1/2-ε）内近似最优收益。从积极的方面来看，我们能够在不同类型货物数量不变的情况下，将相同货物的FPTAS扩展到预算投标人。我们的FPTAS也给出了一个常数近似一般的无嫉妒拍卖。
Traditional incentive-compatible auctions [6,16] for selling multiple goods to unconstrained and budgeted bidders can discriminate between bidders by selling identical goods at different prices. For this reason, Feldman et al. [7] dropped incentive compatibility and turned the attention to revenue maximizing envy-free item-pricing allocations for budgeted bidders.Envy-freeallocations were suggested by classical papers [9,15]. The key property of such allocations is that no one envies the allocation and the price charged to anyone else. In this paper we consider this classical notion of envy-freeness and studyfixed-pricemechanisms which use nondiscriminatory uniform prices for all goods. Feldman et al. [7] gave an item-pricing mechanism that obtains 1/2 of the revenue obtained from any envy-free fixed-price mechanism for identical goods. We improve over this result by presenting an FPTAS for the problem that returns an (1 −ε)-approximation of the revenue obtained by any envy-free fixed-price mechanism for anyε> 0 and runs in polynomial time in the number of biddersnand 1/εeven for exponential supply of goodsm. Next, we consider the case of budgeted bidders with matching-type preferences on the set of goods, i.e., the valuation of each bidder for each item is eithervior 0. In this more general case, we prove that it is impossible to approximate the optimum revenue withinO( min (n,m)1/2 −ε) for anyε> 0 unlessP=NP. On the positive side, we are able to extend the FPTAS for identical goods to budgeted bidders in the case of constant number of different types of goods. Our FPTAS gives also a constant approximation with respect to the general envy-free auction.