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）的领域通过设计通过所谓的真实机制设计了设计师与自私者的目标的主要范围。真实性保证了代理人对误导“错误”（例如，次优的）结果的机制没有兴趣。但是，实现的价格很高。具体而言，需要在设计师和代理商之间进行货币转移，否则唯一的真实机制是独裁统治，如著名的Gibbart-Satterthwaite定理。一方面，独裁统治既不有趣，也不有用，因为结果解决方案可能对设计师的目标任意“不利”（例如，对衡量量度的近似值保证）。另一方面，虽然在某些应用程序中可能是合理的，但总的来说，对于数字货币的存在或根本没有资金的使用，几乎没有理由。在某些情况下，金钱在道德上是不可接受的（例如，支持某些政治决定）甚至是非法的（例如，在器官捐赠中）。该建议旨在重新考虑金钱作为AMD中“必要的邪恶”的作用。我们建议通过利用限制领域，近似和充分动机，放松的真实性观念来调和计算和激励措施，而无需使用货币转移。详细介绍，吉布巴特 - 简历定理证明了以下假设：代理具有不受限制的域（即，不受限制地误导算法的方法），但是许多计算机科学应用只有结构良好的域。如果我们坚持没有金钱的真实性，当代理商受到限制领域时，我们可以实现最佳的近似保证？我们的第三个杠杆作用是AMD中验证概念的新颖应用。在这种情况下，验证意味着可以发现某种代理人的某种不当行为（并受到相应的惩罚）。这个想法模仿了现实生活中的“工作检查检查”通常是常态，并且允许真实的概念放松，从而使代理商的不当行为策略不包含可验证的策略。验证的概念已在AMD中广泛使用。我们在这里询问在多大程度上可以通过验证交易资金。如果没有金钱来使用验证的真实机制的解决方案输出的近似保证有多好？我们希望在（很大程度上）（很大程度上）在此（很大程度上）探讨的中间立场上的知识与基本优化问题有关的中间立场，以及在现实生活中的许多应用，例如组合拍卖和设施的位置，以及通过将特定形式的验证形式与真实性，金钱和其他感兴趣的方式相关联。我们的研究试图建立（i）更应用AMD的基础；（ii）将游戏理论模型应用于非营利部门。