Incentives without monetary transfers

无货币转移的激励措施

基本信息

批准号：
EP/M018113/1
负责人：
Carmine Ventre
金额：
$ 12.65万
依托单位：
Teesside University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2015
资助国家：
英国
起止时间：
2015 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FM018113%2F1
关键词：
Incentives without monetary transfers

项目摘要

The major difficulty of algorithm design has always been identified with the understanding of the combinatorial structure underlying the optimisation problem at hand. However, this might be only one source of complexity for algorithm design. Indeed, the emergence of the Internet as the computing platform has enriched the picture by highlighting the presence of agents that selfishly evaluate the outcome of the computation. As a consequence, nowadays, algorithms have also to work in the presence of these selfish interests, which are often in contrast with the ultimate objective of the computation (e.g., optimality). The field of Algorithmic Mechanism Design (AMD) has as its main scope the realignment of the objective of the designer with those of the selfish agents through the design of so-called truthful mechanisms. Truthfulness guarantees that agents have no interest in misguiding the mechanism towards the computation of "wrong" (e.g., suboptimal) outcomes.Truthfulness, however, comes with a heavy price tag. Specifically, monetary transfers between designer and agents are needed, for otherwise the only truthful mechanisms are dictatorships as from the celebrated Gibbart-Satterthwaite theorem. On one hand, dictatorships are neither interesting nor useful as the outcome solution might be arbitrarily "bad" for the designer's objectives (e.g., with a poor approximation guarantee of the measure of interest). On the other hand, while money might be reasonable in some applications, little justification can be found, in general, for either the presence of a digital currency or the use of money at all. There are contexts in which money is morally unacceptable (e.g., to support certain political decisions) or even illegal (as, e.g., in organ donations). This proposal aims at reconsidering the role of money as a 'necessary evil' in AMD. We propose to reconcile computation and incentives without the use of monetary transfers by leveraging restricted domains, approximation, and well-motivated, relaxed notions of truthfulness. In detail, Gibbart-Satterthwaite theorem is proved under the hypothesis that agents have unrestricted domains (i.e., unrestricted ways to misguide the algorithm), yet many computer science applications only have quite well structured domains. What kind of approximation guarantee of the optimum can we achieve if we insist on truthfulness without money when agents have restricted domains? Our third leverage is a novel application of the concept of verification in AMD. Verification, in this context, means that some kind of misbehaviour of the agents can be uncovered (and punished accordingly). This idea mimics what happens in real life where "inspections of job done" are often the norm and allows for a relaxed notion of truthfulness whereby the set of agents' misbehaving strategies does not contain verifiable ones. The concept of verification has been extensively used in AMD with money; we ask here to what extent we can trade money with verification. How good is the approximation guarantee of the solutions output of truthful mechanisms without money that use verification? We want to advance our knowledge in this (largely) unexplored middle ground between truthfulness, approximation, and money in relation to fundamental optimisation problems, with many applications in real life, such as Combinatorial Auctions and Facility Location, as well as in a more abstract way by relating particular forms of verification to truthfulness, money and other measures of interest. Our study attempts to build the foundations of (i) a more applied use of AMD; and, (ii) the application of game-theoretic models to the non-profit sector.

算法设计的主要困难始终在于理解当前优化问题背后的组合结构。然而，这可能只是算法设计复杂性的来源之一。事实上，互联网作为计算平台的出现，通过强调自私地评估计算结果的代理的存在，丰富了这幅图景。因此，如今，算法也必须在这些自私利益的存在下工作，这些自私利益通常与计算的最终目标（例如，最优性）相反。算法机制设计（AMD）领域的主要范围是通过设计所谓的真实机制来重新调整设计者的目标与自私主体的目标。真实性保证了代理没有兴趣误导机制来计算“错误”（例如，次优）结果。然而，真实性伴随着沉重的代价。具体来说，设计者和代理人之间需要进行货币转移，否则唯一真实的机制就是著名的吉巴特-萨特思韦特定理中的独裁统治。一方面，独裁统治既无趣也无用，因为结果解决方案可能对设计者的目标任意“不利”（例如，对利益衡量的近似保证很差）。另一方面，虽然货币在某些应用中可能是合理的，但一般来说，数字货币的存在或货币的使用几乎没有理由。在某些情况下，金钱在道德上是不可接受的（例如，支持某些政治决策），甚至是非法的（例如，器官捐赠）。该提案旨在重新考虑金钱在 AMD 中作为“必要之恶”的作用。我们建议通过利用受限领域、近似值和动机良好、宽松的真实性概念，在不使用货币转移的情况下协调计算和激励。具体来说，吉巴特-萨特思韦特定理是在代理具有不受限制的领域（即，误导算法的不受限制的方式）的假设下得到证明的，但许多计算机科学应用程序仅具有结构良好的领域。当代理人的领域受到限制时，如果我们坚持不花钱的真实性，我们可以实现什么样的最优近似保证？我们的第三个优势是验证概念在 AMD 中的新颖应用。在这种情况下，验证意味着可以发现代理的某种不当行为（并进行相应的惩罚）。这个想法模仿了现实生活中发生的情况，其中“检查已完成的工作”通常是常态，并允许宽松的真实性概念，即代理的不当行为策略集不包含可验证的策略。验证的概念在 AMD 中被广泛使用，有钱；我们在这里询问我们可以在多大程度上通过验证进行货币交易。在没有使用验证资金的情况下，真实机制的解决方案输出的近似保证有多好？我们希望在与基本优化问题相关的真实性、近似性和金钱之间的这个（很大程度上）未经探索的中间立场上增进我们的知识，并在现实生活中拥有许多应用，例如组合拍卖和设施选址，以及更抽象的应用。通过将特定形式的验证与真实性、金钱和其他利益衡量标准联系起来。我们的研究试图为 (i) AMD 的更实际应用奠定基础； (ii) 博弈论模型在非营利部门的应用。