Envy-Free Revenue Approximation for Asymmetric Buyers with Budgets
Envy-Free Revenue Approximation for Asymmetric Buyers with Budgets
复制标题
为预算不对称的买家提供无嫉妒的收入估算
DOI：
10.1007/978-3-662-53354-3_20
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Orestis Telelis
中科院分区：
文献类型：
--
作者：
E. Markakis;Orestis Telelis
本文研究了具有预算购买者的垄断市场中收入最大化的无嫉妒结果的计算。从以前的作品出发，我们专注于买家与不对称的组合估价功能的项目的子集。我们首先建立一个硬度结果表明，即使有两个相同的添加剂买家，问题是不可近似的。在试图确定听话的家庭的问题的情况下，我们引入的概念ofbudget compatiblebuyers，把一个限制的预算，每个买家在他的估值功能。在此假设下，我们建立近似上界的买家与子模块化的估值偏好子集，以及为买家相同的次可加的估值功能。最后，我们还分析了算法的任意添加剂的估值函数，它产生一个常数因子近似为常数数量的买家。最后，我们提出了几个有趣的开放式问题，关于预算买家的非对称估值函数。
We study the computation of revenue-maximizing envy-free outcomes in a monopoly market with budgeted buyers. Departing from previous works, we focus on buyers with asymmetric combinatorial valuation functions over subsets of items. We first establish a hardness result showing that, even with two identical additive buyers, the problem is inapproximable. In an attempt to identify tractable families of the problem’s instances, we introduce the notion ofbudget compatiblebuyers, placing a restriction on the budget of each buyer in terms of his valuation function. Under this assumption, we establish approximation upper bounds for buyers with submodular valuations over preference subsets as well as for buyers with identical subadditive valuation functions. Finally, we also analyze an algorithm for arbitrary additive valuation functions, which yields a constant factor approximation for a constant number of buyers. We conclude with several intriguing open questions regarding budgeted buyers with asymmetric valuation functions.