Sparse covers for sums of indicators

DOI10.1007/S00440-014-0582-8zbMATH Open1334.60048arXiv1306.1265OpenAlexW1969579021MaRDI QIDQ495555FDOQ495555

Authors: Constantinos Daskalakis, Christos Papadimitriou 

Publication date: 14 September 2015

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• Title not available (Why is that?)
• The Fourier transform of Poisson multinomial distributions and its algorithmic applications
• Query complexity of approximate equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• Auction design with a revenue target
• A size-free CLT for Poisson multinomials and its applications
• The Poisson binomial distribution -- old \& new
• Approximate Nash equilibria in anonymous games

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)