Formation of Parties and Coalitions in Multiple Referendums

Abstract

We consider a thought experiment in which voters could submit binary preferences regarding each of a pre-determined list of independent relevant issues, so that majorities could be tallied per issue. It might be thought that if such voting became technically feasible and widespread, parties and coalitions could be circumvented altogether and would become irrelevant. In this paper, we show, however, why and how voters would spontaneously self-organize into parties, and parties would self-organize into coalitions, prior to elections. We will see that such coordination is possible, even assuming very limited capabilities of communication and coordination. Using both analytical and empirical methods, we show that the average voter in a majority coalition would gain more than if no parties were formed, but the average voter overall (in or out of the coalition) would be worse off. Furthermore, the extent of these gains and losses is inversely proportional to the degree to which voters line along a unidimensional left–right axis.

1 Introduction

It has long been argued that parties form in representative democracies either because they help overcome logistic obstacles or because they serve the interests of politicians who wish to maximize their chances of election and their influence on political affairs (Downs 1957; Schlesinger 1991; Aldrich 1995; Aldrich 2011). We consider here a model in which emerging technology facilitates direct referendums on multiple issues instead of elections of representatives, thus, at least theoretically, eliminating both logistic obstacles and politicians. Our main finding is that even under these conditions, forms of self-organization closely approximating political parties and coalitions nevertheless emerge simply because such self-organization is on average beneficial for participating voters. We show when and how such parties and coalitions form and how they affect outcomes.

To capture the intuition, imagine a state, or any organization, that makes collective decisions through direct democratic means. Specifically, voters vote for or against each of a list of propositions and for each proposition the majority preference is decisive. This setup has long been considered a theoretical possibility (Rae and Daudt 1976; Anscombe 1976). In recent years, the technical barriers to its realization have gradually been surmounted by digital voting methods and cryptographic techniques for reconciling anonymity and verifiability (Schaupp and Carter 2005; Van Dijk 2012). Thus, while the adoption of this setup does not appear imminent, we consider it here as a plausible forward-looking thought experiment.

Under such circumstances, parties and coalitions—formally by-products of representative democracy—would no longer be essential to the operation of the political system. It might be concluded, therefore, that these institutions would cease to be relevant. Nevertheless, we will show in this paper that this is not the case. Voters could use side deals to spontaneously organize themselves into parties and coalitions in a largely predictable way and would be motivated to do so.¹

Consider a simple example. Suppose that 1000 voters are voting on some long list of propositions. Suppose further that 480 of the voters are “positive” types, who support every proposition, and that the other 520 voters are “negative” types, who oppose almost all propositions.² Specifically, suppose that for each proposition, some random 10% of the negative voters are in favor. The result would be that all the propositions would pass. Thus, despite the fact that the negative voters constitute a majority, the average negative voter would regret the result for 90% of the propositions.

The fact that per-issue majority voting can result in a situation in which most voters lose on a majority of issues is well-known (Anscombe 1976). But, it turns out that there are interesting ways to overcome this problem. Suppose, for example, that our 520 negative types were somehow capable of coordinating. Then they could agree to all vote against all propositions. The result would be that the average negative voter would regret the result for only 10% of all propositions. This illustrates that, at least in the case of binary voting, truthful voting is not always a dominant strategy and a group of voters can benefit through coordination.

We will see that such coordination is possible, even assuming very limited capabilities of communication and coordination. Our model makes three simple and plausible assumptions.

First, any “party”, i.e. a set of voters who agree to vote in tandem, would be constrained to vote in accordance with the intra-party majority preference regarding each proposition. Both the technical and regulatory mechanisms for enforcing this are readily available. [Note that our model precludes more sophisticated vote-trading (Ordeshook 1986)].

Second, given a set of parties to choose from, a voter will choose to join the party with preferences most similar to his or her own. We note that although it is conceivable that an insincere choice of party could benefit a voter, as in any voting system (Gibbard 1973; Satterthwaite 1975; Cho 2014), the limited degree of information available to voters in our model would not generally facilitate this type of strategic voting in our model (Campbell et al. 1960; Lazarsfeld et al. 1948; Abramson et al. 2004, 2010).

Third, parties would organize into a coalition—which would also be constrained to vote on each proposition according to the preference of the majority of voters in the coalition—but only if there is a “stable” coalition, i.e. a coalition for which there is no alternative coalition preferable to all parties in that alternative.

Given these assumptions, we will use both analytic and empirical methods to draw a number of conclusions.

Using analytic methods, we will conclude that parties that satisfy our assumptions can always be formed with very little coordination and that, given voter preferences, we can predict what parties are possible. Furthermore, stable majority coalitions can often, though not always, be formed. We further conclude that the average voter in the coalition will be better off than if no parties were formed in the first place, but the average voter overall (in or out of the coalition) would be worse off.

In addition, we develop a simulation method in which we are able to model degrees of unidimensionality—that is, the degree to which parties lie on a single left–right axis (Downs 1957; Stokes 1963; Sanders et al. 2011; Egan 2014). We find that the closer the parties are to lying along a single right-left axis, the greater the chances a stable majority coalition can be found and the greater the chances that (something approximating) the median party is in such a coalition (De Swaan 1973; Laver and Schofield 1990). Consequently, the gain to coalition members at the expense of the others is greatest when the parties do not lie on such a unidimensional continuum.

2 Comments on Related Work

We study here a model in which voters cast binary votes on each of a set of issues. We consider the result of majority voting within spontaneously-formed parties, followed by a second phase involving (weighted) majority voting across parties. Both the model and the idea of two-step voting have been contemplated previously. The literature (Rae and Daudt 1976; Rajat and Kelsey 1987; Nermuth 1992; Nurmi 1988; Laffond and Lainé 2000; Laffond and Lainé 2006; Laffond and Lainé 2009) is focused on the slightly paradoxical fact, found in our work as well, that two-step voting can lead to results in which the average voter is worse off than in straight per-issue majority voting.

