Vi studerar optimeringsproblem som ställs inför en perfekt informerad rektor i ett Bayesian spel, som avslöjar information till spelarna om tillståndet i naturen för att få en önskvärd jämvikt. Detta signalerande problem är den naturliga designfrågan som motiveras av osäkerhet i spel och har tilldragit sig mycket uppmärksamhet på senare tid. Vi presenterar nya hårdhetsresultat för signalerande problem i (a) Bayesian två spelare nollsummespel, och (b) Bayesian nätverk routing spel. För Bayesian nollsum spel, när huvudmannen försöker maximera jämvikt nytta av en spelare, visar vi att det är NP-hård att få en additiv FPTAS. Våra hårdhetsprov utnyttjar dualitet och likvärdigheten av separation och optimering på ett nytt sätt. Dessutom utesluter vi en additiv PTAS som antar planterad clique hårdhet, som säger att ingen polynom tid algoritm kan återställa en planterad clique från en Erdős-Rényi slumpmässig graf. Som komplement till dessa får vi en PTAS för en strukturerad klass av nollsummespel (där erhålla en FPTAS är fortfarande NP-hård) när payoff matriser lyda en Lipschitz villkor. Tidigare resultat uteslöt en FPTAS antar planterade-clique hårdhet, och en PTAS endast för implicita spel med kvasi-polynom storlek strategi uppsättningar. För Bayesian nätverk routing spel, där huvudmannen försöker minimera den genomsnittliga latensen av Nash flödet, visar vi att det är NP-hård att få en (multiplikativ) 4 3 − -- approximation, även för linjär latency funktioner. Detta är det optimala omätbarhetsresultatet för linjär latens, eftersom vi visar att full uppenbarelse uppnår en 4 3 - approximation för linjär latens.
Bhaskar m.fl. REF presenterar snäva hårdhetsresultat för offentlig signalering i både nollsumme- och nätverksroutingspel.
Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games
{'venue': "EC '16", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}