text:
\section{Introduction}

Majority voting is the most popular voting rule for binary decisions. It is often a synonym for voting: in legislatures and committees, agents often express their opinion for one of two available options, the most popular one being elected. Early axiomatized with simple and intuitive axioms (see \cite{may1952set}, and \cite{horan2019positively} for a recent contribution), it plays a central role in analyzing democratic institutions.

Nevertheless, a non-negligible share of voters regret their choice (their vote or their abstention) in different sorts of elections.\footnote{See \cite{bol2018mixed} for an analysis of regret in Canadian elections and a theory that incorporates regret in voters' decision problems.} While many narratives could justify these results, we consider the theoretical insight by \cite{xiong2021designing} as a reasonable justification: preventing such bad outcomes is not easy since only dictatorships are implementable through voting mechanisms.\footnote{A voting mechanism allows each agent to vote for each option and is monotonic in the usual sense: if $x$ wins at some profile and gets additional support from some agent, $x$ remains the winner. For instance, delegation mechanisms (such as \cite{campbell2022liquid} and \cite{dhillon2021information}) belong to the category of voting mechanisms.} This impossibility is tantamount to saying that all usual voting rules admit undesirable equilibria where the minority preferred candidate wins. The logic behind this impossibility is related to the following observation. Whenever a voting profile contains too many votes for the same option, this profile is an equilibrium irrespective of preferences since no agent is pivotal.

These inefficiencies make appealing the design of alternative voting rules. The primary solution considered in the literature\footnote{See \cite{goeree2020improving} for a recent review of the literature addressing this question: They compare several mechanisms that either rely on transfers (such as quadratic voting or markets for votes) or on voting over several issues (such as storable votes). One advantage of our mechanisms is that they are conceived for a single election while not relying on transfers.} when a single election is at stake is as follows: shifting from simultaneous voting to the sequential majority mechanism or roll-call voting, where voters express their preference for one of the two options one after the other, and the most popular option wins.\footnote{The introduction of supermajorities or qualified majority rules where one option needs more than half of the votes to win is often considered. The rationale behind such a solution is clear: to avoid events where both candidates get the same popular support and the winner is considered illegitimate, one should raise the threshold required to be called the winner. This class of rules does not escape from the impossibility described by \cite{xiong2021designing} and thus also admits inefficient equilibria.} Roll-call voting subgame perfect implements the majority-preferred option as long as agents' reasoning relies upon backward induction. Recent experimental findings (see \cite{bolle2022voting}) suggest that while theoretically different, sequential and simultaneous majority voting do not differ much; note that both systems co-exist in the U.S. state legislatures.\footnote{In common value settings, roll-call voting has a main drawback: the dynamic structure might trigger informational cascades (see \cite{anderson2008information} for a review of the experimental literature on cascades). } Moreover, as shown by \cite{spenkuch2018backward}, in the U.S. Senate, where roll-call voting is used, early movers tend to drop the party line to free-ride on late movers; this, in turn, can lead to failures in implementing the majority preferred option.

Do other mechanisms guarantee that the majority-preferred option is the only equilibrium winner with fewer steps? If one focuses on simultaneous mechanisms, the contribution of \cite{maskin1999nash} ensures their existence, as majority voting fulfills the sufficient conditions for being Nash implementable. However, the main objection to  such result is that the mechanism (integer game) achieving the implementation is hard to apply in practice. This objection is reinforced by the recent contribution of \cite{xiong2021designing}, as discussed above, since no known voting mechanism implements the majority option.

We contribute to this literature by providing a positive result: we design three mechanisms that implement the majority option. The mechanisms that we present differ in the timing (simultaneous and dynamic) and the agents' strategies. They have in common the use of lotteries off-equilibrium\footnote{Mechanisms with off-equilibrium lotteries are known to be more permissive than deterministic mechanisms. See \cite{benoit2008nash}, \cite{bochet2007nash} and \cite{laslier2021solution} for recent contributions. \cite{borgers2014robust} develop a similar idea to show that one
can achieve Pareto improvements over random dictatorship through simultaneous mechanisms. In the related framework of the Condorcet jury theorem, \cite{laslier2013incentive} proposes the introduction of a "slightly randomized majority rule" to ensure that the unique equilibrium is informative. Our mechanisms share a similar spirit to this idea but without randomization in equilibrium. Likewise, \cite{nunez2019truth} and \cite{azevedo2019strategy} describe similar ideas for large populations of agents.}  to incentivize agents to vote for their preferred alternative. To deal with lotteries, we impose the mild restriction of stochastic dominance, virtually satisfied by all preference extensions.

Our primary contribution is the design of the Majority voting with random checks.  Its main features are as follows. Initially, agents vote simultaneously for one of the two options. After the vote totals are revealed, a second stage takes place to determine whether the winner of the first round should  be the outcome. Each agent (out of the $p+1$ randomly selected ones) sequentially declares whether she agrees with the winner. If any of these agents agrees, the winner of the first round is the outcome; otherwise, the winner is determined by a lottery by randomly picking one of the initial votes. This lottery's role is to give proper incentives to agents to reveal their preferred alternative. The Majority voting with random checks implements the majority rule under complete and incomplete information.\footnote{We focus on implementation in sequential equilibria (see \cite{baliga1999implementation}). Implementation in extensive form games is also possible via other concepts such as Perfect bayesian (see \cite{brusco1995perfect}) or simply relying on belief restrictions (see \cite{bergin1998extensive}).} The main advantage of this mechanism is that it requires at most $p+2$ stages (voting stage and $p+1$ voters). This implies an important shortening with respect to the sequential majority one which requires $2p+1$ stages. We also extend the mechanism to a setting where agents can abstain in any of the stages making the strategic problem richer.\footnote{We thank Omer Tamuz for suggesting this extension.}

Our second set of contributions is the design of two alternative mechanisms achieving the same implementation goal: the Bloc formation mechanism and the Verification one. The Bloc formation mechanism is the first simultaneous voting-based mechanism, different than an integer game, that Nash implements majority rule. The mechanism is not a pure voting mechanism because agents do not have a strategy that consists exclusively of voting for one of the two options.  Instead, the Bloc formation mechanism requires each agent to vote for one of the two options \textit{and} to nominate $p$ other agents.\footnote{For any positive integer $p$, if $n$ denotes the number of agents with $n=2p+1$, an agent nominates $p$ agents. Note when an agent nominates $p$ agents, a majority agent is always among the nominees since there at most $p$ minority agents.}
This mechanism's definition actually allows us to see a voting profile as a directed network where vertices are the agents and the edges their nominations.\footnote{For completeness, we also provide an equivalent definition of the Majority voting with random checks as a network formation game.} The outcome of the vote depends on the network structure generated by the voting profile. Finally, we design  the Verification mechanism, a voting mechanism in the sense that voters are just required to vote for one of the options. More specifically, these mechanisms request agents to vote for an option in the first stage and, in case some agent disagrees with the first stage majority outcome,  to confirm their choice to ensure no coordination problem exists. The mechanism also relies on the bloc formation as its simultaneous counterpart and uses lotteries to increase agents' pivotality. We show that this mechanism subgame perfect implements  the majority option under complete and incomplete information.

This work is organized as follows. After laying out the model in Section \ref{sec:setting}, Section  \ref{sec:majorityform}  analyzes the Majority voting with Random checks. Section \ref{sec:altmechanisms} considers the Bloc formation and the Verification mechanisms. Section \ref{sec:conclusion} concludes, and the Appendix contains some proofs.

\section{Model \label{sec:setting}}

We consider a finite set $I=\{1,\ldots,n\}$ of agents, with generic element $i$, who need to choose one option out of the set $A=\{a, b\}$. Each agent has strict complete and reflexive  preferences over $A$ where $a R_i b$ denotes that $a$ is strictly preferred to $b$. We denote by $\Theta=\{\theta_a,\theta_b\}$ the type space for each agent. A vector $\theta^n\in \Theta^n$ denotes the profile of all agents' preferences. An agent $i$ is of type $\theta_a$ (resp. $\theta_b$) if and only if $a R_i b$ (resp. $bR_ia$).
A social choice correspondence (SCC) is a mapping $f: \Theta^n \rightrightarrows A$ that selects a non-empty set of options for each profile $\theta^n$. The majority rule is the SCC  that selects $Maj(\theta^n)$ the majority preferred option(s) of the profile $\theta^n$. With $2p+1$ agents ($p$ being a non-negative integer), the majority rule is uniquely defined since $Maj(\theta^n)=x$ if and only if $|\{i\in I \mid x R_i y\}|\geq p+1$.\footnote{The paper is written assuming an odd number of agents to ease notation. However, several of the results extend to the case with an even number of them. If there are $2p$ agents, the majority preferred candidate need not be unique since $Maj(\theta^n)=x$ if $|i\in I \mid x R_i y|\geq p+1$ and $Maj(\theta^n)=\{x,y\}$ if  $|i\in I \mid x R_i y|=p$. }

We let $\Delta$ denote the set of lotteries over $A$ with $\Delta=\{\beta:A \rightarrow [0,1] \mid \sum_{A}\beta(a)=1\}$. A \textit{mechanism} is a function $g: M \rightarrow \Delta$ that assigns to every $m\in M$ a unique element of $\Delta$, where $M=\prod_{i\in I}M_i$, and $M_i$ is the strategy space of agent $i$.

We assume that preferences over lotteries satisfy stochastic dominance (\textbf{SD}). A lottery $\beta$ stochastically
dominates lottery $\eta$ if and only if $\beta$ yields at least as much expected utility
as $\eta$ for any von-Neumann Morgenstern utility representation consistent with the ordinal preferences.

Consider two lotteries $\beta,\eta\in \Delta$. \textbf{SD} requires that for each option $x$, the probability that $\beta$ selects
an option that is at least as preferred as $x$ by the agent is greater or equal to the
probability that $\eta$ selects such an option. Since in our setting there are only two options, we can write for any agent $i$ that:

$$\beta \tilde{R}_i^{\textbf{SD}} \eta \Longleftrightarrow \beta(x) \geq  \eta(x) \text{ and } \beta R_i^{\textbf{SD}} \eta \Longleftrightarrow \beta(x) >  \eta(x),$$

where $\beta \tilde{R}_i^{\textbf{SD}} \eta$ means that agent $i$ weakly prefers $\beta$ to $\eta$ and $\beta R_i^{\textbf{SD}} \eta$ implies that she strictly prefers the former to the latter.

A mechanism specifies a game-form: this means that, when the mechanism is coupled with preferences over options for each of the agents, it defines a normal-form or extensive-form game. For a mechanism $g$, let $\mathrm{NE}^{g}(\theta^n)$ and $\mathrm{SPNE}^{g}(\theta^n)$ respectively denote the set of Nash equilibria and subgame perfect equilibria when the preference profile is $\theta^n$. A mechanism Nash (resp. subgame perfect) implements a social choice correspondence $f$ if for any $\theta^n$, the outcome of any member of $\mathrm{NE}^{g}(\theta^n)$ (resp. $\mathrm{SPE}^{g}(\theta^n)$) is an element of $f(\theta^n)$ and any element of $f(\theta^n)$ is the outcome of some member of $\mathrm{NE}^{g}(\theta^n)$ (resp.   $\mathrm{SPE}^{g}(\theta^n)$).
A similar idea applies to the incomplete information setting where the equilibrium notion upon which we rely is sequential equilibrium (a formal definition is skipped).

\section{Majority voting with Random checks  \label{sec:majorityform}}

This section introduces the main contribution of this work: Majority voting with Random checks ($\chi_{RC}$ in the sequel). Its formal definition follows.

\vspace{.2cm}

\noindent \textbf{Timing.}

\noindent \textit{Voting stage:} Each agent $i$ votes for an option $v_i \in A$. The profile of votes $v$ is publicly announced and the option which gets most votes in $v$ is denoted the winner of the Voting stage.

