\section{Introduction}

For centuries, it has been widely believed  that the influence of a small coalition of voters is negligible in a large election. For example, Condorcet commented in 1785, that {\em ``In single-stage elections, where there are a great many voters, each voter's influence is very small''~\citep{Condorcet1785:Essai}} (see the translation by McLean and Hewitt~\citet[pp.245]{McLean1994:Condorcet}). As another example, Hegel commented in  {\em The Philosophy of Right} in 1821, that  {\em ``the casting of a single vote is of no significance where there is a multitude of electors''} (see the translation and comments by Buchanan~\citet{Buchanan1974:Hegel}).  

Various types of influence were investigated in the literature. For example, {\em coalitional manipulation ($\cm$ for short)} refers to the phenomenon in which a coalition of voters have incentive to misreport their preferences, so that the winner is more favorable to all of them. The {\em margin of victory ($\text{\sc MoV}$ for short)} refers to the phenomenon in which a coalition of voters have the power to change the winner by voting differently, regardless of their incentives. 

Accurately measuring  the influence of voters is   highly significant and plays a central role in many other studies. A small influence can be positive news or negative news, depending on the context. For example, a small influence is desirable under various robustness measures, such as decisiveness~\citep{Gillett1977:Collective}, strategy-proofness~\citep{Gibbard73:Manipulation,Satterthwaite75:Strategy}, privacy~\citep{Liu2020:How}.   On the other hand, a  large influence is desirable in justifying the {\em voting power} of small groups of voters~\citep{Banzhaf-III1968:One-Man}, and therefore would encourage voter turnout~\citep{Downs1957:An-Economic,Riker1968:A-Theory}.  


Building a realistic model to  accurately measure the influence of voters turns out to be a highly  challenging mission.  Clearly, a sensible and informative measure  cannot be completely based on the worst-case analysis. Take coalitional manipulation with a single voter   for example:  for many voting rules, there always exists a situation where a  voter can and has incentive to change the election outcome by changing his/her vote, due to the celebrated Gibbard-Satterthwaite theorem~\citep{Gibbard73:Manipulation,Satterthwaite75:Strategy}. Similarly, unless the voting rule always chooses the same alternative as the winner, there exists a situation where a single voter is highly influential, i.e., $\text{\sc MoV}=1$.

Consequently, there is a large body of literature on understanding the influence of voters using {\em average-case} analysis, especially for  coaliational manipulation. Since the pioneering works by Pazner and Wesley~\citet{Pazner1978:Cheatproofness} and by Peleg~\citet{Peleg1979:Note} in the 1970's, much of the literature has focused on characterizing the asymptotic likelihood for randomly generated votes to be coalitional manipulable,  as the number of voters $n\rightarrow\infty$.
Previous work has established an $O(\frac{1}{\sqrt n})$ upper bound for many commonly-studied voting rules by  a coalition of constantly many manipulators, under the i.i.d.~uniform distribution over all linear orders, known as the {\em Impartial Culture (IC)} in social choice. On the other hand, the quantitative Gibbard-Satterthwaite theorems, e.g.,~\citep{Friedgut2011:A-quantitative,Mossel2015:A-quantitative}, established an $\Omega(\frac{1}{n^{67}})$ lower bound for a single manipulator under all voting rules that are constantly far away from dictatorships, under IC.


To the best of our knowledge, the only known matching lower bound is the $\Omega(\frac{1}{\sqrt n})$   bound for a single manipulator under the plurality rule~\citep{Slinko2002:Asymptotic}.  Little is known for arbitrary sizes of the coalition, other means of coalitional influence, such as margin of victory ($\text{\sc MoV}$), vote controls, and bribery~\citep{Faliszewski2016:Control}, and/or other statistical models for generating votes.  Specifically, IC has been widely criticized of being unrealistic (see, e.g.,  \citep[p.~30]{Nurmi1999:Voting}, \citep[p.~104]{Gehrlein2006:Condorcets}, and~\citep{Lehtinen2007:Unrealistic}), which means that the conclusions drawn under IC may only have limited implications in practice. See Section~\ref{sec:related-work} for more discussions. Therefore, the following  question remains largely open.

\begin{center}
{\bf How likely a coalition of voters can influence large elections under realistic models?}
\end{center}
The importance of answering this question has been widely recognized, as Pattanaik~\citet[p.187]{Pattanaik1978:Strategy} discussed for (coalitional) manipulation soon after the discovery of the Gibbard-Satterthwaite theorem:
{\em ``For, if the likelihood of such strategic voting is negligible, then one need not be unduly worried about the existence of the possibility as such.''
}




\subsection{Our Contributions}
We make three main contributions to address the question on the likelihood of coalitional influence: the main conceptual contribution is a novel and general semi-random model for generating agents' votes, the main modeling contribution is the conversion of commonly-studied coalitional influence problems to the {\em PMV-instability problems}, and the main technical contribution is a powerful theorem for solving general PMV-instability problems, which gives us  accurate characterizations of the likelihood of coalitional influence.


\myparagraph{The new semi-random model.} Our model has two parameters $(\Pi,\psi)$, where $\Pi$ is a set of distributions over all rankings over  $m$ alternatives and $\psi\in [0,1]$, and two adversaries: the {\em distribution adversary} and the {\em data adversary}. In our model, the collection of votes for $n$ agents, called a {\em profile}, is generated in the following three steps:   first,  the distribution adversary  chooses a (worst-case) distribution for each agent, whose collection is denoted by $\vec \pi\in \Pi^n$; then, agents' {\em preliminary profile}  $P$ is generated  from $\vec\pi$ independently; finally, the data adversary modifies $P$ up to $\psi n$ votes to obtain a profile $P'$, denoted by $P' \overset\psi\sim P$.

Given a voting rule $r$,  a budget $B\ge 0$, and a profile $P$, an influence problem is modeled by a binary function $\sat{X}(r,P,B)$. That is,  $\sat{X}(r,P,B)=1$ if there exits a group of no more than $B$ voters who are influential; otherwise $\sat{X}(r,P,B)=0$. Take coalitional manipulation for example, where  $X = \cm$. $\cm(r,P,B)=1$ if and only if there exist a coalition of no more than $B$ voters who have incentive to misreport their preferences to improve the winner. 

Given $\Pi$ and $\psi\in [0,1]$, the {\em max-semi-random likelihood} of $X$ under $r$ with $n$ agents and budget $B$, denoted by $\satmax{X}{\Pi,\psi}(r,n,B)$,  is defined as:
\begin{equation}
\label{dfn:max-s-sat}
\satmax{X}{\Pi,\psi}(r,n,B) \triangleq  \underbrace{\sup\nolimits_{\vec\pi\in\Pi^n}}_{\begin{subarray}{l} \text{distribution}\\ \text{adversary}\end{subarray}}\underbrace{\Pr\nolimits_{P\sim\vec\pi}}_{\begin{subarray}{l} \text{preliminary}\\ \text{profile}\end{subarray}}(\underbrace{\exists P'\overset \psi\sim P}_{\begin{subarray}{l} \text{data adversary}\end{subarray}}\text{ s.t. }\underbrace{\sat{X}(r,P,B)=1}_{\text{influential}}),
\end{equation}
where $P' \overset\psi\sim P$ means that $P'$  can be obtained from $P$ by modifying no more than $\psi n$ votes. 




\myparagraph{The PMV-instability problem.}  We show in Section~\ref{sec:model} that many coalitional influence problems, including $\cm$ and $\text{\sc MoV}$, under commonly studied voting rules can be solved by analyzing the positions of the histogram of the profile w.r.t.~certain polyhedra. In our semi-random model, after the distribution adversary  choses the distributions, the histogram of the random  profile   is a {\em Poisson multivariate variable (PMV)}, whose general version is  defined as follows.
\begin{dfn}[{\bf Poisson multivariate variable (PMV)}{}]
Given $n,q\in\mathbb N$ and a vector $\vec \pi=(\pi_1,\ldots,\pi_n)$ of $n$ distributions over  $\{1,\ldots,q\}$, an $(n,q)$-PMV is denoted by ${\vec X}_{\vec\pi}$, which represents the histogram of $n$ independent random variables whose distributions are $\{\pi_1,\ldots,\pi_n\}$, respectively.
\end{dfn}
We model the goal of influence  as a {\em PMV-instability setting}, where we are given a {\em source} polyhedron $\cpoly{\text{S}}$, a {\em target} polyhedron $\cpoly{\text{T}}$, a set of {\em vote operations} $\voset{}\subseteq \mathbb R^q$, each of which represents a type of  changes to the histogram by the influencers, and a cost vector $\vec c$ for the vote operations in $\voset{}$.  Then, the semi-random likelihood of many coalitional influence problems under commonly-studied voting rules can be modeled as {\em PMV-instability problems} (Definition~\ref{dfn:PMV-instability-problem}), where we are additionally given  $n$ and $B$, and we are interested in the semi-random likelihood for  a PMV to be {\em unstable}, in the sense that the data adversary can change the PMV to be in a set $\csus{n,B}$, which is the subset of $\cpoly{\text{S}}$ whose members can further be made into $\cpoly{\text{T}}$ by performing vote operations in  $\voset{}$ under budget constraint $B$. More precisely, we are interested in characterizing 
$$\sup\nolimits_{\vec\pi\in\Pi^n}\Pr\left(\exists \vec x \overset\psi\sim {\vec X}_{\vec\pi}\text{ s.t. }\vec x \in \csus{n,B}\right) $$


\myparagraph{Characterizing the semi-random likelihood.} We prove the following characterization of the PMV-instability problem, which is our main technical contribution.

\appThm{\boldmath Semi-random instability of PMV for $\psi =0$, informally put}{thm:PMV-instability} {
For any PMV-instability problem, a large class of $\Pi$, any $n\in\mathbb N$, and any $B\ge 0$, the solution to the  PMV-instability problem  falls into one of the following four cases:
$$0,  \exp(-\Theta(n)) ,\text{phase transition at $\Theta(\sqrt n)$, and phase transition at $\Theta(n)$}$$ 
}
In the phase-transition-at-$\Theta(\sqrt n)$ case, the  likelihood increases to its maximum $\text{poly}^{-1}(n)$ before $B=\Theta(\sqrt n)$. In the phase-transition-at-$\Theta( n)$ case, the  likelihood increases from $\exp(-\Theta(n))$ to its maximum $\text{poly}^{-1}(n)$ around $B=\Theta(n)$.  The formal statement of Theorem~\ref{thm:PMV-instability} also characterizes  conditions and asymptotically tight bounds for the four cases. The  $\psi>0$ case is addressed by Theorem~\ref{thm:PMV-instability-psi>0} in Appendix~\ref{sec:psi>0}.

\myparagraph{Applications.} Theorem~\ref{thm:PMV-instability}  and Theorem~\ref{thm:PMV-instability-psi>0}  can be easily applied to accurately bound the semi-random likelihood of coalitional influence in a wide range of settings of interest to resolve  long-standing open questions. In this paper, we present three examples.  

{\bf First,} in Theorem~\ref{thm:PMV-instability-applications} we  prove that for $\cm$ and $\text{\sc MoV}$, many commonly studied voting rules $r$, a large class of $\Pi$ including IC, any coalition size $B\ge 1$, and any sufficiently large $n$, 
$$\satmax{X}{\Pi,0}(r,n,B) =  \Theta\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right)$$
A straightforward application of  Theorem~\ref{thm:PMV-instability-applications} to $\cm$ under IC (Corollary~\ref{coro:IC}) not only closes the $\left(\Omega(\frac{1}{n^{-67}}), O(\frac{1}{\sqrt n})\right)$ gap for these rules with $B=1$ in previous work,  but also provides asymptotically tight bounds on the likelihood of $\cm$ for every $B\ge 1$: roughly speaking, each additional manipulator (up to $O(\sqrt n)$) increases the likelihood of success by $\Theta(\frac{1}{\sqrt n})$ under IC. 

{\bf Second,} in Theorem~\ref{thm:PMV-instability-GSR-upper} we prove  an $O\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right)$ upper bound on the likelihood of many types of coalitional influence, including $\cm$ and $\text{\sc MoV}$, for all {\em generalized scoring rules (GSRs)}~\citep{Xia08:Generalized}, which includes all voting rules mentioned in this paper. This supersedes all previous upper bounds we are aware of  and extends them to arbitrary $B\ge 1$ and a more general (semi-random) model.

{\bf Third,} we propose and investigate a new  coalitional influence problem called {\em coalitional manipulation for the loser}, denoted by $\cml$, which requires that a coalition of voters are incentivized to misreport their preferences in order to make the loser win. We prove in Theorem~\ref{thm:CML}, that for any integer positional scoring rules with $m\ge 3$ (except veto), any $\Pi$ from a large class, and any sufficiently large $n$ and $B$, 
$$\satmax{\cml}{\Pi,0}(r_{\vec s} ,n,B) =  \Theta\left(\min\left\{\frac{B}{\sqrt n},1\right\}^{m-1}\right) $$
While $\cml$ may be of independent interest, the main purpose of this theorem is to illustrate that the likelihood of coalitional influence can be much smaller than $\Theta(\frac{B}{\sqrt n})$ or even $\Omega(\frac{1}{n^{-67}})$, can be non-linear in $B$, the degree of polynomial can depend on $m$, and each additional budget is marginally more powerful.  We are not aware of a similar phenomenon in the literature.
 

\section{Preliminaries and Our Semi-Random Model}
\label{sec:prelim}
For any  $q\in\mathbb N$,  let $[q]=\{1,\ldots,q\}$. Let $\mathcal A=[m]$ denote a set of $m\ge 3$ {\em alternatives}. Let $\mathcal L(\mathcal A)$ denote the set of all linear orders over $\mathcal A$. Let $n\in\mathbb N$ denote the number of agents (voters). Each agent uses a linear order $R\in\mathcal L(\mathcal A)$ to represent his or her preferences, called a {\em vote}, where $a\succ_R b$ or $\{a\}\succ_R\{b\}$ means that the agent prefers alternative $a$ to alternative $b$. The vector of $n$ agents' votes, denoted by $P$, is called a {\em (preference) profile}, sometimes called an $n$-profile. The set of $n$-profiles for all $n\in\mathbb N$ is denoted by $\mathcal L(\mathcal A)^* = \bigcup_{n =1}^{\infty} \mathcal L(\mathcal A)^n$.  A {\em fractional} profile is a   profile $P$ coupled with a possibly non-integer and/or negative weight vector $\vec \omega_P=(\omega_R:R\in P)\in{\mathbb R}^{n}$ for the votes in $P$.
Sometimes  the weight vector is omitted when it is clear from the context. 

For any (fractional) profile $P$, let $\text{Hist}(P)\in {\mathbb R}_{\ge 0}^{m!}$ denote the anonymized profile of $P$, also called the {\em histogram} of $P$, which contains the total weight of every  linear order in $\mathcal L(\mathcal A)$ according to $P$.  An {\em irresolute voting rule} $\cor:\mathcal L(\mathcal A)^*\rightarrow (2^{\mathcal A}\setminus \{\emptyset\})$ maps a profile to a non-empty set of winners in $\mathcal A$. A {\em resolute} voting rule $r$ is a special irresolute voting rule that always chooses a single alternative as the (unique) winner. Often a resolute rule is obtained from an irresolute rule by applying a {\em tie-breaking mechanism}, e.g., lexicographic tie-breaking, which chooses the co-winner with the smallest index as the unique winner.   
 

\vspace{2mm}\noindent{\bf Integer positional scoring rules.}  An {\em (integer) positional scoring rule}  $\cor_{\vec s}$  is  characterized by an integer scoring vector $\vec s=(s_1,\ldots,s_m)\in{\mathbb Z}^m$ with $s_1\ge s_2\ge \cdots\ge s_m$ and $s_1>s_m$. For any alternative $a$ and any linear order $R\in\mathcal L(\mathcal A)$, we let  $\vec s(R,a)=s_i$, where $i$ is the rank of $a$ in $R$.  Commonly studied integer positional scoring rules include  {\em plurality}, which uses the scoring vector $(1,0,\ldots,0)$, {\em Borda}, which uses the scoring vector $(m-1,m-2,\ldots,0)$, and {\em veto}, which uses the scoring vector $(1,\ldots,1,0)$.

We recall the definition of {\em generalized scoring rules (GSRs)}~\citep{Xia08:Generalized} based on separating hyperplanes~\citep{Xia09:Finite,Mossel13:Smooth} as follows. 





\begin{dfn} 
\label{dfn:GISR} A {\em generalized scoring rule (GSR)} $r$ is defined by (1) a set of $K\ge 1$ hyperplanes ${\vec H} = (\vec h_1,\ldots,\vec h_K)\in ({\mathbb R}^{m!})^K$ and (2) a function $g:\{+,-,0\}^K\rightarrow \mathcal A$. For any  profile $P$, we let $r(P) = g(\text{Sign}_{\vec H}(\text{Hist}(P)))$, where 
$\text{Sign}_{\vec H}(\vec x) = (\text{Sign}(\vec h_1\cdot \vec x),\ldots, \text{Sign}( \vec h_K\cdot \vec x))$ represents the signs of $ \vec h_1\cdot \vec x,\ldots,  \vec h_K\cdot \vec x$.    When ${{\vec H}}\in ({\mathbb Z}^{m!})^K$,  $r$ is called an {\em integer GSR (int-GSR)}.  
\end{dfn}

\begin{ex}[{\bf\boldmath Borda as a  GSR}{}]
\label{ex:borda-GSR}
Let $m=3$. Borda with lexicographic tie-breaking is  a GSR with $K=m$ and $\vec H = \{\vec h_1,\vec h_2,\vec h_3\}$  defined as follows. 
\begin{center}
\begin{tabular}{rrrrrrrrl}
& & $x_{123}$ & $x_{132}$ & $x_{213}$ & $x_{231}$ & $x_{312}$ & $x_{321}$ \\
$\vec h_1= $ & $($ & $1,$& $2,$& $-1,$& $-2,$& $1,$& $-1$& $)$\\
$\vec h_2= $ & $($ & $2,$& $1,$& $1,$& $-1,$& $-1,$& $-2$& $)$\\
$\vec h_3= $ & $($ & $1,$& $-1,$& $2,$& $1,$& $-2,$& $-1$& $)$\\
\end{tabular}
\end{center}
Let $\vec x = (x_{123},x_{132},x_{213},x_{231},x_{312},x_{321})$ denote the histogram of a profile, where $x_{123}$ represents the number of $[1\succ 2\succ 3]$ votes. It follows that $\vec h_1\cdot \vec x$ is the  Borda score of alternative $1$ minus the  Borda score of $2$ in the profile; $\vec h_2\cdot \vec x$ is the  Borda score of alternative $1$ minus the  Borda score of $3$ in the profile; and $\vec h_3\cdot \vec x$ is the  Borda score of alternative $2$ minus the  Borda score of $3$ in the profile. The $g$ function chooses the winner based on $\text{Sign}_{\vH}(\text{Hist}(P))$ and the tie-breaking mechanism.\end{ex}




\vspace{2mm}\noindent{\bf Coalitional influence problems.}  Let $r$ be a resolute rule, $P$ be a preference profile, and $B\ge 0$ be a  budget. {\em Coalitional manipulation}  ($\cm$)  is defined by a binary function $\cm(r,P,B)$ such that $\cm(r,P,B)=1$ if and only there exists $P'\subseteq P$ with $|P'|\le B$ and $P^*$ with $|P^*|=|P'|$,  such that for all $R\in P'$, $r(P-P'+P^*)\succ_R r(P)$. The {\em margin of victory} ($\text{\sc MoV}$) is a function $\text{\sc MoV}(r,P,B)$ such that $\text{\sc MoV}(r,P,B)=1$ if and only if no more than $B$ voters can coalitionally change the winner (regardless of their preferences and incentives). 




\vspace{2mm}\noindent{\bf Semi-random likelihood of coalitional influence.}  As discussed in the Introduction, given a coalitional influence problem $X$, a set $\Pi$ of distributions over $\mathcal L(\mathcal A)$, $\psi\in [0,1]$, a voting rule $r$, a number of voters $n\in\mathbb N$, and a budget constraint $B\ge 0$, the {\em max-semi-random likelihood of $X$} ({\em max-semi-random $X$} for short), denoted by $\satmax{X}{\Pi,\psi}(r,n, B)$, is defined in Equation~(\ref{dfn:max-s-sat}).

In the main text we focus on presenting max-semi-random likelihood of $\cm$ for Borda, where $\psi=0$.  See Appendix~\ref{app:more-rule} for definitions of some other commonly studied voting rules (which are GSRs), i.e., ranked pairs, Schulze, maximin, Copeland, and STV, and  Appendix~\ref{app:more-CI}  for the definitions of  some other commonly-studied coalitional manipulation problems, i.e., constructive/destructive control by adding/deleting votes and bribery. Many results in the main text apply to these rules and coalitional influence problems, as stated in their full versions in the Appendix.

\vspace{2mm}\noindent{\bf \boldmath Assumptions on $\Pi$.} Throughout the paper, we make the following two assumptions on $\Pi$: (1) {\em strict positiveness}, which means that there exists a constant $\epsilon>0$ such that the probabilities over all rankings in all $\pi\in\Pi$ are larger than $\epsilon$, and (2) {\em closedness}, which means that $\Pi$ is a closed set in the Euclidean space.  

Clearly, IC corresponds to $\Pi = \{{\pi}_{\text{uni}}\}$, where ${\pi}_{\text{uni}}$ is the uniform distribution over $\mathcal L(\mathcal A)$. Let us take a look at another example of $\Pi$ and its corresponding semi-random likelihood.

\begin{ex}[{\bf\boldmath Semi-random $\cm$ under Borda}{}]
\label{ex:sCM-Borda}
Let $X=\cm$ and $r=\text{Borda}$ with lexicographic tie-breaking. Let $\mathcal A = \{1,2,3\}$ and  $\Pi = \{\pi^1,\pi^2\}$, where $\pi^1$ and $\pi^2$ are distributions in Table~\ref{tab:sCM-Borda}.\\
\begin{minipage}[t][][b]{0.42\textwidth}
When $n=2$ and $B=1$, we have $\satmax{\cm}{\Pi,0}(\text{Borda},2,1) = \sup\nolimits_{\vec\pi\in\{\pi^1,\pi^2\}^n}\Pr\nolimits_{P\sim\vec\pi}\sat{\cm}(\text{Borda},P)$. That is, the adversary has four choices of $\vec \pi$, i.e., $\{(\pi^1,\pi^1),(\pi^1,\pi^2),(\pi^2,\pi^1),(\pi^2,\pi^2)\}$. 
\end{minipage}
\hfill
\begin{minipage}[t][][b]{0.5\textwidth}
\centering
\begin{tabular}{|@{\ }c@{\ }|c|c|c|c|c|c|c| }
\hline & \small $123$& \small $132$& \small $231$& \small $321$& \small $213$& \small $312$ \\

\hline $\pi^1$& $1/4$& $1/4$&$1/4$& $1/12$& $1/12$&$1/12$  \\

\hline $\pi^2$& $1/12$& $1/12$&$1/12$ & $1/4$& $1/4$&$1/4$ \\

\hline
\end{tabular} 
\captionof{table}{\small $\Pi$ in Example~\ref{ex:sCM-Borda}.\label{tab:sCM-Borda}}
\end{minipage}

Each $\vec\pi$ leads to a distribution over the set of all  profiles of two agents, i.e., $\mathcal L(\mathcal A)^2$.  As we will see later in Example~\ref{ex:thm-Borda-CM}, for every sufficiently large $n$,  $\satmax{\cm}{\Pi,0}(\text{Borda},n,1)= \Theta(\frac{1}{\sqrt n })$.  
\end{ex}

 

\section{Coalitional Influence Problems as PMV-Instability Problems}
\label{sec:model}
We start with an example of modeling $\cm$ with $\psi = 0$ as  systems of linear inequalities, which motivates the study of the more general {\em PMV-instability problem} (Definition~\ref{dfn:PMV-instability-problem}).
\begin{ex}
\label{ex:illustration}  
Let $\mathcal A = \{1,2,3\}$ and let $r$ be  Borda  with lexicographic tie-breaking.  Let $\csus{n,B}^{1\ra2}$ denote the histograms of all $n$-profiles  that satisfy the following conditions: (1) the winner before manipulation is $1$, (2) a coalition of no more than $B$ manipulators are motivated to change the winner to $2$ by casting different votes.
Let  $o_1$ (respectively, $o_2$) denote the number of voters who change their votes from $[2\succ 1\succ 3]$ (respectively, $[3\succ 2\succ 1]$) to $[2\succ 3\succ 1]$.  

Then, the histogram $\vec x$ of an $n$-profile is in $ \csus{n,B}^{1\ra2}$  if and only if there exists an integer vector $\vec o = (o_1,o_2)$ such that $(\vec x,\vec o\,)$ is a feasible solution to the following linear program, where the objective is omitted because  only the feasibility matters. 
\begin{align*}
\left.\begin{tabular}{r@{\ }r} $-x_{123}-2 x_{132} + x_{213}+2 x_{231} -  x_{312} + x_{321} \le $ &\phantom{$-$}$ 0$ \\
 $-2x_{123}- x_{132} - x_{213}+ x_{231} + x_{312}  + 2 x_{321} \le $ &$ 0$  \\
  $-\vec x \le $ &$ 0 $
\end{tabular}\right\} & \begin{tabular}{l} \text{1 wins before} \\ \text{manipulation}\end{tabular}\\
\left.\begin{tabular}{r@{\ }r}  
 $x_{123}+2 x_{132} - (x_{213}-o_1) - 2 (x_{231}+o_1+o_2) + x_{312} - (x_{321}-o_2) \le $ &$-1$ \\
 $-x_{123}+ x_{132} - 2(x_{213}-o_1) -  (x_{231}+o_1+o_2) + 2x_{312} +(x_{321}-o_2) \le $ &$ 0$\\
  $- o_1 \le 0$, $-o_2\le 0$,  $- (x_{213}-o_1) \le 0$, $- (x_{321}-o_2) \le 0$,
 $ o_1 + o_2 \le $ &$B$ 
\end{tabular}\right\}& \begin{tabular}{l} \text{2 wins after} \\ \text{manipulation}\end{tabular} 
\end{align*}
\end{ex}


 In Example~\ref{ex:illustration}, the effect of each manipulator can be modeled by its changes to the histogram, and the manipulators aim at manipulating  vectors in a {\em source} polyhedron, which represents $1$ being the winner, into a {\em target} polyhedron, which represents $2$ being the winner, under the budget constraint $B$.  This motivates us to define the general {\em PMV-instability setting} as follows.

 \begin{dfn}[{\bf \boldmath PMV-instability setting}{}]
