Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints

• 成果类型: Article
• 署名作者: Shioura, Akiyoshi
• 署名单位: Tohoku University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0668
• 发表日期: 2015
• 页码: 192-225
• 关键词: set function subject; matroid constraint; convex-functions; equilibrium; relaxation

摘要

We consider the maximization of a gross substitutes utility function under budget constraints. This problem naturally arises in applications such as exchange economies in mathematical economics and combinatorial auctions in (algorithmic) game theory. We show that this problem admits a polynomial-time approximation scheme (PTAS). More generally, we present a PTAS for maximizing a discrete concave function called an M-right angle-concave function under budget constraints. Our PTAS is based on rounding an optimal solution of a continuous relaxation problem, which is shown to be solvable in polynomial time by the ellipsoid method. We also consider the maximization of the sum of two M-right angle-concave functions under a single budget constraint. This problem is a generalization of the budgeted max-weight matroid intersection problem to the one with certain nonlinear objective functions. We show that this problem also admits a PTAS.