\noindent \textit{Confirmation stage:} An order of agents $\pi=(\pi_1, \ldots, \pi_n)$ is selected through a uniform draw. At each stage $t \in \{1,\ldots,p+1\}$, agent $\pi_t$ announces $Y$ or $N$.

 At each stage $t$, the mechanism ends if the nominating agent $\pi_t$ announces $Y$ with the outcome being the winner (most announced option) of the Voting stage. Otherwise, the mechanism proceeds to stage $t+1$ and the next agent announces $Y$ or $N$. If all agents in $\{\pi_1, \ldots, \pi_{p+1}\}$ announced $N$ in the Confirmation stage the outcome is a lottery $\beta(v)$ determined by profile $v$. This lottery  assigns to each option its share of first-stage votes, so that
$\beta_a(v)=\frac{|\{i \in I \mid v_i=a\}|}{n}$ and $\beta_b(v)=1-\beta_a(v)$. The purpose of this lottery is to give incentives to agents to vote for their most preferred option.

Notice that the Confirmation stage announcements $Y$ and $N$ can be viewed as agreement and disagreement with the Voting stage outcome respectively. That is, if at least one agent in $\{\pi_1, \ldots, \pi_{p+1}\}$ agrees with the outcome being the majority winner of the Voting stage, this option is the outcome. On the other hand, if no one agrees, the outcome is the previously mentioned lottery.

We now establish the implementation under complete and incomplete information and discuss the extension to abstention.

\subsection{Complete information }

Before starting the formal argument with complete information, we present an example that illustrates the logic under this mechanism.

\medskip

\noindent \textit{Example 1}: Preferences are given by $aR_i b$ for $i=1,2,3$ and $b R_i a$ for $i=4,5$. Consider any strategy profile in which $v_i=b$ for every agent $i$; the rules of the mechanism imply that $b$ is the outcome, independently of the Confirmation stage. This profile is not an equilibrium since $b$ is not majority preferred. More precisely, any agent with type $\theta_a$ has a profitable deviation. Consider, for instance, that agent 1 deviates and votes $v'_1=a$ rather than $v_1=b$. The outcome after such deviation depends on the agents selected for the Confirmation stage. If either 4 or 5 is selected, $b$ is the outcome since both agents prefer $b$ to $a$ and, thus, in any SPE of the Confirmation stage at least one of them announces $Y$. If neither 4 or 5 is in $\{\pi_1, \ldots,\pi_{p+1}\}$, the Confirmation stage involves only agents $\{ 1, 2,3\}$. All of them strictly prefer to announce $N$ if $Y$ was not announced before. Thus, in the unique SPE of the Confirmation stage, $N$ is announced by all three agents and the outcome of the mechanism is a lottery that selects $a$ with probability 1/5 (random dictatorship in the profile $(a,b,b,b,b)$). Table \ref{tab:MF} illustrates this example. The left part represents the Voting stage profiles: unanimous in the first case, and after the deviation of agent 1 afterwards. The right part illustrates a possible SPE of the Confirmation stage given Voting stage profiles.