In a {\em PMV-instability setting} ${\cal S}{}\triangleq\langle\cpoly{\text{S}}, \cpoly{\text{T}}, \voset{}, \vec c\,\rangle$,   

$\bullet$ $\cpoly{\text{S}}$ and $\cpoly{\text{T}}$ are polyhedra in $\mathbb R^{q}$ for some $q\in\mathbb N$, the subscript S and T represent ``source'' and  ``target'', respectively. For $Y\in \{\text{S},\text{T} \,\}$, let
 $\cpoly{Y} \triangleq \left\{\vec x\in {\mathbb R}^q: {\mathbf A}_Y \times\invert{\vec x}\le \invert{{{\mathbf b}}_Y}\right\},$ 
where ${\mathbf A}_{Y}$ is an integer matrix of $q$ columns; 

$\bullet$ $\voset{}\subseteq {\mathbb R}^{q}$ is a finite set of {\em vote operations}, and let $\vomatrix{}$ denote the $|\voset{}|\times q$ matrix whose rows are the vectors in $\voset{}$; 

$\bullet$ $\vec c \in \mathbb R_{\ge 0}^{|\voset{}|}$  is the cost vector for the vote operations in $\voset{}$.
\end{dfn} 
W.l.o.g.,  we assume  $\vec c>\vec 0$  and  the minimum cost of a single operation is $1$, i.e., $\min_{i\le q}[\vec c\,]_i = 1$. Given a PMV-instability setting ${\cal S}{}$, $n\in\mathbb N$, and a budget $B \ge 0$, we  let $\csus{n,B}$ denote the set of non-negative size-$n$ integer vectors that represent {\em unstable} histograms w.r.t.~vote operations in $\voset{}$ and budget $B$. That is,
$$\csus{n,B} \triangleq \left\{\underbrace{\vec x\in  \cpoly{\text{S}}\cap {\mathbb Z}_{\ge 0}^q}_{\vec x\text{ is in }\cpoly{\text{S}}}: 
\underbrace{\vec x\cdot \vec 1 = n}_{n\text{-profile}}\text{ and }\exists \underbrace{\vec o\in {\mathbb Z}_{\ge 0}^{|\voset{}|}}_{\text{vote operations}}\text{ s.t. }\underbrace{\vec c\cdot\vec o \le B}_{\text{budget constraint}} \text{ and }\underbrace{\vec x+ \vec o\times \vomatrix{}\in\cpoly{\text{T}}}_{\text{manipulated to be in }\cpoly{\text{T}}}\right\}$$

 
\begin{ex
\label{ex:influence-model}
In the setting of Example~\ref{ex:illustration}, $q=m!=6$.  $\csus{n,B}^{1\rightarrow 2}$ is the set of unstable histograms of the PMV-instability setting where $\cpoly{\text{S}}$ (respective, $\cpoly{\text{T}}$) is the polyhedron that represents $1$ (respectively, $2$) being the winner, $\voset{} = \{(0,0,-1,1,0,0), (0,0,0,1,0,-1)\}$ (the indices to rankings are the same as in Example~\ref{ex:borda-GSR}), $\vomatrix{} = \left[\begin{tabular}{@{}r@{, }r@{, }r@{, }r@{, }r@{, }r@{}}0 & 0& -1& 1& 0& 0\\ 0 & 0& 0& 1& 0& -1\end{tabular}\right]$, $\vec c = (1,1)$.
\end{ex}

Notice that Examples~\ref{ex:illustration} and~\ref{ex:influence-model} only capture the   situations where alternative $1$ is manipulated to alternative $2$. Similarly, we can define $\csus{n,B}^{1\rightarrow 3}$, $\csus{n,B}^{2\rightarrow 1}$, $\csus{n,B}^{2\rightarrow 3}$, $\csus{n,B}^{3\rightarrow 1}$, and $\csus{n,B}^{3\rightarrow 2}$. Let $\mathcal M$ denote the set of the six PMV-instability settings, and define 
$$\csus{n,B}^\mathcal M \triangleq \csus{n,B}^{1\rightarrow 2}\cup \csus{n,B}^{1\rightarrow 3}\cup\csus{n,B}^{2\rightarrow 1}\cup\csus{n,B}^{2\rightarrow 3}\cup\csus{n,B}^{3\rightarrow 1}\cup\csus{n,B}^{3\rightarrow 2}$$
It follows that
\begin{equation}
\label{eq:CM-Borda}
\satmax{\cm}{\Pi,0}(\text{Borda}, n, B) =\sup\nolimits_{\vec\pi\in\Pi^n}\Pr\left(  {\vec X}_{\vec\pi}  \in  \csus{n,B}^\mathcal M\right)
\end{equation}
It turns out that many other coalitional influence problems  can be modeled by the union of multiple PMV-instability settings (formally called the {\em PMV-multi-instability setting} in Definition~\ref{dfn:PMV-multi-instability-setting} in Appendix) as proved in the following lemma. 
\begin{lem}[\bf Coalitional Influence  as PMV-instability]
\label{lem:CI-GSR}
For any  $X\in\{\cm,\text{\sc MoV}\}$ and any GSR $r$, there exist multiple PMV-instability settings  $\mathcal M = \{{\cal S}^i:  i\le I\}$   such that for every $n$-profile $P$ and every $B\ge 0$, $\sat{X}(r,P,B) =1$ if and only if $\text{Hist}(P)\in \csus{n,B}^\mathcal M$.
\end{lem}
The full statement  of the lemma (which covers other coalitional influence problems) and its proof can be found in Appendix~\ref{app:proof-prop-CI-GSR}.  In light of \eqref{eq:CM-Borda} and Lemma~\ref{lem:CI-GSR}, we propose the {\em PMV-instability  problem}  as follows. 
\begin{dfn}[{\bf\boldmath  PMV-instability problem}{}]
\label{dfn:PMV-instability-problem}
Given a PMV-instability setting ${\cal S}{}=\langle\cpoly{\text{S}}, \cpoly{\text{T}}, \voset{}, \vec c\,\rangle$,  a set $\Pi$ of distributions over $[q]$, $\psi\in[0,1]$, $n\in\mathbb N$, and $B\ge 0$, we are interested in characterizing
\begin{align*}
&\text{\bf  max-semi-random   instability: }\sup\nolimits_{\vec\pi\in\Pi^n}\Pr\left(\exists \vec x \overset\psi\sim {\vec X}_{\vec\pi}\text{ s.t. }\vec x \in \csus{n,B}\right) 
\end{align*}
\end{dfn}
That is, the max-semi-random instability  is the upper bound  on the probability for the PMV to be unstable after the data adversary makes up to $\psi$ fraction of changes, when the underlying probabilities $\vec\pi$ are adversarially chosen from $\Pi^n$. Notice that when $\vec x,\vec x'\in \mathbb R_{\ge 0}^q$, $\vec x \overset\psi\sim \vec x'$ holds if and only if $|\vec x|_{1} = |\vec x'|_{1}$ and $|\vec x - \vec x'|_{1}\le 2\psi |\vec x'|_1$.






 




 

\section{Solving The PMV-Instability Problem}
\label{sec:PMV-instability}
Let us start with some high-level intuitions   for solving the PMV-instability problem  to motivate the statement and proof of Theorem~\ref{thm:PMV-instability}. We will focus on the $\psi=0$ case in this section for the purpose of clarity, which means that we will focus on characterizing  $\sup_{\vec\pi\in\Pi^n}\Pr({\vec X}_{\vec\pi}\in \csus{n,B})$. The study of the $\psi\in (0,1]$ case can be found in Appendix~\ref{sec:psi>0}.

\vspace{2mm}\noindent{\bf Intuitions.} If $\csus{n,B}=\emptyset$, then the max-semi-random   instability is $0$, and we will refer to this   as the {\bf \boldmath $0$ case}. Suppose the $0$ case does not hold, i.e., $\csus{n,B}\ne \emptyset$, then we will adopt an approximation of $\Pr({\vec X}_{\vec\pi}\in \csus{n,B})$ based on the following two  approximations. 
\begin{itemize}
\item First,  let us {\em pretend} that all integrality constraints in the linear system (like the one in Example~\ref{ex:illustration}) are relaxed. That is, let us pretend that  ${\vec X}_{\vec\pi}$ can take non-integer values, and the vote operation vector $\vec o$ can be fractional (but still need to be non-negative). For simplicity, assume that $\vec c = \vec 1$. Then, the possible changes to the histogram as the result of  a unit of budget is characterized by $\text{\rm CH}(\voset{})$, where $\text{\rm CH}(\cdot)$ represents the convex hull. It follows that $\csus{n,B}$ can be approximated by a polyhedron $\cpoly{B}$, which is  the intersection of $\cpoly{\text{S}}$ and the Minkowski addition of $\cpoly{\text{T}}$ and $\bigcup_{0\le b\le B}-b\cdot \text{\rm CH}(\voset{})$.  See Figure~\ref{fig:illustration-PMV} (a) for an illustration of $\cpoly{B}$ in the shaded area, where $\voset{} = \{\vec o_1,\vec o_2\}$. Notice that $\cpoly{B}$ is in the $-\text{\rm CH}(\voset{})$ direction  of $\cpoly{\text{T}}$.

\item Second,  let us  {\em pretend}  that ${\vec X}_{\vec\pi}$ is distributed as a $(q-1)$-dimensional Gaussian distribution $\mathcal N_{\vec\pi}$ (whose mean is $\sum_{j=1}^n\pi_j\in n\cdot\text{\rm CH}(\Pi)$) in the hyperplane $\{\vec x:\vec x\cdot \vec 1 = n\}$.  This approximation is justified by various multi-variable central limit theorems, e.g.,~\citep{Bentkus2005:A-Lyapunov-type,Valiant2011:Estimating,Daskalakis2016:A-Size-Free,Diakonikolas2016:The-fourier,Raic2019:A-multivariate}. 
\end{itemize}
With these  approximations, we adopt the following approximation of $\Pr({\vec X}_{\vec\pi}\in \csus{n,B})$:
\begin{equation}\label{eq:approximation-intuition}
\Pr({\vec X}_{\vec\pi}\in \csus{n,B})\approx\Pr(\mathcal N_{\vec\pi}\in \cpoly{B})
\end{equation}
\begin{figure}[htp]
\centering
\begin{tabular}{cc}
\includegraphics[width = 0.5\textwidth]{fig/PMV-problem.pdf} & \includegraphics[width = 0.5\textwidth]{fig/PMV-B.pdf}\\
(a) $\cpoly{B}$. & (b) $B_{\text{\rm CH}(\Pi)}$ and $\sus{B_{\text{\rm CH}(\Pi)}}$.
\end{tabular}
\caption{Illustration  of  notation.\label{fig:illustration-PMV}}
\end{figure}
Now, let us take a look at the max-semi-random PMV instability in light of the approximation in \eqref{eq:approximation-intuition}. Because the probability mass of $\mathcal N_{\vec\pi}$ is mostly centered around an $O(\sqrt n)$ neighborhood of its mean, to maximize  $\Pr(\mathcal N_{\vec\pi}\in \cpoly{B})$, the adversary aims at choosing $\vec \pi$ so that the ``volume'' of the intersection of an $O(\sqrt n)$ neighborhood of $\sum_{j=1}^n\pi_j$ and $\cpoly{B}$ is as large as possible. 

When $B = O(\sqrt n)$, it turns out that  $\cpoly{B}$ is close to $\cpolyz{\text{S}}\cap \cpolyz{\text{T}}$, where for any polyhedron ${\mathcal H}  \triangleq \{\vec x: {\mathbf A}\times \invert{\vec x}\le \invert{{{\mathbf b}}} \}$, ${\mathcal H}_{\leq 0}  \triangleq \{\vec x: {\mathbf A}\times \invert{\vec x}\le \invert{\vec 0} \}$ denotes its {\em characteristic cone}, also known as the {\em recess cone}.  Therefore, if $\text{\rm CH}(\Pi)\cap \cpolyz{\text{S}}\cap \cpolyz{\text{T}}=\emptyset$, then the mean of ${\vec X}_{\vec\pi}$ is $\Theta(n)$ away from $\cpolyz{\text{S}}\cap \cpolyz{\text{T}}$, which implies that the likelihood is (exponentially) small due to straightforward applications of Hoeffding's inequality. We call this case the {\bf \boldmath exponential case}.

When $B = O(\sqrt n)$ and $\text{\rm CH}(\Pi)\cap \cpolyz{\text{S}}\cap \cpolyz{\text{T}}\ne \emptyset$,  the adversary can choose $\vec\pi\in\Pi^n$ so that the mean of ${\vec X}_{\vec\pi}$ is either in $\cpolyz{\text{S}}\cap \cpolyz{\text{T}}$ or is $O(1)$ away, which means that the likelihood is large. In this case, there is a  {\bf \boldmath phase transition at $B=\Theta(\sqrt n)$}, as it will be shown that the likelihood reaches its (asymptotic) max at $B = \Theta(\sqrt n)$.

When $B= \Theta(n)$, again, the adversary aims at choosing $\vec\pi\in\Pi^n$  so that the mean of ${\vec X}_{\vec\pi}$ is close to $\cpoly{B}$. Let $B_{\text{\rm CH}(\Pi)}$ denote the smallest budget so that a ``pseudo-conic'' approximation to $\cpoly{B_{\text{\rm CH}(\Pi)}}$, denoted by $\sus{B}$ and is formally defined below in \eqref{eq:CB}, touches $\text{\rm CH}(\Pi)$, which is the convex hull of $\Pi$. See Figure~\ref{fig:illustration-PMV} (b) for an illustration of $B_{\text{\rm CH}(\Pi)}$   and $\sus{B_{\text{\rm CH}(\Pi)}}$ (the shaded area).  It is then expected that when $B<B_{\text{\rm CH}(\Pi)}\cdot n$, the max-semin-random instability whould be  small, and when  $B>B_{\text{\rm CH}(\Pi)} \cdot n$, the max-semin-random   instability whould be large. In other words, the semi-random stability has a {\bf \boldmath phase transition at  $B=\Theta(n)$}.


Nevertheless, characterizing the conditions and likelihood for each case is still challenging, as the approximation above is only meant to provide a qualitative  intuition. Existing multi-variate central limit theorems are often too coarse due to an $\Omega(\frac{1}{\sqrt n})$ error, as discussed in~\citep{Xia2021:How-Likely}.
 

\vspace{2mm}\noindent{\bf Notation.} Now let us define notation to formalize the intuitions discussed above. For any budget $B\ge 0$, we let $\cpoly{B}$ denote the relaxation of $\csus{n,B}$ by removing the size constraint and the integrality constraints on $\vec x$ and on $\vec o$. Recall that  $\vec o$ still needs to be non-negative. That is,
\begin{equation}\label{dfn:HB}
\cpoly{B} \triangleq \left\{\vec x\in  \cpoly{\text{S}}:  \exists \vec o\in {\mathbb R}_{\ge 0}^{|\voset{}|} \text{ s.t. }\vec c\cdot\vec o \le B \text{ and }\vec x+ \vec o\times \vomatrix{}\in\cpoly{\text{T}}\right\}
\end{equation}
For example, Figure~\ref{fig:illustration-PMV} (a) illustrates  $\cpoly{B}$ in the shaded area. $\cpoly{B}$ is a polyhedron because it is the intersection of $\cpoly{\text{S}}$ and the  Minkowski addition of $\cpoly{\text{T}}$ and the following polyhedron $\mathcal Q_{B}$:
$$\mathcal Q_{B} \triangleq \left\{- \vec o\times \vomatrix{}:  \vec o\in {\mathbb R_{\ge 0}^{|\voset{}|}} \text{ and }\vec c\cdot \vec o\le B   \right\}$$
Specifically, with infinite budget ($B=\infty$), we have 
$$\cpoly{\infty} = \left\{\vec x\in  \cpoly{\text{S}}:  \exists \vec o\in {\mathbb R}_{\ge 0}^{|\voset{}|} \text{ s.t. }  \vec x+ \vec o\times \vomatrix{}\in\cpoly{\text{T}}\right\} = \cpoly{\text{S}}\cap (\cpoly{\text{T}}+ \mathcal Q_{\infty})$$
For every $ B\ge 0$, we define $\sus{B}$ to be the polyhedron that consists of all (possibly non-integer) vectors in $\cpolyz{\text{S}}$ that can be manipulated to be in $\cpolyz{\text{T}}$ by using (possibly non-integer) operations $\vec o$ under budget constraint $B$. That is,   
\begin{equation}
\label{eq:CB}
\sus{B} \triangleq \left\{\vec x\in  \cpolyz{\text{S}}:  \exists \vec o\in {\mathbb R}_{\ge 0}^{|\voset{}|} \text{ s.t. } \vec c\cdot \vec o\le B\text{ and }\vec x+ \vec o\times \vomatrix{}\in\cpolyz{\text{T}}\right\} 
\end{equation}
It is not hard to verify that 
$\sus{B}   = \cpolyz{\text{S}}\cap (\cpolyz{\text{T}} + \mathcal Q_{B} )$  and $\sus{B}$ can be viewed as a ``pseudo-conic'' approximation to $\cpoly{B}$, as $\sus{B}$ is defined based on the characteristic cones of $\cpoly{\text{S}}$ and $\cpoly{\text{T}}$, though $\sus{B}$ itself may not be a cone. Specifically,  $\sus{0}$  and $\sus{\infty}$  will play a central role in Theorems~\ref{thm:PMV-instability} and~\ref{thm:PMV-multi-instability}. It is not hard to verify that
$$\sus{0} \triangleq \cpolyz{\text{S}}\cap \cpolyz{\text{T}}, \text{ and} $$
\begin{equation}
\label{eq:cone-infty}
\sus{\infty} \triangleq \left\{\vec x\in  \cpolyz{\text{S}}:  \exists \vec o\in {\mathbb R}_{\ge 0}^{|\voset{}|} \text{ s.t. } \vec x+ \vec o\times \vomatrix{}\in\cpolyz{\text{T}}\right\} = \cpolyz{\text{S}}\cap \left(\cpolyz{\text{T}} + \mathcal Q_{\infty}\right)
\end{equation}
Figure~\ref{fig:illustration-PMV} (b) illustrates $\sus{0}$ (which is a line) and $\sus{\infty}$ (which is the same as $\cpolyz{\text{S}}$).  Both $\sus{0}$ and $\sus{\infty}$ are polyhedral cones, because the intersection Minkowski addition  of two polyhedral cones is a polyhedral cone. Notice that when $B \not\in \{0,\infty\}$, $\sus{B }$ may not be a cone.

 



For any set $\Pi^*\subseteq {\mathbb R}^q$, let $B_{\Pi^*}\in\mathbb R$ to be the minimum budget $B $ such that the intersection of $\Pi^*$ and $\sus{B }$ is non-empty. If no such $B $ exists (i.e., $\Pi^*\cap \sus{\infty}=\emptyset$), then we let $B_{\Pi^*} \triangleq \infty$. Formally,
\begin{equation}
\label{eq:B-min}
B_{\Pi^*} \triangleq \inf \{B^*\ge 0: \Pi^*\cap \sus{B } \ne \emptyset\}
\end{equation}
Figure~\ref{fig:illustration-PMV} (b) illustrates $B_{\text{\rm CH}(\Pi)}$ and $\sus{B_{\text{\rm CH}(\Pi)}}$ in the shaded area, where $\Pi= \{\pi^1,\pi^2\}$ and $\text{\rm CH}(\Pi)$ is the {\em convex hull} of $\Pi$, which is the line segment between $\pi^1$ and $\pi^2$ in this case.   

Next, we define  notation and conditions used in the statement of the  theorem.


\begin{dfn
\label{dfn:conditions}
Given a PMV-instability setting, $\Pi$, $B$, and $n$, define
$$d_0 = \dim(\sus{0}), d_{\infty} =  \dim(\sus{\infty})\text{, and } d_{\Delta}  = d_{\infty}  - d_0,$$
where $\dim(\sus{0})$ is the {\em dimension} of $\sus{0}$, which is the dimension of the minimal affine space that contains $\sus{0}$. We also define the following three conditions:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline $\condition{1}$ & $\condition{2}$ & $\condition{3}$  \\
\hline $\csus{n,B}=\emptyset$ & $\text{\rm CH}(\Pi)\cap\sus{\infty}=\emptyset$ & $\text{\rm CH}(\Pi)\cap\sus{0}=\emptyset$ \\
\hline
\end{tabular}
\end{center}
\end{dfn}
Recall that $\text{\rm CH}(\Pi)$ is the convex hull of $\Pi$. Because $\sus{0}\subseteq \sus{\infty}$, $d_\Delta\ge 0$. Also notice that $\condition{2}$ implies $\condition{3}$, or equivalently, $\neg\condition{3}$ implies $\neg\condition{2}$.



\begin{thm}[\bf \boldmath Semi-Random  PMV-Instability, $\psi =0$]
\label{thm:PMV-instability} Given any $q\in\mathbb N$, any closed and strictly positive $\Pi$ over $[q]$, and any PMV-instability setting ${\cal S}{} = \langle\cpoly{\text{S}},\cpoly{\text{T}},\voset{},\vec c\,\rangle$, any $C_2>0$ and $C_3>0$ with $C_2<B_{\text{\rm CH}(\Pi)}<C_3$,  any $n\in \mathbb N$, and any $B\ge 0$, 
$$ 
 \begin{array}{r@{}|l|@{}l@{}|l|}
\cline{2-4} & \text{\bf Name} &  \text{\bf\  Likelihood}&  \text{\bf Condition}\\
\cline{2-4} \multirow{6}{*}{$\sup_{\vec\pi\in\Pi^n}\Pr\left({\vec X}_{\vec\pi} \in \csus{n,B}\right)= \left\{\begin{array}{@{}r@{}}\\\\\\\\\\\end{array}\right.$}& \text{0 case}& \ 0 &\condition{1}\\
\cline{2-4}& \text{exp case}& \ \exp(-\Theta(n)) &\neg \condition{1}\wedge \condition{2}\\
\cline{2-4}&  \text{PT-$\Theta(\sqrt n)$}& \ \Theta\left(\dfrac{\min\{B+1,\sqrt n\}^{d_{\Delta}}}{(\sqrt n)^{q-d_0}} \right) &\neg \condition{1}\wedge \neg \condition{3}\\
\cline{2-4}& \text{PT-$\Theta(n)$} & \begin{array}{ l l } \exp(-\Theta(n)) &\text{if }B\le C_2n \\ \hline \Theta\left( (\frac{1}{\sqrt n})^{q-d_\infty}  \right) &\text{if }B\ge C_3n\end{array}&\begin{array}{@{}l}\text{otherwise, i.e.,}\\ \neg \condition{1}\wedge \neg \condition{2}\wedge \condition{3}\end{array}\\
\cline{2-4}
\end{array}
$$
\end{thm}
The $B+1$ value is introduced to handle the $B<1$ case. For every $B\ge 1$,   $\Theta(B+1)=\Theta(B)$.\\
\begin{minipage}[t][][b]{0.3\textwidth}
\noindent{\bf The four cases.} Following the intuition presented at the beginning of this  section, we  call the first case  in Theorem~\ref{thm:PMV-instability} the  {\em $0$ case}, the second case the  {\em  exponential case}, the third case the   {\em phase transition at $\Theta(\sqrt n)$ case} (PT-$\Theta(\sqrt n)$ for short), and the last case, which contains two subcases, the  {\em phase transition at $\Theta(n)$ case} (PT-$\Theta(n)$  for short).
\end{minipage}
\hfill
\begin{minipage}[t][][b]{0.65\textwidth}
\centering
\includegraphics[width = 1\textwidth]{fig/PMV-manipulation.pdf}

\captionof{figure}{\small Illustration of Theorem~\ref{thm:PMV-instability}.  The x-axis is  in log scale. \label{fig:PMV-instability}}
\end{minipage}

\vspace{1mm}Figure~\ref{fig:PMV-instability} illustrates the max-semi-random instability as a function of $B$ for the exp case, PT-$\Theta(\sqrt n)$ case, and PT-$\Theta(n)$ case, respectively. Figure~\ref{fig:PMV-cases} (a)  illustrates  condition $\condition{2} = [\text{\rm CH}(\Pi)\cap\sus{\infty}=\emptyset]$ for the exp case. Figure~\ref{fig:PMV-cases} (b)  illustrates  condition $\neg\condition{3} =  [\text{\rm CH}(\Pi)\cap\sus{0}\ne \emptyset]$  for the PT-$\Theta(\sqrt n)$ case. Figure~\ref{fig:illustration-PMV} (b) illustrates condition $\neg\condition{2}\wedge \condition{3} =  [\text{\rm CH}(\Pi)\cap\sus{\infty} \ne \emptyset]\wedge [\text{\rm CH}(\Pi)\cap\sus{0} = \emptyset]$  for the PT-$\Theta(n)$ case.

\begin{figure}[htp]
\centering
\begin{tabular}{cc}
\includegraphics[width = 0.5\textwidth]{fig/PMV-exp.pdf} & \includegraphics[width = 0.5\textwidth]{fig/PMV-sqrt.pdf}\\
(a) The exp case. & (b) The PT-$\Theta(\sqrt n)$ case.
\end{tabular}
\caption{Illustration of the exp case and phase-transition-at-$\Theta(\sqrt n)$ case.\label{fig:PMV-cases}}
\end{figure}
\noindent{\bf Limitations and powers of Theorem~\ref{thm:PMV-instability}.}  Theorem~\ref{thm:PMV-instability} has  two major limitations. First, it misses a knife-edge case of $B$, i.e., when $B$ is around  $B_{\text{\rm CH}(\Pi)}\cdot n$. Second, the constants in asymptotic bounds may be exponentially large in $m$.   Despite these limitations, we believe that  Theorem~\ref{thm:PMV-instability} provides a general and useful tool for studying PMV-instability problems, because it converts the complicated PMV-instability problems, which involve  reasoning about the likelihood of discrete events (about the PMV) that cannot be easily bounded by standard techniques, to deterministic geometric problems about $\text{\rm CH}(\Pi)$, $\sus{0}$, $\sus{\infty}$, $d_0$, and $d_\infty$.  It provides an almost complete characterization of the PMV-instability problem, which can be easily applied to resolve long-standing open questions, e.g., in Corollary~\ref{coro:IC}. Practically, $\dim_0$ and $\dim_\Delta$ can still be hard to characterize, but at least Theorem~\ref{thm:PMV-instability} provides a useful guideline about what to look for. See Section~\ref{sec:applications} for some examples.

  
\vspace{2mm}\noindent{\bf Proof sketch of Theorem~\ref{thm:PMV-instability}.} At a high level, the proof follows after the intuitions presented  in the beginning of this subsection. The hardest part is the proof of the (asymptotically tight) polynomial bounds in the PT-$\Theta(\sqrt n)$ case. Take $\sup$ and $B = O(\sqrt n)$ for example. To prove the polynomial upper bound, our proof can be viewed as upper-bounding the ``volume''  of the intersection of an $O(\sqrt n)$ neighborhood of $\sum_{j=1}^n\pi_j$ and $\cpoly{B}$. We prove that, in $d_0$ dimensions, the volume is large, and each such dimension contributes a multiplicative $O(1)$ factor to the likelihood; in $d_\Delta$ dimensions, the volume is $O(B)$, and each such dimension contributes a multiplicative $O\left(\frac{B+1}{\sqrt n}\right)$ factor to the likelihood; and in the remaining $q-d_\infty$ dimensions, the volume is $O(1)$, and each such dimension contributes a multiplicative $O(\frac{1}{\sqrt n})$ factor to the likelihood. Putting all together, this proves the desired upper bound
$$O(1)^{d_0}\times O\left(\frac{B+1}{\sqrt n}\right)^{d_\Delta}\times  O\left(\frac{1}{\sqrt n}\right)^{q-d_\infty} =  O\left(\dfrac{ (B+1)^{d_{\Delta}}}{(\sqrt n)^{q-d_0}} \right)$$


  To prove the polynomial lower bound,  we first pretend that the PMV can take non-integer values, then  enumerate  (possibly non-integral) vectors that are far away from each other by exploring two directions. The first direction is the convex hull of $\sus{0}$, which is a   $(d_0-1)$-dimensional space that represents no budget ($B=0$), and each such dimension contributes an $\Omega(\sqrt n)$ multiplicative factor  to the total number of desirable vectors. The second direction is the convex hull of $\sus{\infty}$, which is a   $d_\Delta$-dimensional space   that represents infinite budget ($B=\infty$), and each such dimension contributes an $\Omega(B+1)$ multiplicative factor  to the total number of desirable vectors. Then, we  prove that for each such (possibly non-integral) vector, there exists a nearby integer vector, and apply the pointwise concentration bound~\citep[Lemma~1]{Xia2021:How-Likely} to prove the desired lower bound. The full version of the theorem and its full proof can be found in Appendix~\ref{app:proof-thm-PMV-instability}. 
  
  

\section{Back to The Coalitional Influence Problems}
\label{sec:applications} 

\myparagraph{The overall approach.}  
We propose the following two-step polyhedral approach in Procedure~\ref{proc:application} for characterizing   semi-random $X$.
\renewcommand{\algorithmcfname}{Procedure}
\begin{algorithm} 
\caption{The polyhedral approach for  semi-random coalitional influence}\label{proc:application}
\begin{algorithmic}
\item {\bf Input:}  $X$, $r$, $\Pi$, $\psi$
\item {\bf Step (i):} Model $X$ under $r$ as a union of multiple PMV-instability setting $\mathcal M$.
\item {\bf Step (ii):} Characterize the conditions and degree of polynomial for $\mathcal M$ by applying Theorem~\ref{thm:PMV-instability} and combining the results. 
\end{algorithmic}
\end{algorithm}

Step (i) is often easy.
The hardness of Step (ii) is highly problem-dependent, and we see two potential difficulties: first, it might be hard to verify for which $n$,  $B$, and PMV-instability problem,  the $0$ case of Theorem~\ref{thm:PMV-instability} does not happen; and second, sometimes the combination of the results of the applications of Theorem~\ref{thm:PMV-instability} are too complicated. 

In this section, we present three applications of Procedure~\ref{proc:application}  to illustrate its usefulness.

\myparagraph{The first application} is an asymptotically tight characterization for many commonly studied voting rules (defined in Appendix~\ref{app:more-rule}). Recall that ${\pi}_{\text{uni}}$ is the uniform distribution over $\mathcal L(\mathcal A)$.
\begin{thm}[{\bf Max-Semi-Random Coalitional Influence: Commonly Studied Rules}{}]
\label{thm:PMV-instability-applications}{
Let $r$ be an integer positional scoring rule, STV, ranked pairs, Schulze, maximin, or Copeland with lexicographic tie-breaking for any fixed $m\ge 3$. For  any closed and strictly positive $\Pi$ with ${\pi}_{\text{uni}}\in\text{\rm CH}(\Pi)$, any $X\in \{\cm,\text{\sc MoV}\}$, there exists $ N>0$  such that for any $n>N$ and any $B\ge 1$,
$$\satmax{X}{\Pi,0}(r ,n,B) =  \Theta\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right)  $$
Moreover, for any $\psi>0$, $\satmax{X}{\Pi,\psi}(r ,n,B) =\Theta(1)$.
} \end{thm}
\noindent{\bf Proof sketch.} We apply Procedure~\ref{proc:application} to $X=\cm$  under any  integer positional scoring rule $r_{\vec s}$ to illustrate the idea.  For Step (i) of Procedure~\ref{proc:application}, we adopt the same representation as in the proof of Lemma~\ref{lem:CI-GSR}. Due to the $O\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right)$ upper bound in Theorem~\ref{thm:PMV-instability-GSR-upper}, which will be proved soon, it suffices to prove the  $\Omega\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right)$  lower bound by identifying a PMV-instability setting ${\cal S}$ that represents some unstable histograms $\csus{n,B}$, and then apply  Theorem~\ref{thm:PMV-instability} to ${\cal S}$ to prove that for all $B\ge 1$, 
\begin{equation}
\label{eq:B-ineq-main-text}
 \sup\nolimits_{\vec\pi\in \Pi^n}\Pr\nolimits_{P\sim\vec \pi}(\text{Hist}(P)\in\csus{n,B}) = \Theta\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right)
