Mixture Selection, Mechanism Design, and Signaling
Mixture Selection, Mechanism Design, and Signaling
复制标题
混合物选择、机制设计和信号传导
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
Yu Cheng;Ho Yee Cheung;S. Dughmi;E. Emamjomeh;Lining Han;S. Teng
我们提出并研究了一个基本的算法问题，我们称之为混合选择，在许多博弈论应用中作为一个构建块出现：给定一个从n维超立方体到有界区间[-1，1]的函数g，和一个有界元素的n × rn矩阵A，最大化m维单纯形中x上的g（Ax）。当人们试图在拍卖中为销售的物品设计彩票时，或者在贝叶斯博弈中通过提供信息为代理人设计后验信念时，这个问题自然会出现。信令）。当g同时满足两个“光滑”性质：关于L∞范数的Lipschitz连续性和噪声稳定性时，我们提出了一个近似算法。后一个概念，我们定义和迎合我们的设置，控制的程度，低概率-和可能相关-错误的输入g可以影响其输出。我们的算法的近似保证优雅地退化为函数的Lipschitz连续性和噪声稳定性的g。特别地，当g是0（1）-Lipschitz连续且0（1）-稳定时，我们得到了混合选择的一个（加性）多项式时间近似格式（PTAS）.我们还表明，这两个假设本身都不足以为添加剂PTAS，这两个假设一起不足以为添加剂完全多项式时间近似方案（FPTAS）。我们将我们的混合物选择算法应用到一些不同的博弈论应用中，重点关注机制设计和最优信号的问题。特别是，我们在以前的工作中提出的一些开放问题上取得了进展，很容易将它们简化为混合选择：我们解决了Dughmi，Han和Nisan [10]提出的小菜单彩票设计问题的一个重要特例;我们解决了Emek等人[12]和Miltersen和Sheffet [5]提出的贝叶斯第二价格拍卖中的收入最大化信号问题;对Dughmi [9]提出的正规型博弈中的最优信号问题设计了一个拟多项式时间近似方案，并对Alonso和Camara [3]的投票模型中的最优信号问题设计了一个近似算法。
We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function g from the n-dimensional hypercube to the bounded interval [-1, 1], and an n × rn matrix A with bounded entries, maximize g(Ax) over x in the m-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a.k.a. signaling). We present an approximation algorithm for this problem when g simultaneously satisfies two “smoothness” properties: Lipschitz continuity with respect to the L∞ norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability - and possibly correlated - errors in the inputs of g can impact its output. The approximation guarantee of our algorithm degrades gracefully as a function of the Lipschitz continuity and noise stability of g. In particular, when g is both 0(1)-Lipschitz continuous and 0(1)-stable, we obtain an (additive) polynomial-time approximation scheme (PTAS) for mixture selection. We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive fully polynomial-time approximation scheme (FPTAS). We apply our algorithm for mixture selection to a number of different game-theoretic applications, focusing on problems from mechanism design and optimal signaling. In particular, we make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection: we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan [10]; we resolve the problem of revenue-maximizing signaling in Bayesian secondprice auctions posed by Emek et al. [12] and Miltersen and Sheffet [5]; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi [9]; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and Camara [3].