Abstract-Det har varit en ny ökning av intresset för informationens roll i strategiska interaktioner. Mycket av detta arbete syftar till att förstå hur den realiserade jämvikten i ett spel påverkas av osäkerhet i miljön och den information som finns tillgänglig för spelare i spelet. Att lura under denna litteratur är en grundläggande, men till stor del outforskad, algoritmisk fråga: hur ska en "marknadsskapare" som är insatt i ytterligare information, och utrustad med ett specificerat mål, informera spelarna i spelet? Detta är en informativ analog av mekanismen design frågan, och betraktar informationsstrukturen i ett spel som ett matematiskt objekt som ska utformas, snarare än en exogen variabel. Vi initierar en komplex-teoretisk undersökning av utformningen av optimala informationsstrukturer i allmänna Bayesian spel, en uppgift som ofta kallas signalering. Vi fokuserar på en av de enklaste ögonblicken i signalfrågan: Bayesian nollsummespel, och en rektor som måste välja en informationsstruktur som maximerar jämvikt payoff av en av spelarna. I denna inställning visar vi att optimal signalering är beräkningsbar, och i vissa fall svår att approximera, förutsatt att det är svårt att återställa en planterad klick från en Erdős-Rényi slumpmässig graf. Detta trots det faktum att ekvilibria i dessa spel är beräkningsbara i polynom tid, och därför tyder på att hårdheten av optimal signalering är ett distinkt fenomen från hårdheten i jämvikt beräkning. Med tanke på informationsstrukturernas icke-lokala karaktär, på vägen till våra resultat, visar vi oss vara en "förstärkande lemma" för det planterade kliqueproblemet som kan vara av oberoende intresse. Specifikt visar vi att även om vi planterar många cliques i en Erdős-Rényi slumpmässig graf, så mycket så att de flesta noder i grafen är i någon planterad clique, återställa en konstant bråkdel av planterade cliques är inte lättare än den traditionella planterade clique problem.
Daughmi REF initierar en komplex-teoretisk studie av optimal offentlig signal i de grundläggande två-spelare nollsummespel, och uppvisar hårdhet resultat.
On the Hardness of Signaling
{'venue': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'journal': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}