\end{equation}
In fact, ${\cal S}$ is similar to that defined in Example~\ref{ex:illustration} and~\ref{ex:influence-model}. Let $\cpoly{\text{S}}$ denote the set of vectors where alternative $1$'s total score is at least as high as alternative $2$'s total score, which is strictly higher than the total score of any other alternative. Let $\cpoly{\text{T}}$ denote the set of vectors where $2$'s total score is the strictly highest. Let $\voset{\pm}^{1\rightarrow 2}$ denote the vote operations where a ranking with $2\succ 1$ is replaced by another ranking. Let ${\cal S}= \langle\cpoly{\text{S}}, \cpoly{\text{T}}, \voset{\pm}^{1\rightarrow 2},\vec 1\,\rangle$. 


For Step (ii) of Procedure~\ref{proc:application}, we apply  Theorem~\ref{thm:PMV-instability} to ${\cal S}$. We prove $\condition{1}=\text{false}$ for any sufficiently large $n$ by explicitly constructing a profile where a single manipulator can and has incentive to change the winner from $1$ to $2$. Then, we show that $\condition{3}=\text{false}$, because 
(1)  ${\pi}_{\text{uni}}\in \text{\rm CH}(\Pi)$ (assumption in Theorem~\ref{thm:PMV-instability-applications}), and (2) ${\pi}_{\text{uni}}\in \sus{0}$ (because $\sus{0}=\cpolyz{\text{S}}\cap \cpolyz{\text{T}}$ represents vectors where $1$ and $2$ are co-winners, and $r_{\vec s}({\pi}_{\text{uni}}) =\mathcal A$). This means that the polynomial case of Theorem~\ref{thm:PMV-instability} holds. It is not hard to verify that $d_0 = \dim(\sus{0}) = m!-1$. We then prove that $d_\infty  = m!$ by showing that an interior point of $\cpolyz{\text{S}}$ can be manipulated to an interior point of $\cpolyz{\text{T}}$. Inequality \eqref{eq:B-ineq-main-text} then follows after the polynomial case of $\sup$ of Theorem~\ref{thm:PMV-instability}, which proves the $\cm$ part under $r_{\vec s}$. 

