ﻻ يوجد ملخص باللغة العربية
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 times m$ 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^infty$ norm, and noise stability. The latter notion, which we define and cater to our setting, controls the degree to which low-probability errors in the inputs of $g$ can impact its output. When $g$ is both $O(1)$-Lipschitz continuous and $O(1)$-stable, we obtain an (additive) 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 FPTAS. We apply our algorithm to different game-theoretic applications from mechanism design and optimal signaling. 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; we resolve the problem of revenue-maximizing signaling in Bayesian second-price auctions posed by Emek et al. and Miltersen and Sheffet; we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi; and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and C^{a}mara.
Game theory is often used as a tool to analyze decentralized systems and their properties, in particular, blockchains. In this note, we take the opposite view. We argue that blockchains can and should be used to implement economic mechanisms because
We study Bayesian automated mechanism design in unstructured dynamic environments, where a principal repeatedly interacts with an agent, and takes actions based on the strategic agents report of the current state of the world. Both the principal and
Optimal mechanism design enjoys a beautiful and well-developed theory, and also a number of killer applications. Rules of thumb produced by the field influence everything from how governments sell wireless spectrum licenses to how the major search en
We study online pricing algorithms for the Bayesian selection problem with production constraints and its generalization to the laminar matroid Bayesian online selection problem. Consider a firm producing (or receiving) multiple copies of different p
Selecting the most influential agent in a network has huge practical value in applications. However, in many scenarios, the graph structure can only be known from agents reports on their connections. In a self-interested setting, agents may strategic