论文标题
与在线物品和离线代理商的真实匹配
Truthful Matching with Online Items and Offline Agents
论文作者
论文摘要
我们研究了在线两部分匹配中福利最大化的真实机制。在我们的（多参数）设置中，每个买家都与一套（可能是私人）所需的项目相关联，并且具有私人价值，可以在她所需的集合中分配项目。与代理商在线到达的大多数在线匹配设置不同，在我们的设置中，这些物品在整个过程的整个过程中以对抗性顺序在线到达。由于买家能够在未来的回合中制定策略，这对真实机制的设计构成了重大挑战。在不同情况下，我们几乎可以全面了解竞争比率，包括近视与非侧型代理商，迟来与及时付款以及私人与公共期望的套装。除其他结果外，我们还确定了著名的$ e/（e-1）$竞争比率的边界，以karp，vazirani和vazirani的顶点加权在线匹配扩展到真实的代理商和在线物品。
We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier for which the celebrated $e/(e-1)$ competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.
