2015/12/11 by Umang Bhaskar, Bhaskar, Umang, Yu Cheng +5 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1512.03543
openalex publication_date 2015/12/11 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We study the optimization problem faced by a perfectly informed principal in\na Bayesian game, who reveals information to the players about the state of\nnature to obtain a desirable equilibrium. This signaling problem is the natural\ndesign question motivated by uncertainty in games and has attracted much recent\nattention. We present new hardness results for signaling problems in (a)\nBayesian two-player zero-sum games, and (b) Bayesian network routing games.\n For Bayesian zero-sum games, when the principal seeks to maximize the\nequilibrium utility of a player, we show that it is NP-hard to obtain an\nadditive FPTAS. Our hardness proof exploits duality and the equivalence of\nseparation and optimization in a novel way. Further, we rule out an additive\nPTAS assuming planted clique hardness, which states that no polynomial time\nalgorithm can recover a planted clique from an Erd Hos-R 'enyi random graph.\nComplementing these, we obtain a PTAS for a structured class of zero-sum games\n(where obtaining an FPTAS is still NP-hard) when the payoff matrices obey a\nLipschitz condition. Previous results ruled out an FPTAS assuming\nplanted-clique hardness, and a PTAS only for implicit games with\nquasi-polynomial-size strategy sets.\n For Bayesian network routing games, wherein the principal seeks to minimize\nthe average latency of the Nash flow, we show that it is NP-hard to obtain a\n(multiplicative) (4/3 - \ε)-approximation, even for linear latency\nfunctions. This is the optimal inapproximability result for linear latencies,\nsince we show that full revelation achieves a (4/3)-approximation for linear\nlatencies.\n