Crafting consensus

Abstract

The paper analyzes the problem of a committee chair using favors at her disposal to maximize the likelihood that her proposal gains committee support. The favors increase the probability of a given member approving the chair’s proposal via a smooth voting function. The decision-making protocol is any quota voting rule. The paper characterizes the optimal allocation of any given level of favors and the optimal expenditure-minimizing level of favors. The optimal allocation divides favors uniformly among a coalition of the committee members. At a low level of favors, the coalition comprises all committee members. At a high level, it is the minimum winning coalition. The optimal expenditure level guarantees the chair certain support of the minimum winning coalition if favors are abundant and uncertain support of all committee members if favors are scarce; elitist or egalitarian committees are compatible with a strategic chair. The results are robust to changing the chair’s objectives and to alternative voting functions, and reconcile theoretical predictions with empirical observations about legislative bargaining experiments, lobby vote buying and executive lawmaking.

Appendix 1: Proofs

1.1 Preliminaries

We present a series of auxiliary results that facilitate the proofs below. First, consider a random variable $X_{j}$ representing success or failure in a single Bernoulli trial with a probability of success $p\in [0,1]$. The number of successes in n independent identical Bernoulli trials follows a Binomial distribution B(n, p) with the probability mass function f(k, n, p), giving a probability of exactly $k\in \{0,\ldots ,n\}$ successes.

Lemma 1

Suppose $n\in {\mathbb {N}}_{\ge 1}$, $k\in \{0,\ldots ,n-1\}$ and $p\in (0,1)$. Then $f(k+1,n,p)\ge f(k,n,p)$ if and only if $k+1\le (n+1)p$.

Proof

Fix $n\in {\mathbb {N}}_{\ge 1}$, $k\in \{0,\ldots ,n-1\}$ and $p\in (0,1)$. We have $f(k,n,p)=\left( {\begin{array}{l}n\\ k\end{array}}\right) p^{k}(1-p)^{n-k}$ and, hence,

$$\begin{aligned} \frac{f(k+1,n,p)}{f(k,n,p)}=\frac{(n-k)p}{(k+1)(1-p)}. \end{aligned}$$

(8)

Thus, $f(k+1,n,p)\ge f(k,n,p)\Leftrightarrow \frac{(n-k)p}{(k+1)(1-p)}\ge 1\Leftrightarrow np\ge k+1-p$.

We denote the probability of exactly k or more successes by $F(k,n,p)=\sum _{s=k}^{n}f(s,n,p)$. Below, we often differentiate F(k, n, p) with respect to p. To this end, it is helpful to express F(k, n, p) in terms of a regularized incomplete beta function (see Olver et al. 2010, for details):

$$\begin{aligned} F(k,n,p)=I_{p}(k,n-(k-1)) \end{aligned}$$

(9)

where

$$\begin{aligned} I_{x}(a,b)&=\frac{B(x,a,b)}{B(a,b)}\\ B(x,a,b)&=\int _{0}^{x}t^{a-1}(1-t)^{b-1}dt\\ B(a,b)&=\frac{(a-1)!(b-1)!}{(a+b-1)!}\\ \end{aligned}$$

(10)

are a regularized incomplete beta function, an incomplete beta function and a complete beta function, respectively. The derivative of F(k, n, p) for $p\in (0,1)$ and $k\in \{0,\ldots ,n\}$ is thus equal to

$$\begin{aligned} \frac{\partial F(k,n,p)}{\partial p}=\frac{k}{p}f(k,n,p). \end{aligned}$$

(11)

Note that, for any $n\in {\mathbb {N}}_{\ge 1}$ and $k\in \{0,\ldots ,n\}$, $f(k,n,p)>0$ when $p\in (0,1)$.

Working with F(k, n, p) is in general problematic. However, it can be bounded for large n. The following is a direct application of Theorem 1 in Hoeffding (1963) to the random variables $X_{j}$ representing the success or failure in the Bernoulli trials.

Theorem 1

(Hoeffding 1963) Let random variable $X_{j}\in \{0,1\}$ represent success ($X_{j}=1$) or failure ($X_{j}=0$) with ${\mathbb {P}}[X_{j}=1]=p\in (0,1)$ for $\forall j\in \{1,\ldots ,n\}$. Then

$$\begin{aligned} {\mathbb {P}}\left[ \textstyle \sum _{j=1}^{n}X_{j}\ge n(p+t)\right] \le \exp {[-2nt^{2}]} \end{aligned}$$

(12)

for $0<t\le 1-p$ and $\forall n\in {\mathbb {N}}_{\ge 1}$.²⁹

The final result represents the bound on the upper tail of the Binomial distribution expressed as a fraction of its probability mass function.

Theorem 2

(Diaconis and Zabell 1991) For any integer k satisfying $k>np$ where $n\in {\mathbb {N}}_{\ge 1}$ and $p\in (0,1)$

$$\begin{aligned} \frac{F(k,n,p)}{f(k,n,p)}\le \frac{k(1-p)}{k-np}. \end{aligned}$$

(13)

We use the bound on the upper tail since an exact expression in terms of a hypergeometric function (for details see Olver et al. 2010, Section 8.17), that is,

$$\begin{aligned} \frac{F(k,n,p)}{f(k,n,p)}=(1-p)\,_{2}F_{1}(1,1+n,1+k,p) \end{aligned}$$

(14)

is difficult to work with. The hypergeometric function itself is defined as

$$\begin{aligned} \,_{2}F_{1}(a,b,c,z)=\sum _{s=0}^{\infty }\frac{a)_{s}b)_{s}}{c)_{s}}\frac{z^{s}}{s!} \end{aligned}$$

(15)

where $(a)_{n}$ is Pochhammer’s symbol defined as $a(a+1)\ldots (a+n-1)$ if $n\ge 1$ and 1 for $n=0$. From Olver et al. (2010, Section 15.4), we have $\lim _{p\rightarrow 1^{-}}(1-p)\,_{2}F_{1}(1,1+n,1+n,p)=1$.

Despite F(k, n, p) / f(k, n, p) in general being not amenable to manipulation, it is monotone in some variables.

Lemma 2

Suppose $n\in {\mathbb {N}}_{\ge 1}$, $k\in \{0,\ldots ,n\}$ and $p\in (0,1)$. Then $\frac{F(k,n,p)}{f(k,n,p)}$ is nondecreasing in p.

Proof

Fix $n\in {\mathbb {N}}_{\ge 1}$, $k\in \{0,\ldots ,n\}$ and $p\in (0,1)$. We have

$$\begin{aligned} \frac{F(k,n,p)}{f(k,n,p)}=\frac{\sum _{s=k}^{n}f(s,n,p)}{f(k,n,p)}=\sum _{s=k}^{n}\frac{f(s,n,p)}{f(k,n,p)}. \end{aligned}$$

(16)

For any $s\in \{k,\ldots ,n\}$, we have