The $\psi>0$ case follows after a straightforward application of Theorem~\ref{thm:PMV-instability-psi>0}. $\hfill\Box$

The full statement of Theorem~\ref{thm:PMV-instability-applications} (including other coalitional influence problems such as the ones defined in Appendix~\ref{app:more-CI})  and its full proof can be found in Appendix~\ref{app:applications-proofs}. The next example shows an application of Theorem~\ref{thm:PMV-instability-applications} to Borda. 
\begin{ex}
\label{ex:thm-Borda-CM}
In the setting of Example~\ref{ex:sCM-Borda}, notice that ${\pi}_{\text{uni}} = \frac12(\pi^1+\pi^2)$, which means that ${\pi}_{\text{uni}}\in\text{\rm CH}(\Pi)$. It follows from Theorem~\ref{thm:PMV-instability-applications} that for all  sufficiently large $n$, $\satmax{\cm}{\Pi,0}(\text{Borda},n,1) =  \Theta\left( \frac{1}{\sqrt n} \right) $.
\end{ex}

Theorem~\ref{thm:PMV-instability-applications} leads to the following  corollary on IC, where $\Pi = \{{\pi}_{\text{uni}}\}$ and $\psi = 0$.
\begin{coro}[{\bf Likelihood of Coalitional Influence w.r.t.~IC}{}]
\label{coro:IC}
Let $r$ be an integer positional scoring rule, STV, ranked pairs, Schulze, maximin, or Copeland with lexicographic tie-breaking for fixed $m\ge 3$. For any $X\in \{\cm,\text{\sc MoV}\}$,   there exists $N>0$  such that for any $n>N$ and any $B\ge 1$,