\begin{table}[h]
    \centering
    \begin{tabular}{c|c|c|c|c||c|c|c|c|c||c|}
          \multicolumn{5}{c||}{Voting stage} & \multicolumn{5}{c||}{Confirmation stage} & Outcome\\
         \hline
 1 & 2 & 3 & 4 & 5 & 1 & 2 & 3 & 4 & 5 & \\
        \hline
        \hline
        \multicolumn{11}{c}{\textbf{Unanimous vote for} $b$, $\{\pi_1,\pi_2,\pi_3\}=\{1,2,3\}$}\\
        \hline
         $b$ & $b$ & $b$ & $b$ & $b$ & $N$ & $N$ & $N$ & - & - & $b$ \\
         \hline
        \hline
        \multicolumn{11}{c}{\textbf{Deviation to $v'_1=a$}, $\{\pi_1,\pi_2,\pi_3\}=\{1,2,5\}$}\\
        \hline
         \textbf{a} \color{black} & $b$ & $b$ & $b$ & $b$ & $N$ & $N$ & - & - & $Y$ & $b$ \\
          \hline
        \hline
        \multicolumn{11}{c}{\textbf{Deviation to $v'_1=a$}, $\{\pi_1,\pi_2,\pi_3\}=\{1,2,3\}$}\\
        \hline
         \textbf{a} \color{black} & $b$ & $b$ & $b$ & $b$ & $N$ & $N$ & $N$ & - & - & $1/5a+4/5b$
    \end{tabular}
    \caption{Majority voting with Random checks}
    \label{tab:MF}
\end{table}
\color{black}

Therefore, by deviating from  $v_1=b$ to $v'_1=a$, agent 1 induces a lottery that assigns $a$ a positive probability; by \textbf{SD}, agent 1 prefers to deviate showing that any strategy profile in which $v_i=b$ for every agent $i$ cannot be an equilibrium.

\color{black}

A similar logic to the one described in the example shows that at least $p+1$ agents who prefer the majority option are sincere in the Voting stage of \textit{any} equilibrium which leads to the implementation result, stated formally as follows.

\begin{proposition}\label{pro:MVRCcom}
The Majority voting with Random checks subgame perfect implements the majority rule.
\end{proposition}

\begin{proof}
We solve the game backwards starting from Confirmation stage. Notice first that in case the profile $v$ is unanimous, Confirmation stage does not affect the outcome. Assume that $v$ is not unanimous and denote by $x$ the winning option of the Voting stage and by $y$ the remaining one.

Assume that no agent from $\{\pi_1, \ldots, \pi_{p}\}$ announced $Y$ and consider agent $\pi_{p+1}$. If $xR_{\pi_{p+1}}y$ the unique best response is $Y$ and it is $N$ otherwise.

Consider now agent $\pi_{p}$ and assume no $Y$ was announced before. Then the best response of $\pi_{p}$ is:

- $Y$ if $xR_{\pi_p}y$ and  $yR_{\pi_{p+1}}x$;

- $N$ if $yR_{\pi_p}x$ and  $yR_{\pi_{p+1}}x$;

- $\{N,Y\}$ otherwise.

This logic can be extended to earlier agents in $\pi$ in the following way. For
any agent $\pi_i$ with $i \leq p+1$ the best response at Stage 2 is:

- $Y$ if $xR_{\pi_i}y$ and  $yR_{\pi_j}x$ for all $i<j\leq p+1$;

- $N$ if $yR_{\pi_j}x$ for all $i \leq j\leq p+1$;

-$\{N,Y\}$ otherwise.

Then the SPE outcome of Stage 2 is the following one.

\begin{lemma}\label{lemma:RCcompl}
    For any non-unanimous profile $v$ of the Voting stage, the SPE outcome of the Confirmation stage is:

- $x$ (the winner of Voting stage) if $x R_i y$ for some $i \in \{\pi_1,\ldots, \pi_{p+1}\}$;

- the lottery $\beta(v)$ otherwise.
\end{lemma}

Consider now the Voting stage where we let $a$ denote the majority preferred option and $b$ the minority preferred one.
Notice first, that if $a$ is the winner of the Voting stage, the equilibrium outcome is $a$. This follows from Lemma \ref{lemma:RCcompl} and the fact that for any order $\pi$, the subset $\{\pi_1, \ldots, \pi_{p+1}\}$ includes some majority agent.

We claim that there are at least $p+1$ votes in favor of $a$ in the profile $v$ in any equilibrium. By contradiction, assume that this is not the case. Then there are only two possible cases in which $b$ is selected as an outcome with positive probability.

\noindent \textbf{Case 1:} $v$ is unanimous in favor of $b$. Consider some agent $i$ with type $\theta_a$. If she deviates to $v'_i=a$, then if $\{\pi_1, \ldots, \pi_{p+1}\}$ contains only majority agents, the outcome is a lottery according to Lemma \ref{lemma:RCcompl} and it assigns positive probability to $a$. Thus, such deviation is profitable for agent $i$. It follows that the unanimous profile $v$ in favor of $b$ is not an equilibrium.

\noindent \textbf{Case 2:} There are less than $p+1$ votes for $a$ in the profile $v$. It follows that there is some majority agent $i$ with $v_i=b$. Then, the deviation to $v'_i=a$ is profitable. Indeed, if after such deviation $a$ is the winner of the Voting stage, $a$ is the equilibrium outcome.
If this is not the case, $b$ is the winner of $(v'-i,v_{-i})$. Thus, if some minority agent is in $\{\pi_1,\ldots,\pi_{p+1}\}$, $b$ is the outcome by Lemma \ref{lemma:RCcompl}. However, if only majority agents are in $\{\pi_1,\ldots,\pi_{p+1}\}$, the outcome is the lottery $\beta(v'_i,v_{-i})$. Deviation by $i$ to $v'_i=a$ increases the probability of $a$ in such lottery: assuming that the number of votes for $a$ in $v$ is $n_a$ the probabilities are the following:

    $$\beta_a(v)=\frac{n_a}{n}<\frac{n_a+1}{n}=\beta_a(v'_i,v_{-i}).$$

Thus, we have eliminated all profiles $v$ in which less than $p+1$  agents vote $a$ as potential equilibria and this completes the proof.
\end{proof}

\subsection{Incomplete information }

We now prove that the Majority voting with Random checks implements the majority rule when we relax the assumption of complete information.
For simplicity of the argument we assume that each agent believes that the types of other agents are $i.i.d.$ and assigns probability $q_a$ (resp. $1-q_a$) to each agent being $\theta_a$ (resp. $\theta_b$). Later we show that the $i.i.d.$ assumption can be relaxed without affecting the result. A strategy for an agent $i$ is a mapping $\sigma_i=(\sigma^1_i,\sigma^2_i)$ where $\sigma^1_i:\theta\rightarrow A$ and $\sigma^2_i:\theta \times H_{i-1} \rightarrow \{Y,N\}$ stand for the strategies in each of the stages and $H_{i-1}$ is the set of all possible histories before the Confirmation stage announcement of agent $i$. A first-stage vote of agent $i$, $v^1_i$, is revealing given strategy $\sigma^1_i$ if either $(\sigma^1_i)^{-1}(v^1_i)=\theta_a$ or $(\sigma^1_i)^{-1}(v^1_i)=\theta_b$, in other words, if after observing $v^1_i$ other agents learn the type of agent $i$.

\begin{proposition}\label{pro:MVRCincom}
    Under incomplete information, Majority voting with Random checks implements the majority rule in sequential equilibrium.
\end{proposition}

\begin{proof}
Fix any strategy profile $\sigma^1$, vote profile $v$ and order $\pi$ of agents. Denote by $x$ the majority winner of the Voting stage given $v$ and by $y$ the remaining option.

Consider agent $\pi_{p+1}$ and assume that all Confirmation stage votes prior to her were $N$. Then, the best response of $\pi_{p+1}$ is to vote $Y$ if $x R_{\pi_{p+1}} y$ and $N$ otherwise.

Consider now some agent $\pi_{t}$ and assume that all Confirmation stage votes prior to her were $N$. Her best response is the following:

- $Y$ if $x R_{\pi_{t}} y$ and agent $i$ assigns positive probability to the event that all agents in $\{\pi_{t+1}, \ldots, \pi_{p+1}\}$ prefer $y$ to $x$;

- $N$ if $y R_{\pi_{t}} x$ and agent $i$ assigns positive probability to the event that all agents in $\{\pi_{t+1}, \ldots, \pi_{p+1}\}$ prefer $y$ to $x$;

- $\{Y,N\}$ otherwise.

Note that based on our assumption on prior beliefs, if some agent upon observing $v$ assigns probability 0 to the event that all agents in $\{\pi_{t+1}, \ldots, \pi_{p+1}\}$ prefer $y$ to $x$ then all agents do so. More precisely, this happens only if some agent in $\{\pi_{t+1}, \ldots, \pi_{p+1}\}$ prefers $x$ to $y$ and her Voting stage strategy was revealing. It follows, that in case of non-revealing strategies for agents in $\{\pi_{t+1},\ldots,\pi_{p+1}\}$ agent $\pi_t$ strictly prefers to be truthful, i.e. to announce $Y$ if the winner of $v$ is her preferred option and $N$ otherwise. Thus, we can summarize the outcome of the Confirmation stage as follows.

\begin{lemma}\label{lemma:RCincompl}
    For any strategy profile $\sigma^1$ and Voting stage profile $v$, the sequential equilibrium outcome of the Confirmation stage is:

    - $x$ if $v_i=x$ for all $i \in I$,

    - $x$ if some agent in $\{\pi_1, \ldots, \pi_{p+1}\}$ prefers the winner at $v$,

    -the lottery $\beta(v)$ otherwise.

    \end{lemma}

    Consider the Voting stage of the mechanism, some agent $i \in I$ and some profile $\sigma^1_{-i}$ of strategies of other agents.  We now show that $i$ strictly prefers to vote for her most preferred option.

  Assume w.l.o.g. $a R_i b$. Notice first that there is no $v_{-i}$ for which $i$ strictly prefers to vote $v_i=b$. However, voting $v_i=b$ may be a best response if $i$ is indifferent between voting $a$ or voting $b$ for all possible realizations of types $\theta^n_{-i}$ and votes $v_{-i}$ of other agents given strategies $\sigma^1_{-i}$.

 Consider some realization $\theta^n_{-i}$ and $v_{-i}$ such that the majority preferred option (among all agents including $i$) is not the one getting the most votes in $v_{-i}$. In this case, $i$ strictly prefers to vote $v_i=a$ independently of whether $a$ or $b$ is the majority preferred option. Indeed, when $i$'s vote is the $p+1^{th}$ in favor of $a$, by voting $a$ rather than $b$, she induces the outcome to be $a$ rather than a lottery (if $a$ is the majority preferred option) or a lottery with $a$ being selected with positive probability rather than $b$ (if $b$ is the majority preferred option). Otherwise, the outcome is the lottery $\beta(v)$ for any vote of $i$, so that she strictly prefers to vote $a$.

 If in some strategy profile $\sigma^1_{-i}$, the probability of such event is 0, that is for all possible realizations $\theta^n_{-i}$ and $v_{-i}$ the majority preferred option gets the most votes in $v_{-i}$, voting $b$ is a best response. We now show that no such strategy profile exists.

    Consider some profile $\theta^n_{-i}$ such that $p-1$ agents in $I \setminus \{i\}$ are of type $\theta_a$ and the remaining $p+1$ agents are of type $\theta_b$. This event occurs with positive probability. By assumption, given $\sigma^1_{-i}$, any realization of $v_{-i}$ is such that the majority of agents in $I \setminus i$ vote for $b$ (since $b$ is the majority preferred option). Now consider a different profile $\theta^{n'}_{-i}$ such that $\theta^n_h=\theta^{n'}_h$ for all $h \in I \setminus \{i,j\}$ with agent $j$ being $\theta_b$ in $\theta^n_{-i}$ and $\theta_a$ in $\theta^{n'}_{-i}$. That is, the profile $\theta^{n'}_{-i}$ is such that $a$ is the majority preferred option (since $a R_i b$) and the only difference with $\theta^{n}_{-i}$ is the preference of agent $j$. By assumption, in the profile $\theta^{n'}_{-i}$ for any realization $v_{-i}$ the majority of agents in $I \setminus \{i\}$ vote $a$. Notice, however, that each agent can condition her strategy only on her type since this is the information available to agents at the time of the vote. Thus, for all agents in $I \setminus \{i,j\}$ the probability to vote for $a$ or $b$ remains the same when moving from $\theta^n_{-i}$ to $\theta^{n'}_{-i}$. Thus, the only change in votes occurs for agent $j$. Assume that either when $j$ is of type $\theta_b$ (as in $\theta_{-i}$) or of type $\theta_a$ (as in $\theta'_{-i}$) agent $j$ randomizes, i.e. votes for $a$ and for $b$ with positive probabilities. In this case there is some profile $v_{-i}$ which occurs with positive probability under $\theta^n_{-i}$ and $\theta^{n'}_{-i}$. However, this contradicts the assumption that for any realization of $v_{-i}$  the majority preferred option obtains the majority of the votes. Thus, it must be that agent $j$ votes $a$ when she is of type $\theta_a$ and $b$ when she is of type $\theta_b$: she votes sincerely. Notice that agent $j$ was random so that the same logic applies to any agent in $I \setminus \{i\}$. Thus, $i$ is indifferent between voting $a$ or $b$ only if all other agents are truthful.

    Consider now profile $\theta^n_{-i}$ such that exactly $p$ agents are of type $\theta_a$ and $p$ remaining agents are of type $\theta_b$. Since they are truthful there are $p$ votes for $a$ and $p$ votes for $b$. In this case if $v_i=a$ the outcome is $a$ as prescribed by Lemma \ref{lemma:RCincompl} whereas if $v_i=b$, the outcome is a lottery which assigns positive probability to $b$. Thus, $i$ strictly prefers to be truthful. This completes the proof.
    \color{black}

\end{proof}

Notice that our initial assumption on prior beliefs being $i.i.d.$ was too demanding. If the prior beliefs satisfy the following weaker conditions, the result remains valid:

- Each agent assigns a positive probability to the event $T_a$ (the event where $p$
agents other than $i$ have type $\theta_a$ and $p$ agents have type $\theta_b$);

- For any subset of agents $I' \subset I$ and any agent $j \in I \setminus I'$, for any $x,y \in A$, $x \neq y$, $Pr(\forall i \in I', i \text{ is of type } \theta_x \mid j \text{ is of type } \theta_y)>0$.

\subsection{Abstention}

We now discuss a second extension of the Majority voting with Random checks mechanism where we allow the agents to abstain. The possibility of abstention makes the strategic problem richer. Indeed, the abstention of many agents of the majority type can induce the victory of the minority and make agents indifferent between abstaining or voting for any of the options.\footnote{In one considers the simultaneous majority mechanism, any strategy profile in which all majority agents abstain and two minority agents vote sincerely is a Nash equilibrium irrespective of preference.} In order to deal with abstention, we extend the definition of the mechanism as follows.

\vspace{.2cm}

\noindent \textbf{Timing.}

\noindent \textit{Voting stage:} Each agent $i$ votes for an option or abstains, that is $v_i \in A \cup \emptyset$. The profile of votes $v$ is publicly announced. We call the option which gets most votes in $v$ the winner of the Voting stage. If no agent participates, i.e. $v_i=\emptyset$ for all $i \in I$, the outcome is a lottery which assigns probability 1/2 to each of the options.

\noindent \textit{Confirmation stage:} An order of agents $\pi=(\pi_1, \ldots, \pi_n)$ is selected through an uniform draw (from all the agents independent of whether they participated or abstained in the Voting stage). At each stage $t \in \{1,\ldots,p+1\}$, agent $\pi_t$ announces $Y$ or $N$ or abstains.

At each stage $t$, the mechanism ends if the confirming agent $\pi_t$ announces $Y$ for some $t \in \{1,\ldots,p+1\}$ with the outcome being the winner of the Voting stage. If the two options are tied in the Voting stage the outcome is the lottery which assigns probability 1/2 to each option.

 If all agents in $\{\pi_1, \ldots, \pi_{p+1}\}$ announced $N$ or abstained in Confirmation stage the outcome is a lottery $\beta(v)$, which assigns to each option its share of first-stage votes, so that
$\beta(v)_a=\frac{|\{i \in I \mid v_i=a\}|}{n}$ and $\beta_b(v)=1-\beta_a(v)$.

\begin{proposition}\label{prop:RCabst}
The Majority voting with Random checks subgame perfect implements the majority rule in the presence of abstention.
\end{proposition}

The proof of the result can be found in the Appendix.
As a final comment on this mechanism, observe the existence of the following equilibrium.
Consider a strategy profile where there are two votes for the majority preferred option and all agents announce $Y$. This is a subgame perfect equilibrium for any preference profile. Indeed, no deviation is possible in the Voting stage since the winner is not altered by adding or substracting one vote. In the Confirmation stage, there is always a majority agent among the ones taking part so that she strictly prefers to announce $Y$. Thus, only two initial votes suffice to guarantee that the majority option is elected.

\section{Alternative implementing mechanisms  \label{sec:altmechanisms}}

In this section, we introduce two mechanisms, beyond Majority voting with random checks, that implement the majority rule. The first one, the Bloc formation mechanism, is the first simultaneous mechanism (beyond integer games) that implements the majority rule. The second one, the Verification mechanism, allows agents to verify their vote after an initial vote. Note that both mechanisms are based on the idea of network formation. The final part of the section shows how to redefine Majority voting with random checks as a mechanism with nominations.

\subsection{Bloc formation mechanism  \label{sec:blocformation}}

\subsubsection{Simultaneous blocs\label{simbloc}}

In the Bloc formation mechanism, the message $m_i$ of agent $i$ consists of (1.) a vote for an option $v_i$ and (2.)  a nomination of $p$ agents excluding herself (denoted $c_i$). Formally, the mechanism is denoted $\chi_{BF}: M\rightarrow \Delta$ with, for all $i\in I$, $M_i:=A \times 2_p^{-i}$ where $2_p^{-i}$ denotes the sets of $p$ agents different from $i$ where $|A|=2p+1$.

\vspace{.3cm}

The central notion of this mechanism is the idea of a bloc of agents. A bloc in favor of option $x$ is a majority group of agents, denoted $B$, such that each agent votes for $x$ while only nominating agents in $B$. This can be defined as follows.
\begin{definition}\label{def:bloc}
A set $B$ of agents forms a \textbf{bloc} in favor of option $x$ in the profile $m$ if:
\begin{enumerate}
    \item $|B|\geq p+1$ (majority group),
    \item $v_i=x$ for each $i\in B$ (only votes for $x$),
    \item  $c_i\subset B$ for each $i\in B$ (only nominations in $B$).
\end{enumerate}
\end{definition}
\vspace{.3cm}

The outcome of the Bloc formation mechanism $\chi_{BF}$  depends on whether a bloc forms in the message profile or not. Denote by $B^m$ the set of blocs formed in profile $m$.  By definition, all blocs in a profile (if any) favor the same option since each bloc contains a majority of agents. Therefore, for any profile $m$ in which there is a bloc in favor of option $x$, $\chi_{BF}(m)=x$.

\vspace{.3cm}

\noindent If the profile $m$ does not contain a bloc, the outcome is a lottery over $A$ that depends on $m$. For each option $x\in A$, the weight of $x$ associated to $m$, denoted $\eta^x(m)$, equals:

$$\eta^x(m)=\sum_{i\in I}\eta_{i}(m) \mathbbm{1}\{v_i=x\} \: \text{ with } \eta_i(m)=\frac{|\{j\in I\setminus \{i\} \mid i \in c_j\}|}{np}.$$

To see the logic behind this formula, we let $\eta_i(m)$ be the weight of agent $i$, that is the share of nominations of $i$ in the total nominations $np$. By construction, $\sum_{i\in I}\eta_{i}(m)=1$ for any $m\in M$. When all the other agents nominate $i$, agent $i$ has the maximal possible weight of $\eta_i(m)=\frac{n-1}{np}$ whereas $\eta_i(m)=0$ when none of the other agents nominate $i$.

We thus interpret $\eta^x(m)$  as the sum of the weights of the agents who vote for $x$ so that, by construction, $\eta^a(m)+\eta^b(m)=1$. Notice that the weight $\eta^x(m)$ is strictly increasing in the number of nominations for $x$-agents and, thus, in the number of $x$-agents among nominated agents.

The previous rules of the mechanism can be summarized as follows. For each message profile $m$, the outcome of the Bloc formation mechanism $\chi_{BF}$ coincides with:
$$\chi_{BF}(m)=\begin{cases}
a & \text{if } m \text{ admits a bloc in favor of } a, \\
b & \text{if } m \text{ admits a bloc in favor of } b, \\
\eta(m) & \text{otherwise.}
\end{cases}$$

\medskip

A noteworthy comment on the Bloc formation mechanism deals with its strategic implications. Deciding for which option to vote should be easy. This is the case as we show next. For any agent $i$ with $x R_i y$, any nomination $c_i\in 2^{-i}_p$ and any message $m_{-i}$ of the agents different from $i$, agent $i$ weakly prefers to vote $x$, that is to vote for her most preferred option since:

$$\chi_{BF}(x,c_i,m_{-i})\tilde{R}^{SD}_i\chi_{BF}(y,c_i,m_{-i}).$$

To see why there is a preference of voting honestly, observe that for a given announcement profile of the rest of the agents, the following cases arise. In the case that the outcome is a lottery (i.e. no bloc), this is immediate since she strictly prefers to be sincere. In the case that the agent is part of a bloc, it is always better for an agent to vote for her preferred option (it can create a bloc, prevent its formation or have no impact). Finally, if the profile admits a bloc independently of the agent's behavior, agent $i$'s vote is irrelevant. Similarly, there is a weak preference for nominating agents who voted for one's preferred option.

\subsubsection{Voting profile as a directed graph\label{blocnetwork}}

It is useful to consider blocs in terms of the graph theory. Notice that for any message profile $m=(v,c)$ the nomination profile $c$ creates a directed graph in which the vertices are the agents and the edges their nominations. Formally, for each message profile $m=(v,c)$ denote by $G_{m}=(I,C)$ the directed graph formed by $c$ where the set $I$ of agents coincides with the set of vertices, and $C$ is the adjacency matrix such that $C_{ij}=1$ if $j \in c_i$ and $C_{ij}=0$ otherwise.

We can formulate an option definition of bloc using the adjacency matrix.

\begin{definition}\label{def:blocgraph}
A set $B$ of agents forms a \textbf{bloc} in favor of  option $x$ in profile $m$ if:

1. $|B| \geq p+1$

2. $v_i=x$ $\forall i \in B$ and

3. the restriction of $C$ to set $B$ of agents, denoted $C_B$, is such that $\sum^{|B|}_{h=1} C_{ih}=p$ $\forall i \in B$.
\end{definition}

It follows from Definition \ref{def:blocgraph} that if a set $B$ of agents forms a bloc in favor of $x$ in $m$, then there is no path from any agent $i \in B$ to any agent $j \in I \setminus B$ in the associated graph $G_m$.  It is straightforward that Definition \ref{def:blocgraph} is equivalent to Definition \ref{def:bloc} in which all agents in $B$ vote for the same option and nominate other agents in $J$ exclusively. Firstly, both definitions require at least $p+1$ agents to vote for the same option. To show that $\sum^{|B|}_{h=1} C_{ih}=p$ $\forall i \in B$ is equivalent to agents in $B$ voting for other agents in $B$ exclusively, observe that the row $i$ of the adjacency matrix $C$ gives the nominations of agent $i$. Thus, $\sum^{n}_{h=1} C_{ih}=p$ by definition of the mechanism. Since, according to Definition \ref{def:blocgraph}, $\sum^{|B|}_{h=1} C_{ih}=p$ $\forall i \in B$, $C_{ih}=0$ for all $h \in I \setminus B$, that is no agent $i \in B$ is voting for any agent outside $B$ which proves the equivalence.

We need some additional definitions to formulate the main results regarding blocs.

We say that $G_J$ is a subgraph of a graph $G$ induced by the set $J \subseteq I$ of vertices if it includes all vertices in $J$ and its adjacency matrix $C_J$ is the restriction of $C$ to
$J$ (i.e includes only rows and columns corresponding to vertices in $J$).

\begin{definition}
A subgraph $G_J$ for some $J \subseteq I$ of a graph $G$ is strongly connected if there exists a path in each direction between any pair $i$, $j$ of vertices with $i,j \in J$.
\end{definition}

\begin{definition}
A bloc $B \subseteq I$ in favor of $x$ is effective iff it is strongly connected.
\end{definition}

Figure \ref{fig:blocs} gives two examples of the directed graphs created by the Bloc formation mechanism. The vertices represent the agents, the letters their votes and the arrows show nominations. Figure \ref{subfig:nobloc} presents a profile with no blocs. Indeed, the only possible bloc could involve agents $\{1,2,3\}$ since all vote for $a$ and while the rest vote for $b$. However, agent 1 (resp. agent 3) nominates agent 5 (resp. agent 4), thus, violating the conditions to form a bloc. In Figure \ref{subfig:bloc}, the profile admits two blocs:   $\{1,4,5\}$ and $\{1,2,3,4,5\}$. Indeed, in any of these subsets all agents vote for $b$ and nominate only agents in the bloc. Moreover, only the bloc $\{1,4,5\}$ is strongly connected, thus, effective. Notice that there is no path from agent 4 to agent 2, which prevents $\{1,2,3,4,5\}$ to be an effective bloc.

\begin{figure}[h]
\center
\begin{subfigure}[b]{0.45\textwidth}
\centering
  \includegraphics[width=0.8\textwidth]{Illustr22.png}
  \caption{No blocs.}
  \label{subfig:nobloc}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.45\textwidth}
\centering
     \includegraphics[width=0.8\textwidth]{Illustr12.png}
     \caption{Two blocs, $\{1,4,5\}$ and $\{1,2,3,4,5\}$, in favor of $b$.}
  \label{subfig:bloc}
\end{subfigure}
\caption{Voting profiles formed by the Bloc formation mechanism.}
\label{fig:blocs}
\end{figure}

The next proposition defines some important properties of an effective bloc.

\begin{proposition}\label{prop:effective}
Any profile $m$ of the Bloc formation mechanism admitting a bloc also admits an effective bloc $B^*$. Moreover, the effective bloc $B^*$ is unique and satisfies $B^*=\cap_{B \in B^{m}}B$.
\end{proposition}

\begin{proof}
\textbf{Existence.} Let $m$ be some profile with $B^{m} \neq \emptyset$ and consider w.l.o.g. that all blocs are in favor of $x$. Assume by contradiction that there is no effective bloc $B^*$ in $m$. Therefore, any bloc $B \in B^{m}$ is not effective, thus, not strongly connected. It follows that there are 2 vertices $i,j \in B$ such that there is no path in $G_{m}$ either from $i$ to $j$ or from $j$ to $i$, or both. W.l.o.g. assume that there is no path from $i$ to $j$. It follows that there is a group $B'\subseteq B$ of agents with $i \in B'$ such that there is no path from any agent in $B'$ to agent $j$. Since $B$ is a bloc, it follows that $\forall h \in B'$, $c_h \subset B'$. Thus, $B'$ is a bloc. It follows that if $B$ is a bloc which is not strongly connected, it contains another bloc of smaller size. Thus, since the minimal size of a bloc is $p+1$, for each bloc $B$ which fails to be strongly connected, there is a bloc contained in $B$ which is strongly connected.

\textbf{Uniqueness.} Assume by contradiction that for some profile $m$ there are two non-identical effective blocs $B^*$ and $B^{'*}$. Since each bloc consists of at least $p+1$ agents, $B^* \cap B^{'*} \neq \emptyset$. Thus, there is some agent $i$ such that $i \in B^* \cap B^{'*}$. By definition of a bloc, there is no path from $i$ to any $j \in B^* \setminus (B^* \cap B^{'*})$ since $i\in B^{'*}$. Likewise, there is no path from $i$ to any $h \in B^{'*} \setminus (B^* \cap B^{'*})$. By assumption, blocs $B^*$ and $B^{'*}$ are effective and, thus, strongly connected. It follows that there is a path between any two vertices of an effective bloc, reaching the desired contradiction.

$\boldsymbol{B^*=\cap_{B \in B^{m}}B}$\textbf{.} We have shown that each bloc which is not effective must include an effective bloc. We have also shown that the effective bloc is unique. The claim follows directly from the two observations.
\end{proof}

The previous proposition shows that in any profile $m$ with blocs, the intersection of the blocs is non-empty and is a bloc itself. Moreover, this intersection is strongly connected meaning that there is no agent which can be removed from it in such way that the profile still admits a bloc. This property has an important implication on the strategic behavior, as summarized by the next result: for any profile $m$ admitting a bloc, any agent in the effective bloc has a strategy $m'_i$ that allows her to break all blocs in $m$ (i.e. no bloc in $(m'_i,m_{-i})$).

\begin{proposition}\label{prop:deveffective}
For any profile $m$ admitting a bloc, any agent $i$ in the effective bloc $B^*$ has a strategy $m'_i$ such that $B^{(m'_i,m_{-i})}=\emptyset$.
\end{proposition}

\begin{proof}
Take some $m$ with $B^{m}\neq \emptyset$. W.l.o.g. assume that all blocs in $B^{m}$ are in favor of $x$ and consider some agent $i$ in the effective bloc $B^*$. Notice that since $|B^*| \geq p+1$ and $B^*$ is strictly connected, for any $B \in B^{m}$ and any $j \in B$ there is a path from $j$ to $i$. Consider a deviation $m'_i=(y,c_i)$, that is let agent $i$ to switch and vote for $y$ instead of $x$ while keeping her nominations unchanged. After such deviation, $i$ cannot be a part of a bloc in favor of $x$ since she votes for $y$.

By definition of a bloc, for any bloc $B$ there is no path from the members of the bloc to the agents in $I \setminus B$. However, as stated before, since $i \in B^*$, there is a path to $i$ from any member of any bloc in $B^{m}$. Thus, there is no bloc in favor of $x$ in profile $(m'_i, m_{-i})$.

Notice also that since $B^{m} \neq \emptyset$ and since $c_i$ includes only agents voting for $x$, there can be no bloc in favor of $y$ in $(m'_i,m_{-i})$. Thus, $B^{(m'_i,m_{-i})}=\emptyset$, ending the proof.\end{proof}

\subsubsection{Nash implementation \label{blocnash} }
 The main result of this section is as follows.
\begin{proposition}\label{theorem:CFimpl}The Bloc formation mechanism Nash implements the majority rule.
\end{proposition}
 The formal proof of Proposition \ref{theorem:CFimpl} is included in the Appendix, we give some intuition for it in the next lines.  Let $a$ be the majority preferred option and $b$ the minority one (assume that the majority is uniquely defined for simplicity).

First, it is rather intuitive that an equilibrium selecting $a$ exists. By definition, there are at least $p+1$ such agents. If these agents vote in favor of $a$ and nominate each other, this constitutes a bloc in favor of it and hence an equilibrium. Indeed, no agent within the bloc wants to deviate (she obtains her most preferred outcome) and no agent outside the bloc can alter the outcome (by definition).

Second, suppose that the outcome is a lottery with full support. Since the weight with which each option wins is strictly increasing in the votes it obtains from the agents with positive weight, the agents find it optimal to behave sincerely and vote for their most preferred option. This, in turn, leads to the formation of a bloc in favor of $a$.

Finally, we argue that no bloc can be formed in favor of $b$, the minority option. Assume, by contradiction, that such bloc exists. Then, as shown in \ref{blocnetwork}, an effective bloc exists and includes some majority agent. Then, by Proposition \ref{prop:deveffective} a majority agent - member of the effective bloc can break all the blocs in favor of $b$ in the profile leading to a lottery being the outcome. Such deviation is profitable for a majority agent, contradicting the existence of an equilibrium in which a bloc in favor of $b$ is formed. The next example illustrates the logic of the mechanism on this precise point.

\noindent \textit{Example 2:} The preferences of the agents ($N=\{1,2,3,4,5\}$) are such that $aR_i b$ for $i=1,2,3$ and $bR_ia$ for $i=4,5$ so that $a$ is majority-preferred. Remark that no equilibrium profile admits a bloc in favor of $b$. Indeed, let $m=(c,v)$ be the profile where each agent votes $b$ (i.e. $v_i =b\: \forall i$) and  nominations are as follows: $c_1=4,5$,  $c_2=1,3$, $c_3=1,2$, $c_4=1,5$ and $c_5=1,4$. The profile $m$ admits two blocs:  $\{1,4,5\}$ and $\{1,2,3,4,5\}$. The bloc $\{1,4,5\}$ is the effective one since one cannot find a smaller group that nominate each other while voting $b$. If any agent $i\in\{1,4,5\}$ deviates to $m'_i=(a,c_i)$, the profile $(m'_i,m_{-i})$ admits no bloc and the outcome is a lottery between $a$ and $b$. Since agent 1 prefers $a$ to $b$, she has a profitable deviation and thus the profile $m$ is not an equilibrium.