$$\begin{aligned} \frac{f(s,n,p)}{f(k,n,p)}=\frac{\left( {\begin{array}{l}n\\ s\end{array}}\right) }{\left( {\begin{array}{l}n\\ k\end{array}}\right) }\frac{p^{s}}{p^{k}}\frac{(1-p)^{n-s}}{(1-p)^{n-k}}=\frac{\left( {\begin{array}{l}n\\ s\end{array}}\right) }{\left( {\begin{array}{l}n\\ k\end{array}}\right) }\left( \frac{p}{1-p}\right) ^{s-k} \end{aligned}$$

(17)

and the lemma follows since $\frac{\partial }{\partial p}\frac{p}{1-p}=\frac{1}{(1-p)^{2}}\ge 0$.

Lemma 3

Suppose $n\in {\mathbb {N}}_{\ge 1}$, $k\in \{1,\ldots ,n\}$ and $r\in \{0,\ldots ,n-k\}$. Then $\frac{F(k,n-r,\frac{k}{n-r})}{f(k,n-r,\frac{k}{n-r})}$ is nonincreasing in r.

Proof

Fix $n\in {\mathbb {N}}_{\ge 1}$, $k\in \{1,\ldots ,n\}$ and $r\in \{0,\ldots ,n-k\}$. Since $r\in \{0,\ldots ,n-k\}$, $n-r\in \{k,\ldots ,n\}$ and thus $\frac{k}{n-r}\in (0,1)$ unless $r=n-k$. We thus have

$$\begin{aligned} \frac{F(k,n-r,\frac{k}{n-r})}{f(k,n-r,\frac{k}{n-r})}=\sum _{s=k}^{n-r}\frac{f(s,n-r,\frac{k}{n-r})}{f(k,n-r,\frac{k}{n-r})}. \end{aligned}$$

(18)

When $r\in \{0,\ldots ,n-k-1\}$ increases to $r+1$, the sum in (18) is over fewer terms. It thus suffices to show that $f(s,n-r,\frac{k}{n-r})/f(k,n-r,\frac{k}{n-r})$ is nonincreasing in r. For $s\in \{k,\ldots ,n-r\}$ we have

$$\begin{aligned} \frac{f(s,n-r,\frac{k}{n-r})}{f(k,n-r,\frac{k}{n-r})}&=\frac{\left( {\begin{array}{l}n-r\\ s\end{array}}\right) }{\left( {\begin{array}{l}n-r\\ k\end{array}}\right) }\frac{\left( \frac{k}{n-r}\right) ^{s}}{\left( \frac{k}{n-r}\right) ^{k}}\frac{\left( \frac{n-r-k}{n-r}\right) ^{n-r-s}}{\left( \frac{n-r-k}{n-r}\right) ^{n-r-k}}\\&=\frac{k!}{s!}\frac{(n-r-k)!}{(n-r-s)!}\left( \frac{k}{n-r-k}\right) ^{s-k}\\&=\frac{k!}{s!}k^{s-k}\underbrace{\frac{n-r-k}{n-r-k}\frac{n-r-k-1}{n-r-k}\cdot \ldots \cdot \frac{n-r-s+1}{n-r-k}}_{s-k}.\\ \end{aligned}$$

(19)

Each of the last $s-k$ terms writes $\frac{n-r-k-i}{n-r-k}$ for $i\in \{0,\ldots ,s-k-1\}$ and the lemma follows since $\frac{\partial }{\partial r}\frac{n-r-k-i}{n-r-k}=\frac{-i}{(n-r-k)^2}\le 0$.

1.2 Proof of Proposition 1

First, note that the ${{\mathbb {FA}}}$ problem has a solution, as it involves maximization of the continuous objective function ${\mathbb {P}}_{q|n}$ over a compact region X(b). ${\mathbb {P}}_{q|n}$ is differentiable with respect to every coordinate of ${\mathbf {p}}$; hence, any solution to ${{\mathbb {FA}}}$ necessarily satisfies the standard Kuhn and Tucker (1951) conditions. No further constraint qualification is required, as the constraints of ${{\mathbb {FA}}}$ are cut out by affine functions (Pardalos 2009). The Lagrangian for ${{\mathbb {FA}}}$ is

$$\begin{aligned} L({\mathbf {p}},\lambda ,{\mathbf {m}}^{+},{\mathbf {m}}^{-})={\mathbb {P}}_{q|n}[{\mathbf {p}}]-\lambda \left[ \sum _{i=1}^{n}p_{i}-b\right] -{\mathbf {m}}^{+}*({\mathbf {p}}-{\mathbf {1}})+{\mathbf {m}}^{-}*{\mathbf {p}} \end{aligned}$$

(20)

where $\lambda$, ${\mathbf {m}}^{+}=(m_{i}^{+})_{i\in N}$ and ${\mathbf {m}}^{-}=(m_{i}^{-})_{i\in N}$ are Lagrange multipliers and ${\mathbf {1}}$ is the unit vector in ${\mathbb {R}}^{n}$. Throughout, we denote the solution to ${{\mathbb {FA}}}$ by ${\mathbf {p}}^{*}$, $\lambda ^{*}$, ${\mathbf {m}}^{+,*}$ and ${\mathbf {m}}^{-,*}$. The typical element of ${\mathbf {p}}^{*}$ is $p_{i}^{*}$ and similarly for ${\mathbf {m}}^{+,*}$ and ${\mathbf {m}}^{-,*}$.