$\hfill \Pr\nolimits_{P\sim \text{IC}}(\sat{X}(r,P,B)) =  \Theta\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right) \hfill $
\end{coro}
As discussed in the Introduction, the $X=\cm$ and $B=1$ case of Corollary~\ref{coro:IC} proves the $\Omega\left(\min\left\{\frac{1}{\sqrt n},1\right\}\right)$ matching lower bound for all commonly studied voting rules investigated in the literature, for which only a matching lower bound for plurality was previously known.  

\myparagraph{The second application} is an upper bound for all generalized scoring rules  and all closed and strictly positive $\Pi$ with $\psi = 0$. 
\begin{thm}[{\bf Upper bound on Coalitional Influence  under GSRs}{}]
\label{thm:PMV-instability-GSR-upper}
Let $r$ denote any GSR with fixed $m\ge 3$. For any closed and strictly positive $\Pi$, any $X\in\{ \cm, \text{\sc MoV}\}$, any $n$, and any $B\ge 1$,
$$\hfill \satmax{X}{\Pi,0}(r,n,B) =  O\left(\min\left\{\frac{B}{\sqrt n},1\right\}\right) \hfill $$
\end{thm}
\noindent{\bf Proof sketch.} For Step (i) of  Procedure~\ref{proc:application}, we adopt the same representation as in the proof of Lemma~\ref{lem:CI-GSR}. Step (ii) relies on the notation and results of a general dichotomy theorem on the semi-random likelihood of influence problems for GSRs (Theorem~\ref{thm:GSR} in Appendix~\ref{sec:semi-random-CI}). The proof can be found in Appendix~\ref{app:proof-Lemma-PMV-upper}. 
$\hfill\Box$ 

