Approximate Mechanisms without Payments

机制设计关注的是协议的设计-所谓的机制-用于聚合一组人类或人工代理的偏好，这些代理可能会歪曲他们的偏好，以实现更好的结果。在这种情况下，如果每个代理人如实地透露他的偏好符合其最大利益，则该机制被称为激励相容。使激励机制兼容的一种常见技术是在代理人之间进行货币转移。然而，由于各种原因，可以进行这种支付的假设是有问题的：例如，通常不清楚如何在像互联网这样的开放系统中强制支付，并且道德或法律的考虑可能会阻止在特定情况下使用金钱。该项目的目标是研究机制的力量，牺牲最优的结果，以实现激励兼容性没有支付。更具体地说，我打算改进和扩展最近获得的机器学习问题的结果，并在算法机制设计中的中心问题（如调度或资源分配）上设计无报酬的机制。两个具体的问题，我想调查关注的阻力操纵组代理，一个属性大类的支付为基础的机制不能保证，和随机化的作用，在设计的机制没有支付。

Mechanism design is concerned with the design of protocols - so-called mechanisms - for aggregating the preferences of a group of human or artificial agents, who may misrepresent their preferences to achieve a better outcome for themselves. In this context, a mechanism is called incentive compatible if it is in the best interest of each agent to reveal his preferences truthfully. A common technique to make mechanisms incentive compatible uses monetary transfers between agents. The assumption that such payments can be made is however problematic for a variety of reasons: for example, it is often not clear how to enforce payments in open systems like the Internet, and ethical or legal considerations may prevent the use of money in specic scenarios. The goal of the proposed project is to study the power of mechanisms that sacrice optimality of the outcome in order to achieve incentive compatibility without payments. More specifically, I intend to improve and extend results recently obtained for a machine learning problem, and design mech- anisms without payments for central problems in algorithmic mechanism design, like scheduling or resource allocation. Two specific issues I want to investigate concern resistance against manipulation by groups of agents, a property large classes of payment-based mechanisms cannot guarantee, andthe role of randomization in the design of mechanisms without payments.