Our work differs from all this previous work in one crucial way. Previous research assumes the prior existence of parties and/or constituencies that serve as the basis for two-step voting. By contrast, our work begins from a setting in which there are no parties and argues that the benefit to be had (at the expense of other voters) from forming parties will trigger the spontaneous formation of parties. We show precisely which parties will form and when and how these parties will self-organize into coalitions. Thus, we not only confirm empirically and analytically that parties can serve to the detriment of the average voter, we also demonstrate the extent to which this phenomenon is likely to be realized in various settings within a realistic forward-looking context.

The partitioning of voters into parties in some optimal way, as we consider here, has also been studied in the multi-agent systems literature, where it is called “coalition formation” (Shehory and Kraus 1998; Rahwan et al. 2015).³ Our model of party formation is very similar to the model considered in the multi-agent literature in that a partition is stable when no voter has an incentive to deviate from the party/coalition to which she belongs (Osborne et al. 1994) and the obtained stable partition is meant to maximize overall utility (Sen et al. 2000) (or, in our case, minimize regret). In the multi-agent literature, a variety of algorithms have been proposed to obtain this result for cooperative agents (Yang and Luo 2007; Gruszczyk and Kwasnicka 2008; Sandholm et al. 1998) and for non-cooperative agents (Aknine et al. 2004; Genin and Aknine 2010) in static and dynamic settings (Klusch and Gerber 2002). Our model is a specific partition function game in which utility is determined solely by the outcome of the vote for each issue (Riker 1962; Dodd 1976).

The model analyzed here is intermediate between direct democracy and representative democracy. In a very associative sense, it is similar to liquid (or delegative) democracy (Christoff and Grossi 2017; Kahng et al. 2018; Brill 2018), in which voters can delegate their votes to another voter, who in turn can delegate to another voter, and so on. Once the process has ended, each voter’s vote receives weight proportional to the number of votes delegated to her, directly or indirectly. In our model, on the other hand, once the initial seed parties have been declared, the process of delegation and voting is deterministic.

3 Model Description and Analysis

In this section we present first the basic definitions of voters and the outcome of an election (Sect. 3.1), then in Section 2.2 we present the process of partitioning the voters to parties, in Sect. 3.3 we analyze the regret of the voters from partitioning, and finally in Sect. 3.4 we define coalition and study its impact on the regret of the voters.

3.1 Voters

Let $A = \{a_{1}, \ldots a_{q} \}$ be a set of issues regarding each of which a society must make a binary decision. These may address social welfare policies, legalization of drugs, foreign policy, national security and so on. We assume throughout this paper that these issues are logically independent, so that we avoid dependency paradoxes of the sort considered by (Brams et al. 1998). A voter makes an independent binary choice regarding each issue (“for” or “against”).

Definition 1 [Profile]

For a voter v, the profile of v is the vector ${\text{v}} = {\text{v}}_{1}, \ldots,{\text{v}}_{\text{q}}$, where ${\text{v}}_{\text{i}} \in \left\{{1, - 1} \right\}$ represents the binary preference of v regarding issue ${\text{a}}_{\text{i}}$.