Theorem~\ref{thm:PMV-instability-GSR-upper} immediately extends all previous $O\left( \frac{1}{\sqrt n}  \right) $ upper bound on $\cm$ for a single manipulator ($B=1$) that will be discussed in Section~\ref{sec:related-work} to any coalition size $B\ge 1$, because all rules studied in these works are GSRs.  

\myparagraph{The third application} studies a new  notion of coalitional manipulation that aims at making the loser win under integer positional scoring rules. For any positional scoring rule, the loser is the alternative with the minimum total score.

\begin{dfn}[\bf Coalitional manipulation for the loser] Given any integer positional scoring rule $r_{\vec s}$ with lexicographic tie-breaking, for any profile $P$ and any $B\ge 0$, we define $\cml(r_{\vec s}, P, B) = 1$ if and only if a coalition of no more than $B$ voters have incentive to misreport their preferences to make the loser under $P$ win. 
\end{dfn}

Clearly, under veto, no coalition of voters have incentive to misreport their preferences to make the loser win, i.e., $\cml(\text{veto}, P, B)=0$ for all $P$ and $B$. This is because any voter who  prefers the loser to the winner cannot reduce the difference between the total score of the loser and the sum of total score of all other alternatives, which means that no matter how they vote, the loser would not become the winner. The following theorems characterizes the max-semi-random $\cml$ under any other integer positional scoring rule for every sufficiently large $n$ and $B$.

