Sparse covers for sums of indicators

DOI10.1007/s00440-014-0582-8zbMath1334.60048arXiv1306.1265MaRDI QIDQ495555

Constantinos Daskalakis, Christos H. Papadimitriou

Publication date: 14 September 2015

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.1265

zbMATH Keywords

approximation algorithms; total variation distance; approximate Nash equilibria; anonymous games; Poisson binomial distributions; sparse covers

Mathematics Subject Classification ID

91A15: Stochastic games, stochastic differential games

60F99: Limit theorems in probability theory

Related Items

Approximate Nash equilibria in anonymous games, Learning Poisson binomial distributions, Query complexity of approximate equilibria in anonymous games, Auction Design with a Revenue Target, Query Complexity of Approximate Equilibria in Anonymous Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Binomial approximation to the Poisson binomial distribution
• Translated Poisson approximation for Markov chains
• A semigroup approach to Poisson approximation
• Random symmetric polynomials
• Markov chains, Riesz transforms and Lipschitz maps
• Anonymous games with binary actions
• Congestion games with player-specific payoff functions
• Approximate Nash equilibria in anonymous games
• Learning Poisson binomial distributions
• Translated Poisson approximation using exchangeable pair couplings
• An approximation theorem for the Poisson binomial distribution
• Binomial Approximation to the Poisson Binomial Distribution: The Krawtchouk Expansion
• The Poisson Approximation to the Poisson Binomial Distribution
• On the rate of Poisson convergence
• Normal Approximation by Stein’s Method
• Le Cam's Inequality and Poisson Approximations
• On oblivious PTAS's for nash equilibrium
• An Efficient PTAS for Two-Strategy Anonymous Games