More generally, take any profile in which a bloc is formed in favor of $b$. Any bloc consists of at least $p+1$ agents, thus, it includes at least one majority agent. Since the effective bloc is included in the rest of the blocs, we can always find a majority agent with a profitable deviation. Thus no bloc in favor of the minority preferred option is possible.

\subsection{Verification mechanism\label{sec:ratverication}}

This final section presents the Verification mechanism. This mechanism, that we denote $\chi_{DV}$, incentivizes the formation of blocs in favor of the majority option and it leads to a lottery in the absence of blocs. The main advantage is that agents are treated symmetrically (all agents vote either once or twice) its main flaw is that other equilibria might involve more than $n$ stages.

In the first stage, agents vote simultaneously for one of the two options. The votes are announced at the end of the stage. In the second stage, agents are asked to ratify the result. If all ratify the result, the outcome is the majority winner of the first stage. If some agent fails to ratify, a verification stage starts. The verification stage asks agents to vote again for one of the two options, this time in a sequentially in an exogenous commonly known order. If at least $p+1$ agents of the ones who voted for the majority winner of the first stage confirm their votes, the outcome is the winner of the first stage.  Otherwise (namely many agents do not confirm their vote), the outcome is a lottery with endogenously determined weights. As we show in the sequel, the $\chi_{DV}$ mechanism admits several equilibria, all of which select the majority preferred option. Among its main advantages, it admits equilibria without verification, that is two-stage equilibria.