\begin{thm}[\bf Max-Semi-Random Coalitional Manipulation for The Loser]
\label{thm:CML}{
Let $r_{\vec s}$  be an integer positional scoring rule with lexicographic tie-breaking for fixed $m\ge 3$ that is different from veto. For  any closed and strictly positive $\Pi$ with ${\pi}_{\text{uni}}\in\text{\rm CH}(\Pi)$, there exists $ N>0$ and $B^*>0$ such that for any $n>N$ and any $B\ge B^*$,
$$\satmax{\cml}{\Pi,0}(r_{\vec s} ,n,B) =  \Theta\left(\min\left\{\frac{B}{\sqrt n},1\right\}^{m-1}\right)  $$
Moreover, for any $\psi>0$, $\satmax{\cml}{\Pi,\psi}(r_{\vec s} ,n,B) =\Theta(1)$.} \end{thm}
\noindent{\bf Proof sketch.}  For Step (i) of  Procedure~\ref{proc:application},  we first define a set of PMV-instability settings, denoted by $\mathcal M_{\cml}$, that represents $\cml$ under $r_{\vec s}$.  For every pair of different alternatives $a,b$, define a PMV-instability setting ${\cal S}_{\cml}^{a\rightarrow b} = (\cpoly{\text{S}}, \cpoly{\text{T}}, \voset{\pm}^{a\rightarrow b}, \vec 1)$, where  $\cpoly{\text{S}}$ denotes the set of vectors where $a$ is the winner and $b$ is the loser under $r_{\vec s}$, and  $\cpoly{\text{T}}$ denotes the set of vectors where $b$ is the winner  under $r_{\vec s}$. Define $\mathcal M_{\cml} = \left\{{\cal S}_{\cml}^{a\rightarrow b}: a,b\in\mathcal A, a\ne b\right\}$. 
It is  not hard to verify that   $\mathcal M_{\cml}$ represents $\cml$ under $r_{\vec s}$.

Then, for Step (ii) of Procedure~\ref{proc:application}, we  apply Theorem~\ref{thm:PMV-instability} to every ${\cal S}_{\cml}^{a\rightarrow b}$. We first prove $\condition{1} = \text{false}$  for any sufficiently large $n$ and $B$, by constructing a successful manipulation by $B$ voters.  Then, let $\sus{0}^{a\rightarrow b}= \cpolyz{\text{S}}\cap \cpolyz{\text{T}}$. We have ${\pi}_{\text{uni}}\in \text{\rm CH}(\Pi)\cap \sus{0}$, which means that $\condition{3} = \text{false}$. Therefore, the polynomial case of Theorem~\ref{thm:PMV-instability} holds. It is then not hard to verify that   $d_0 = \dim(\sus{0}^{a\rightarrow b}) = m!-(m-1)$ and $d_{\infty} = \dim(\cpolyz{\text{S}}) = m!$, which means that $d_{\Delta} =  m-1 $. By Theorem~\ref{thm:PMV-instability}, we have
$$\hfill \sup\nolimits_{\vec\pi\in\Pi^n}\Pr\left({\vec X}_{\vec\pi} \in \csus{n,B}\right)= \Theta\left(\dfrac{\min\{B+1,\sqrt n\}^{m-1}}{(\sqrt n)^{m!-(m!-(m-1))}} \right) = \Theta\left(\min\left\{\frac{B}{\sqrt n},1\right\}^{m-1}\right)\hfill $$

Theorem~\ref{thm:CML} follows after applying this bound to all $a\ne b$. The $\psi>0$ case follows after a straightforward application of Theorem~\ref{thm:PMV-instability-psi>0}. The full proof can be found in Appendix~\ref{app:proof-thm-CML}. $\hfill\Box$



\section{Related Work and Discussions}
\label{sec:related-work}
Due to the large body of literature, below we briefly discuss some closely related work. More detailed discussions can be found in Appendix~\ref{app:related-work}.

