2019/05/08 by Jason Long, Adam Zsolt Wagner, Long, Jason +1
Computer Science · Economics, Econometrics and Finance · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Dynamical Systems (math.DS) #FOS: Mathematics #Game Theory and Voting Systems #math.CO #math.DS
paper · pdf · doi:10.48550/arxiv.1905.03145
9 pages
arxiv created 2019/05/08 · openalex publication_date 2019/05/08 · arxiv updated 2019/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note we study randomized voting trees, previously introduced by Fisher, Procaccia and Samorodnitsky. They speculate that a non-trivial performance guarantee may be achievable using randomized, balanced trees whose height is carefully chosen. We explore some connections to the so-called Volterra quadratic stochastic operators, and show that uniformly random voting trees cannot provide a performance guarantee that is linear in the number of individuals.