A formal definition of the $\chi_{DV}$ mechanism follows. For each arbitrary order $\pi$ of agents, let $\chi_{DV}:M \rightarrow \Delta$ be a mechanism with $m_i=(v^1_i,\omega_i,v^2_i) \in M_i:A\times \{R,V\}\times A$ being the message of agent $i$. While an order of agents is required in stage 3, the equilibrium outcome is order-independent. The game stages are as follows.

\medskip

\noindent \textbf{Timing.}

\noindent \textit{Voting stage}: Each agent simultaneously announces $v^1_i\in A$. Profile $v^1$ is publicly announced at the end of the stage.

\noindent \textit{Ratification stage}: Each agent $i$ simultaneously announces $\omega_i\in \{R,V\}$ to state whether she ratifies the outcome ($R$) or wants a verification ($V$).
If all ratify, the outcome is the majority winner in the profile $v^1$.
Profile $\omega$ is publicly announced at the end of the stage. If some agent votes $V$, stage 3 starts.

\noindent \textit{Verification stage}: Each agent $i$ sequentially announces $v^2_i \in A$ according to the order $\pi$ knowing announcements $v^2_{\pi_1},v^2_{\pi_2},\ldots,v^2_{\pi_{i-1}}$ of the predecessors.

\medskip

\noindent The outcome of the Verification mechanism $\chi_{DV}$ for each message profile $m$ is as follows.

\noindent A. If all agents ratify the voting outcome in stage 2, the outcome is the majority winner of the voting profile $v^1$.

\noindent B. If some agent asks for a verification in stage 2, the outcome depends on the votes in Stage 3.

\noindent B.1. If there is a bloc in favor of some option $x$, then $x$ is selected. A bloc in favor of option $x$ is formed in $m$ if there is a set $J$ of at least $p+1$ agents with $v^1_j=x$ and $v^2_j=x$ $\forall j \in J$. That is, a bloc in favor of $x$ consists of a majority of agents voting twice for $x$.

\noindent B.2. In the absence of a bloc in the profile $m$, the outcome is a lottery $\beta$ over $A$. For each profile $m$, let $s_a(m)=|\{j \in I \mid v^1_j=a\}|$ be the  votes for $a$ in  stage 1 and $\phi_a(m)=|\{j \in I \mid v^2_j=a\}|$  be the votes for $a$ in  stage 3. In this case, the outcome of the profile $m$ is:

\begin{enumerate}
    \item $a$ if $s_a(m)=n$ or $\phi_a(m)=n$ and $s_a(m)>0$,
    \item $b$ if $s_b(m)=n$ or $\phi_b(m)=n$ and $s_b(m)>0$,
    \item otherwise is a lottery $\beta(m)$ with probabilities:\end{enumerate}

\begin{equation}\label{eq:proba}
    \beta_a(m)=\frac{\phi_a(m)\frac{s_a(m)}{s_b(m)}}{\phi_a(m)\frac{s_a(m)}{s_b(m)}+\phi_b(m)\frac{s_b(m)}{s_a(m)}} \: \textrm{ and }\beta_b(m)=1-\beta_a(m).
\end{equation}

Remark that the probability $\beta_a(m)$ is strictly increasing in $s_a(m)$ and in $\phi_a(m)$ and strictly decreasing in $s_b(m)$ and in $\phi_b(m)$. This probability being increasing plays a key role in the sequel since, whenever the outcome is a lottery, an agent has a strict incentive to vote sincerely.

Figure \ref{fig:VV} illustrates the outcome of the verification $\chi_{DV}$ mechanism when preferences are given by $aR_i b$ for $i=1,2$ and $bR_3 a $. Figure \ref{fig:VV}(a) and Figure \ref{fig:VV}(b) consider Voting stage announcements $v^1=(b,b,a)$ and $\widehat{v}^1=(a,b,a)$ correspondingly. The subgame perfect outcome equals $(\frac{1}{3}a,\frac{2}{3}b)$ (since $s_a(m)=1$ and $\phi_a(m)=2$) and $(\frac{8}{9}a,\frac{1}{9}b)$ (since $s_a(m)=2$ and $\phi_a(m)=2$). Observe that the probability of $a$ in the outcome increases when the first-stage profile $v^1$ is replaced by the profile $\widehat{v}^1$, which is caused by the monotonicity of the lottery in (\ref{eq:proba}) with respect to the number of votes for $a$ in the first-stage profile.

\begin{figure}[h]
\center
\begin{subfigure}[b]{0.45\textwidth}
\tikzset{every picture/.style={line width=0.75pt}}

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]

\draw   (337,90.25) .. controls (337,88.18) and (338.68,86.5) .. (340.75,86.5) .. controls (342.82,86.5) and (344.5,88.18) .. (344.5,90.25) .. controls (344.5,92.32) and (342.82,94) .. (340.75,94) .. controls (338.68,94) and (337,92.32) .. (337,90.25) -- cycle ;
\draw   (417,170.25) .. controls (417,168.18) and (418.68,166.5) .. (420.75,166.5) .. controls (422.82,166.5) and (424.5,168.18) .. (424.5,170.25) .. controls (424.5,172.32) and (422.82,174) .. (420.75,174) .. controls (418.68,174) and (417,172.32) .. (417,170.25) -- cycle ;
\draw   (257,170.25) .. controls (257,168.18) and (258.68,166.5) .. (260.75,166.5) .. controls (262.82,166.5) and (264.5,168.18) .. (264.5,170.25) .. controls (264.5,172.32) and (262.82,174) .. (260.75,174) .. controls (258.68,174) and (257,172.32) .. (257,170.25) -- cycle ;
\draw   (456,231.25) .. controls (456,229.18) and (457.68,227.5) .. (459.75,227.5) .. controls (461.82,227.5) and (463.5,229.18) .. (463.5,231.25) .. controls (463.5,233.32) and (461.82,235) .. (459.75,235) .. controls (457.68,235) and (456,233.32) .. (456,231.25) -- cycle ;
\draw   (376,231.25) .. controls (376,229.18) and (377.68,227.5) .. (379.75,227.5) .. controls (381.82,227.5) and (383.5,229.18) .. (383.5,231.25) .. controls (383.5,233.32) and (381.82,235) .. (379.75,235) .. controls (377.68,235) and (376,233.32) .. (376,231.25) -- cycle ;
\draw   (216,231.25) .. controls (216,229.18) and (217.68,227.5) .. (219.75,227.5) .. controls (221.82,227.5) and (223.5,229.18) .. (223.5,231.25) .. controls (223.5,233.32) and (221.82,235) .. (219.75,235) .. controls (217.68,235) and (216,233.32) .. (216,231.25) -- cycle ;
\draw   (296,231.5) .. controls (296,229.43) and (297.68,227.75) .. (299.75,227.75) .. controls (301.82,227.75) and (303.5,229.43) .. (303.5,231.5) .. controls (303.5,233.57) and (301.82,235.25) .. (299.75,235.25) .. controls (297.68,235.25) and (296,233.57) .. (296,231.5) -- cycle ;
\draw [line width=3]    (340.75,90.25) -- (260.75,170.25) ;
\draw    (340.75,90.25) -- (420.75,170.25) ;
\draw [line width=3]    (260.75,170.25) -- (219.75,231.25) ;
\draw    (260.75,170.25) -- (299.75,231.5) ;
\draw [line width=3]    (420.75,170.25) -- (379.75,231.25) ;
\draw    (420.75,170.25) -- (459.75,231.25) ;
\draw    (219.75,231.25) -- (195,289.5) ;
\draw    (299.75,231.5) -- (275,289.75) ;
\draw    (379.75,231.25) -- (355,289.5) ;
\draw    (459.75,231.25) -- (435,289.5) ;
\draw [line width=3]    (219.75,231.25) -- (244,291.5) ;
\draw [line width=3]    (299.75,231.5) -- (324,291.75) ;
\draw [line width=3]    (379.75,231.25) -- (404,291.5) ;
\draw [line width=3]    (459.75,231.25) -- (484,291.5) ;

