Metadata only
Date
2024-03-24Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
We consider binary group decision-making under a rich model of liquid democracy recently proposed by Colley, Grandi, and Novaro (2022): agents submit ranked delegation options, where each option may be a function of multiple agents' votes; e.g., "I vote yes if a majority of my friends vote yes." Such ballots are unravelled into a profile of direct votes by selecting one entry from each ballot so as not to introduce cyclic dependencies. We study delegation via monotonic Boolean functions, and two unravelling procedures: MinSum, which minimises the sum of the ranks of the chosen entries, and its egalitarian counterpart, MinMax. We provide complete computational dichotomies: MinSum is hard to compute (and approximate) as soon as any non-trivial functions are permitted, and polynomial otherwise; for MinMax the easiness results extend to arbitrary-arity logical ORs and ANDs taken in isolation, but not beyond. For the classic model of delegating to individual agents, we give asymptotically near-tight algorithms for carrying out the two procedures and efficient algorithms for finding optimal unravellings with the highest vote count for a given alternative. These algorithms inspire novel tie-breaking rules for the setup of voting to change a status quo. We then introduce a new axiom, which can be viewed as a variant of the participation axiom, and use algorithmic techniques developed earlier in the paper to show that it is satisfied by MinSum and a lexicographic refinement of MinMax (but not MinMax itself). Show more
Publication status
publishedExternal links
Book title
AAAI-24 Technical Tracks 9Journal / series
Proceedings of the AAAI Conference on Artificial IntelligenceVolume
Pages / Article No.
Publisher
AAAIEvent
Subject
Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); FOS: Computer and information sciencesOrganisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
Related publications and datasets
Is new version of: https://doi.org/10.48550/ARXIV.2312.11932
More
Show all metadata
ETH Bibliography
yes
Altmetrics