\vspace{2mm}\noindent{\bf Likelihood of coalitional manipulability: upper bounds w.r.t.~IC.} As discussed earlier, a series of work has established an $O(\frac{1}{\sqrt n})$  upper bound on the likelihood of single-voter manipulability  under commonly studied voting rules w.r.t.~IC~\citep{Pattanaik1975:Strategic,Pazner1978:Cheatproofness,Peleg1979:Note,Nitzan1985:Vulnerability,Fristrup1989:A-Note,Kim1996:Statistical,Slinko2002:Asymptotic,Slinko2002:On-Asymptotic,Slinko2002:The-Majoritarian,Baharad02:Asymptotic,Slinko2004:How-large,Maus2007:Anonymous,Pritchard09:Asymptotics}. The likelihood of coalitional manipulability was also considered for a few rules with certain sizes of  the coalition~\citep{Pazner1978:Cheatproofness,Peleg1979:Note,Slinko2004:How-large,Pritchard09:Asymptotics}. All these results are straightforward corollaries of our Theorem~\ref{thm:PMV-instability-GSR-upper}, which implies an $O\left(\min\left(\frac{B}{\sqrt n},1\right)\right)$ upper bound for every  $B\ge 1$ w.r.t.~IC under a wide range of voting rules, including (but not limited to) the ones studied in previous work.

\vspace{2mm}\noindent{\bf Likelihood of coalitional manipulability: lower bounds w.r.t.~IC.}  A series of work on quantitative Gibbard-Satterthwaite theorems~\citep{Friedgut2011:A-quantitative,Dobzinski08:Frequent,Xia08:Sufficient,Isaksson10:Geometry,Mossel2015:A-quantitative} established polynomial lower bounds on the likelihood of strategic voting by a single manipulator ($B=1$) w.r.t.~IC.
Many of these results applied to any voting rule, and are therefore more general than the $\cm$ part of Theorem~\ref{thm:PMV-instability-applications} and Corollary~\ref{coro:IC}. On the other hand, Theorem~\ref{thm:PMV-instability-applications} is stronger and more general in some other aspects: it works for every $B\ge 1$, more coalitional influence problems, and a more general and realistic (semi-random) model, and it provides asymptotically tight bounds. Its application to $\cm$ w.r.t.~IC in Corollary~\ref{coro:IC} establishes an $\Omega(\frac{1}{\sqrt n })$ matching bound for many commonly studied rules, among which  this matching lower bound was only known for the plurality rule~\citep{Slinko2002:Asymptotic}. 





\vspace{2mm}\noindent{\bf Likelihood of coalitional manipulability: other distributions.} Results under i.i.d.~distributions~\citep{Peleg1979:Note,Procaccia2007:Junta,Xia08:Generalized,Mossel13:Smooth,Xia15:Generalized} demonstrated  a phase transition from powerless to powerful at $\Theta(\sqrt n)$ manipulators.   
There is a large body of literature on the likelihood of $\cm$ under the {\em Impartial Anonymous Culture (IAC)}, which  assumes that each histogram happens equally likely  and resembles the flat Dirichlet distribution, by theoretical analysis~\citep{Lepelley1987:The-proportion,Saari1990:Susceptibility,Lepelley1994:The-vulnerability,Huang2000:Analytical,Favardin2002:Borda,Favardin2006:Some,Slinko2006:How-the-size,Wilson2007:Probability,Lepelley2008:On-Ehrhart} and by computer simulations~\citep{Lepelley2003:Voting,Pritchar07:Exact,Green-Armytage2016:Statistical}. Both IAC and IC are mainly of theoretical interest and  {\em ``are poor proxies of political electorates''}~\citep{Nurmi2012:On-the-Relevance}.  

\vspace{2mm}\noindent{\bf Other coalitional influence problems.}
All results in this paper also work for $\text{\sc MoV}$, which  measures the stability of elections and provides an upper bound on $\cm$. Some previous proofs of upper bounds on $\cm$ were done for $\text{\sc MoV}$~\citep{Slinko2002:Asymptotic,Xia08:Generalized}. The phase transition  behavior for $\cm$ also happens for $\text{\sc MoV}$~\citep{Mossel13:Smooth,Xia15:Generalized}. Previous work has also investigated expected $\text{\sc MoV}$~\citep{Pritchard2006:Average} and $\text{\sc MoV}$ for tournament rules~\citep{Brill2022:Margin}.
 The likelihood of $\text{\sc MoV}=1$ has been used to measure the {\em decisiveness} of voting, sometimes called {\em voting power}, which plays an important role in the paradox of voting~\citep{Downs1957:An-Economic} and in  power indices in cooperative game theory. For two alternatives under the plurality rule, the voting power is equivalent to the likelihood of ties~\citep{Good1975:Estimating}. In general, $\text{\sc MoV}=1$ and the election being tied are different events,  as shown in Example~\ref{ex:ties-stable} and~\ref{ex:noties-unstable} in Appendix~\ref{app:tie-instability}.

Beyond $\cm$ and $\text{\sc MoV}$, there is a large body of work on the computational complexity of other types of coalition influence problems, such as constructive/destructive control (making a designated alternative win/lose) by adding/deleting votes, and bribery (different changes in votes have different costs). See~\citep{Faliszewski2016:Control} for a recent survey and see Appendix~\ref{app:more-CI} for their definitions. Little was known about  their likelihood of success, except~\citep{Xia15:Generalized}, which  does not provide an accurate characterization as discussed in Appendix~\ref{app:related-work}. The full versions of our results in the Appendix provide the first asymptotically tight bounds for these coalitional influence problems.



\myparagraph{\bf \boldmath Generality and limitations of our semi-random model.} The distribution adversary's part of our model is  the same as the semi-random model  proposed in~\citep{Xia2020:The-Smoothed}, which has two major limitations: the independence of noises among agents' preferences, and  the strict positiveness of $\Pi$. Our model addresses the two limitations by introducing the data adversary, who modifies the (semi-randomly) generated data and therefore introduce strong and adversarial correlations. Specifically, our model is more general because the $\psi=0$ case of our model degenerates to the model in~\citep{Xia2020:The-Smoothed}. How to further generalize our model by introducing (statistical) correlations and relaxing the strict positiveness of $\Pi$ for the distribution adversary is an important and challenging directions for future research.
 


\vspace{2mm}\noindent{\bf Technical novelty.} While our Procedure~\ref{proc:application} is similar to the ``polyhedral approaches" adopted  in previous work  on semi-random social choice~\citep{Xia2020:The-Smoothed,Xia2021:How-Likely,Xia2021:Semi-Random}, the main technical tool of this paper (Theorem~\ref{thm:PMV-instability} for $\psi =0$ and Theorem~\ref{thm:PMV-instability-psi>0} for $\psi>0$) are  significant and non-trivial extensions of the main technical theorems in previous work, especially~\citep[Theorem~1]{Xia2021:How-Likely}, which  can be viewed as  a special case of our Theorem~\ref{thm:PMV-instability} with $\cpoly{\text{S}}= \cpoly{\text{T}}$, $B=0$. The hardest part  is  the  polynomial lower bounds, whose $\cpoly{\text{S}}= \cpoly{\text{T}}$ and $B=0$ case was proved in~\citep[Theorem~1]{Xia2021:How-Likely} by explicitly enumerating sufficiently many target integer vectors for the PMV. However, due to the generality of the PMV-instability problem, we do not see an easy way to perform a similar enumeration. To address this technical challenge, we take a different approach by first pretending that the PMV can take non-integer values, then  enumerating  (possibly non-integral) vectors that are far away from each other by exploring two directions: the direction that represents no budget (i.e., $B=0$) and the direction that represents infinite budget (i.e., $B=\infty$), and finally proving that for each such (possibly non-integral) vector, there exists a nearby integer target vector for the PMV.  
We believe that our Theorem~\ref{thm:PMV-instability} and Theorem~\ref{thm:PMV-instability-psi>0} are useful and general tools for studying likelihood of coalitional influence, as exemplified by its applications to prove  Theorems~\ref{thm:PMV-instability-applications}--\ref{thm:CML}, Corollary~\ref{coro:IC}, and a general Theorem~\ref{thm:GSR} (Appendix~\ref{sec:semi-random-CI}).



\myparagraph{\bf Semi-random analysis and smoothed analysis in general.} Semi-random analysis~\citep{Blum1990:Some,Blum1995:Coloring} refers to the  analysis under a model where the process of generating  instances has adversarial components and random components. For example, in the smoothed complexity analysis~\citep{Spielman2009:Smoothed}, the input to an algorithm is obtained from an adversarially chosen ``ground truth'' plus a (small) random perturbation.  This can be viewed as the adversary directly choosing a distribution over data (from a set of distributions).  See~\citep{Feige2021:Introduction} for a recent survey of various semi-random models and complexity results under them.

\section{Summary and Future Work}
We extend previous studies on average-case likelihood of coalitional manipulation in elections in three aspects: (1)  a more general and realistic semi-random model that introduces correlations among agents' preferences, (2) many other coalitional influence problems, and (3) arbitrary  coalition size, by taking the polyhedral approach (Procedure~\ref{proc:application}).
While we do not think that results in this paper are  the final answers to the  question  in Introduction,
we do believe that they are a non-trivial step forward, because they address  long-standing open questions  and expand  the scope of previous work to more general and realistic settings.

Moving forward, we see three natural directions for future work. {\bf More realistic models:} as discussed in Section~\ref{sec:related-work}, a natural question is how to relax the statistical independence and strict positiveness constraints on the distribution adversary to build a more realistic yet  still tractable model. At a high level, the data adversary may be viewed as another influencer. Therefore, another natural question is how to incorporate different kinds of adversaries and influencers to the model.  
{\bf Stronger theorems:} as discussed after Theorem~\ref{thm:PMV-instability}, characterizing the constants in the bounds is a natural open question.  Additionally, as discussed in the Introduction, Theorem~\ref{thm:PMV-instability-GSR-upper} poses a challenge to designing natural rules with lower likelihood of coalitional influence, or improving the $\Omega(\frac{1}{n^{-67}})$ lower bound (and extending it to $B\ge 2$). {\bf More applications:}  how to develop informative characterizations as done in Section~\ref{sec:applications} for other rules, other coalition influence problems, or other applications such as matching, resource allocation, fair division~\citep{Bai2022:Fair}, judgement aggregation~\citep{Liu2022:Semi-Random}, are important and challenging tasks.   

\newpage
 \tableofcontents

 
  





\newpage