\draw (331,69) node [anchor=north west][inner sep=0.75pt]   [align=left] {1};
\draw (249,144) node [anchor=north west][inner sep=0.75pt]   [align=left] {2};
\draw (414,146) node [anchor=north west][inner sep=0.75pt]   [align=left] {2};
\draw (202,209) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (294,209) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (361,210) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (456,211) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (293,105.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (231,181.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (193,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (274,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (352,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (433,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (386,181.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (379,102.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (281,178.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (441,178.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (237,244.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (317,244.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (396,244.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (477,244.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (188,295.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (482,295.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (228,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\boldsymbol{\frac{1}{3} a,}\\
\boldsymbol{\frac{2}{3} b}
\end{array}$};
\draw (262,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{1}{3} a,\\
\frac{2}{3} b
\end{array}$};
\draw (308,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{1}{9} a,\\
\frac{8}{9} b
\end{array}$};
\draw (342,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{1}{3} a,\\
\frac{2}{3} b
\end{array}$};
\draw (388,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{1}{9} a,\\
\frac{8}{9} b
\end{array}$};
\draw (422,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{1}{9} a,\\
\frac{8}{9} b
\end{array}$};

\end{tikzpicture}
\caption{$v^1=(b,b,a)$}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.45\textwidth}
\tikzset{every picture/.style={line width=0.75pt}}

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]

\draw   (337,90.25) .. controls (337,88.18) and (338.68,86.5) .. (340.75,86.5) .. controls (342.82,86.5) and (344.5,88.18) .. (344.5,90.25) .. controls (344.5,92.32) and (342.82,94) .. (340.75,94) .. controls (338.68,94) and (337,92.32) .. (337,90.25) -- cycle ;
\draw   (417,170.25) .. controls (417,168.18) and (418.68,166.5) .. (420.75,166.5) .. controls (422.82,166.5) and (424.5,168.18) .. (424.5,170.25) .. controls (424.5,172.32) and (422.82,174) .. (420.75,174) .. controls (418.68,174) and (417,172.32) .. (417,170.25) -- cycle ;
\draw   (257,170.25) .. controls (257,168.18) and (258.68,166.5) .. (260.75,166.5) .. controls (262.82,166.5) and (264.5,168.18) .. (264.5,170.25) .. controls (264.5,172.32) and (262.82,174) .. (260.75,174) .. controls (258.68,174) and (257,172.32) .. (257,170.25) -- cycle ;
\draw   (456,231.25) .. controls (456,229.18) and (457.68,227.5) .. (459.75,227.5) .. controls (461.82,227.5) and (463.5,229.18) .. (463.5,231.25) .. controls (463.5,233.32) and (461.82,235) .. (459.75,235) .. controls (457.68,235) and (456,233.32) .. (456,231.25) -- cycle ;
\draw   (376,231.25) .. controls (376,229.18) and (377.68,227.5) .. (379.75,227.5) .. controls (381.82,227.5) and (383.5,229.18) .. (383.5,231.25) .. controls (383.5,233.32) and (381.82,235) .. (379.75,235) .. controls (377.68,235) and (376,233.32) .. (376,231.25) -- cycle ;
\draw   (216,231.25) .. controls (216,229.18) and (217.68,227.5) .. (219.75,227.5) .. controls (221.82,227.5) and (223.5,229.18) .. (223.5,231.25) .. controls (223.5,233.32) and (221.82,235) .. (219.75,235) .. controls (217.68,235) and (216,233.32) .. (216,231.25) -- cycle ;
\draw   (296,231.5) .. controls (296,229.43) and (297.68,227.75) .. (299.75,227.75) .. controls (301.82,227.75) and (303.5,229.43) .. (303.5,231.5) .. controls (303.5,233.57) and (301.82,235.25) .. (299.75,235.25) .. controls (297.68,235.25) and (296,233.57) .. (296,231.5) -- cycle ;
\draw [line width=3]    (340.75,90.25) -- (260.75,170.25) ;
\draw    (340.75,90.25) -- (420.75,170.25) ;
\draw [line width=3]    (260.75,170.25) -- (219.75,231.25) ;
\draw    (260.75,170.25) -- (299.75,231.5) ;
\draw [line width=3]    (420.75,170.25) -- (379.75,231.25) ;
\draw    (420.75,170.25) -- (459.75,231.25) ;
\draw    (219.75,231.25) -- (195,289.5) ;
\draw    (299.75,231.5) -- (275,289.75) ;
\draw    (379.75,231.25) -- (355,289.5) ;
\draw    (459.75,231.25) -- (435,289.5) ;
\draw [line width=3]    (219.75,231.25) -- (244,291.5) ;
\draw [line width=3]    (299.75,231.5) -- (324,291.75) ;
\draw [line width=3]    (379.75,231.25) -- (404,291.5) ;
\draw [line width=3]    (459.75,231.25) -- (484,291.5) ;

\draw (331,69) node [anchor=north west][inner sep=0.75pt]   [align=left] {1};
\draw (249,144) node [anchor=north west][inner sep=0.75pt]   [align=left] {2};
\draw (414,146) node [anchor=north west][inner sep=0.75pt]   [align=left] {2};
\draw (202,209) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (294,209) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (361,210) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (456,211) node [anchor=north west][inner sep=0.75pt]   [align=left] {3};
\draw (293,105.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (231,181.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (193,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (274,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (352,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (433,247.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (386,181.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (379,105.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (281,178.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (441,178.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (237,244.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (317,248.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (396,244.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (477,244.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (188,295.4) node [anchor=north west][inner sep=0.75pt]    {$a$};
\draw (482,295.4) node [anchor=north west][inner sep=0.75pt]    {$b$};
\draw (228,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\boldsymbol{\frac{8}{9} a,}\\
\boldsymbol{\frac{1}{9} b}
\end{array}$};
\draw (262,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{8}{9} a,\\
\frac{1}{9} b
\end{array}$};
\draw (308,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{2}{3} a,\\
\frac{1}{3} b
\end{array}$};
\draw (342,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{8}{9} a,\\
\frac{1}{9} b
\end{array}$};
\draw (388,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{2}{3} a,\\
\frac{1}{3} b
\end{array}$};
\draw (422,295.4) node [anchor=north west][inner sep=0.75pt]  [font=\small]  {$ \begin{array}{l}
\frac{2}{3} a,\\
\frac{1}{3} b
\end{array}$};

\end{tikzpicture}
\caption{$\widehat{v}^1=(a,b,a)$}
\end{subfigure}
\caption{Verification stage outcome of $\chi_{DV}$ with order of play 1,2,3. \small{Bold indicates the best response of each agent at each node.}}
\label{fig:VV}
\end{figure}

We now analyse the equilibrium behavior under the $\chi_{DV}$ mechanism under complete and incomplete information.

\subsubsection{Complete information}

Before describing the equilibria of the game, we define the strategies of the agents. For each agent $i$ the strategy is $\sigma_i=(\sigma^1_i, \sigma^2_i, \sigma^3_i)$ with $\sigma^1_i: \theta^n \rightarrow A$, $\sigma^2_i:\theta^n \times A^n \rightarrow \{R,V\}$ and  $\sigma^3_i: \theta^n \times H_{i-1} \rightarrow A$ where $H_{i-1}=\{(v^1,\omega,v^2_{\pi_1},..,v^2_{\pi_{i-1}})\in A^n \times \{R,V\}^n \times A^{i-1}\}$ is the set of all possible histories before the vote of agent $i$ in stage 3, with generic element $h_{i-1}$.

The next example illustrates how the Verification mechanism works.

\noindent \textit{Example 3}: Preferences are given by $aR_i b$ for $i=1,2,3$ and $b R_i a$ for $i=4,5$. Let $\sigma$ be the strategy profile defined as follows:
\begin{center}for $i=1,2,3$, $\sigma_i^1=a$, \:
$\sigma_i^2=\begin{cases}
			R, & \text{if } Maj(v^1)=a\\
            V, & \text{otherwise}
		 \end{cases}$ and $\sigma_i^3=a$ for any $h_{i-1}$.\\
for $i=4,5$, \: \: $\sigma_i^1=b$, \:
$\sigma_i^2=\begin{cases}
			R, & \text{if } Maj(v^1)=b\\
            V, & \text{otherwise}
		 \end{cases}$ and $\sigma_i^3=b$ for any $h_{i-1}$.
\end{center}
Notice that $\sigma_i^3$ assumed is truthful for each $i$ (in line with Lemma \ref{lemma:verif}). The profile $\sigma$ is an equilibrium that generates the bloc $\{1,2,3\}$ in favor of $a$. Agents 1,2,3 obtain their most preferred option in this profile and hence have no profitable deviation. Agents 4,5 have no profitable deviation either: none of their deviations can lead to an outcome different from $a$, due to the existence of a bloc.

Consider now the profile $\hat{\sigma}$ that leads to the election of $b$ since every agent votes for $b$ on the equilibrium path.
\begin{center}
 for $i=1,2,3,4,5$, $\hat{\sigma}_i^1=b$, \:
$\hat{\sigma}_i^2=R$ for any $v^1$ and \:
$\hat{\sigma}_i^3=\begin{cases}
			a, & \text{ if } a R_i b \text{ and } v^1 \neq (b,b,b,b,b)\\
			b, & \text{ if } a R_i b \text{ and } v^1= (b,b,b,b,b) \text{ or } b R_i a.\\
		 \end{cases}$.
\end{center}

The profile $\hat{\sigma}$ is not an equilibrium. In stage 1, if agent $1$ deviates to:

\begin{center}$\gamma^1_1=a$,
$\gamma_1^2=\begin{cases}
			R, & \text{if } Maj(v^1)=a\\
            V, & \text{otherwise}
            \end{cases}$ and $\gamma_1^3=a$ for any history,
            \end{center}
this leads to a lottery between $a$ and $b$. Indeed, by deviating to $\gamma^1_1=a$, the outcome corresponding to the stage 3 is the one associated to truth-telling so that $a$ wins with probability $\frac{3(\frac{1}{4})}{3(\frac{1}{4})+2(\frac{4}{1})}=\frac{3}{35}$ and $b$ with probability $\frac{32}{35}$ (since $s_a(m)=1$ and $\phi_a(m)=3$). This is a profitable deviation for agent 1, proving that $\hat{\sigma}$ is not an equilibrium.

\begin{proposition}

  \label{th:verication}
For any order of the agents in the verification stage,
the Verification mechanism  subgame perfect implements the majority rule and admits equilibria where no verification is required. \end{proposition}

The proof shows that the unique outcome of the game is the majority preferred option, building on the result of Lemma \ref{lemma:verif} (in the appendix) according to which the equilibrium outcome of the verification stage for any profile $v^1$ is unique and is equivalent to the one induced by truth-telling.

\begin{proof}

Lemma \ref{lemma:verif} shows that the unique SPE outcome of the Verification stage is the outcome of truth-telling. We now consider the earlier stages of the mechanism to complete the proof of the proposition.

\noindent \textbf{ A. Ratification stage}

At this stage, an agent's decision is rather simple. She strictly prefers verifying if she anticipates that the outcome is better than at the Voting stage. Note that if the outcome after verification remains unchanged, the agent is indifferent at the Ratification stage.

\noindent \textbf{B. Voting stage}

We now consider the first stage of the mechanism, letting $a$ denote the majority preferred option.
There are 2 possible cases: either less than $p+1$ majority agents vote for $a$ in the first stage (B.1) or and at least $p+1$ majority agents do so (B.2).

\noindent \textbf{Case B.1: } If the profile $v^1$ is unanimous in favor of $b$, the outcome is $b$.
If the profile $v^1$ is not unanimous in favor of $b$, as established in A., the second-stage SPE outcome is equivalent to the one under truth-telling. Thus the SPE outcome is a lottery with all majority agents announcing $a$ and all minority agents announcing $b$. Consider now a deviation $\hat{v}^1_i=a$ by a majority agent who voted $b$ in the first stage before ($v^1_i=b$). Given the SPE of the second stage, after such deviation there is either a bloc in favor of $a$ if this agent is the $p+1^{th}$ majority agent to vote $a$ in the first stage, or a lottery where the probability of $a$ strictly increases  according to equation (\ref{eq:proba}). Thus, this deviation is strictly profitable. Therefore, the first-stage profile in which less than $p+1$ majority agents vote $a$ can not be part of a SPE equilibrium.

\noindent  \textbf{Case B.2: } There are at least $p+1$ majority agents who vote for $a$ in the first stage. Assume first that the profile $v^1$ is unanimous in favor of $a$. If $v^1_i=a$ for all $i \in I$, it is an equilibrium. Indeed, by deviating to $\hat{v}^{1}_j=b$ any minority agent $j$ is not changing the outcome given that the outcome of the verification stage is equivalent to the one under truth-telling and the remaining agents ($n-1$) vote for $a$ in the first stage. If the profile $v^1$ is not unanimous, the second-stage SPE outcome is $a$ with a bloc of majority agents being formed in favor of $a$. Each of the majority agents has no profitable deviation since $a$ is their preferred option. No minority agent's deviation can prevent the bloc in favor of $a$. Thus, the described profile is an equilibrium and  $a$ is the only equilibrium outcome.
\end{proof}

\subsubsection{Incomplete information \label{sec:incomplete}}

We now extend the implementation result of the Verification mechanism to an incomplete information setting. We assume that each agent believes that the types of other agents are $i.i.d.$ and assigns probability $q_a$ (resp. $1-q_a$) to each agent being $\theta_a$ (resp. $\theta_b$). Notice that the $i.i.d.$ assumption can be relaxed for the same reasons as discussed in the analysis of the Majority voting with Random checks. A strategy for an agent $i$ is a mapping $\sigma_i=(\sigma^1_i,\sigma^2_i)$ where $\sigma^1_i:\theta\rightarrow A$ and $\sigma^2_i:\theta \times H_{i-1}\rightarrow A$ stand for the strategies in each of the steps and $H_{i-1}$ is defined as in the complete information case. We denote the message profile by $m=(v^1,v^2) \in M=A^{|I|} \times A^{|I|}$. A first-stage message of agent $i$, $v^1_i$, is revealing given strategy $\sigma^1_i$ if either $(\sigma^1_i)^{-1}(v^1_i)=\theta_a$ or $(\sigma^1_i)^{-1}(v^1_i)=\theta_b$, in other words, if after observing $v^1_i$ other agents learn the type of agent $i$.

The proof is relatively similar to the one under complete information: we first prove that the only sequential equilibrium outcome of the verification stage is the one generated by truth-telling (Lemma \ref{le:truth} in the appendix) and then, by backward induction, prove the claim for the whole game.

\begin{proposition}\label{prop:Ta}
Under incomplete information, the Verification mechanism  implements the majority rule in sequential equilibria.
\end{proposition}
\begin{proof}
We now show that every agent strictly prefers to be sincere in the first stage.

W.l.o.g. take agent $1$ with type $\theta_a$ and let $\sigma_{-1}$ denote the strategy of her opponents. Recall that agent $1$ weakly prefers to be sincere in the first stage. It suffices to prove that there is some event where agent 1 strictly prefers to be sincere and that this event arises with positive probability. If this is the case, then $\textbf{SD}$ implies that agent 1 strictly prefers to be sincere in the first stage.

Let $T_a$ be the event where $p$
agents have type $\theta_a$ and $p$ agents have type $\theta_b$, all different from agent 1. Agent $1$ assigns to the event $T_a$ probability $\pi_a>0$ where $\pi_a=C^{n-1}_{p}(q_a)^p (1-q_a)^{p}$.

Moreover, if the event $T_a$ arises, no bloc can be formed without agent 1 being part of it. Indeed, as shown by Lemma \ref{le:truth}, the outcome of the verification stage is equivalent to the one under truth-telling. Moreover, by definition, the formation of a bloc requires at least $p+1$ agents voting equally in the voting and in the verification stage. However, exactly $p$ of them have type $\theta_a$ and exactly $p$ of them have type $\theta_b$. W.l.o.g we can assume that the former agents vote $a$ in the verification stage while the latter ones vote $b$ due to Lemma \ref{le:truth}. Therefore, we have two cases to describe the vote of agent 1: either agent 1 is part of a bloc in favor of $a$ or no bloc is formed.

In the first case, agent 1 strictly prefers to report her type ensuring that her best option is implemented. In the second case, no bloc is formed so that the outcome is a lottery: again, she strictly prefers to report her type since the weight of $a$ is strictly increasing in the number of votes obtained in the first stage.\end{proof}

\subsection{Random Checks mechanism as a network formation game}

The Random checks mechanism presented in Section 3 requires the agents to vote for an option and to agree or disagree with the outcome afterwards unlike the later mechanisms which rely on a network formation game through nominations. In this section we show how the Random checks mechanism can be reformulated to include the network formation at the Confirmation stage. The results presented in Propositions \ref{pro:MVRCcom} and \ref{pro:MVRCincom} hold under this alternative formulation.

\vspace{.2cm}

\noindent \textbf{Timing.}

\noindent \textit{Voting stage:} Each agent $i$ votes for an option $v_i \in A$. The profile of votes $v$ is publicly announced. We call the option which gets most votes in $v$ the majority option and the other the minority option for given profile $v$.

\noindent \textit{Nomination stage:} An order of agents $\pi=(\pi_1, \ldots, \pi_n)$ is selected through an uniform draw. At each stage $t \in \{1,\ldots,p+1\}$, agent $\pi_t$ nominates $p$ other agents, denoted $c_{\pi_t}$.

At each stage $t$, the mechanism ends if the nominating agent $\pi_t$ announces $Y$. Otherwise, the mechanism proceeds to stage $t+1$ and the next agent nominates. Formally, at each stage $t$:
\begin{enumerate}
\item if $v_{\pi_t}=v_j$ for all $j\in c_{\pi_t}$, a \textit{bloc} in a favor of $v_{\pi_t}$ is formed by $\{\pi_t,c_{\pi_t}\}$ and $v_{\pi_t}$ is the outcome;
 \item if $v_{\pi_t} \neq v_j$ for at least some $j \in c_{\pi_t}$, the stage $t+1$ starts.
\end{enumerate}

If no bloc is formed after the nominations of the $p+1$ agents, the outcome is the lottery $\beta(v)$ based on profile $v$ defined in the same way as for the main formulation of the mechanism in Section 3.

\section{Conclusion \label{sec:conclusion}}

We have considered the implementation of the majority rule in a preference aggregation setting through several mechanisms. The key idea of this work is that introducing lotteries in the mechanisms removes the undesirable equilibria widespread in the voting literature and helps design shorter mechanisms. Lotteries allow agents to be pivotal more often, while, in all of the considered mechanisms, lotteries do not arise in equilibrium so that the socially desirable option is always selected. We leave it to future empirical research to determine to which extent the proposed mechanisms outperform the classic voting procedures.
Finally, some of our proposals consider voting as a network formation game; this deserves further investigation in the context of implementation and coalition formation.
\bibliographystyle{aer}

redpajama_set_name: RedPajamaArXiv


text:
Q: Italics in the function 'plotweb', bipartite package R I made a visualisation of a bipartite network using the function 'plotweb' from the bipartite package. Now I want to put the labels in italics (species names).
plotweb(datamatrix)

I can't find any useful command in the help tab for this function. Other suggestions?

A: Unfortunately, bipartite::plotweb doesn't seem to allow an argument like font = 3, which in graphics::par stands for italic font.
Here I suggest two solutions:
1 - Transform all text to italic with par(font = 3)
One way to get the desired italic font could be to force all the font of the graphical device to italic:
library(bipartite)

par(font = 3)
data(Safariland)
plotweb(Safariland)

When done with a graph and moving to another, you can run dev.off() to switch graphical parameters to their default original values. Or save the default par and rewrite when needed:
dpar <- par()

par(font = 3)
data(Safariland)
plotweb(Safariland)

par(dpar)

2 - Transform the plot to a gTree object and edit only what you need (grid package ideology)
You can transform the plot generated by plotweb to a gTree object. A gTree acts as a container list of many grid graphical objects/components ("grobs").
However, this solution is far more verbose and convoluted. The advantage is that you can do almost any fine tuning you wish.
library(bipartite)
library(gridGraphics)

data(Safariland)

# Creates a gTree object from the "usual" plot generated by `plotweb`
my_gTree <- grid.grabExpr(grid.echo(function() plotweb(Safariland)))
# View the structure of the newly created gTree object
View(my_gTree)

# Example of editing the font of the text grobs in the range 28-36,
# that is, the bottom labels (use regular expression)
my_gTree <- editGrob(grob = my_gTree,
                     gPath = "graphics-plot-1-text-2[8-9]|3[0-6]",
                     gp = gpar(font = 3L),
                     grep = TRUE,
                     global = TRUE)
# Plot the edited graph
grid.newpage(); grid.draw(my_gTree)

If you wish, you can save it with ggplot2::ggsave()
library(ggplot2)
ggsave(filename = "plotweb-grid-version-trial.png", plot = my_gTree)

If you want to edit a particular label, you can try:
my_gTree[["children"]][["graphics-plot-1-text-1"]][["gp"]][["font"]] <- 3L

Further more, if you want to match certain grob label by species name, then you could do something like below, where I only change to italics the species "Aristotelia chilensis" & "Schinus patagonicus". Unfortunately, it gets convoluted, but it proves the fine tuning that can be done with the grid package:
# Get all grobs referring to species labels
label_grobs <- getGrob(gTree = my_gTree,
                       gPath = "graphics-plot-1-text-.*",
                       grep = TRUE,
                       global = TRUE)
# Get the species labels
sp <- rep(NA_character_, length(label_grobs))
for (i in 1:length(label_grobs)){
  sp[i] <- label_grobs[[i]][["label"]]
}
# Edit only those grobs of desired species
sp_idx <- which(sp %in% c("Aristotelia chilensis", "Schinus patagonicus"))
for (i in sp_idx){
  grob_char <- paste0("graphics-plot-1-text-", i)
  my_gTree[["children"]][[grob_char]][["gp"]][["font"]] <- 3L
}
# display and save the edited gTree
grid.newpage(); grid.draw(my_gTree)
ggsave(filename = "plotweb-grid-edit-by-species.png", plot = my_gTree)

redpajama_set_name: RedPajamaStackExchange


text:
Grundy County IAGenWeb
Genealogy &
You Are Here > Home > Churches > Westfriesland Presbyterian Church
Family Pages
Land and Locations
Lookups/Volunteers
Westfriesland Church
Westfriesland Church Has 75th Anniversary Sept. 17
Plans Complete For Diamond Jubilee On Friday, Sept. 17th; Church Has Had Six Pastors
Westfriesland Presbyterian church in German township, Grundy county, will observe its 75th anniversary on Friday of this week with fitting services for this happy occasion. There will be services in the forenoon, afternoon and evening. All members of the church, former members living elsewhere, and others will join together in a day of joy and reverence.
Organized in 1873
The Westfriesland church was organized in 1873. The early records of the church were later destroyed by fire and it is not definitely known who the organizing proponents were. Rev. J. E. Drake, who for many years was pastor of the Colfax Presbyterian church, expresses the belief that the leaders in the organization were Rev. Vander Las, John Arends and Adrian Van Vliet. Rev. John Arends was the first pastor who appears to have worked towards the organization of the Westfriesland church two years before the organization was completed in 1873. There were 35 families who became members of the organization in 1873. The first church building was not completed until the following year.
The first minutes dated Jan. 3, 1874, appear definitely to be of the first annual congregational meeting of the Westfriesland Presbyterian congregation.
John Arends was the moderator, and Jacob Kallemyn was the secretary. These first minutes reveal a motion set forth to drop (to laten fallen) Westfriesland Presbyterian Kerk and to adopt (aantememen) the name of Second Presbyterian Church of German Township, Grundy County, Iowa. Rev. John Arends was chosen as a one-man committee to have the church incorporated under the name of the "Second Presbyterian Church of German Township, Grundy County, Iowa; Postoffice, Ackley, Hardin County, Iowa." However, later the name was officially changed again to "Westfriesland" in 1897 and incorporated in 1898.
Bought 2 Acres Of Ground For $50
The minutes of the first congregational meeting show that two acres of ground were purchased from Hendrick DeVries for $50 on which the church was built, a cemetery ground provided and on which later a parsonage was erected.
The first church building was remodeled and enlarged in 1908. In 1924 a small tornado tore down the spire and the present front of the building was erected.
Church Has Had 6 Pastors
Westfriesland has had six pastors during its 75-year history. Longest to serve was Rev. Henry Johnson who was the directing head of this church for 23 years. He is the only former pastor still living. Names of pastors and their years of service are given below:
John K. Arends, 1873-1880
Godfrey Moery, 1880-1884
L. Kliebenstein, 1884-1905
J. J. Agena, 1905-1920
Henry Johnson, 1921-1944
Peter H. Eekhoff, 1944-
In a Church-Going Neighborhood
Westfriesland church was erected in a community of church-going people. There are more rural churches in German and Pleasant Valley townships than in all other townships in Grundy county. The folks up there all are members of some church and they all attend regularly. That part of the county was among the earliest to receive pioneer settlers, partly due to the early coming through of the railroad and because of the richness of the soil. The pioneers who came remained there. Many who are now in the seventies and up to the nineties still reside on farms there or in nearby towns of Wellsburg, Ackley and Aplington. Their descendants remained to follow in the footsteps of their forebears and they are carrying on well their traditions. Nearly all of them are of German or Netherlands descent still services in the many churches during the early years were carried on in the language of the fatherland of the members. Gradually services in the churches adopted the standard language of this country.
Growth in Membership
Because of the many churches established within a small area in the northwest portion of Grundy county, the membership in all of them had to be limited. Westfriesland which began with a membership of 35 now has 140.
Present Church Remodeled
The present church building was remodeled during Rev. Johnson's ministry in 1941. A full basement was completed under the church for a heating system and a kitchen and dining room. The old building was raised and a 16-foot extension was added to the north. New hardwood floors were laid and the auditorium of the church received a new ceiling.
Hammond Electric Organ
A new Hammond electric organ was installed in December 1946. Mrs. Lester Neymeyer is the organist and Mrs. Elmer Younker is her assistant.
Church Societies
Westfriesland church is blessed with earnest and efficient societies.
The Ladies' Aid Society was organized Nov. 10, 1921, and they have been giving their church most helpful service ever since. There are at present 20 members of this organization. There are three charter members. They are Mrs. M. K. Huesman, Mrs. Arend K. Arends and Mrs. Will K. Harken.
The Christian Endeavor Society dates back to 1908. Rev. Agena was the first president, C. H. Ulfers the first treasurer and H. E. Deters, secretary. The Society has been functioning continuously since its organization. It now has 19 members.
All Attend Sunday School
Practically all members of the church attend Sunday school services regularly.
Golden Hour Circle
Latest of the Societies of this church is the Golden Hour Circle which was organized in January 1947. There are now 13 members.
The Quartette is a popular organization who are called upon frequently to assist in social functions in the church. Members of the organization are Jans Huesman, Donald Snittjer, John L. Meyer and John V. Janssen. Mrs. Lester Neymeyer is the accompanist.
The volunteer choir with 21 voices is also a popular organization which participates in regular services and on special occasions.
--The Grundy Register (Grundy Center, Iowa), 16 September 1948
W. Friesland Church Records Destroyed by Fire in '70s
No definite date can be set for the organization of the West Friesland Presbyterian Church of Ackley, for when the farm home of the first pastor, the Rev. John K. Arends, was destroyed by fire, the records of the church were destroyed with it.
Most historical sources give the date of its beginning as 1873. It was once called the Second German Presbyterian Church of German Township, Grundy County, after the congregation voted in 1874 to drop the name Westfriesland Presbyterian Kerk and to adopt the other name. However, the name was officially changed back to Westfriesland in 1897 and incorporated in 1898.
The Rev. John Arends, pastor of the East Friesland Church from 1866 to the summer of 1870, was the Westfriesland church's first pastor in 1879. From 1871 to 1874 the pulpit was vacant, probably because the organization had not been accomplished. They seem to have been completed in 1873 and the Rev. Arends again became minister until his death in 1880. Other organizers of the church appear to have been Dr. J. E. Drake, the Rev. Jan VanderLas, John Arends and Adrian VanVliet.
In the minutes of the congregational meeting of January 3, 1874, a certain Hendrick DeVries offered to sell two acres of ground east of the cemetery of the "Ware Hollands Gereformeerde Kerk"--the true Holland Reformed Church--for the sum of $50. The two-acre plot was purchased and plans were laid for the building of the first church.
The church building was completed by the end of June, 1874. John Rath contracted lumber for the church, 28 by 40 feet, for $685.
The church was remodeled in 1908, and a bell was installed which is still in use to call people to worship. In 1924 a small tornado ripped down the steeple of the church, and the present front was erected when the damage was repaired.
The present parsonage was erected in the summer of 1928 at a cost of $6,000.
The church was remodeled in 1941, when a full basement was added as well as an extension to the building.
One son of the church, Harold, son of Mrs. Joe Fisher and the late Mr. Fisher, is serving in the mission field in Lebanon.
There have been but seven pastors of the West Friesland Church during the 84 years of its history. These devoted men were John K. Arends, 1873-1880; Godfrey Moery, 1880-1884; L. Kliebenstein, 1884-1905; J. J. Agena, 1905-1920; Henry Johnson, 1921-1944; Peter Eekhoff, 1944-1955; Norman Flink, 1955-____.
The church is noted for its men's quartet, which has appeared in gospel song concerts on many occasion, here and in other churches.
The history of the West Friesland Church has been one of consecrated service to God and mankind. In 1973, its Centennial anniversary will be observed.
--Ackley World-Journal (Ackley, Iowa), 1 August 1957, pg 56
also see: History of the German Presbyterian Church of Grundy County
Name Years Served
Rev. John K. Arends 1873-1880
Rev. Godfrey Moery 1880-1884
Rev. Ludwig Kliebenstein 1884-1905
Rev. J. J. Agena 1905-1920
Rev. Henry Johnson 1921-1944
Rev. Peter H. Eekhoff 1944-1955
Rev. Norman Flink 1955-1962
Rev. Kenneth Remer 1965-1985
Rev. Chuck Westendorf
Grundy County IAGenWeb |
Copyright © IAGenWeb. All Rights Reserved

redpajama_set_name: RedPajamaCommonCrawl


Iceland, Finland, Faroe, Indonesia, Philipines, Islands, Italy, Belgium, Lithuania, France, Slovenia, Poland, Czech Republic, Ukraina, Slovakia, Germany,Estonia, Hungary, Russia, Spain.
During the festival choirs take part in special concerts organized in the impressive Cathedral of Barcelona (optional). As the organizing committee we proudly announce our 9th year cooperating with the Barcelona Cathedral in the organization of the choir festival. We are the largest organizer of choir concerts at this Cathedral.
Many people and several cultural associations are involved in the organization of the festival. Residents of Barcelona and Lloret de Mar fell in love with the festival since it first edition in 2011 and have actively participated in the preparation of this event. Therefore we are convinced that you'll spend your few days full of fun, sun, and unforgettable artistic impressions.
Choirs have the possibility of participating in the 8th International Choir Festival without participating in the choir competition.
We are very pleased to invite your choir to participate in the 2018 edition of the International 'Pau Casals' Choir Competition & Festival "Canco Mediterrania". We look forward to your application!
*The average water temperature of the Mediterranean Sea (Costa Brava) between the 15th and 20th of September is about 22-23° C. "Costa Brava- Best of the World 2012 top Travel Destination - National Geographic Traveller".
More information under the General conditions Tab.


Console MetricsWatts, HR, speed, RPM, Distance, Time, Calories, and Programs. Quick button to change from KM to Miles.
Running Surface17.25" or 43.81 cm wide. Length undisclosed.
Lightest high quality manual treadmill on the market.
280 lbs isn't anything to sneeze at but it's still the lightest high quality manual treadmill on the market. This is 45 lbs lighter than the Trueform Performance model for example. This comes at the expense of less durable plastic side runners however vs the metal ones of the TrueForm model.
Console is included in the price and has Bluetooth and Ant+ connectivity options.


text:
Нагру́дний знак «А. С. Мака́ренко» (Нагру́дний знак «Анто́н Мака́ренко») — заохочувальна відомча відзнака Міністерства освіти і науки України. Має третій (найвищий) ступінь серед відзнак, запроваджених міністерством. Названо на честь українського педагога Антона Макаренка.

Відомості про нагороду

Нагрудним знаком «Антон Макаренко» нагороджуються педагогічні працівники професійно-технічних навчальних закладів, вищих навчальних закладів I—II рівнів акредитації, державні службовці, які досягли визначних успіхів у вихованні підростаючого покоління, науковому та навчально-методичному забезпеченні виховної роботи, підготовці висококваліфікованих педагогічних працівників.

Див. також
 Нагороди та премії імені А. С. Макаренка
 Медаль А. С. Макаренка

Література
 Майборода В. К. Нагороди в галузі освіти //  — С. 543—544.

Нагороди України в галузі освіти
Відзнаки Міністерства освіти і науки України
Нагрудні знаки
Нагороди, які носять ім'я Антона Макаренка
2005 в Україні

redpajama_set_name: RedPajamaWikipedia


The story of the Canning Stock Route's construction.
Eleanor Smith, who was a nurse before her marriage in 1930, travelled extensively in the outback.
She became fascinated with Trotman's stories and spent day after day by his fireside listening and taking notes until his five expeditions fell into place and she was able to reproduce them 'in Trotman's own words'. She has performed a remarkable feat of listening, organising and writing to enable Trotman to tell his story in the first person, in a rich, economical and always convincing style.
This edition includes 23 pages of illustrations.
ISBN 978-0-85905-579-6, (2014, new), Softcover, A4, illustrated, 120pp, 350 g.
A detailed listing and text of the discoveries from 1829 to Bayley and Ford. Essential reference for historians and prospectors. The culmination of decades of collecting data.
George McDonald was an Inspector of Police in Kalgoorlie during the 1890s.
In Beyond Boundary Fences he relates stories of the early Murchison goldfield's characters, Aboriginals, bushmen and outlaws.
New updated third edition. A brief history of the Australian Loton Families from the early 1800s to 2012 and some hidden history of the Swan River settlement.
Only available from Harold Loton, Unit 72, St Louis Estate, 14 Albeert Street. Claremont, 6010.
The best book on bicycle history ever. The effect of the bicycle on the Australian outback.
This extraordinary book describes the conceptualisation of the human body, soul, and health at the Kukatja people, who now live at Balgo, in the far north of Western Australia. It is without a doubt the best book I have read in the past two decades on any topic concerning Australian Aborigines. Packed with absolutely fascinating and new information, it also makes a challenging read; the effort required is, however, amply rewarded.
In a very moving Foreword to this book Dr Frank Mills writes. "Out of the tragic shambles that was Sandakan, Peter Firkins has produced a heroic figure comparable in courage and selflessness to that of the legendary 'Weary' Dunlop, and whose story should be known by all Australians in the same way.
Beyondie Station at Kumarina, north of Meekatharra, was taken up in the 1920s by Bob George, a Rabbit Proof Fence boundary rider. He protected a young part-Aboriginal girl, later marrying her. Yibbie had ten children with Bob George and later attachments, and most were sent by Bob to Sister Kate's home in Perth for their education. Of the children today, two of the girls survive. One is a Perth lawyer, and the other, Evalene, was involved in a pastoral life. This is the interesting story of growing up in the wildest bush and in the equally feral children's home. The George family were well-known in the upper Murchison/Gascoyne region and this autobiography is an interesting and important reflection of life in that country. It was written by 2003 but ignored by publishers, perhaps because its content was not considered abrasive enough in the 'culture wars' of that time.
United Kingdom immigrants in the 1800s who became settlers in Western Australia. An important social history and of great genealogical interest.


Seth Rogen and writing partner Evan Goldberg (Pineapple Express, Superbad) just scored some more great folks for The End of the World, the duo's directorial debut already set to feature Jay Baruchel, Jonah Hill, Craig Robinson, Danny McBride, and Aziz Ansari. Add Emma Watson, Jason Segel, and David Krumholtz to the party at James Franco's house, where everyone will be playing his or her self in an apocalypse scenario. According to The Hollywood Reporter, "the script has fun with the actors, who might or might not make it out alive." Hermione makes it out alive. Always.


text:
You are here: Home / Sports Memorabilia / Sports Memorabilia News / Game-used Bobby Orr Jersey Brings $191,200
Game-used Bobby Orr Jersey Brings $191,200
April 23, 2010 By Rich Mueller
The 1966-67 game-worn rookie jersey of NHL legend Bobby Orr, widely considered the greatest defenseman in hockey history, sold Friday for $191,200. The price includes a 19.5% Buyer's Premium.
The buyer purchased the jersey via Heritage Auctions' internet bidding platform. The name and location of the winning bidder were not publicly revealed.
"If ever there was such a thing, then this jersey is indeed the Holy Grail of hockey collectibles," said Chris Ivy of Heritage. "It's as much about the $191,200 final price as it is about Orr's place as one of the most beloved NHL players in the history of the sport."
This jersey is one of only three jerseys worn by Orr during his historic first season in Boston, and one of only two known to survive to this day. The consignor of the jersey, John Rows, is the nephew of Garry Young, then-head Bruins scout, and later a coach for the Golden Seals and Blues. Young rescued the Orr jersey, gifting it to his sons, who later gifted it to Rows.
The number "4" on the jersey is a number that will never be seen on another Bruins jersey, as it was retired by the franchise in a raucous ceremony in January 1979, just months after Orr's damaged knees made further play impossible.
The jersey is among the highest priced game worn NHL jerseys ever to be sold.
Filed Under: Sports Memorabilia News Tagged With: Boston, Chris Ivy, Dallas, Garry Young, Heritage, Hockey, Jersey, John Rows, NHL, Orr


Special Education Essay Topics aboriginal education essay topics. http://staging.sharedlabs.com/treasurer....nottingham what needs our best cv experts help you get you may spare writing service in dubai. Replace your student planner and notebook with Studious set a homework. Nih suggested cover letter format.