Sparse covers for sums of indicators

DOI10.1007/S00440-014-0582-8MaRDI QIDQ495555zbMATH OpenOpenAlexFDO

Authors Constantinos Daskalakis, Christos Papadimitriou

Publication date 14 September 2015

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmstotal variation distanceapproximate Nash equilibriaanonymous gamesPoisson binomial distributionssparse covers

Mathematics Subject Classification ID

Limit theorems in probability theory (60F99) Stochastic games, stochastic differential games (91A15)

Abstract: For all $n,epsilon>0$, we show that the set of Poisson Binomial distributions on $n$ variables admits a proper $epsilon$-cover in total variation distance of size $n^2+ncdot(1/epsilon{)}^{O(lo{g}^2(1/epsilon))}$, which can also be computed in polynomial time. We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games.

Recommendations

• A size-free CLT for Poisson multinomials and its applications
• The Fourier transform of Poisson multinomial distributions and its algorithmic applications
• Playing anonymous games using simple strategies
• Approximate Nash equilibria in anonymous games
• The cover number of a matrix and its algorithmic applications

Cites work

• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 512559 (Why is no real title available?)
• scientific article; zbMATH DE number 1089160 (Why is no real title available?)
• scientific article; zbMATH DE number 777866 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 919364 (Why is no real title available?)
• scientific article; zbMATH DE number 932631 (Why is no real title available?)
• A semigroup approach to Poisson approximation
• An Efficient PTAS for Two-Strategy Anonymous Games
• An approximation theorem for the Poisson binomial distribution
• Anonymous games with binary actions
• Approximate Nash equilibria in anonymous games
• Binomial approximation to the Poisson binomial distribution
• Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion
• Congestion games with player-specific payoff functions
• Le Cam's Inequality and Poisson Approximations
• Markov chains, Riesz transforms and Lipschitz maps
• Normal Approximation by Stein’s Method
• On oblivious PTAS's for nash equilibrium
• On the rate of Poisson convergence
• Random symmetric polynomials
• The Poisson Approximation to the Poisson Binomial Distribution
• Translated Poisson approximation for Markov chains
• Translated Poisson approximation using exchangeable pair couplings

Cited in

(8)

• The Fourier transform of Poisson multinomial distributions and its algorithmic applications
• Query complexity of approximate equilibria in anonymous games
• The Poisson binomial distribution -- old \& new
• Approximate Nash equilibria in anonymous games
• Auction design with a revenue target
• scientific article; zbMATH DE number 7307484 (Why is no real title available?)
• Query complexity of approximate equilibria in anonymous games
• A size-free CLT for Poisson multinomials and its applications

This page was built for publication: Sparse covers for sums of indicators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q495555)