To prove part 1, note that, $\forall {\mathbf {p}}\in X(b)$, ${\mathbb {P}}_{q|n}[{\mathbf {p}}]\le 1$. If $b\ge q$, then for any ${\mathbf {p}}'$ with $|\{i\in N|p_{i}'=1\}|\ge q$ we have ${\mathbb {P}}_{q|n}[{\mathbf {p}}']=1$ and, hence, ${\mathbf {p}}'$ is a solution to ${{\mathbb {FA}}}$. Conversely, for any ${\mathbf {p}}'$ with $|\{i\in N|p_{i}'=1\}|<q$ we have ${\mathbb {P}}_{q|n}[{\mathbf {p}}']<1$ and, hence, ${\mathbf {p}}'$ is not a solution to ${{\mathbb {FA}}}$.

The proof of part 2 is significantly more involved. Suppose $b<q$. Simple argument shows that the constraint presented by b has to be binding in any solution to ${{\mathbb {FA}}}$, so that $\sum _{i=1}^{n}p_{i}^{*}=b$. The following lemma helps to prove the remaining claims.

Lemma 4

Suppose $b<q$. Given ${\mathbf {p}}^{*}$, if $p_{i}^{*}\in (0,1)$ and $p_{j}^{*}\in (0,1)$ for some $i\in N$ and $j\in N{\setminus }\{i\}$, then $p_{i}^{*}=p_{j}^{*}$.³⁰

Proof

Using (20), the first-order necessary condition for the optimality of ${\mathbf {p}}^{*}$ for any $p_{i}^{*}\in (0,1)$ is

$$\begin{aligned} \frac{\partial L({\mathbf {p}}^{*},\lambda ^{*},{\mathbf {m}}^{+,*},{\mathbf {m}}^{-,*})}{\partial p_{i}}=\frac{\partial {\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]}{\partial p_{i}}-\lambda ^{*}=0. \end{aligned}$$

(21)

Let ${\mathbf {p}}^{\{ij\}}$ be obtained from ${\mathbf {p}}$ by dropping $p_{i}$ and $p_{j}$ and, similarly, $N^{\{ij\}}=N{\setminus }\{i,j\}$. Recall that ${\mathbb {P}}_{s|n}^{*}[{\mathbf {p}}]$ denotes the probability of exactly s out of n committee members accepting the chair’s proposal when allocated favors ${\mathbf {p}}$. We have

$$\begin{aligned} {\mathbb {P}}_{q|n}[{\mathbf {p}}]&=\,{\mathbb {P}}_{q|n-2}[{\mathbf {p}}^{\{ij\}}](1-p_{i})(1-p_{j})\\&\quad +\,{\mathbb {P}}_{q-1|n-2}[{\mathbf {p}}^{\{ij\}}](p_{i}(1-p_{j})+(1-p_{i})p_{j})\\&\quad +\,{\mathbb {P}}_{q-2|n-2}[{\mathbf {p}}^{\{ij\}}]p_{i}p_{j}\\ &=\,{\mathbb {P}}_{q|n-2}[{\mathbf {p}}^{\{ij\}}]+(p_{i}+p_{j}){\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]\\&\quad +\, p_{i}p_{j}\left[ {\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]-{\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]\right] .\\ \end{aligned}$$

(22)

${\mathbb {P}}_{q|n}^{*}$ in (22) is well defined if $n\ge 1$ and $n\ge q\ge 0$. For $n\ge 1$ and $q>n$ or $q<0$, we use, by convention, ${\mathbb {P}}_{q|n}^{*}=0$. Similarly, for $n=q=0$, we use ${\mathbb {P}}_{q|n}^{*}=1$ and for $n=0$ and $q\ne 0$ we use ${\mathbb {P}}_{q|n}^{*}=0$. We do not need to consider $n<0$, as the lemma clearly holds for $n=1$.

If $p_{i}^{*}\in (0,1)$ and $p_{j}^{*}\in (0,1)$ such that $i\ne j$ exist, then from (21), we have $\frac{\partial {\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]}{\partial p_{i}}=\frac{\partial {\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]}{\partial p_{j}}$ and thus, using (22),

$$\begin{aligned} \left( p_{i}^{*}-p_{j}^{*}\right) \left[ {\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]-{\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]\right] =0. \end{aligned}$$

(23)

Suppose, towards a contradiction, $p_{i}^{*}\in (0,1)$, $p_{j}^{*}\in (0,1)$ and $p_{i}^{*}\ne p_{j}^{*}$. From (23), ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]={\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]$. This is impossible with $n=2$. Hence, suppose $n\ge 3$.

First, we claim that ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]={\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]$ and $n\ge 3$ implies $2\le q\le n-1$. Suppose $q=1$. Then ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0$ and ${\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=\prod _{k\in N^{\{ij\}}}(1-p_{k}^{*})$, so that ${\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0$ implies $\sum _{i\in N}p_{i}^{*}\ge n-2\ge 1$, a contradiction to $b<q=1$. Alternatively, suppose $q=n$. Then ${\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0$, so that ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0$ implies that ${\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]=0$, a contradiction to optimality of ${\mathbf {p}}^{*}$ as ${\mathbb {P}}_{q|n}[{\mathbf {p}}(0,\frac{b}{n},0)]>0$. Hence, suppose $q\in \{2,\ldots ,n-1\}$.

Second, we claim that ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]={\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]>0$. Suppose not. Then, unless ${\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]=0$, there exists $s\in \{q,\ldots ,n-2\}$ such that ${\mathbb {P}}_{s|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]>0$. Since, for some $s\in \{q,\ldots ,n-2\}$, ${\mathbb {P}}_{s|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]>0={\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]={\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]$, we have $\sum _{i\in N}p_{i}^{*}\ge q$, a contradiction to $b<q$.

As ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]={\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]>0$, there exists at least one coordinate of ${\mathbf {p}}^{\{ij\},*}$, $p_{k}^{*}$, such that $p_{k}^{*}\in (0,1)$. If all coordinates of ${\mathbf {p}}^{\{ij\},*}$ were equal either to zero or unity, then we would have ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]\in \{0,1\}$ and ${\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]\in \{0,1\}$ with both probabilities equal to unity impossible. Rewriting, we have

