Unravelling Expressive Delegations: Complexity and Normative Analysis

We consider binary group decision-making under a rich model of liquid democracy: 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 nontrivial 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 algorthmic techniques developed earlier in the paper to show that it is satisfied by MINSUM and a lexicographic refinement of MINMAX (but not MINMAX itself).