Events Calendar

AI SEMINAR

Speaker: Shaddin Dughmi, USC Computer Science

Talk Title: On the hardness of signaling

Series: AISeminar

Abstract: 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 ofthe 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 subgraph in a random undirected graph.



Biography: Shaddin Dughmi is an Assistant Professor in the Department of Computer Science at USC, where he is a member of the Theory Group. He received a B.S. in computer science, summa cum laude, from Cornell University in 2004, and a PhD in computer science from Stanford University in 2011. He is a recipient of the NSF CAREER award, the Arthur L. Samuel best doctoral thesis award, and the ACM EC best student paper award.

Host: Greg Ver Steeg

More Info: PER SPEAKER'S REQUEST, THIS WILL NOT BE WEBCASTED

Webcast: PER SPEAKER'S REQUEST, THIS WILL NOT BE WEBCASTED

Location: Information Science Institute (ISI) - 1135

WebCast Link: PER SPEAKER'S REQUEST, THIS WILL NOT BE WEBCASTED

Audiences: Everyone Is Invited

Contact: Alma Nava / Information Sciences Institute

Event Link: PER SPEAKER'S REQUEST, THIS WILL NOT BE WEBCASTED