AND Testing and Robust Judgement Aggregation

DOI10.1145/3357713.3384254MaRDI QIDQ6328333arXivFDO

Authors Yuval Filmus, Noam Lifshitz, Dor Minzer, Elchanan Mossel

Publication date 31 October 2019

Published in arXiv

Full work available at URL https://doi.org/10.1145/3357713.3384254

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DMcs.GTmath.CO

Abstract: A function $fcolon{0,1}^{n}o0,1$ is called an approximate AND-homomorphism if choosing $$ randomly, we have that $$ with probability at least $1-epsilon$, where $xlandy=(x_{1}land{y}_1,ldots,x_{n}land{y}_n)$. We prove that if $fcolon{0,1}^{n}o0,1$ is an approximate AND-homomorphism, then $f$ is $delta$-close to either a constant function or an AND function, where $delta(epsilon)o0$ as $epsilono0$. This improves on a result of Nehama, who proved a similar statement in which $delta$ depends on $n$. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if $f$ is $epsilon$-close to satisfying judgement aggregation, then it is $delta(epsilon)$-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama's result, in which $delta$ decays polynomially with $n$. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation $mathrmTf=lambdag$, where $mathrmT$ is the downwards noise operator $$, $f$ is $[0,1]$-valued, and $g$ is $0,1$-valued. We identify all exact solutions to this equation, and show that any approximate solution in which $mathrmTf$ and $lambdag$ are close is close to an exact solution.

This page was built for publication: AND Testing and Robust Judgement Aggregation

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