2019/11/01 by Filmus, Yuval, Lifshitz, Noam, Minzer, Dor +1 · 1 citation
#Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.00159
A function f\colon\0,1\n→ \0,1\ is called an approximate AND-homomorphism if choosing \bf x,\bf y∈\0,1\n randomly, we have that f(\bf x∧ \bf y) = f(\bf x)∧ f(\bf y) with probability at least 1-ε, where x∧ y = (x1∧ y1,…,xn∧ yn). We prove that if f\colon \0,1\n → \0,1\ is an approximate AND-homomorphism, then f is δ-close to either a constant function or an AND function, where δ(ε) → 0 as ε→0. This improves on a result of Nehama, who proved a similar statement in which δ 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 ε-close to satisfying judgement aggregation, then it is δ(ε)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama's result, in which δ decays polynomially with n. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation \mathrm T f = λg, where \mathrm T is the downwards noise operator \mathrm T f(x) = 𝔼\bf y[f(x ∧ \bf y)], 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 \mathrm T f and λg are close is close to an exact solution.