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

Friday March 21, 2014 12:00 PM

On the Hardness of Signaling

Speaker: Shaddin Dughmi, Department of Computer Science, University of Southern California
Location: Baxter 127

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.

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

Contact: Jenny Niese at Ext. 6010 jenny@hss.caltech.edu