NDLI: On the Hardness of Signaling

Content Provider	IEEE Xplore Digital Library
Author	Dughmi, S.
Copyright Year	2014
Description	Author affiliation: Dept. of Comput. Sci., Univ. of Southern California, Los Angeles, CA, USA (Dughmi, S.)
Abstract	There has been a recent surge of interest in the role of information in strategic interactions. Much of this work seeks to understand how the realized equilibrium of a game is influenced by uncertainty in the environment and the information available to players in the game. Lurking beneath this literature is a fundamental, yet largely unexplored, algorithmic question: how should a "market maker" who is privy to additional information, and equipped with a specified objective, inform the players in the game? This is an informational analogue of the mechanism design question, and views the information structure of a game as a mathematical object to be designed, rather than an exogenous variable. We initiate a complexity-theoretic examination of the design of optimal information structures in general Bayesian games, a task often referred to as signaling. We focus on one of the simplest instantiations of the signaling question: Bayesian zero-sum games, and a principal who must choose an information structure maximizing the equilibrium payoff of one of the players. In this setting, we show that optimal signaling is computationally intractable, and in some cases hard to approximate, assuming that it is hard to recover a planted clique from an Erdos-Renyi random graph. This is despite the fact that equilibria in these games are computable in polynomial time, and therefore suggests that the hardness of optimal signaling is a distinct phenomenon from the hardness of equilibrium computation. Necessitated by the non-local nature of information structures, en-route to our results we prove an "amplification lemma" for the planted clique problem which may be of independent interest. Specifically, we show that even if we plant many cliques in an Erdos-Renyi random graph, so much so that most nodes in the graph are in some planted clique, recovering a constant fraction of the planted cliques is no easier than the traditional planted clique problem.
Sponsorship	IEEE Comput. Soc. Tech. Comm. Math. Found. Comput.
Starting Page	354
Ending Page	363
File Size	369703
Page Count	10
File Format	PDF
ISBN	9781479965175
ISSN	02725428
DOI	10.1109/FOCS.2014.45
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-10-18
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Games Game theory Bayes methods Linear programming Complexity theory Clustering algorithms Polynomials Planted Clique Mechanism Design Signaling
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Mixture Selection, Mechanism Design, and Signaling

On the Hardness of Signaling (2014)

On the complexity of succinct zero-sum games

Linear Programming Modeling for Solving Fuzzy Zero-Sum Games

On the hardness of signaling (2014)

DDoS Defense Mechanism Analysis Based on Signaling Game Model

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

On the optimality of k-means clustering

On the Hardness of Signaling

Similar Documents

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

Mixture Selection, Mechanism Design, and Signaling

On the Hardness of Signaling (2014)

On the complexity of succinct zero-sum games

Linear Programming Modeling for Solving Fuzzy Zero-Sum Games

On the hardness of signaling (2014)

DDoS Defense Mechanism Analysis Based on Signaling Game Model

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

On the optimality of k-means clustering

On the Hardness of Signaling