Let $sign(x) = \left\{{\begin{array}{*{20}l} {- 1,} \hfill & {x < 0} \hfill \\ {1,} \hfill & {x > 0} \hfill \\ {0,} \hfill & {x = 0} \hfill \\ \end{array}} \right.$

For a vector $\langle x\rangle = \langle x_{1}, \ldots,x_{q} \rangle$, let $sign(\langle x\rangle) = \langle sign(x_{1}), \ldots,sign(x_{q)} \rangle$.

Definition 2 [Outcome-V]

The outcome of an election given the set of voters $V = \{v^{1}, \ldots,v^{t} \}$ is $o(V) = sign\left({\sum\nolimits_{i = 1}^{t} {\langle v^{i} \rangle}} \right)$. That is, each issue is determined by the majority of voters.

To illustrate the definitions, we use a running example. The voters’ profile over three issues are presented in Table 1. The outcome of the election given $V = \{v^{1}, \ldots,v^{21} \}$ is $o(V) = \langle - 1,1, - 1\rangle$. For instance, the majority of the voters (14 of 21) oppose the first issue and thus its value is − 1.

Table 1 The voters’ profile over three issues

We measure a voter’s (dis-)satisfaction with the outcome of a vote according to the number of issues for which the outcome fails to accord with the voter’s preference. Let d(v, v′) be the Hamming distance between two voting profiles, $d(v,v^{{\prime}}) = \frac{{\sum\nolimits_{i = 1}^{q} {|v_{i} - v_{i}^{{\prime}} |}}}{2}$. We formally define a voter’s regret with regard to an outcome as follows:

Definition 3 [Regret-v]

The regret of a voter $v \in V$ is $r(v,V) = d(v,o(V))$.

Note that we implicitly assume that all issues are of equal importance to all voters. This assumption can be relaxed, for example by using a weighted Hamming distance in the above definition (d(v, v′)), but we retain it for simplicity.

3.2 Stable Parties

We now consider how a set of voters might collude to lower their collective regret. A set of voters form a party⁴:

Definition 4 [Party]

A party p is a set of voters, possibly with distinct individual profiles, that collectively casts |p| copies of a single profile: $\langle p\rangle = \langle p_{1}, \ldots,p_{q} \rangle$. The profile cast by a party is called its actual profile.

Note that, unlike in the case of an individual voter, a party profile might include 0’s. That is, p_j might be 0, for some values of j.

Let V be the set of all voters and let $P = \{p^{1}, \ldots,p^{n} \}$ be a partition of V into n parties.

Definition 5 [Outcome-P]

The outcome of an election given the partition $P = \{p^{1}, \ldots,p^{n} \}$ is $o(P) = sign\left({\sum\nolimits_{i = 1}^{n} {|p^{i} | \cdot \langle p^{i} \rangle}} \right)$.

For a party p, the (non-binary) vector $\sum\nolimits_{v \in p} {\langle v\rangle}$ is called the natural weighted profile of p and the vector $sign\left({\sum\nolimits_{v \in p} {\langle v\rangle}} \right)$ is called the natural profile of p. That is, the natural profile of a party is the one that accords with the majority of party members for each issue.

Definition 6 [Natural party]

A party p is natural if its actual profile is its natural profile: $\langle p\rangle = sign\left({\sum\nolimits_{v \in p} {\langle v\rangle}} \right)$.

We assume here that all parties must be natural in this sense, whether for pragmatic or regulatory reasons. Given that every party in a partition is natural, we can determine the outcome of an election from the partition.

Definition 7 [Natural outcome]

The natural outcome of an election given the partition $P = \{p^{1}, \ldots,p^{n} \}$ is $o*(P) = sign\left({\sum\nolimits_{i = 1}^{n} {|p^{i} | \cdot \left({sign\left({\sum\nolimits_{v \in p} {\langle v\rangle}} \right)} \right)}} \right)$.

As above, we define the distance between a voter and a party as the Hamming distance between their respective profiles: $d(v,p) = \frac{{\sum\nolimits_{i = 1}^{q} {|v_{i} - p_{i} |}}}{2}$. We assume that a voter votes for the nearest party. (This assumption both accords with observed behavior of voters and, as we shall soon see, is a plausible strategy given uncertainty regarding the votes of other voters.)

Definition 8 [Stable voter]

Given a voter v and a partition ${\text{P}} = \{p^{1}, \ldots,p^{n} \}$, v is said to be a stable voter if v belongs to the nearest party: $v \in p^{k}$ where k = argmin_j d(v, p^j).

We define a stable partition as a partition in which both our above assumptions are satisfied simultaneously: each party is natural and each voter is stable:

Definition 9 [Stable partition]

Given a set of voters V and a partition of, $P = \{p^{1}, \ldots,p^{n} \}$, we say that P is a stable partition of V if:

• 1. Every $p^{j} \in P$ is a natural party.

• 2. Every $v \in V$ is a stable voter.

To illustrate the non-triviality of the stability requirement for partitions, consider the following examples. Assume the partition of the voters in Table 1 to two parties: p¹ contains the voters in groups 1 and 5 and p² the rest of the voters. The first requirement for stable partition is that the two parties must be natural. This will be satisfied by defining the respective party profiles $\langle p^{1} \rangle = \langle - 1, - 1, - 1\rangle$ and $\langle p^{2} \rangle = \langle 1,1, - 1\rangle$. However, in this case the voters in group 3 will not be stable since their profile is closer to $\langle p^{1} \rangle$ than to $\langle p^{2} \rangle$. By contrast, consider the partition where p¹ contains the voters in groups 1, 3 and 5 and p² the rest of the voters. The natural profile of the parties are $\langle p^{1} \rangle = \langle - 1,1, - 1\rangle$ and $\langle p^{2} \rangle = \langle 1,1, - 1\rangle$. All the voters in this case are stable since each one of them belongs to the closest party. Thus, this is a stable partition.

Given the large number of possible partitions, the question is how voters can organize themselves into a partition that is stable?

First note that there are two extreme partitions that are trivially stable.

Definition 10 [Individualist partition; unity partition]

The individualist partition I is the partition in which each voter is its own party. The unity partition U is the partition in which all voters are in a single party.

Both of these partitions yield the same outcome: $o(I) = o(U) = sign\left({\sum\nolimits_{i = 1}^{n} {\langle v^{i} \rangle}} \right)$. We will call this outcome the per-issue majority. Moreover, both of these partitions are stable. In the case of the individualist partition, the natural profile of each party (i.e. voter) v is obviously just $\langle v\rangle$ and the partition is stable since d(v, v) = 0. Likewise, the unity partition is stable since the only party is necessarily the closest party.

More importantly, however, there is a procedure that can be used by voters to obtain a non-trivial stable partition. Let $\left\| V \right\|$ be the number of distinct profiles among the set of voters V and let m be some number such that $1 \le m \le \left\| V \right\|$. Consider the following procedure:

Procedure 1

• 1. m random voters with distinct profiles declare parties

• 2. each voter joins the nearest party

• 3. each party announces its (new) natural profile

  Steps 2 and 3 are repeated until no voter switches parties.

In Step 2, ties are broken randomly, except in cases of a tie between a voter’s current party and another party, in which case the voter stays put. Procedure 1 is analogous to a well-known clustering procedure known as k-means (MacQueen 1967).

To demonstrate how the procedure works, consider the case in which voters v¹, v⁷ and v¹⁰, with the corresponding actual profiles $\langle - 1, - 1, - 1\rangle,\langle 1,1,1\rangle,\langle - 1,1, - 1\rangle$, declare parties p¹, p² and p³, respectively. According to the second step of Procedure 1, each voter joins the nearest party. This results in the partition shown in the rows associated with iteration 1 in Table 2. Note that voters $v^{13} - v^{16}$ and $v^{17} - v^{21}$ are equidistant to p² and p³. In this case, suppose that $v^{17} - v^{20}$ join p³, while $v^{13} - v^{16}$ and v²¹ join p². Now, the party profiles are updated in accordance with the third step of the procedure. The new natural weighted and unweighted profiles, respectively, of each party are shown in the sixth and seventh columns. At the end of the first iteration, v²¹ is not stable since the new natural profile of p³ is closer than that of p², and thus in the second iteration, voter v²¹ moves to party p³. As a result, the profile of party p² is updated and now the partition becomes stable.

Table 2 Parties and their profiles after a first and second iterations of the procedure

Theorem 1

Procedure 1 converges in a finite number of iterations to a stable partition.⁵

Of course, it follows immediately from this theorem that non-trivial stable partitions exist.

We consider now the possibility that voters in small parties might abandon that party in favor of a larger party, since small parties are less likely to participate in a coalition, as shall be described below. We can adjust the procedure slightly as follows:

Procedure 2

• 1. m random voters with distinct profiles declare parties

• 2. each voter joins the nearest party

• 3. each party announces the number of current members; if a party has fewer than proportion ε of all voters, each member of that party joins the next nearest party (i.e., the party disbands)

• 4. each party announces its (new) natural profile

  Steps 2–4 are repeated until no voter switches parties.

It is easy to see that this adjusted procedure also converges in a finite number of iterations to a stable partition, though in this case we are also guaranteed that the final number of parties is bounded above by 1/ε.

It is important to note that the above procedure requires no central coordination. Voters and parties need only know (tentative) party profiles at each stage of the procedure.

3.3 Collective Regret

Our key analytic results concern the effect of party and coalition formulation on the collective regret of voters. We begin by extending the definition of regret introduced earlier. Recall that o*(P) is the natural outcome of partition P.

Definition 11 [Regret]

Given a partition P, the total regret of a party$p \in P$ is $r(p,P) = \sum\nolimits_{v \in p} {d(v,o^{*} (P))}$. The total regret of the partition P is $r(P) = \sum\nolimits_{p \in P} {r(p,P)}$.

Collectively, the voters’ preference is to minimize aggregate regret. But each individual party, like each individual voter, seeks to minimize its own regret. Our first result is that any time non-trivial parties are formed, collective regret is increased.

Theorem 2

For any partition P, the total regret of all voters is more than or equal to the total regret of all voters for the individualist partition:

$$ r(P) = \mathop \sum \limits_{v \in V} d(o^{*} (P),v) \ge \mathop \sum \limits_{v \in V} d(o^{*} (I),v) = r(I). $$

But the disincentive to form parties that is implied by this theorem is offset by the advantage party members obtain. Let P/p be the partition obtained from the partition P by disbanding party p; that is, the members of party p vote as individuals, while all other parties remain the same. We find that, all other parties being held fixed, party members are, on average, better off coordinating than not.

Theorem 3

For any partition P, the total regret of all voters in party$p \in P$is less than or equal to the total regret of those voters in partition P/p:

$$ r(p,P) = \mathop \sum \limits_{v \in p} d(o^{*} (P),v) \le \mathop \sum \limits_{v \in p} d(o^{*} (P/p),v) = r(p,P/p). $$

This is a somewhat weak justification of our assumption that voters should prefer to join parties, since it holds on average for party members, but not necessarily for a given individual voter. In fact, an individual voter $v \in p$ only affects the outcome regarding issue i if three conditions hold: (1) v is decisive within p regarding issue i; (2) a majority of voters not in p oppose v regarding issue i; (3) the number of voters in p is greater than the difference between the majority and minority voters not in p. In other words, v is indifferent unless he is a swing voter in a swing party. Thus, in principle, a voter should wish to join a party that is not too small (condition 3) and in which members are evenly divided regarding many issues (condition 1), rather than the nearest party. However, since we assume that during the party formation process, tentative parties announce only their profiles and the number of voters, as a practical matter, voters can be presumed to join the nearest party that is not too small.

3.4 Stable Coalitions

We have seen above that, regardless of their respective profiles, voters can, with a small amount of interaction, spontaneously organize themselves into parties. We will now see that sometimes, though not always, parties can organize themselves into coalitions by merging.

We have stipulated that parties must be natural.⁶ We will now stipulate further that merged parties—coalitions—must be natural as well, thus trivially avoiding complicated intra-coalitional conflicts (Bowler et al. 2016). Thus, while merging implicitly involves issue-trading among parties, the naturalness constraint precludes strategic issue-trading (Ordeshook 1986).

Definition 12 [Coalition; majority coalition]

A coalition is a set of parties, $C \subseteq P$, that merge into a single party. A coalition C is a majority coalition if a majority of voters in V are in C.

We can think of a coalition as simply being a less granular version of a partition. A voter who is a member of a party in coalition C is said to be a member of C. The natural profile of a coalition C is defined exactly the same way as the natural profile of a party: $\langle C\rangle = sign\left({\sum\nolimits_{v \in C} {\langle v\rangle}} \right)$. We denote a partition P in which parties $C \subseteq P$ have formed a coalition by P/C.

The regret of party p given coalition C in partition P is computed as the regret of the party given P where C is considered as one party. This regret is denoted by r(p, P/C). Table 3 shows the total regret of the various parties shown in Table 2 for each possible (non-trivial) coalition. For instance, the outcome given the coalition {p², p³} is $\langle - 1,1,1\rangle$. The regret of party p² given the coalition {p², p³} is 11.

Table 3 Total regret of different parties shown in Table 2 coalitions

We now consider the consequences of such coalition formation. We saw above that total regret over all voters would be minimized if voters would not form parties or coalitions at all. Nevertheless, voters are incentivized to form parties and coalitions because those voters who do join coalitions do in fact diminish their own overall regret. Of course, per the previous theorem, they increase the regret of non-coalition members at least as much as they diminish their own regret.

Theorem 4

For any majority coalition C in partition P, the total regret of voters in C is less than or equal to the total regret of those same voters for the individualist partition:

$$ \mathop \sum \limits_{v \in C} d(o(P/C),v) \le \mathop \sum \limits_{v \in C} d(o(I),v). $$

In short, while the average voter minimizes regret in an individualist (or unity) partition (that is, if there were no parties or coalitions formed at all), the average member of a majority coalition always has less than or equal regret than they would have in an individualist partition.

This theorem can be demonstrated in Table 3. The overall regret for the individualist partition is 21. Now consider, for example, the majority coalition, {p², p³}. The overall regret of the outcome determined by this coalition is 26, so that, as is inevitable, overall regret increases. But the total regret of coalition parties {p², p³} is 14, which is less than the total regret of these parties in an individualist partition – 15.

The question then is which majority coalition will in fact be formed.

For a given partition P, we say that a party p prefers coalition C′ to coalition C, if the regret of party p given coalition C′ in partition P is less than the regret of party p given coalition C in partition P. We say that coalition C is dominated by coalition C′ if all parties in C′ prefer C′ to C. A stable coalition is not dominated by an alternative coalition:

Definition 13 [Stable coalition]

Given a partition P, a majority coalition C is stable if there is no coalition C′ such that every party in C′ prefers C′ to C: ${\nexists}C^{\prime} \subseteq 2^{P} \;{\text{s}} . {\text{t}}.\; \forall p \in C^{\prime} r(p,P/C) > r(p,P/C^{\prime})$.

Note that coalition stability is closely related to the notion of the “core” of a coalition game (Banerjee, Konishi, and Sönmez 2001).

As can be seen in Table 3, two of the coalitions shown for our example are stable. For example, coalition {p², p³} is stable since, party p³ in the alternative coalition {p¹, p³} prefers the coalition {p², p³} (with regret = 3) to coalition {p¹, p³} (with regret = 5), while party p¹ does not prefer the coalition {p¹, p²} to coalition {p², p³} (same regret = 12). However, the coalition {p¹, p²} is not stable since it is dominated by coalition {p¹, p²}, party p¹ prefers it with regret = 6 and party p³ prefers it with regret = 5. Note that there are partitions for which there is no stable majority coalition (and there are partitions for which there is more than one stable majority coalition).

We present examples for each one of the situations. Above we have demonstrated a partition where some of the possible majority coalitions are stable. Next, we present an example where no stable majority coalition exists. For this, assume the voters and their partitioning to parties appear in Table 4. Note that this is a stable partition since all voters are stable and all parties have a natural profile.

Table 4 Voters partition

There are three possible majority coalitions, as presented in the first row of Table 5. The cells of the table show the regret of each coalition to each one of the parties. For instance, the regret of party p¹ in coalition {p¹, p²} is 7. The last row indicates which coalition dominates the coalition in the header of that column and caused it to be not stable. For instance, the coalition {p¹, p²} is dominated by the coalition {p¹, p³} since the regret of the parties p¹ and p³ is lower in coalition {p¹, p³} than in coalition {p¹, p²}. As can be seen each coalition is dominated by another coalition and thus there is no stable coalition.

Table 5 The regret of each party given optional coalitions

To summarize what we have seen so far, it is always possible for voters to form stable parties. Furthermore, in some, but not all, cases, parties can form stable coalitions.

Our main contention is that for those cases where a stable coalition exists, the outcome will be precisely the formation of such a coalition. Crucially, this coalition is likely to yield a different outcome than the expected one in which each issue is resolved by the majority. As we have seen, it is always the case that this outcome will be better than per-issue majority for the average coalition member and worse than per-issue majority for the average non-coalition member. In the following section, we’ll use simulations to consider under what circumstances such a stable coalition is likely to exist and to what extent the outcome of such a coalition deviates from the per-issue majority.

Some intuition can be gained by returning to the example, mentioned in the introduction, in which 480 (“positive”) voters vote + 1 on every issue and 520 (“negative”) voters vote − 1 on 90% of issues. Suppose that, for each issue, roughly 10% of negative voters vote + 1. Since 532 (= 480 positive voters + 52 negative voters) vote + 1 for each issue, the expected outcome is + 1 for all issues.

Now let’s see what happens according to our model. Some number of voters declare parties, most likely including at least one positive type and one negative type. All stable partitions will include one positive party (with natural profile + 1 for all issues) and one or more negative parties. The only stable majority coalition will include all the negative parties and its natural profile will be − 1 for all issues, which determines the actual outcome.

Note that the total regret for the natural outcome—a per-issue majority—is 468 per issue, while the total regret for the actual outcome is greater—532 per issue. The total regret of voters in the coalition (the negative types) is, however, reduced from 468 (520 – 52 negative types voting positive for that issue) to 52 per issue, while the total regret of voters in the opposition (the positive types) is increased from 0 to 480 per issue.

We emphasize the two crucial points. First, the outcome that results from voters self-organizing into parties and coalition can be very different than the outcome obtained from a straightforward per-issue majority. Second, as must always be the case, the reduction in regret of the coalition is not as great as the increase in regret to the opposition.

4 Simulations

In this section, we evaluate the party formation and coalition formation procedures by a simulation. Specifically, we examine the parameters that affect the stable coalition and the regret of the voters in the coalition and out of the coalition. In Sect. 4.1 we describe how we generated the simulation and in Section 4.2 we present the results of our experiments.

4.1 Experimental Setup

We consider simulations of voter behavior. The first step is to generate a set of voter profiles. In principle, we could simply generate these randomly. This would not, however, reflect any realistic situation. Rather, we first generate a set of voter prototypes and then we generate voter profiles on the basis of these prototypes. More specifically, in these simulations we initially define “ideal” prototypes. The ideal prototypes are all of the form $\langle - 1, \ldots, - 1,1, \ldots,1\rangle$, where the extreme prototypes are $\langle 1, \ldots,1\rangle$ (we will call this the “right” extreme) and $\langle - 1, \ldots, - 1\rangle$ (the “left” extreme). The point of defining ideal prototypes this way is to capture the notion of unidimensionality: all voters lie on a single left–right axis, so that the later a voter transitions from − 1 to 1 the more left-wing the voter. This definition of ideal prototypes lying along a single dimension allows us to conveniently generate actual prototypes that vary from unidimensionality in a measurable way.

Specifically, we generate eleven such ideal prototypes, each of length 50 (the number of issues), where the transition points are after 0, 5, 10, …, 50 issues, respectively. Now, to generate the actual voter profiles, we introduce two types of noise to the ideal prototypes. The first is called prototype noise. In defining actual prototypes for a given trial, we begin with an ideal prototype and introduce some specified amount of noise, 0 ≤ α ≤ 0.5. That is, we generate the actual profile corresponding to an ideal prototype by keeping or switching each bit according to a coin toss with probability α of landing on “switch”. The lower the prototype noise, the closer voters are to lying along a single left–right axis. When α = 0.5, prototypes are entirely random.

The second type of noise is called voter noise. Given a prototype, a voter profile of that type is generated by introducing some specified amount of noise, 0 ≤ β ≤ 0.5. That is, we generate each voter profile associated with a given prototype by keeping or switching each bit according to a coin toss with probability β of landing on “switch”. The lower the voter noise, the more loyally voters toe the party line. When β = 0.5, voters are entirely independent of party affiliation.

In each trial below, we generate 1000 voter profiles. The number of voters assigned to each prototype is generated according to a beta distribution with α = β = 2. In this way, the number of voters of parties near the center of the spectrum is greatest and tapers off gradually towards either extreme.

Given a set of voters generated as described above, we generate parties and coalitions. To generate parties, we choose 15 random seeds and run Procedure 2, using a threshold of 5% for party participation (ε = 0.05). Clearly, the resulting partition into parties depends on the initial random seeds. Furthermore, for a given partition, there might be more than one possible stable majority coalition. As in related contexts (Ray 2007), there are various methods for selecting one coalition from among many possible ones. For the purpose of these experiments, in cases of multiple stable coalitions for a given partition, we assume that the coalition is formed according to the preference of the largest party capable of forming a coalition; that is, we choose the coalition with the least regret for the largest party that is a member of some stable majority coalition.

We consider two main types of questions:

• 1. How do prototype noise and voter noise affect the chances of there being some stable majority coalition? And when there is such a coalition, how much regret is saved by the coalition and at what price to the opposition?

• 2. To what extent is the outcome, after party and coalition formation, predictable despite the randomness in the choice of initial seeds and how much does it differ from a straight majority vote (with no parties or coalitions).

We shall see that the answers to these questions are tightly connected to the extent to which voters lie along a single right-left axis.

5 Results

For our first experiment, we proceed as follows. For each combination of choice of prototype noise level (0, 0.1, 0.2, 0.3, 0.4, 0.5) and choice of voter noise level (0, 0.1, 0.2, 0.3, 0.4), we generate 100 distinct sets of voters. (Note, though, that when both noise types are 0, there is actually just a single possible set of voters and that when voter noise = 0.5, voters are entirely random so that prototype noise is not relevant.) In each case, we generate random seeds and run both party and coalition formulation. First we check, for what proportion of the 100 trials there is at least one stable coalition. Results are shown in Fig. 1.

Fig. 1

Proportion of trials with a stable coalition

Note that the proportion of runs yielding a stable coalition decreases as prototype noise increases. In fact, when there is no prototype noise—that is, prototypes align on a single left–right dimension—there will almost always exist a stable coalition, even with voter noise of up to 30%. More generally, the proportion of runs with stable coalitions appears to be invariant with respect to voter noise until such noise becomes extreme (0.4 or above).

Now let’s consider, for those cases where a stable coalition exists, by how much regret is decreased for members of the coalition and increased for the opposition, compared to a straight majority. In Fig. 2, for each combination of prototype noise and voter noise, the bar above the 0 line indicates the amount of increased regret for opposition members and the bar below the line indicates the amount of decreased regret for coalition members. We have already proved analytically that the decrease in regret for coalition members is always less than the increase in regret for opposition members and this is borne out in the figure. Furthermore, we find that both values grow with prototype noise and diminish with voter noise. The most extreme deviations from the regret obtained from straight per-issue majority are for the case where prototypes are essentially random—not lying along a unidimensional left–right axis—but where voters hew closely to the party line.

Fig. 2

The bar above the 0 line indicates the amount of increased regret for opposition members and the bar below the line indicates the amount of decreased regret for coalition members

The reason for this is made evident in Fig. 3. When prototype noise is 0, the largest party is also the median party along the single left–right axis. As can be seen in the figure, in such cases the median party is always in a stable majority coalition; thus, the coalition will not deviate much from the median profile, which itself does not deviate much from the per-issue majority. As prototype noise increases, the proportion of cases for which the majority party—a reasonable proxy for the median party—is in a stable majority coalition decreases, resulting in greater deviation from the per-issue majority.

Fig. 3

The proportion of cases for which the majority party is in a stable coalition

We now wish to consider how often we are able to predict the actual outcome of such a vote despite the inherent randomness of party formation and how often this prediction will differ from the “expected” outcome, namely, the result of a majority vote on each issue.

Since we wish to determine the predictability of results in the face of random seed selection, we design a slightly different experiment than that considered above. Here we choose 10 voter sets for each combination of prototype noise and voter noise. For each such set, we run 100 trials in each of which we randomly choose 15 seeds to begin the process of party formation. We wish to see which outcomes are almost invariant over seed choice.

First, we show in Fig. 4 the average proportion of issues for which the outcome agrees with a straight per-issue majority vote for each degree of prototype noise. This is an average value over all 100 seeds for each of 10 voter sets and all degrees of voter noise from 0 to 0.4, so it does not tell us anything about predictability yet. As is evident, agreement decreases as party prototypes depart from a unidimensional left–right axis. This is consistent with what we saw in Fig. 2.

Fig. 4

The average proportion of issues for which the outcome agrees with a straight per-issue majority vote for each degree of prototype noise

We regard the outcome regarding an individual issue as “predictable” if at least 80% of the 100 randomized seed selections yield the same result for that issue. In Fig. 5, we show, for each value of prototype noise, the proportion of predictable issues. (Note that each such value represents an average over 50 runs—10 voter sets and 5 values of voter noise.) The blue part of the bar represents the issues where the outcome agrees with a majority vote and the orange presents the outcome in which it does not agree with a majority vote.

Fig. 5

% Of predictable issues (at least 80% of the 100 randomized seed selections yield the same result for that issue), distinguished by cases that yield the same result as majority (blue) and those that do not (orange). (Color figure online)

Thus, we find that as prototype noise increases—that is, the less voters lie along a single left–right axis—the more difficult it is to predict the actual outcome. Nevertheless, since it is precisely in such cases that there is most frequent disagreement between actual outcomes and the expected outcome, these are the cases for which we can confidently predict surprising outcomes.

6 Conclusions

We have considered the scenario in which voters participate in multi-issue referendums in which each issue is binary and meant to be resolved by majority vote. We make a number of straightforward assumptions about the degree of possible direct communication among voters. Given recent advances in communications technology for preserving both verifiability and anonymity, this is an increasingly plausible scenario.

We have found that in this setting it is easy for voters to self-organize into parties and coalitions and likely that they will do so. Assuming only that parties and coalitions must satisfy some “stability” criteria, we have seen that the particular ways in which voters will form parties and coalitions is at least partially predictable. In particular, party formation will conform to the results of the well-known k-means clustering algorithm.

We have found further that outcomes based upon such parties and coalitions can deviate from the natural majority-vote outcome. When this happens, members of the coalition profit even as the total regret of all voters is increased. For this reason, voters are incentivized to self-organize into parties and coalitions, even though this results in harm to overall social welfare.

Furthermore, simulations based upon two kinds of artificially introduced noise, voter noise and prototype noise, show that the above results are tightly tied to the extent to which voters lie along a unidimensional left–right axis. The closer voters are to unidimensionality, the more frequently stable coalitions can be formed but the lower the overall harm to social welfare in cases where such a coalition is formed. The greater the voters’ deviation from unidimensionality, the greater the number of issues for which the outcome will be (predictably) different than the majority preference.

A number of problems are left for future work. Our framework can be extended to scenarios in which each voter assigns different weights to different issues or in which voters share only some of their preferences. Similarly, voters might prefer to join parties strategically rather than to simply join the nearest party. This line of research would open interesting game-theoretic directions we have ignored in this paper.

Finally, we note that the harm to social welfare caused by spontaneous formation of parties and coalitions raises interesting questions about the desirability and feasibility of regulatory schemes for mitigating this harm.

Appendix: Proofs

Proof of Theorem 1

To prove the theorem, we first define intra-party regret, a measure of voters’ dissatisfaction with their respective parties.

Definition 5 [Intra-party regret]

Given a partition P, for each party $p \in P$, let $\langle p\rangle$ be the (not necessarily natural) profile of p.The intra-party regret for a party p is $ir(p,\langle p\rangle) = \sum\nolimits_{v \in p} {d(v,\langle p\rangle)}$. Let $\langle p\rangle$ represent the set of profiles of parties in P. The total intra-party regret of the partition P is $ir(P,\langle P\rangle) = \sum\nolimits_{p \in P} {d(p,\langle p\rangle)}$.

It is important to distinguish between intra-party regret, which is the dissatisfaction of voters with their respective parties, and total regret, which is the dissatisfaction of voters with the outcome of an election.

We will show that Procedure 1 converges to a stable partition. The key idea is that each step of the procedure decreases the value of $ir(P,\langle P\rangle)$. Since $ir(P,\langle P\rangle)$ is bounded from below, the process must converge. Furthermore, since at the last step, we require that the party be natural and the voters be stable, the final result is a stable partition.

It remains to show that $ir(P,\langle P\rangle)$ diminishes at each step.

First, we show that each application of Step 2 diminishes $ir(P,\langle P\rangle)$. Specifically, we must show that intra-party regret is diminished when each voter joins the nearest party. For a given voter v, let p^j(v) be the party of v prior to Step 2 and let p*^(v) be the party of v subsequent to Step 2. Then, p*^(v) is the nearest party to v. Let P be the partition prior to Step 2 and let P′ be the partition that results from Step 2. Note that in Step 2, voters switch parties but the party profiles remain fixed. Then we have:

$$ ir(P^{{\prime}},\langle P\rangle) = \mathop \sum \limits_{v \in V} d(v,\langle P^{*(v)} \rangle) \le \mathop \sum \limits_{v \in V} d(v,\langle P^{j(v)} \rangle) = ir(P,\langle P\rangle) $$

Now we show that each application of Step 3 diminishes $ir(P,\langle P\rangle)$. In Step 3, we change the profile of each party to its natural profile, but we do not change the membership of any party. For a party p, let its profile prior to Step 3 be $\langle p\rangle$ and let its profile subsequent to Step 3 be $\langle p\rangle^{*} = sign\left({\sum\nolimits_{v \in p} {\langle v\rangle}} \right)$. We need to show that:

$$ ir(P,\langle P\rangle^{*}) = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{v \in p} d(v,\langle p\rangle^{*}) \le \mathop \sum \limits_{p \in P} \mathop \sum \limits_{v \in p} d(v,\langle p\rangle) = ir(P,\langle P\rangle) $$

To see this, consider each issue i separately. Let $v_{i} \in \{1, - 1\}$ be the ith element in the profile of v. That is, it represents the preference of voter v regarding issue i. Likewise, for a party p, let $p_{i} \in \{1, - 1\}$ and $p_{i}^{*} \in \{1, - 1\}$ be the ith element in $\langle P\rangle$ and $\langle P\rangle^{*}$, respectively. Regarding issue i, the preference of the majority of voters in p is $sign\left({\sum\nolimits_{v \in p} {v_{i}}} \right)$ and the difference between support for the majority and minority preference is $m_{i} = \left| {\sum\nolimits_{v \in p} {v_{i}}} \right|$. The intra-party regret for p is thus:

$$ \mathop \sum \limits_{v \in p} d(v_{i},p_{i}) = \left\{{\begin{array}{*{20}l} {\frac{{\left| p \right| - m_{i}}}{2},} \hfill & {p_{i} = sign\left({\mathop \sum \limits_{v \in p} v_{i}} \right) = p_{i}^{*}} \hfill \\ {\frac{{\left| p \right| + m_{i}}}{2},} \hfill & {otherwise} \hfill \\ \end{array}} \right. $$

We now have the following inequality:

$$ ir(P,\langle P\rangle) = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{v \in p} d(v,\langle p\rangle) = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{v \in p} \mathop \sum \limits_{i = 1}^{q} d(v_{i},p_{i}) = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{i = 1}^{q} \mathop \sum \limits_{v \in p} d(v_{i},p_{i}) = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{i = 1}^{q} \frac{{\left| p \right| \pm m_{i}}}{2} \ge \mathop \sum \limits_{p \in P} \mathop \sum \limits_{i = 1}^{q} \frac{{\left| p \right| - m_{i}}}{2} = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{i = 1}^{q} \mathop \sum \limits_{v \in p} d(v_{i},p_{i}^{*}) = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{v \in p} \mathop \sum \limits_{i = 1}^{q} d(v_{i},p_{i}^{*}) = \mathop \sum \limits_{p \in P} \mathop \sum \limits_{v \in p} d(v,\langle p^{*} \rangle) = ir(P,\langle P^{*} \rangle) $$

□

Proof of Theorem 2

Consider each issue i separately. Let $v_{i} \in \{1, - 1\}$ be the ith element in the profile of v. That is, it represents the preference of voter v regarding issue i. Regarding issue i, the natural outcome of the individualist partition is $sign\left({\sum\nolimits_{v \in V} {v_{i}}} \right)$ and the difference between support for the majority and minority preference in V is $m_{i} = \left| {\sum\nolimits_{v \in p} {v_{i}}} \right|$. Since for the individualist partition each issue is decided in favor of the majority of voters, the overall regret of voters for the individualist partition regarding issue i is $\frac{{\left| V \right| - m_{i}}}{2}$. For any other partition, each issue is decided either in favor of the majority or the minority, so the overall regret of voters regarding issue i is either $\frac{{\left| V \right| - m_{i}}}{2}$ or $\frac{{\left| V \right| + m_{i}}}{2}$. Thus we have for any partition $P:\;r(P) = \mathop \sum \limits_{i = 1}^{q} \frac{{\left| V \right| \pm m_{i}}}{2} \ge \mathop \sum \limits_{i = 1}^{q} \frac{{\left| V \right| - m_{i}}}{2} = r(I)$ □

Proof of Theorem 3

As in the proof of Theorem 2, consider each issue i separately and let $v_{i} \in \{1, - 1\}$ be the ith element in the profile of v. Let $n_{i} = \sum\nolimits_{{p_{j} \ne p}} {p_{i}^{j}}$ and let $t_{i} = \sum\nolimits_{v \in p} {v_{i}}$. Then the outcome of the vote for issue i when the members of party p vote as individuals is sign(n_i + t_i). The outcome of the vote for issue i when the members of party p vote as a party is sign(n_i+ sign($\sum\nolimits_{v \in p} {v_{i}}$)|p|). Denote the regret of members of p for issue i by r_i(p, P) when they vote as a party and by r_i(p, P/p) when they vote as individuals. If sign(n_i)= sign(t_i) or if |t_i| > |n_i|, the outcome accords with the majority preference in p, whether the members of p vote as a party or as individuals; r_i(p, P) = r_i(p, P/p)= $\frac{{\left| p \right| - m_{i}}}{2}$, where $m_{i} = \left| {\sum\nolimits_{v \in p} {v_{i}}} \right|$. Otherwise, if |p| < |n_i|, then the outcome accords with the minority preference in p, whether the members of p vote as a party or as individuals; r_i(p, P) = r_i(p, P/p)= $\frac{{\left| p \right| + m_{i}}}{2}$. Finally, if |p| > |n_i|, the outcome accords with the majority preference of p if and only if they vote as a party. In this case r_i(p, P/p) = $\frac{{\left| p \right| + m_{i}}}{2}$ and r_i(p, P) = $\frac{{\left| p \right| - m_{i}}}{2}$ . Thus, for every i, r_i(p, P/p) ≥ r_i(p, P) so that r(p, P/p) = ∑_ir_i(p, P/p) ≥ ∑_ir_i(p, P) = r(p, P). □

Proof of Theorem 4

Consider each issue i separately. Regarding any issue i, the outcome given a majority coalition C is according to the majority preference within C. That is, $o(P/C) = sign\sum\nolimits_{v \in C} {v_{i}}$. The difference between support for the majority and minority preference within the coalition is $m_{i} = \left| {\sum\nolimits_{v \in C} {v_{i}}} \right|$. Thus, the overall regret of voters in the coalition regarding issue i is $\frac{{\left| C \right| - m_{i}}}{2}$. For the individualist partition, each issue is decided in favor of the majority of all voters, which might be the same as the majority of coalition members or not. Thus, the overall regret of coalition members regarding issue i is either $\frac{{\left| C \right| - m_{i}}}{2}$ (when the majority of voters share the preference of the majority of coalition members) or $\frac{{\left| C \right| + m_{i}}}{2}$ (otherwise). Thus, we have,

$$ \mathop \sum \limits_{v \in C} d(o(I),v) = \mathop \sum \limits_{i = 1}^{q} \frac{{\left| C \right| \pm m_{i}}}{2} \ge \mathop \sum \limits_{i = 1}^{q} \frac{{\left| C \right| - m_{i}}}{2} = \mathop \sum \limits_{v \in C} d(o(P/C),v). $$

□