31 problems

Let $m\geq 2$, let $\rho\in[0,1]$, and let $\varepsilon>0$. For a function $f:\{1,\ldots,m\}^n\to\Delta_m$, write $\operatorname{Inf}_i(f_j)$ for the influence of coordinate $i$ on…

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a transitive-symmetric function, meaning that for every $1\leq i<j\leq n$ there is a permutation $\sigma$ of $[n]$ with $\sigma(i)=j$ such that…

Let $T=(A,\succ)$ be a tournament, and let $\operatorname{TEQ}$ denote the tournament equilibrium set. A nonempty subset $X\subseteq A$ is TEQ-retentive if…

Let $m=3$ candidates have the six possible rankings, with ranking probabilities $p_1,p_2,p_3,p_4,p_5,p_6$ satisfying $p_i\geq 0$ and $\sum_{i=1}^6p_i=1$. For $n$ voters, write…

Let $\mathcal{N}$ be the underlying set of alternatives and let $\mathrm{Sym}(\mathcal{N})$ denote its symmetric group. A completion assigns tie-breaking data to each input, and a…

Quantitative approximate polymorphism conjecture. The dependence between $\epsilon$ and $\delta$ in the Alekseev--Filmus theorem can be improved to polynomial or even linear.

Majority relation conjecture. The majority relation $\prec^{\mathrm{maj}}_{\rho}$ is the total order $<_u$, where $u$ is the product of the leftmost $p$ factors in the displayed fa…

Let $m$ labelers independently provide preferences over $n$ responses under the impartial culture condition, and consider the probability that there is no Condorcet winning respons…

Let $g$ be the function defined in Theorem, and let $k$ and $i$ be the parameters occurring there. Strict exclusion conjecture. One has … and … The paper presents this as a stronge…

The paper considers an extension of classical propositional calculus in which binary preference relations are defined over propositional formulae. Decidability conjecture. This log…

Bounded-arithmetic conjecture for Arrow's theorem. The first-order formalisation of Arrow's theorem is provable in

Let $S_k$ be the set of rankings of $k$ candidates, and let $f\colon S_k^n\to\Delta_k$ be a ranked-choice voting method, where $\Delta_k$ is the simplex of randomized outcomes on t…

Let $n$ be large, let $k\geq 3$ be the number of candidates, and let voters cast independent uniformly random votes. A voting method is balanced when each candidate has equal proba…

A ranked vote is a ranking of $k$ candidates, and a voting method assigns a winning candidate to each profile of voters' rankings. A method is fair when candidates are treated symm…

Let a preference profile on four candidates be ell-1-Euclidean if it is realizable by candidate positions and voter ideal points in the plane, with preferences determined by the el…

A social welfare order is an ordering of infinite utility streams, and the Anonymity and Weak Pareto axioms require, respectively, invariance under permutations of individuals and…

The paper considers ethical preferences over utility streams satisfying stationarity and a sensitivity (Pareto) condition known as restricted dominance. Limited discontinuity is an…

Let $S$ be a random fixed-length circular society with $n$ voters, approval set length $p$, and piercing number $\tau(S)$. For a positive integer $k$, Extended probability formula.…

Conjecture. The conclusion of Proposition can be improved by taking $F:\N^{\N}\to\N$; that is, there is such an $F$ whose range is not restricted to ${0,1}$ and which has the analo…

Degree-bound conjecture. There exist $d$-regular graphs whose associated voting rules are unbiased but not transitive-symmetric whenever

Square-root-logarithmic bound conjecture. There exist voting rules that are unbiased, totally asymmetric, and have winning coalitions of size

Let $A:= \{n \in \mathbb{N}: \text{there exists a symmetric intersecting family }\mathcal{F} \subset \mathcal{P}([n]) \text{ with } |\mathcal{F}|=2^{n-1}\}$. Equivalently, $A$ is t…

Weak characteristic-function conjecture. The results hold for any $N$ that satisfies

Fix $\epsilon>0$. For each $m$, let $\delta$ be the probability lower bound supplied by the lemma for a neutral, independent-of-irrelevant-alternatives generalized social welfare f…

Fix $\epsilon>0$. For each number $m$ of alternatives, let $\delta_m$ be a lower bound for the probability that the associated generalized social welfare function has no generalize…