Regular Extensions of Half-Integral Choice Models

The Problem

Consider an election with $n$ candidates. A choice model assigns, for every subset $S$ of candidates and every candidate $i \in S$, a probability $P_i(S)$ representing the likelihood that $i$ is chosen from $S$. These probabilities must be non-negative and sum to one over each subset. A choice model satisfies regularity if enlarging the set of available alternatives never increases the probability of choosing any particular candidate, i.e. $P_i(S) \geq P_i(T)$ whenever $S \subseteq T$ and $i \in S$. Regularity is one of the weakest rationality axioms in choice theory, yet it already imposes significant structure.

A natural question arises: suppose we only observe pairwise data. That is, for each pair of candidates $i$ and $j$, we know the probability $a_{ij}$ that $i$ is chosen over $j$ (with $a_{ij} + a_{ji} = 1$). When can such a system of pairwise frequencies be extended into a full choice model over all subsets that satisfies regularity? This is the regular extension problem, and characterizing exactly when a regular extension exists remains a major open question.

The Half-Integral Case

We study the special case where every pairwise frequency is drawn from $\{0, 1/2, 1\}$. This restriction gives the problem a clean combinatorial structure. The pairwise data can be encoded as a directed graph — called the choice graph — where the presence of an arc $(i, j)$ indicates that $i$ is chosen with certainty over $j$ ($a_{ij} = 1$), and the absence of any arc between $i$ and $j$ means they are evenly matched ($a_{ij} = 1/2$). A necessary condition for a regular extension is that the pairwise frequencies satisfy the triangle inequalities ($a_{ij} + a_{jk} + a_{ki} \geq 1$). We show that in the half-integral setting, this forces the choice graph to be transitive and antisymmetric, i.e. a partially ordered set (poset). This poset structure is central to the analysis.

Given the poset, a key reduction is that for any subset $S$, the choice probabilities $P_i(S)$ depend only on the maximal elements of $S$ (those not beaten by any other member of $S$). This reduces the problem to assigning probabilities on antichains (independent sets in the poset) in a manner consistent with regularity across all subsets simultaneously.

The Hypergraph and Our Conjecture

For any antichain $S$ in the poset, we construct a hypergraph $\mathcal{H}_S$ whose vertices are the elements of $S$ and whose hyperedges capture the intersection patterns of the down-closures (lower sets) of elements above $S$ in the poset. The critical structural notion is beta-acyclicity: a hypergraph is beta-acyclic if it contains no cyclic sequence of hyperedges where consecutive edges share vertices but no vertex appears in three consecutive edges.

We conjectured that a half-integral instance admits a regular extension if and only if $\mathcal{H}_S$ is beta-acyclic for every antichain $S$. Intuitively, beta-cycles create circular constraints that make it impossible to consistently select winners: each candidate in the cycle is forced to probability zero by the structure of its neighboring hyperedges, violating the requirement that probabilities sum to one.