Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar

There has been a recent surge of interest in algorithmic questions relating to information revelation in games and auctions. Given that equilibrium outcomes of a game are intimately related to the beliefs of its participants, how should a "market maker" with access to additional information, and equipped with a specified objective, inform players in the game? We consider the computational complexity of two of the simplest instantiations of this question: (1) A Bayesian zero-sum game  in which the principal must choose an information structure maximizing the equilibrium payoff of one of the players; (2) A single-item auction in which the seller possesses additional information regarding the item for sale, and must release, subject to a communication constraint, information regarding the item so as to maximize the resulting welfare at equilibrium. In both cases, we show that optimal signaling is computationally intractable, and in fact hard to approximate, assuming that it is hard to recover a planted dense partition in a random undirected graph. The latter hardness assumption, while non-standard, is intimately related to the densest k-subgraph problem and other  dense-subgraph-detection problems, whose hardness of approximation remains poorly understood.