We study the approval-based multi-winner election problem where \(n\) voters jointly decide a committee of \(k\) winners from \(m\) candidates. We focus on the axiom average justified representation (AJR) proposed by Fernández, Elkind, Lackner, García, Arias-Fisteus, Basanta-Val, and Skowron (2017). AJR postulates that every group of voters with a common preference should be sufficiently represented in that their average satisfaction should be no less than their Hare quota. Formally, for every group of \(\lceil \ell \cdot \tfrac{n}{k} \rceil\) voters with \(\ell\) common approved candidates, the average number of approved winners for this group should be at least \(\ell\). It is well-known that a winning committee satisfying AJR is not guaranteed to exist for all multi-winner election instances. In this paper, we study the likelihood of the existence of AJR under the Erdos–Rényi model. We consider the Erdos–Rényi model parameterized by \(p \in [0,1]\) that samples multi-winner election instances from the distribution where each voter approves each candidate with probability \(p\) (and the events that voters approve candidates are independent), and we provide a clean and complete characterization of the existence of AJR committees in the case where \(m\) is a constant and \(n\) tends to infinity. We show that there are two phase transition points \(p_1\) and \(p_2\) (with \(p_1 \le p_2\)) for the parameter \(p\) such that: 1) when \(p \lt p_1\) or \(p \gt p_2\), an AJR committee exists with probability \(1 - o(1)\), 2) when \(p_1 \lt p \lt p_2\), an AJR committee exists with probability \(o(1)\), and 3) when \(p = p_1\) or \(p = p_2\), the probability that an AJR committee exists is bounded away from both \(0\) and \(1\).

We investigate majority voting where agents possess private information about an unobservable ground truth that determines their preferences. In such settings, agents may hold different preferences and (collectively) engage in counterintuitive strategic behaviors. Previous work either assumes strategic behavior occurs without coordination or with unlimited coordination, yielding overly inclusive or exclusive predictions about voting outcomes. We incorporate coordination ability—the largest coalition size at which agents could strategically coordinate—into the analysis. Under the ex-ante Bayesian k-strong equilibrium framework, where no group of at most k agents can benefit from deviation, we provide closed-form characterizations of when informed majority decisions, the decision favored by the majority if the ground truth is common knowledge, are achievable. Specifically, we determine (1) when all k-strong equilibria reach the informed majority decision and (2) when at least one such equilibrium exists. These conditions depend on three factors: coordination ability, fraction of majority agents, and information structure. The boundary for the second question exhibits surprising complexity--non-continuous, non-linear, and segmental. Our results reveal the complicated landscape and provide refined predictions for strategic behavior across different coordination levels.

We study the voting problem with two alternatives where voters' preferences depend on a not-directly-observable state variable. While equilibria in the one-round voting mechanisms lead to a good decision, they are usually hard to compute and follow. We consider the two-round voting mechanism where the first round serves as a polling stage and the winning alternative only depends on the outcome of the second round. We show that the two-round voting mechanism is a powerful tool for making collective decisions. Firstly, every (approximated) equilibrium in the two-round voting mechanisms (asymptotically) leads to the decision preferred by the majority as if the state of the world were revealed to the voters. Moreover, there exist natural equilibria in the two-round game following intuitive behaviors such as informative voting, sincere voting, and surprisingly popular strategies. This sharply contrasts with the one-round voting mechanisms in the previous literature, where no simple equilibrium is known. Finally, we show that every equilibrium in the standard one-round majority vote mechanism gives an equilibrium in the two-round mechanisms that is not more complicated. Therefore, the two-round voting mechanism provides a natural equilibrium in every instance, including those where one-round voting fails, and it can reach an informed majority decision whenever one-round voting can. Our experiments on LLM voters also imply that two-round voting leads to the correct outcome more often than one-round voting under some circumstances.

We characterize the maximum likelihood that two voting rule outcomes are different and that the winner of one voting rule is the loser of another (implying that they are {\em drastically different}) on positional scoring rules, Condorcet winner/loser, Copeland, Ranked Pairs, and STV (Single Transferable Vote) under any fixed number of alternatives. The most famous problem in this scope is strong Borda’s paradox, in which the winner of the plurality rule is the Condorcet loser. Under mild assumptions, we show that the maximum likelihood that different rules are drastically different is $\Theta(1)$ except for a few special cases, demonstrating the difference between these rules. We also prove that two scoring rules with linear independent scoring vectors have different winners with probability $\Theta(1)$, no matter how similar they are. Our analysis adopts the {\em smoothed social choice framework} \cite{xia2020smoothed} and can be applied to a variety of statistical models, including the standard impartial culture (IC).

We study the group strategic behaviors in Bayesian games. Equilibria in previous work do not consider group strategic behaviors with bounded sizes and are too ''strong'' to exist in many scenarios. We propose the ex-ante Bayesian k-strong equilibrium and the Bayesian k-strong equilibrium, where no group of at most k agents can benefit from deviation. The two solution concepts differ in how agents calculate their utilities when contemplating whether a deviation is beneficial. Intuitively, agents are more conservative in the Bayesian k-strong equilibrium than in the ex-ante Bayesian k-strong equilibrium. With our solution concepts, we study collusion in the peer prediction mechanisms, as a representative of the Bayesian games with group strategic behaviors. We characterize the thresholds of the group size k so that truthful reporting in the peer prediction mechanism is an equilibrium for each solution concept, respectively. Our solution concepts can serve as criteria to evaluate the robustness of a peer prediction mechanism against collusion. Besides the peer prediction problem, we also discuss two other potential applications of our new solution concepts, voting and Blotto games, where introducing bounded group sizes provides more fine-grained insights into the behavior of strategic agents.

We study the voting game where agents' preferences are endogenously decided by the information they receive, and they can collaborate in a group. We show that strategic voting behaviors have a positive impact on leading to the "correct" decision, outperforming the common non-strategic behavior of informative voting and sincere voting. Our results give merit to strategic voting for making good decisions.

Studying the computational complexity and designing fast algorithms for determining winners under voting rules are classical and fundamental questions in computational social choice. In this paper, we accelerate voting by leveraging quantum computation: we propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. We show that our algorithm can be quadratically faster than any classical algorithm (based on sampling with replacement) under a wide range of common voting rules, including positional scoring rules, Copeland, and single transferable voting (STV). Precisely, our quantum-accelerated voting algorithm outputs the correct winner with high probability in $\Theta\left(\frac{n}{\text{MOV}}\right)$ time, where $n$ is the number of votes and $\text{MOV}$ is margin of victory, the smallest number of voters to change the winner. In contrast, any classical voting algorithm based on sampling with replacement requires $\Omega\left(\frac{n^2}{\text{MOV}^2}\right)$ time under a large class of voting rules. Our theoretical results are supported by experiments under plurality, Borda, Copeland, and STV.