Imagine a city holding a referendum to decide two issues simultaneously: whether to build a new public swimming pool, and whether to build a water purification plant. A voter might strongly favor the swimming pool, provided the water purification plant is also built. If the purification plant fails, the pool becomes an expensive, unhygienic liability, so the voter would prefer no pool at all.
When voters face multiple related issues, voting on each issue independently can lead to severe democratic failures. This research direction explores how to model, vote on, and aggregate preferences when choices are fundamentally interdependent.
The Multiple Election Paradox
Traditional social choice theory often assumes separability—the idea that a voter's preference on one issue is independent of the outcomes of all others. As emphasized by Meir et al. (2021) and Alouf-Heffetz et al. (2022), this assumption severely limits the real-world applicability of voting systems to complex, logically or resource-linked policy environments.
When we ignore these links and force voters to vote on issues separately, we run into the multiple election paradox. Conitzer et al. (2011) demonstrate that issue-by-issue independent voting can easily result in a combination of winners that a majority of the voters completely reject. Jérôme Lang, in Lang (2007), explains that this stems from a fundamental structural flaw: independent aggregation completely fails to account for the conditional nature of individual preferences. Furthermore, trying to resolve this by letting voters iteratively change their minds can lead to unstable voting cycles, a problem that Kavner et al. (2023) show can only be mitigated by introducing uncertainty about other voters' intentions.
The core challenge is combinatorial. If an election contains $n$ binary issues, there are $2^n$ possible outcomes. Expecting voters to rank or even evaluate an exponential number of combinations is practically and computationally impossible.
Compact Representation via Conditional Preference Networks
To bypass this combinatorial explosion, researchers leverage graph-based structures to compactly represent conditional preferences. The primary tool for this is the Conditional Preference Network (CP-net).
As described by Wicker et al. (2007), CP-nets use directed graphs to formalize "all else being equal" (ceteris paribus) preferences. In a CP-net, each node represents an issue, and directed edges represent dependencies. If a voter's preference for issue $B$ depends on the outcome of issue $A$, then $A$ is a parent of $B$. The voter specifies their preference for $B$ conditionally (e.g., "If $A$ is true, I prefer $B$; if $A$ is false, I prefer not-$B$").
[Issue A: Purification Plant]
│
▼
[Issue B: Swimming Pool] (Preference depends on A)
Chen et al. (2021) demonstrate that this graphical structure allows practical preference-aggregation platforms to capture complex user choices without requiring exponential input. This graph-based approach is highly versatile; for instance, Sikdar et al. (2019) extend it to hierarchical bundle matching in housing markets using CMI-trees, while Wang et al. (2020) apply it to multi-type resource allocation to ensure fair division when items are complementary.
Decomposing the Vote: Sequential Aggregation
Why does structuring preferences as a graph help us aggregate votes? The key insight, formalized by Lang (2007), is that if voters share a common dependency structure that forms a Directed Acyclic Graph (DAG), a massive combinatorial election can be broken down into a sequence of small, local votes.
Instead of voting on everything at once, the election proceeds via a topological sort of the graph:
- Identify the "root" issues that have no parents (e.g., Issue $A$).
- Hold a standard majority vote on those root issues and finalize their outcomes.
- Move down the graph to the children (e.g., Issue $B$). Since the outcome of $A$ is now fixed, voters' conditional preferences for $B$ collapse into simple, unconditional preferences.
- Vote on $B$, and repeat until all issues are resolved.
While sequential voting makes winner determination computationally trivial, it introduces strategic vulnerabilities. Because the outcome of early votes dictates the preferences in later votes, the order of the agenda matters immensely. Conitzer et al. (2009) study this "agenda control" problem, proving that while a malicious chairperson could theoretically manipulate the final outcome by altering the voting sequence, finding the rigging sequence is fortunately NP-complete.
More fundamentally, sequential voting faces strict theoretical limits. Xia et al. (2009) prove a Dichotomy Theorem showing that for any election involving more than two binary issues, any sequential voting rule that guarantees both fairness (neutrality) and optimality (efficiency) must inevitably be a dictatorship or a trivial rule.
Conditional Approval and Structural Tractability
To circumvent the limitations of strict sequential agendas, recent work focuses on allowing voters to express conditional preferences simultaneously. Barrot et al. (2016) introduce Conditional Approval Voting, where voters submit ballots approving sets of values for a variable contingent on the states of its parent variables.
When preferences are aggregated simultaneously under these conditional models, the computational feasibility of finding a winner depends entirely on the topology of the underlying dependency graph. Markakis et al. (2021) analyze the Conditional Minisum (CMS) protocol and establish that winner determination is highly efficient if the dependency graph has a bounded treewidth—meaning the graph is structurally close to a tree without complex, tightly looping interdependencies. If the treewidth is unbounded, the problem becomes completely intractable.
Finally, this structural approach allows researchers to address representation and fairness. While classic proportional public decision models, such as those by Skowron et al. (2022), assume independent issues, Brill et al. (2023) successfully extend proportionality guarantees to interdependent domains. By leveraging dependency graphs, they show how to ensure that minority groups of voters retain a fair, proportional share of influence over the collective outcome, even when the issues being decided are deeply entangled.
Key Foundational Work
Vote and Aggregation in Combinatorial Domains with Structured Preferences (2007) — contributed 3 concept elements to this direction.
Compact Value-Function Representations for Qualitative Preferences (2004) — contributed 2 concept elements to this direction.
CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements (2004) — contributed 1 concept elements to this direction.