The voter basis and the admissibility of tree characters

DOI10.1007/S11083-021-09553-8MaRDI QIDQ2665833zbMATH OpenOpenAlexFDO

Authors Andrew Beveridge, Ian Calaway

Publication date 19 November 2021

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.08332

zbMATH Keywords

admissibilityHasse diagrampower setpreference orderseparabilitytotal order

Mathematics Subject Classification ID

Total orders (06A05) Voting theory (91B12) Social choice (91B14)

Abstract: When making simultaneous decisions, our preference for the outcomes on one subset can depend on the outcomes on a disjoint subset. In referendum elections, this gives rise to the separability problem, where a voter must predict the outcome of one proposal when casting their vote on another. A set $Ssubset[n]$ is separable for preference order $succeq$ when our ranking of outcomes on $S$ is independent of outcomes on its complement $[n]-S$. The admissibility problem asks which characters $mathcalCsubsetmathcalP([n])$ can arise as the collection of separable subsets for some preference order. We introduce a linear algebraic technique to construct preference orders with desired characters. Each vector in our $2^n$-dimensional voter basis induces a simple preference ordering with nice separability properties. Given any collection $mathcalCsubsetmathcalP([n])$ whose subset lattice has a tree structure, we use the voter basis to construct a preference order with character $mathcalC$.

Review text

Given a total order on the power set of a finite set $[n]$, a subset $S$ of $[n]$ is separable when for any subsets $X$, $Y$ of $S$ and any subset $Z$ of $[n]-S$, the ordering of $X$ and $Y$ is the same as the ordering of $X'$ and $Y'$, where $X'$ (or $Y'$) is the union of $X$ (or $Y$) and $Z$. The character of a total order is the collection of all its separable subsets. A collection $\mathcal{H}$ of subsets of $[n]$ is admissible when there exists a total order on the power set of $[n]$ such that the character of this total order is $\mathcal{H}$. A tree collection is a collection of subsets of $[n]$ containing the empty set and $[n]$, and such that every pair of its members is either nested or disjoint. The main result of the paper states that every tree collection is admissible. The proof is constructive; a linear algebraic technique to construct total orders on $[n]$ is introduced.

Recommendations

• Symmetry extensions of ``neutrality. II: Partial ordering of dictionaries
• Permutations of separable preference orders
• A note on the voting problem
• Preference orders on families of sets -- when can impossibility results be avoided?
• Approval voting under dichotomous preferences: a catalogue of characterizations

Cites work

• Additive representability of finite measurement structures
• Boolean term orders and the root system B_n
• Classifying interdependence in multidimensional binary preferences
• Cubic preferences and the character admissibility problem
• Finite linear qualitative probability
• Flippable pairs and subset comparisons in comparative probability orderings
• Intuitive Probability on Finite Sets
• Preseparable extensions of multidimensional preferences
• Separable discrete preferences
• The mathematics of referendum elections and separable preferences
• The Mathematics of Voting and Elections: A Hands-On Approach
• The on-line encyclopedia of integer sequences
• Voting, the symmetric group, and representation theory

Cited in

(1)

• Cubic preferences and the character admissibility problem

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The voter basis and the admissibility of tree characters

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