Bernoulli Factories and Black-box Reductions in Mechanism Design
Bernoulli Factories and Black-box Reductions in Mechanism Design
复制标题
伯努利工厂和机构设计中的黑盒简化
作者：
S. Dughmi;Jason D. Hartline;Robert D. Kleinberg;Rad Niazadeh
我们提供了一个多项式时间减少从贝叶斯激励相容机制设计贝叶斯算法设计福利最大化问题。与以前的结果不同，我们的减少实现了多维和连续型空间的问题的确切激励兼容性。在之前的黑盒约简中，阻止精确激励相容性的关键技术障碍是修复违反激励约束的行为需要理解机制输出的分布，这通常是难以计算的。通过抽样估计产出分布的约简不可避免地会受到抽样误差的影响，这通常会排除确切的激励相容性。我们克服了这一障碍，采用和推广伯努利工厂的文献中的计算模型。在伯努利工厂问题中，给出了一个将“输入硬币”的偏差映射到“输出硬币”的偏差的函数，挑战是仅在样本访问输入硬币的情况下有效地模拟输出硬币。这是设计用于二分匹配的激励相容机制的关键成分，其可用于使Hartline等人的近似激励相容约简。[18]完全激励相容。
We provide a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces. The key technical barrier preventing exact incentive compatibility in prior black-box reductions is that repairing violations of incentive constraints requires understanding the distribution of the mechanism’s output, which is typically #P-hard to compute. Reductions that instead estimate the output distribution by sampling inevitably suffer from sampling error, which typically precludes exact incentive compatibility. We overcome this barrier by employing and generalizing the computational model in the literature on Bernoulli Factories. In a Bernoulli factory problem, one is given a function mapping the bias of an “input coin” to that of an “output coin,” and the challenge is to efficiently simulate the output coin given only sample access to the input coin. This is the key ingredient in designing an incentive compatible mechanism for bipartite matching, which can be used to make the approximately incentive compatible reduction of Hartline et al. [18] exactly incentive compatible.