$$\begin{aligned} {\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]-{\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]= & {} \,p_{k}^{*}\left[ {\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]-{\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\right] \\& +\,(1-p_{k}^{*})\left[ {\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]-{\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\right] .\\ \end{aligned}$$

(24)

Third, we claim that ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\ne {\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$. To see this, suppose that ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$. Then, by (24), ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$, since ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]-{\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0$. If $n=3$, then $q\in \{2,\ldots ,n-1\}$ implies $q=2$ and we have ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0\ne {\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=1$. If $n=4$, then $q\in \{2,\ldots ,n-1\}$ implies $q\in \{2,3\}$. Suppose $q=2$. Then ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$, ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=1-{\mathbf {p}}^{\{ijk\},*}$ and ${\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]={\mathbf {p}}^{\{ijk\},*}$, and thus either ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\ne {\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ or ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\ne {\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$. Suppose $q=3$. Then ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=1-{\mathbf {p}}^{\{ijk\},*}$, ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]={\mathbf {p}}^{\{ijk\},*}$ and ${\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$, and again either ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\ne {\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ or ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\ne {\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$. If $n\ge 5$, we argue first that $q\in \{2,n-1\}$ is not possible. To see this, suppose $q=2$. Then ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$ and ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=\prod _{l\in N^{\{ijk\}}}(1-p_{l}^{*})$ so that ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$ implies $\sum _{i\in N}p_{i}^{*}\ge n-3\ge 2$, a contradiction to $b<q=2$. Alternatively, suppose $q=n-1$. Then ${\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$, so that ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$ implies that ${\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]=0$, a contradiction to optimality of ${\mathbf {p}}^{*}$ as ${\mathbb {P}}_{q|n}[{\mathbf {p}}(0,\frac{b}{n},0)]>0$.

For $n\ge 5$ and $q\in \{3,\ldots ,n-2\}$, we have ${\mathbb {P}}_{s|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ independent of s for $s\in \{q-3,q-2,q-1\}$. If ${\mathbb {P}}_{s|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$ $\forall s\in \{q-3,q-2,q-1\}$, then, unless ${\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]=0$, there exists $s'\in \{q,\ldots ,n\}$ such that ${\mathbb {P}}_{s'|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]>0$ and, hence, as ${\mathbb {P}}_{s|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$ $\forall s\in \{q-3,q-2,q-1\}$, $\sum _{i\in N}p_{i}^{*}\ge q$, a contradiction to $b<q$. If, ${\mathbb {P}}_{s|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=1$ for some $s\in \{q-3,q-2,q-1\}$, then ${\mathbb {P}}_{s'|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=0$ $\forall s'\in \{q-3,q-2,q-1\}{\setminus }\{s\}$ and, hence, ${\mathbb {P}}_{s|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ depends on s. Hence, if ${\mathbb {P}}_{s|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ is independent of s, then ${\mathbb {P}}_{s|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]=c\in (0,1)$ $\forall s\in \{q-3,q-2,q-1\}$. This implies that the number of unit coordinates in ${\mathbf {p}}^{\{ijk\},*}$, u, satisfies $u\le q-3$, that there are at least two interior coordinates in ${\mathbf {p}}^{\{ijk\},*}$ and thus that the number of zero or unit coordinates in ${\mathbf {p}}^{\{ijk\},*}$, $z+u$, satisfies $z+u\le n-5$.

Furthermore, we argue that $z\le n-q-2$. Since the number of committee members receiving positive favors $3+u+n-3-z-u=n-z$ has to be at least q, we have $z\le n-q$ and it thus suffices to rule out $z\in \{n-q-1,n-q\}$. Note that ${\mathbb {P}}^{*}_{s|n-3}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}^{*}_{s-u|n-3-u-z}[{\mathbf {p}}^{\{ijkuz\},*}]$ for $s\in \{q-3,q-2,q-1\}$, where ${\mathbf {p}}^{\{ijkuz\},*}$ denotes ${\mathbf {p}}^{*}$ after dropping $p_{i}^{*}$, $p_{j}^{*}$, $p_{k}^{*}$ and all unit and zero coordinates. If $z=n-q$, then we have ${\mathbb {P}}^{*}_{q-2|n-3}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}^{*}_{q-2-u|q-3-u}[{\mathbf {p}}^{\{ijkuz\},*}]=0$, since $q-3-u\ge 0$ by $u\le q-3$, and ${\mathbb {P}}^{*}_{q-3|n-3}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}^{*}_{q-3-u|q-3-u}[{\mathbf {p}}^{\{ijkuz\},*}]\ne 0$, a contradiction. If $z=n-q-1$, then we have ${\mathbb {P}}^{*}_{q-1|n-3}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}^{*}_{q-1-u|q-2-u}[{\mathbf {p}}^{\{ijkuz\},*}]=0$, since $q-2-u\ge 0$ by $u\le q-3$, and ${\mathbb {P}}^{*}_{q-2|n-3}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}^{*}_{q-2-u|q-2-u}[{\mathbf {p}}^{\{ijkuz\},*}]\ne 0$, a contradiction.

Thus we conclude that ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ and ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]={\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ is not possible since ${\mathbb {P}}_{q|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ is, as a function of q, first increasing and then decreasing, except possibly for two equal maxima (Darroch 1964).³¹

Finally, we claim that $p_{i}^{*}\ne p_{j}^{*}$ provides a contradiction. From $p_{i}^{*}\ne p_{j}^{*}$, either $p_{i}^{*}\ne p_{k}^{*}$ or $p_{j}^{*}\ne p_{k}^{*}$. Without loss of generality, assume $p_{i}^{*}\ne p_{k}^{*}$. Since ${\mathbb {P}}_{q-3|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\ne {\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$, ${\mathbb {P}}_{q-2|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]\ne {\mathbb {P}}_{q-1|n-3}^{*}[{\mathbf {p}}^{\{ijk\},*}]$ and thus, replacing $p_{k}^{*}$ with $p_{i}^{*}$ in (24), we have

$$\begin{aligned} {\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{jk\},*}]-{\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{jk\},*}]\ne 0 \end{aligned}$$

(25)

for any $n\ge 3$ and $q\in \{2,\ldots ,n-1\}$. Hence, by (23), $p_{j}^{*}=p_{k}^{*}$ as $p_{k}^{*}\in (0,1)$. Moreover, $p_{i}^{*}\ne p_{j}^{*}$ implies ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]-{\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0$ by (23) and, hence, by (22), ${\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]$ depends only on $p_{i}^{*}+p_{j}^{*}$. Therefore, for all sufficiently small $\epsilon \ne 0$, ${\mathbf {p}}^{\prime }$ identical to ${\mathbf {p}}^{*}$ except that $p_{i}^{\prime }=p_{i}^{*}-\epsilon$ and $p_{j}^{\prime }=p_{j}^{*}+\epsilon$ also solves ${{\mathbb {FA}}}$. Repeating the same argument that lead to $p_{j}^{*}=p_{k}^{*}$, using $p_{i}^{\prime }$ and $p_{j}^{\prime }$ instead, we have $p_{j}^{\prime }=p_{k}^{\prime }$, which is contradiction since $p_{j}^{*}=p_{k}^{*}=p_{k}^{\prime }$ implies $p_{j}^{*}=p_{j}^{\prime }$ but $p_{j}^{*}\ne p_{j}^{\prime }$.

Fix ${\mathbf {p}}^{*}$. By Lemma 4, ${\mathbf {p}}^{*}={\mathbf {p}}(r^{*},p^{*},s^{*})$ where $p^{*}=\frac{b-s^{*}}{n-r^{*}-s^{*}}$. What remains to be shown are $s^{*}=0$, $r^{*}\le n-q$ and, when $b<q-1$, $r^{*}=0$. That $r^{*}\le n-q$ is obvious. If $r^{*}>n-q$, then the number of committee members receiving non-zero favors is $n-r^{*}<q$ and ${\mathbb {P}}_{q|n}[{\mathbf {p}}(r^{*},p^{*},s^{*})]=0$.

For $s^{*}=0$ and $r^{*}=0$ if $b<q-1$, first note that both hold for $n=1$, thus suppose $n\ge 2$. We proceed by analyzing the first order necessary conditions for optimality derived from (20). These read

$$\begin{aligned}\frac{\partial {\mathbb {P}}_{q|n}({\mathbf {p}}^{*})}{\partial p_{i}}-\lambda ^{*}+m^{-,*}_{i}=0 &\quad {\text {if }}\,p_{i}^{*}=0\\ \frac{\partial {\mathbb {P}}_{q|n}({\mathbf {p}}^{*})}{\partial p_{i}}-\lambda ^{*}=0 & \quad {\text {if }}\,p_{i}^{*}\in (0,1)\\ \frac{\partial {\mathbb {P}}_{q|n}({\mathbf {p}}^{*})}{\partial p_{i}}-\lambda ^{*}-m^{+,*}_{i}=0&\quad {\text {if }}\,p_{i}^{*}=1\\ \end{aligned}$$

(26)

which, using the non-negativity of the Lagrange multipliers, can be rewritten as

$$\begin{aligned} \left. \frac{\partial {\mathbb {P}}_{q|n}({\mathbf {p}}^{*})}{\partial p_{i}}\right| _{p_{i}^{*}=1}\ge \left. \frac{\partial {\mathbb {P}}_{q|n}({\mathbf {p}}^{*})}{\partial p_{i}}\right| _{p_{i}^{*}\in (0,1)}\ge \left. \frac{\partial {\mathbb {P}}_{q|n}({\mathbf {p}}^{*})}{\partial p_{i}}\right| _{p_{i}^{*}=0} \end{aligned}$$

(27)

and implies that

$$\begin{aligned} {\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]\ge {\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}] \end{aligned}$$

(28)

for any pair $p_{i}^{*}>p_{j}^{*}$ by (22).

Consider $q=1$. Then $s^{*}=0$ holds since $b<q$ and $r^{*}=0$ if $b<q-1$ holds vacuously as $q-1=0$. Consider $q=n$. Suppose, towards a contradiction, that $s^{*}>0$. Then there exists $p_{i}^{*}=1$ and, since $b<q$, $p_{j}^{*}<1$, so that (30) must hold. The left hand side of (30) equals zero and, hence, ${\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0$ so that ${\mathbb {P}}_{q|n}[{\mathbf {p}}(r^{*},p^{*},s^{*})]=0$, a contradiction. Suppose, towards another contradiction, that $r^{*}>0$. Then ${\mathbb {P}}_{q|n}[{\mathbf {p}}(r^{*},p^{*},s^{*})]=0$ since $q=n$, a contradiction. By covering $q=1$ and $q=n$, we have covered $n=2$. Thus suppose $n\ge 3$ and $q\in \{2,\ldots ,n-1\}$.

Consider the number of entries in ${\mathbf {p}}^{*}={\mathbf {p}}(r^{*},p^{*},s^{*})$ that differ from zero and unity, $n-r^{*}-s^{*}$. We argue that $n-r^{*}-s^{*}\ge 2$. If $n-r^{*}-s^{*}=0$, then b is an integer and $b<q$ implies $b\le q-1$, so that $s^{*}\le q-1$ and, hence, ${\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]=0$. To see that $n-r^{*}-s^{*}\ne 1$, suppose, towards a contradiction, that $n-r^{*}-s^{*}=1$. Then, unless ${\mathbb {P}}_{q|n}[{\mathbf {p}}^{*}]=0$, we have $s^{*}=q-1$. Pick $p_{i}^{*}=1$ and $p_{j}^{*}\in (0,1)$. Then ${\mathbf {p}}^{\{ij\},*}$ in (30) is $n-2$ vector with $q-2$ unit coordinates and $n-q$ zero coordinates, and, hence, ${\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0<1={\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]$, a contradiction. Thus $n-r^{*}-s^{*}\ge 2$.

Moreover, we argue that $r^{*}=n-q$ when $s^{*}\ge 1$ is not possible. Suppose, towards a contradiction, that $r^{*}=n-q$ and $s^{*}\ge 1$. Pick $p_{i}^{*}=1$ and $p_{j}^{*}\in (0,1)$. Then ${\mathbf {p}}^{\{ij\},*}$ in (30) is $n-2$ vector with $n-r^{*}-2=q-2$ positive coordinates, and, hence, ${\mathbb {P}}_{q-1|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]=0<{\mathbb {P}}_{q-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]$, a contradiction.

We now show that $s^{*}=0$. Suppose, towards a contradiction, that $s^{*}\ge 1$. Since $s^{*}\ge 1$ and $n-r^{*}-s^{*}\ge 2$, we can pick $p_{i}^{*}=1$ and $p_{j}^{*}\in (0,1)$. Then ${\mathbf {p}}^{\{ij\},*}$ has $r^{*}$ zero coordinates, $s^{*}-1$ unit coordinates and $n-2-r^{*}-(s^{*}-1)$ of the $p^{*}$ coordinates. In (30), we have ${\mathbb {P}}_{s|n-2}[{\mathbf {p}}^{\{ij\},*}]={\mathbb {P}}_{s-(s^{*}-1)|n-2-r^{*}-(s^{*}-1)}[{\mathbf {p}}^{\{ijuz\},*}]$ for $s\in \{q-2,q-1\}$, where ${\mathbf {p}}^{\{ijuz\},*}$ denotes ${\mathbf {p}}^{*}$ after dropping $p_{i}^{*}$, $p_{j}^{*}$, $r^{*}$ zero coordinates and $s^{*}-1$ unit coordinates. We have $n-2-r^{*}-(s^{*}-1)=n-r^{*}-s^{*}-1\ge 1$ by $n-r^{*}-s^{*}\ge 2$, $s-(s^{*}-1)\ge 0$ $\forall s\in \{q-2,q-1\}$ by $s^{*}\le q-1$, and $s-(s^{*}-1)\le n-2-r^{*}-(s^{*}-1)\Leftrightarrow r^{*}\le n-2-s$ $\forall s\in \{q-2,q-1\}$ by $r^{*}\le n-q-1$ when $s^{*}\ge 1$. Therefore, by Lemma 1, we can rewrite (30) as

$$\begin{aligned} \left( n-2-r^{*}-(s^{*}-1)+1\right) p^{*}&=b-s^{*}\\&\ge q-2-(s^{*}-1)+1\\ \end{aligned}$$

(29)

which simplifies to $b\ge q$, a contradiction.

We now show that $r^{*}=0$ if $b<q-1$. Suppose, towards a contradiction, that $r^{*}\ge 1$ and $b<q-1$. Since $r^{*}\ge 1$ and $n-r^{*}\ge 2$, we can pick $p_{j}^{*}=0$ and $p_{i}^{*}\in (0,1)$. Then ${\mathbf {p}}^{\{ij\},*}$ has $r^{*}-1$ zero coordinates and $n-2-(r^{*}-1)$ of the $p^{*}$ coordinates. In (30), we have ${\mathbb {P}}_{s|n-2}[{\mathbf {p}}^{\{ij\},*}]={\mathbb {P}}_{s|n-2-(r^{*}-1)}[{\mathbf {p}}^{\{ijz\},*}]$ for $s\in \{q-2,q-1\}$, where ${\mathbf {p}}^{\{ijz\},*}$ denotes ${\mathbf {p}}^{*}$ after dropping $p_{i}^{*}$, $p_{j}^{*}$ and $r^{*}-1$ zero coordinates. We have $n-2-(r^{*}-1)=n-r^{*}-1\ge 1$ by $n-r^{*}\ge 2$, $s\ge 0$ $\forall s\in \{q-2,q-1\}$ by $q\ge 2$, and $s\le n-2-(r^{*}-1)\Leftrightarrow r^{*}\le n-1-s$ $\forall s\in \{q-2,q-1\}$ by $r^{*}\le n-q$. Therefore, by Lemma 1, we can rewrite (30) as

$$\begin{aligned} \left( n-2-(r^{*}-1)+1\right) p^{*}&=b\\&\ge q-2+1\\ \end{aligned}$$

(30)

which simplifies to $b\ge q-1$, a contradiction. $\square$

1.3 Proof of Proposition 2

We first observe that ${{\mathbb {CE}}}$, $\max _{b\in [0,B]}(B-b){\mathbb {R}}_{q|n}[b]$, admits a solution by the Weierstrass theorem since ${\mathbb {R}}_{q|n}[b]$ is continuous in b, which in turn follows from the Theorem of the Maximum (Aliprantis and Border 2006, Theorem 17.31). We also observe that the solution to ${{\mathbb {CE}}}$, $b^{*}$, has to satisfy $b^{*}\le q$ for any B. For $b\ge q$, ${\mathbb {R}}_{q|n}[b]=1$, hence, the objective function of ${{\mathbb {CE}}}$ is decreasing in b for $b>q$.

For part 1, we must show that $b^{*}\ne q$ when $B<q+1$. Suppose, towards a contradiction, that $b^{*}=q$ and $B<q+1$. Since $b^{*}=q$, then ${\mathbb {R}}_{q|n}[b^{*}]=1$, and the value of the objective function in ${{\mathbb {CE}}}$ equals $B-q$. Since $b^{*}=q$, by Proposition 1 part 1, ${\mathbf {p}}^{*}$ that solves ${{\mathbb {FA}}}$ given $b^{*}=q$ satisfies $|\{i\in N|p_{i}^{*}=1\}|\ge q$. Consider ${\mathbf {p}}'$ identical to ${\mathbf {p}}^{*}$ except that for i such that $p_{i}^{*}=1$, $p_{i}'=1-\epsilon$ for some small $\epsilon >0$. The objective function in ${{\mathbb {CE}}}$ evaluated at ${\mathbf {p}}'$ is $(B-q+\epsilon )(1-\epsilon )$. Since $b^{*}=q$, we must have

$$\begin{aligned} B-q&\ge (B-q+\epsilon )(1-\epsilon )\\ B&\ge q+1-\epsilon \\ \end{aligned}$$

(31)

for any $\epsilon >0$. However, since $B<q+1$, there always exists $\epsilon >0$ such that $B<q+1-\epsilon$, a contradiction.

For part 2, suppose, towards a contradiction, that $b^{*}$ implies $r^{*}=n-q$ in ${{\mathbb {FA}}}$ and $B<q-\frac{1}{q}$. Since the number of committee members receiving positive favors is $n-r^{*}=q$, the objective function in ${{\mathbb {CE}}}$ under $r^{*}=n-q$ is

$$\begin{aligned} (B-b)\left( \frac{b}{q}\right) ^{q} \end{aligned}$$

(32)

and standard argument shows that $b^{*}=B\frac{q}{q+1}$. However, since $B<q-\frac{1}{q}$, we have $b^{*}=B\frac{q}{q+1}<q-1\Leftrightarrow B<q-\frac{1}{q}$, so that, by Proposition 1 part 2, $r^{*}=0$, a contradiction.

For part 3, when $B<q-1$, $b\in [0,B]$ in ${{\mathbb {CE}}}$ implies $b^{*}<q-1$, which implies $r^{*}=0$ in ${{\mathbb {FA}}}$.

To see that $\tilde{b}^{*}\ge b^{*}$ if $\tilde{B}>B$, where $\tilde{b}^{*}$ solves ${{\mathbb {CE}}}$ given $\tilde{B}>B$, suppose, towards a contradiction, that $\tilde{b}^{*}<b^{*}$. From $b^{*}\le q$, we have $\tilde{b}^{*}<q$. Because $b^{*}$ solves ${{\mathbb {CE}}}$ given B and $\tilde{b}^{*}$ solves ${{\mathbb {CE}}}$ given $\tilde{B}$, we have

$$\begin{aligned} (B-b^{*}){\mathbb {R}}_{q|n}[b^{*}]&\ge (B-\tilde{b}^{*}){\mathbb {R}}_{q|n}[\tilde{b}^{*}]\\ (\tilde{B}-\tilde{b}^{*}){\mathbb {R}}_{q|n}[\tilde{b}^{*}]&\ge (\tilde{B}-b^{*}){\mathbb {R}}_{q|n}[b^{*}].\\ \end{aligned}$$

(33)

Summing the two inequalities, we have ${\mathbb {R}}_{q|n}[b^{*}](B-\tilde{B})\ge {\mathbb {R}}_{q|n}[\tilde{b}^{*}](B-\tilde{B})$, which, by $\tilde{B}>B$, implies ${\mathbb {R}}_{q|n}[b^{*}]\le {\mathbb {R}}_{q|n}[\tilde{b}^{*}]$. However, from the structure of the ${{\mathbb {FA}}}$ problem, we have ${\mathbb {R}}_{q|n}[b^{*}]>{\mathbb {R}}_{q|n}[\tilde{b}^{*}]$ when $\tilde{b}^{*}<b^{*}$ and $\tilde{b}^{*}<q$. $\square$

1.4 Proof of Proposition 3

As in the proof of Proposition 2, $b^{*}\le q$. Moreover, since ${\mathbb {R}}_{q|n}[0]=0$, $b^{*}\ne 0$. Thus it suffices to show that $b^{*}\notin (0,q)$. Moreover, if we show that $b^{*}=q$ for B, then $b^{*}=q$ for any $B'\ge B$. To see this, if $b^{*}=q$ under B, we have

$$\begin{aligned} B-q\ge (B-b){\mathbb {R}}_{q|n}[b] \end{aligned}$$

(34)

$\forall b\in [0,q]$. Therefore, $\forall b\in [0,q]$ and any $c\ge 0$,

$$\begin{aligned} B+c-q&\ge (B-b){\mathbb {R}}_{q|n}[b]+c\\&\ge (B+c-b){\mathbb {R}}_{q|n}[b]\\ \end{aligned}$$

(35)

where the second inequality follows from ${\mathbb {R}}_{q|n}[b]\in [0,1]$, and, hence, $b^{*}=q$ under $B+c\ge B$.

In order to show $b^{*}\notin (0,q)$, it suffices to show that $(B-b)F(q,n-r,\frac{b}{n-r})$ is increasing for any $b\in (0,q)$ and $r\in \{0,\ldots ,n-q\}$. To see this, we know that ${\mathbb {R}}_{q|n}[b]$ is continuous in b on (0, q) and, by Proposition 1, $\forall b\in (0,q)$, $R_{q|n}[b]\in \{F(q,n-r,\frac{b}{n-r})|r\in \{0,\ldots ,n-q\})$.

Fix $n\in {\mathbb {N}}_{\ge 1}$, $q\in \{1,\ldots ,n\}$, $B\ge q+(1-\frac{q}{n})\,_{2}F_{1}(1,1+n,1+q,\frac{q}{n})$, $b\in (0,q)$ and $r\in \{0,\ldots ,n-q\}$. Because $q+(1-\frac{q}{n})\,_{2}F_{1}(1,1+n,1+q,\frac{q}{n})=q+\frac{F(q,n,\frac{q}{n})}{f(q,n,\frac{q}{n})}\ge q+1$, we have $B\ge q+1$. We claim that $\frac{\partial }{\partial b}(B-b)F(q,n-r,\frac{b}{n-r})>0$.

Suppose first that $r=n-q$. Then $F(q,n-r,\frac{b}{n-r})=F(q,q,\frac{b}{q})=\left( \frac{b}{q}\right) ^{q}$ and we have $\frac{\partial }{\partial b}(B-b)F(q,n-r,\frac{b}{n-r})=\left( \frac{b}{q}\right) ^{q-1}[B-b-\frac{b}{q}]$, where $B-b-\frac{b}{q}>B-q-1\ge 0$. Since we have proven our claim for $r=n-q$, suppose $r\in \{0,\ldots ,n-q-1\}$, so that we can also suppose $q\in \{1,\ldots ,n-1\}$. This implies $n-r\in \{q+1,\ldots ,n\}$ and, hence, $\frac{b}{n-r}\in (0,\frac{q}{q+1})\subset (0,1)$.

Since $\frac{\partial }{\partial b}(B-b)F(q,n-r,\frac{b}{n-r})=(B-b)\frac{q}{b}f(q,n-r,\frac{b}{n-r})-F(q,n-r,\frac{b}{n-r})$, we have

$$\begin{aligned} \frac{\frac{\partial }{\partial b}(B-b)F(q,n-r,\frac{b}{n-r})}{f(q,n-r,\frac{b}{n-r})}&=(B-b)\frac{q}{b}-\frac{F(q,n-r,\frac{b}{n-r})}{f(q,n-r,\frac{b}{n-r})}\\&\ge (B-b)\frac{q}{b}-\frac{F(q,n-r,\frac{q}{n-r})}{f(q,n-r,\frac{q}{n-r})}\\&\ge (B-b)\frac{q}{b}-\frac{F(q,n,\frac{q}{n})}{f(q,n,\frac{q}{n})}\\&>B-q-\frac{F(q,n,\frac{q}{n})}{f(q,n,\frac{q}{n})}\ge 0.\\ \end{aligned}$$

(36)

The first equality uses $f(q,n-r,\frac{b}{n-r})>0$. The first and the second inequality follows from Lemma 2 and 3 respectively. The third inequality follows by $b<q$ and the last inequality by $B\ge q+(1-\frac{q}{n})\,_{2}F_{1}(1,1+n,1+q,\frac{q}{n})$, or, equivalently, $B\ge q+\frac{F(q,n,\frac{q}{n})}{f(q,n,\frac{q}{n})}$. This proves the main claim of the proposition.

What remains is $q+1+q(1-\frac{q}{n})\ge q+(1-\frac{q}{n})\,_{2}F_{1}(1,1+n,1+q,\frac{q}{n})$ for any $n\in {\mathbb {N}}_{\ge 1}$ and $q\in \{1,\ldots ,n\}$. For $q=n$, because $\lim _{q\rightarrow n}(1-\frac{q}{n})\,_{2}F_{1}(1,1+n,1+n,\frac{q}{n})=1$, the inequality writes $q+1\ge q+1$. Suppose $q\in \{1,\ldots ,n-1\}$. Then, we have

$$\begin{aligned} q+\left(1-\frac{q}{n}\right)_{2}F_{1}\left(1,1+n,1+q,\frac{q}{n}\right)&=q+\frac{F(q,n,\frac{q}{n})}{f(q,n,\frac{q}{n})} \\&= q+1+\frac{F(q+1,n,\frac{q}{n})}{f(q+1,n,\frac{q}{n})}\frac{f(q+1,n,\frac{q}{n})}{f(q,n,\frac{q}{n})}\\&=q+1+\frac{F(q+1,n,\frac{q}{n})}{f(q+1,n,\frac{q}{n})}\frac{q}{q+1} \leq q+1+\frac{(q+1)(1-\frac{q}{n})}{q+1-q}\frac{q}{q+1} \\&= q+1+q(1-\frac{q}{n}). \end{aligned}$$

(37)

The first equality follows by (14). The second equality uses $F(q,n,\frac{q}{n})=\sum _{s=q}^{n}f(q,n,\frac{q}{n})=f(q,n,\frac{q}{n})+\sum _{s=q+1}^{n}f(s,n,\frac{q}{n})=f(q,n,\frac{q}{n})+F(q+1,n,\frac{q}{n})$. The third equality uses $\frac{f(q+1,n,\frac{q}{n})}{f(q,n,\frac{q}{n})}=\frac{(n-q)\frac{q}{n}}{(q+1)(1-\frac{q}{n})}=\frac{q}{q+1}$, similarly to the proof of Lemma 1. The inequality follows from Diaconis and Zabell’s Theorem 2. The last equality is algebra. $\square$

1.5 Proof of Proposition 4

To prove the proposition, we use Hoeffding’s Theorem 1. Let $b'=\frac{b}{n}$, $q'=\frac{q}{n}$, $B'=\frac{B}{n}$ and $r'=\frac{r}{n}\in [0,1-q']$. Given n and r, $n-r=n(1-r')$ of the committee members receive positive favors and vote yes with probability $p=\frac{b}{n-r}=\frac{b'}{1-r'}$. Set $t=\frac{q-b}{n-r}=\frac{q'-b'}{1-r'}$ in the statement of Theorem 1. Then $t\in (0,1-p]$ as $q'-b'>0$ and $t\le 1-p\Leftrightarrow \frac{q'-b'}{1-r'}\le 1-\frac{b'}{1-r'}\Leftrightarrow q'\le 1-r'$, which holds since $r'\le 1-q'$.

Using Theorem 1, we have

$$\begin{aligned} F(q,n-r,b/(n-r))&=\,F(n(1-r')(p+t),n(1-r'),b'/(1-r'))\\ &\le\,\exp {[-2n(1-r')t^{2}]}\\ &\le\,\exp {\left[ -2n\frac{(q'-b')^{2}}{1-r'}\right] }\\ \end{aligned}$$

(38)

where $\frac{(q'-b')^{2}}{1-r'}>0$ for any $r'\in [0,1-q']$.

Now, $b'$ is optimal in ${{\mathbb {CE}}}$ if $(B-b)F(q,n-r,b/(n-r))\ge B-q$, or, equivalently,

$$\begin{aligned} F(q,n(1-r'),b'/(1-r'))\ge \frac{B'-q'}{B'-b'}. \end{aligned}$$

(39)

Fixing $b'$ such that $\epsilon =q'-b'>0$ and assuming $B'>q'$, there exists $\underline{n}_{\,\epsilon }$ such that for any $n\ge \underline{n}_{\,\epsilon }$

$$\begin{aligned} F(q,n(1-r'),b'/(1-r'))\le \exp {\left[ -2n\frac{(q'-b')^{2}}{1-r'}\right] }<\frac{B'-q'}{B'-b'} \end{aligned}$$

(40)

as $\lim _{n\rightarrow \infty }{\exp {\left[ -2n\frac{(q'-b')^{2}}{1-r'}\right] }}=0$, which concludes the proof. $\square$

1.6 Proof of Proposition 5

Suppose first that g is linear. The objective function in ${{\mathbb {FA}}_{g}}$ rewrites as

$$\begin{aligned}\sum _{s=0}^{n}{\mathbb {P}}_{s|n}^{*}[{\mathbf {p}}]g(s)&=\sum _{s=1}^{n}{\mathbb {P}}_{s-1|n-1}^{*}[{\mathbf {p}}^{\{i\}}]\left[ g(s)p_{i}+g(s-1)(1-p_{i})\right] \\ &=\sum _{s=1}^{n}{\mathbb {P}}_{s-1|n-1}^{*}[{\mathbf {p}}^{\{i\}}]\left[ g(s-1)p_{i}+kp_{i}+g(s-1)(1-p_{i})\right] \\ &=kp_{i}+\sum _{s=1}^{n}{\mathbb {P}}_{s-1|n-1}^{*}[{\mathbf {p}}^{\{i\}}]g(s-1)\\ \end{aligned} $$

(41)

where the first and the third equality follow by algebra and the second equality uses linearity of g. Proceeding iteratively, $\sum _{s=0}^{n}{\mathbb {P}}_{s|n}^{*}[{\mathbf {p}}]g(s)=k\sum _{i\in N}p_{i}+\sum _{s=n}^{n}{\mathbb {P}}_{s-n|n-n}^{*}[{\mathbf {p}}^{\{1\ldots n\}}]g(s-n)=k\sum _{i\in N}p_{i}+g(0)$ and, hence, any ${\mathbf {p}}\in X(b)$ such that $\sum _{i\in N}p_{i}=b$ constitutes a solution to ${{\mathbb {FA}}_{g}}$.

Suppose now that g is either convex or concave. The objective function in ${{\mathbb {FA}}_{g}}$ rewrites as

$$\begin{aligned}\sum _{s=0}^{n}{\mathbb {P}}_{s|n}^{*}[{\mathbf {p}}]g(s)&=\sum _{s=0}^{n}g(s)\left[ \begin{array}{l}(p_{i}(1-p_{j})+(1-p_{i})p_{j}){\mathbb {P}}_{s-1|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]\\ +\,p_{i}p_{j}{\mathbb {P}}_{s-2|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]+(1-p_{i})(1-p_{j}){\mathbb {P}}_{s|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]\end{array}\right] \\ &=\sum _{s=2}^{n}{\mathbb {P}}_{s-2|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]\left[ \begin{array}{l}g(s-1)(p_{i}(1-p_{j})+(1-p_{i})p_{j})\\ +\, g(s)p_{i}p_{j}+g(s-2)(1-p_{i})(1-p_{j})\end{array}\right] \\ &=\sum _{s=2}^{n}{\mathbb {P}}_{s-2|n-2}^{*}[{\mathbf {p}}^{\{ij\}}]\left[ \begin{array}{l}p_{i}p_{j}\left[ g(s)-2g(s-1)+g(s-2)\right] \\ +\, (p_{i}+p_{j})\left[ g(s-1)-g(s-2)\right] +g(s-2)\end{array}\right] .\\ \end{aligned}$$

(42)

Suppose ${\mathbf {p}}^{*}$ constitutes a solution to ${{\mathbb {FA}}_{g}}$. Then $(p_{i}^{*},p_{j}^{*})$ has to constitute a solution to

$$\begin{aligned} \max _{(p_{i},p_{j})\in {\mathbb {R}}^{2}}&\quad \sum _{s=2}^{n}{\mathbb {P}}_{s-2|n-2}^{*}[{\mathbf {p}}^{\{ij\},*}]z(p_{i},p_{j},s)\\ {\text {s.t.}}&\quad (p_{i},p_{j})\in X(p_{i}^{*}+p_{j}^{*}). \end{aligned} \quad\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ \ \ ({{\mathbb {FA}}_{g}'})$$

where

$$\begin{aligned} z(p_{i},p_{j},s)=\left[ \begin{array}{l}p_{i}p_{j}\left[ g(s)-g(s-1)-(g(s-1)-g(s-2))\right] \\ +(p_{i}+p_{j})\left[ g(s-1)-g(s-2)\right] +g(s-2)\end{array}\right] . \end{aligned}$$

(43)

Clearly, solution to ${{\mathbb {FA}}}_{g}'$, $(p_{i}',p_{j}')$ satisfies $p_{i}'+p_{j}'=p_{i}^{*}+p_{j}^{*}=k^{*}$. Substituting $p_{i}+p_{j}=k^{*}$ into $z(p_{i},p_{j},s)$ gives

$$\begin{aligned} \frac{\partial }{\partial p_{i}}z(p_{i},k^{*}-p_{i},s)&=(k^{*}-2p_{i})\Delta ^{2}g(s)\\ \frac{\partial ^{2}}{\partial ^{2}p_{i}}z(p_{i},k^{*}-p_{i},s)&=-2\Delta ^{2}g(s)\\ \end{aligned} $$

(44)

where $\Delta ^{2}g(s)=g(s)-g(s-1)-(g(s-1)-g(s-2))$.

To prove part 1, suppose $p_{i}^{*}\ne p_{j}^{*}$, so that $k^{*}>0$. Since g is convex, $\Delta ^{2}g(s)>0$ and, hence, $\frac{\partial ^{2}}{\partial ^{2}p_{i}}z(p_{i},k^{*}-p_{i},s)<0$, so that the objective function in ${{\mathbb {FA}}}_{g}'$ is strictly concave in $p_{i}$. Therefore, $(p_{i}',p_{j}')=(\frac{k^{*}}{2},\frac{k^{*}}{2})$, a contradiction to $p_{i}^{*}\ne p_{j}^{*}$.

To prove part 2, suppose $p_{i}^{*}\in (0,1)$ and $p_{j}^{*}\in (0,1)$ so that $k^{*}>0$. Since g is concave, $\Delta ^{2}g(s)<0$ and, hence, $\frac{\partial ^{2}}{\partial ^{2}p_{i}}z(p_{i},k^{*}-p_{i},s)>0$, so that the objective function in ${{\mathbb {FA}}}_{g}'$ is strictly convex in $p_{i}$. Therefore, either $(p_{i}',p_{j}')\in \{(k^{*},0),(0,k^{*})\}$ if $k^{*}\in (0,1]$ or $(p_{i}',p_{j}')\in \{(1,k^{*}-1),(k^{*}-1,1)\}$ if $k^{*}\in (1,2]$. In both cases, $(p_{i}^{*},p_{j}^{*})$ cannot constitute a solution to ${{\mathbb {FA}}}_{g}'$, a contradiction.$\square$