Truthful Generalized Assignments via Stable Matching

• 成果类型: Article
• 署名作者: Chen, Ning; Gravin, Nick; Lu, Pinyan
• 署名单位: Nanyang Technological University; Microsoft; Microsoft Research Asia; Microsoft; Microsoft China
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0625
• 发表日期: 2014
• 页码: 722-736
• 关键词: Approximation

摘要

In the generalized assignment problem (gap), a set of jobs seek to be assigned to a set of machines. For every job-machine pair, there are a specific value and an accommodated capacity for the assignment. The objective is to find an assignment that maximizes the total sum of values given that the capacity constraint of every machine is satisfied. The GAP is a classic optimization problem and has been studied extensively from the algorithmic perspective. Dughmi and Ghosh [Dughmi S, Ghosh A (2010) Truthful assignment without money. ACM Conf. Electronic Commerce (ACM, New York), 325-334.] proposed the game theoretical framework in which every job is owned by a selfish agent who aims to maximize the value of his own assignment. They gave a logarithmic approximation truthful in expectation mechanism and left open the problem whether there exists a truthful mechanism with a constant approximation factor. In this paper, we give an affirmative answer to this question and provide a constant approximation mechanism that enjoys a stronger incentive property of universal truthfulness than that of truthfulness in expectation. Our mechanism is inspired by stable matching, which is a fundamental solution concept in the context of matching marketplaces. The mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling.