TL;DR研究不使用支付的真实机制的设计,以解决广义分配问题(GAP)及其变体。引入私人估值的模型,并研究了几种 GAP 变体,开发了一个基于 LP 的通用技术,可以将设计真实机制的问题降低到该问题的分数版本,获得了一些近似算法且吻合上下界,这个技术也可用于其他基于 LP 的问题。
Abstract
We study the design of truthful mechanisms that do not use payments for the
generalized assignment problem (GAP) and its variants. An instance of the GAP
consists of a bipartite graph with jobs on one side and ma