Group Wisdom at a Price: Jury Theorems with Costly Information

1 Introduction

A cornerstone of the idea of wisdom of the crowds is the fact that individuals with different and possibly wrong beliefs can improve their chance of being correct about a ground truth state by aggregating their opinions. This intuition is memorably captured by the Condorcet Jury Theorem (CJT) [Condorcet, 1785; Nitzan and Paroush, 2017; Dietrich and Spiekermann, 2021], which states that a majority vote on a yes/no question is likely to produce the correct answer if voters cast their ballots independently of each other and are better than random at identifying the truth. Additionally, the probability of a correct group decision under these conditions grows as more agents are added to the group, to the point where, in the limit, groups of infinite size are guaranteed to be infallible. The CJT has been invoked in a variety of issues of practical relevance, from jury design [Mukhopadhaya, 2003; McCannon, 2011], to the prediction of political elections [Murr, 2015], and also as a justification of democracy as a desirable political system [Goodin and Spiekermann, 2018; Landemore, 2021].

Despite its appealing message, the CJT has attracted persistent criticism due to its assumptions, perceived to be highly idealized. Indeed, many of the optimistic conclusions of the CJT break down when these assumptions are relaxed [Nitzan and Paroush, 1984; Dietrich and List, 2004; Austen-Smith and Banks, 1996; Pivato, 2019], and a considerable literature has developed trying to recover those conclusions under more realistic conditions [Grofman et al., 1983; Ladha, 1992; Paroush, 1997; List and Goodin, 2001].

In this paper we question the assumption that possession of better-than-chance competence is frictionless, and ask what voting behavior looks like if, prior to casting their ballot, agents are required to put in some effort in order to acquire an appropriate level of competence. As in the standard setting, our setup implies that more voters translates to better decisions: but can we still expect, in the presence of effort, that every member of the group will vote? Concretely, we assume that agents have a choice between participating in the decision process, i.e., making the effort to educate themselves on the matter and casting a vote, and abstaining without effort.

We model this scenario as a game in which agents want to balance their interest in a correct (group) decision with the effort required to contribute to such a decision, and look at four variations of the basic framework. In the first, agents are assumed to have identical features; in the second, they differ in terms of how much value they place on getting the right answer; in the third, they differ in terms of their competences; in the fourth they are embedded in a social network, and thus differ in their awareness of the other agents. We then go on to study voter turnout in the pure Nash equilibria of the games thus defined, with an eye towards group accuracy in the limit, as the size of the group grows.

Contributions. We characterize the pure Nash equilibria (both simple and strong) for these games. We find that their structure incentivizes agents to vote only when they have the chance to be pivotal by breaking a potential tie, and that the addition of effort places an upper limit on the number of voters at equilibrium. Consequently, in all variations of the basic framework considered here we find that increasing the size of the overall group does not necessarily lead to an increase in group accuracy (measured over the agents that vote), thereby undermining the customary wisdom of crowds effect. Notwithstanding, we show that this effect can be recovered in certain social networks: by narrowing the horizon to their immediate neighbors, agents can end up seeing themselves as pivotal and vote at equilibrium, even though, under full awareness of the entire voting profile, they would not have an incentive to vote. This result depends on the topology of the graph, and raises interesting questions for future work.

Related Literature. Our paper is a contribution to the area of epistemic social choice (see [Elkind and Slinko, 2016]). More specifically, it adds to the broader line of research showing that when information acquisition is costly the conclusions of the CJT might not hold: if their chance of affecting the outcome is negligible, agents may decide to free ride on their peers by not acquiring information [McCannon and Walker, 2016; Ben-Yashar and Nitzan, 2001]. The main way to model this effect, which we also take as inspiration here, is to assume that voters receive a signal about the state of the world that can be accessed at a cost, and then to look at how the incentive structure influences voter behavior [Mukhopadhaya, 2003; Persico, 2004; Gerardi and Yariv, 2008; Koriyama and Szentes, 2009]. A related approach addresses the problem of information acquisition by moving from the so-called voting paradox [Aidt, 2000], which acknowledges that if voters were to behave rationally then in big elections no information acquisition would occur, as the actual benefit to voters would not be worth the learning effort [Ghosal and Lockwood, 2003; Martinelli, 2006; Feddersen, 2004; Feddersen et al., 2006; Feddersen and Sandroni, 2006].

A common assumption in the literature is that information gained depends on the amount of effort expended, with agents deciding on the quantity of effort to make. Here we take a simplified approach, according to which effort is a fixed quantity: voters either abstain or vote 'to the best of their abilities' with an associated effort. We believe this assumption is appropriate especially in small groups (e.g., trials, or pools of reviewers for academic conferences) where the required effort, either in terms of time invested or amount of research, is similar for all parties involved. Importantly, such a design choice also allows us to combine effort with other elements, e.g., individual differences in ability, different levels of interest and social networks. A similar effort model was studied by Bloembergen et al. [2019] in the context of wisdom of the crowds for liquid democracy.

Outline. The paper is structured as follows. Section 2 introduces key notation and concepts. Section 3 looks at the basic setting, in which agents' stakes and competences are uniform. Section 4 relaxes the assumption of uniform stakes, while Section 5 relaxes the assumption of uniform competences. Section 6 studies strategic behavior when knowledge of other agents' choices is constrained by a social network. Finally, Section 7 offers conclusions and outlines future work.

For reasons of space, detailed proofs are omitted. However, the main results are accompanied by discussions and intuitions which double as proof sketches.

2 Preliminaries

We assume a group of agents N = {1, ..., n}, with n ≥ 2, faced with a binary decision. Each agent i ∈ N chooses an action ai ∈ {0, 1}, with ai = 1 if the agent votes and ai = 0 if they abstain. An action profile is a vector a ∈ {0, 1}n , indicating the action taken by every agent. We focus here only on pure strategies, i.e., every agent's strategy is the action they decide to pursue. If a is an action profile, |a| = |{i ∈ N | ai = 1}| is the number of people voting in a. The action profile (a′i , a-i) is the profile that is exactly like a except that agent i takes action a′i instead of action ai. Each agent i has a utility function ui : {0, 1}n → R over action profiles. An action profile a∗ = (a∗1 , . . . , a∗n ) is a (pure) Nash equilibrium (NE) if there is no agent i and action a′i ∈ {0, 1} such that ui(a′i , a∗-i ) > ui(a∗ ) [Nash, 1950; Shoham and Leyton-Brown, 2008]. In an NE no agent wants to unilaterally deviate from its current action. A coalition is a set C ⊆ N. We write aC for the vector of actions taken by each agent in C. Given an action profile a, we denote with (aC, aN\C) the profile exactly like a except that each i ∈ C takes the action assigned in aC. A profile a is a strong (pure) Nash equilibrium (SNE) if there is no coalition C ⊆ N and action profile a′C such that ui(a′C , aN\C) > ui(a), for all i ∈ C. In a strong Nash equilibrium no coalition of agents wants to deviate from its current actions. The size of an equilibrium is the number of agents who vote in it.

Our primary assumptions are that each agent i ∈ N has a competence pi ∈ (1/2, 1), such that if i decides to vote, they are correct with probability pi, and that the group decision is taken by majority vote over the agents that decide to vote, with a (fair) coin toss in case of a tie. We also want to allow i to have a stake bi ∈ R>0 in the matter, which quantifies how much i cares about the group making the right decision. Lastly, we consider an effort e ∈ (0, 1 2 ), which is a cost imposed when agents decide to vote. We take competence, stake and effort to be factors in the agent's utility function ui, written here in its most general form as:

where P(a, p) is a place-holder function, to be instantiated with concrete expressions shortly, capturing the probability that a group of agents voting according to a and having competences p is correct. Intuitively, ui(a) is the probability that the group is correct, multiplied by i's stake in the matter, minus the effort required to vote. Naturally, an agent derives satisfaction from the group making a correct decision: the choice to express this satisfaction using P (a, p) indicates that we think of its value in expectation. Note that if the agent votes the effort amounts to e, whereas if they abstain the effort is 0, in which case their utility is derived entirely from the accuracy achieved by the agents that do decide to vote.

In the following sections we look at equilibria arising in this setup under concrete assumptions about how utility is derived. Specifically, we are interested in how good groups are at tracking the truth in such equilibria. Thus, we denote by δ(n, p) the group accuracy obtained at a Nash equilibrium 1 of minimal size in a society with n agents that have competences p; if no such equilibrium exists, we take δ(n, p) = 0. Inspired by Golub and Jackson [2010], we say that a group is wise if limn→∞ δ(n, p) = 1. The focus on small equilibria reflects an interest in the worst-case scenario in which we see the fewest number of voters we can rationally expect to get. On the flip side, any positive result for this scenario paints a very optimistic picture.

Finally, a notion that will play an important role is that of a maximal Nash equilibrium (MNE), which is an NE a such that P(a, p) ≥ P(a′ , p), for any other NE a′ , for a given profile of competences p and effort e, i.e., an NE where maximum group accuracy is obtained.

1 NE or SNE, depending on the analysis.

3 Equal Competence, Equal Stakes

In the basic setup we make all agents equally competent, i.e., pi = p ∈ ( 1 2 , 1), for i ∈ N, and set stakes uniformly to 1, i.e., bi = 1, for each i ∈ N. Consequently, we write p instead of p and can safely ignore the bi's.

Given a competence level p, a group of ℓ ≤ n voting agents and an integer k ≤ ℓ, we write P (ℓ, k) for the probability that exactly k out of the ℓ agents vote for the correct option. As customary, we assume that voters cast their ballots independently of each other, thus obtaining:

Given our assumptions, if ℓ out of the n agents show up to vote, the group accuracy M(ℓ, p) is the probability that the group gets the right answer:

Intuitively, the probability that the group is correct is the probability that a strict majority of the ℓ voting agents gets the right answer, together with the probability that the coin toss results in a favorable answer in case ℓ is even and the vote results in a tie. Important to our purposes is the fact that, if ℓ is odd, then M(ℓ-1, p) < M(ℓ, p) = M(ℓ+1, p), i.e., M(ℓ, p) grows monotonically with ℓ, but with non-zero jumps only from one odd value to the next. Moreover, the marginal accuracy gain M(ℓ, p) - M(ℓ - 1, p) obtained by adding one extra group member decreases monotonically with ℓ. These claims are proven rigorously in the appendix.

Under the above assumptions agent i's utility in a profile a is obtained by instantiating Equation (1) as follows:

i.e., the expected value of a correct decision reached by the voting agents, normalized by the effort i makes with its contribution. The setup here is close to that of the standard CJT, with two notable departures: group accuracy is defined for any size of the group (not just odd size) and, as we now show, not all agents are willing to vote. We start with the extreme cases when (almost) no one wants to vote.

Intuitively, p - 1/2 is the jump in group accuracy obtained by going from no voters to one voter: if the effort is higher than this jump, then no one has an incentive to vote. More interesting things happen when e < p - 1/2: to get a handle on them, we first define ne = max{ℓ ∈ N|M(ℓ, p) - M(ℓ - 1, p) ≥ e}, i.e., ne is the largest number of voters for which the jump in group accuracy from ne - 1 voters to ne exceeds the effort required to vote. This allows us to characterize the Nash equilibria of the voting game.

Theorem 1. If e < p- 1/2, a profile a is an NE iff |a| is odd and |a| ≤ ne.

Theorem 1 says that the Nash equilibria are those voting profiles where the number of voters that show up to vote is at most ne, and that number is odd. Its two findings can be understood, intuitively, as follows. Firstly, agents have an incentive to vote only if they can improve the group accuracy: given that M(ℓ, p) = M(ℓ + 1, p) for odd ℓ, this happens only when having a chance to cast the decisive vote in case of a perfect tie between the other voters. Second, the jump in accuracy from enlarging the voting group only goes so far: the marginal accuracy gain M(ℓ, p) - M(ℓ - 1, p) decreases monotonically as ℓ increases, and as soon as it dips below e any incentive to add new voters disappears. This explains the maximum cap of ne voters in a Nash equilibrium. Lastly, note that a Nash equilibrium always exists: as when e < p - 1/2, a one voter profile is an NE. 2

An immediate consequence of Proposition 1 and Theorem 1 is that wisdom of the crowds is lost, as the group accuracy in the Nash equilibrium of minimal size gets stuck at 0 or 1, i.e., δ(n, p) is equal to M(0, p) if the effort is larger than p - 1/2, and δ(n, p) is equal to M(1, p) otherwise.

Observation 1 indicates that we cannot expect wisdom of the crowds in an equilibrium. Can we do better with a strengthening of Nash equilibria? To answer this question, we characterize here also strong Nash equilibria (SNE), i.e., equilibria in which no coalition of agents has any incentive to deviate. An important auxiliary notion here is that of a Nash equilibrium of maximal group accuracy, referred to as MNE. If a is an MNE, its group accuracy M(|a|, p) is maximal and we write nmax = |a| for the number of voters in a. Since M(ℓ, p) grows monotonically with ℓ, maximal group accuracy is achieved in the equilibria with the most possible voters, i.e., nmax = ne if ne ≤ n, and nmax = n otherwise. Notably, neither an MNE can have a bigger size than ne, regardless of n (Theorem 1). Increasing the number of agents does not always help: once n = ne adding agents to the group will not change the accuracy that can be reached at an MNE.

Theorem2. A voting profile a is an SNE iff a is anMNE and M(nmax, p) ≥ M(n, p) - e.

As expected, a strong Nash equilibrium also needs to be a regular Nash equilibrium. In particular, it can be shown that if the profile is an NE, then no coalition of voters would drop out. Yet, any voting profile a with |a| < nmax cannot be a strong Nash equilibrium, as a coalition of nmax - |a| nonvoters would prefer to pitch in and vote in order to reach the highest accuracy attainable in a Nash equilibrium, which suggests that a group of ne voters is the most efficient option if coalitions are allowed. At the same time, having nmax voters succeeds at producing a strong Nash equilibrium only as long as the effort allows it: as soon as M(n, p)-M(nmax, p) > e, such an equilibrium ceases to exist. Thus, since the maximum accuracy of any NE, given e and p, is achieved at M(nmax, p), increasing n does not result in higher accuracy.

2 If e = 0 then every odd profile, as well as the profile with all agents in N, is a Nash equilibrium. If voting does not have a cost, then there is no drawback in showing up to vote.

So uniform effort undermines the wisdom of uniformly competent crowds even in the case of strong Nash equilibria.

4 Heterogeneous Stakes

In this section we consider heterogeneous stakes, while keeping the accuracies equal to p ∈ (1/2, 1). For clarity, the utility of an agent with a voting profile a in these conditions is:

i.e., utility is derived from the group accuracy scaled by how much the agent cares for the matter, captured by the term bi ∈ R+. We assume throughout the section that stakes are collected in the vector b = (b1, . . . , bn), and we write b+ = max{bi | i ∈ N} for the value of the largest stake. For a given voting profile a, we denote with b1min (a) = min{bi | ai = 1} the minimal stake among the agents that vote in a.

As in Section 3, we obtain that too high an effort leads to universal abstention, while lower levels of effort result in Nash equilibria of odd size. However, the introduction of heterogeneous stakes means that the particular thresholds are more complicated and that in certain cases to have an equilibrium the voter with the highest stakes wants to vote.

Proposition 2. Let a be a voting profile. Then: (i) if e > b+(p - 1 2 ), then a is an NE iff |a| = 0; (ii) if e = b+(p- 12 ), then a is an NE iff either |a| = 0 or |a| = 1 and ai = 1 for i s.t. bi = b+; (iii) if e < b+(p - 12 ), then a is an NE iff |a| is odd and b1min (a)(M(|a|, p) - M(|a| - 1, p)) ≥ e.

Notably, this shows that also in this case wisdom of the crowds is lost. Indeed, a slightly different version of Observation 1 holds for this setting.

Here too we look at SNEs. Can we obtain some form of wisdom of the crowds if we allow for coalitions to coordinate? To characterize strong equilibria, we need to look at the upper bound for an NE. By doing this we show that an upper threshold for the accuracy of an NE exists in this setting as well. We need some extra notation. Let ne,b be the threshold ne for a game with uniform accuracies p, uniform stakes equal to 1 and effort set to e/b. Recall that b+ =max{bi | i ∈ N}.

Theorem 3 indicates that given a certain stakes profile b the value b+ can be used to determine the upper bound of the size (and consequently, of the accuracy) of any equilibrium. Indeed, the threshold ne,b+ corresponds to the size of the equilibrium that is generated when there are at least ne,b+ agents with stakes equal to b+. As a consequence, if by adding people to a group the value for b+ does not increase, then the accuracy at the MNE may also not increase: larger groups do not always fare better.

Furthermore, Theorem 3 directly affects SNEs as well, as only a profile that is an NE can be an SNE. We use some further auxiliary notation. If N is the set of agents and b = (b1, . . . , bn) is a vector of stakes, N≥b = {i ∈ N | bi ≥ b} denotes the set of agents with stakes at least as large as b.

As in Theorem 2, the fact that a is an NE ensures that no coalition of voters deviates. The second condition then implies that no coalition of non-voters wants to show up to vote. An important, though expected, consequence is that the second condition implies that an SNE is also an MNE, as bi (M(|a| + x, p) -M(|a|, p)) ≤ e, where x = |{j ∈ N≥bi | aj = 0}|, holds only for MNEs. Indeed, the size of an SNE (if it exists) is unique, namely the same as the one of an MNE. As in Section 3, we can distinguish two cases: either there exists no SNE, as the second condition is not true for any MNE profile, or it exists and has accuracy equal to the MNE. And, again, as in Section 3, its existence depends on the agents left out from the voting at an MNE: if those agents could be able to produce a better outcome by moving together, the MNE would not be stable in terms of coalitions. In order to find an upper bound for the accuracy of an SNE it is enough to consider Theorems 3 and 4.

As long as b+ is kept constant, adding more agents does not make the accuracy at an SNE surpass the threshold set by M(ne,b+ , p).

5 Different Competences

In this section we revert to uniform stakes (which can thus be conveniently ignored in the analysis), but assume heterogenenous competences pi ∈ (1/2, 1). The immediate challenge is to define the accuracy of a group of voters with different competences: as in previous sections, we look at the probability of the majority voting for the right answer. Thus, given a profile p of competences, with |p| ≤ n, we take Np to be the set of agents in N whose competences are present in p. We then define the set W of winning coalitions as W = {S ⊆ Np | |S| ≥ (|p|+1)/2}, and the set T of tie coalitions, as T = {S ⊆ Np | |S| = |p|/2}. We take M(p) to be the probability that the majority of the voters represented in p gets the right answer, defined as follows:

The utility of i ∈ N with a voting profile a becomes@

Before presenting our results, we briefly introduce some new notation. If p = (p1, . . . , pk) is a profile of competences, then p + p′ = (p1, . . . , pk, p′ ) and, for pi in p, p - pi = (p1, . . . , pi-1, pi+1, . . . , pk). We write p+ = max{pi | i ∈ N} for the maximal competence of the agents in N. Given a voting profile a, we also write p1min (a) = min{pi | ai = 1} for the minimal competence among the voting agents and p0max (a) = max{pi | ai = 0} for the maximal competence among the non-voters. In addition, we write p(a) to denote the vector of competences of the voters in the profile a, i.e., for any i s.t. ai = 1 the value pi occurs in p.

As in previous sections, we start by studying the dependence of Nash equilibria on effort.

Proposition 3. Let a be a profile. Then: (i) if e > p+ - 12 , then a is an NE iff |a| = 0; (ii) if e = p+ - 1 2 , then a is an NE iff either |a| = 0 or |a| = 1 and ai = 1 with pi = p+; (iii) if e < p+ - 12 , a is an NE iff M(p(a)) ≥ M(p(a) - p1min (a)) + e and M(p(a)) ≥ M(p(a) + p0max (a)) - e. 3

If e ≥ p+ - 1/2, Proposition 3 is similar to Propositions 1 and 2. The difference emerges when e < p+ - 1/2, as the odd size of a profile is not a sufficient condition to guarantee that no non-voter wants to pitch in: the condition M(p) ≥ M(p - p1min (a)) + e must be explicitly added. Still, it can be proven that every NE is odd and, more importantly, that odd profiles where the competence of every voter is at least as high as that of every non-voter are always Nash equilibria, given an appropriate marginal increase in accuracy.

Corollary 1. If the profile a is such that |a| is odd, p1min (a) ≥ p0max (a) and M(p(a)) ≥ M(p(a)-p1min (a))+e then a is an NE.

Intuitively, no non-voter in an even profile wants to vote when their competence is lower than that of the agents already voting. An important consequence of Corollary 1 is that a profile a with only one voter, i.e., one (or one of those) with the highest accuracy in the group, is always an equilibrium. This implies that δ(n, p) = p+, for any n ∈ N: again, we find, wisdom is not necessarily achieved by adding more agents.

Notably, working with different levels of competence makes it more difficult to determine the maximum accuracy of a Nash equilibrium (i.e., accuracy at an MNE), other than by listing all possible Nash equilibria, as the group accuracy is no longer directly correlated with the number of voters: equilibria with the largest size may not be MNEs. Nonetheless, we can still provide an upper bound for the accuracy of an NE (which is, obviously, also an upper bound for the accuracy of an MNE). Such an upper bound shows that, also in this setting, the accuracy of any NE or SNE cannot be higher than a certain threshold, regardless of n. Denote with ne,p the value for ne in a homogeneous group with an effort e and accuracy p. And, call n+P the highest value in the set NP = {i ∈ N | ne,p = i for p ∈ (1/2, p+]} based on e. Notably, we know that ne,p ∈ N+ and that ne,p does not depend on n for any e, p, from Section 3; consequently, n+P ∈ N and does not depend on n either.

Theorem5. If the a is an NE, thenM(p(a)) ≤M(n+P , p+).

3 The profile a is assumed to have size bigger than 0, as size 0 would not be an equilibrium here

The reasoning is straightforward. First, we find the maximal size for an MNE. Then, we compute the highest accuracy that can be reached with that size (in the limit case in which every agent has an accuracy of p+). Indeed, if every voter has the same competence p+, M(p) corresponds to M(n+P , p+) of the homogeneous setting. Consequently, we can deduce that if p+ is kept constant for the group no Nash equilibrium can do better than that, regardless of n, and SNEs incur in the same situation, as any SNE must also be an NE.

Proposition 4. A voting profile a is an SNE iff it is an NE and M(p(a)) ≥ M(pmax) - e.

For the same reason as above, for any n, if a is a SNE M(p(a)) ≤ M(n+P , p+) given that for all i, pi ≤ p+. Wisdom of the crowds is again inhibited: adding more people to a group (with competence lower than the actual value p+) does not always increase the minimal accuracy of an SNE.

6 Voting on a Network

In this section we take the set N of agents to be nodes in an undirected graph Gn = (N,E), with E as the set of edges and |N| = n. The neighborhood of i is N(i) = {j ∈ N | {i, j} ∈ E} and the closed neighborhood of i is N[i] = N(i) ∪ {i}. We will assume that the maximum degree of any node in Gn, called its max-degree, is bounded by a constant d ∈ N>0. As in Section 3, agents choose one of two actions (voting or abstaining), are correct with uniform probability p ∈ (1/2, 1) and have equal stakes bi = 1. But, in contrast to Section 3, here we assume that, when choosing what action to take, agents are aware only of the actions of their neighbors. Thus, if a is an action profile, we write N 1 [i] = {j ∈ N[i] | aj = 1} for the set of agents in the closed neighborhood of i that vote. Consequently, agent i's utility with a is:

i.e., an agent's utility is the accuracy of its closed neighborhood, minus the effort required to vote. Intuitively, we assume that agents have access only to local information about the rest of the electorate and use that to decide whether to vote or abstain. Consequently, the pure Nash equilibria for the corresponding normal-form game follow the logic sketched in Section 3: an agent votes only if they have the chance to be pivotal and if their marginal contribution to group accuracy is higher than the effort. For ease of reasoning, we assume in the following that the effort e is such that the maximum group size to which agents can make a positive contribution is d∗ + 1, where d∗ is the maximum degree of any node in Gn. Thus, the addition of networks adds a particular twist to the setting of Section 3: an agent i's group consists now of its closed neighborhood (rather than all of N), and i has an incentive to vote only if they have an even number of voting peers in this neighborhood.

We write δ(Gn, p) for the probability of a correct majority vote from the agents voting in a Nash equilibrium of minimal size. 4 We note that a Nash equilibrium, as described above, corresponds to an odd dominating set of Gn (i.e., a dominating set of odd size), though preciously little is known about the minimal size of such sets outside of certain special classes of graphs [Caro and Klostermeyer, 2003]. Note, as well, that the setup in Section 3 is the special case when Gn is the complete graph on N-though, naturally, we want to see how the accuracy of the group behaves on different types of graphs.

4 This notion is consistent with the idea of group accuracy used in Section 3: if ℓ agents vote in the NE of minimal size, then

A graph Gn is a tree if it is connected and acyclic. We think of trees as having a designated root, with descendants going down to the terminal leaves. The depth of a node is defined as its distance from the root. We say that a tree Gn has even branching factor if every node has an even number of descendants. A path is a tree having two nodes of degree 1 and the remaining n - 2 nodes of degree 2. A star is a graph with a node c ∈ N, called the center, such that every other node in N is adjacent only to c. A graph is a cycle if its nodes are connected in a closed chain. The Nash equilibria for these types of graphs can be characterized precisely, showcasing diverging conditions for the wisdom of crowds effect.

Proposition 5. If Gn is a star graph with c ∈ N as center, then if |N| is odd, the only Nash equilibrium is the profile where c votes, while if |N| is even, the only Nash equilibria are the two profiles where either c alone votes, or every node other than c votes.

Intuitively, the situations described in Proposition 5 are the only ones in which the parity condition on the number of voting neighbors is satisfied, with Figure 1 giving an illustration for the star graph G4. An immediate consequence of Proposition 5 is that the minimal size of Nash equilibria in star graphs is 1, regardless of the size of these graphs, showing that such societies are not guaranteed to be wise.

Note that for the star graph G4 in Figure 1 we also obtain a Nash equilibrium with 3 voters, even though the effort is such that individual agents have no incentive to vote in numbers larger than 2: in this case the topology of the graph opens up the possibility of higher turnout in equilibrium, which also leads to better group accuracy.

We now show that, in pleasant contrast to the negative results obtained thus far, there are types of graphs in which the size of even the smallest equilibria grows monotonically with n. Significantly, since more voters here means a better chance at finding the truth, this means that even in the worst-case scenario, the accuracy of these graphs goes to 1 as n goes to infinity, albeit more slowly than with full participation. The relevant results here are a series of characterizations of the Nash equilibria on various classes of graphs. For the first result, we take the nodes of a path graph Gn to be v0, . . . , vn.

δ(Gn, p) = M(ℓ, p). The added complication is that ℓ, in this setup, will also depend on the topology of Gn.

Proposition 6. If Gn is a path graph, then, for any 0 ≤ i ≤ n - 2 such that i ≡ 0 (mod 3), the Nash equilibria are as follows: (i) if n ≡ 0 (mod 3), then ai = ai+2 = 0, ai+1 = 1; (ii) if n ≡ 1 (mod 3), then ai+1 = ai+2 = 0, ai = 1; (iii) if n ≡ 2 (mod 3), then either ai = ai+2 = 0, ai+1 = 1, or ai+1 = ai+2 = 0, ai = 1.

Intuitively, Nash equilibria on paths are characterized by one voter, followed by two non-voters, followed by a voter. An immediate consequence is that the number of voters on a path graph is ⌈ n3 ⌉, an observation consistent with Caro and Klostermeyer [2003].

Proposition 7. If Gn is a cycle, then, for any 0 ≤ i ≤ n- 2 such that i ≡ 0 (mod 3), the Nash equilibria are as follows: (i) if n ≡ 0 (mod 3), then either all three of ai, ai+1, ai+2 are 1, or exactly one of them is; (ii) if n ≡ 1 (mod 3) or n ≡ 2 (mod 3), then all three of ai, ai+1, ai+2 are 1.

Proposition 7 implies that there are at least n3 voters in a minimal size Nash equilibrium of a cycle Gn, for any n ∈ N. And we obtain a similar result for trees of even branching factor.

Proposition 8. If Gn is a tree of even branching factor, bounded max-degree and depth at least 2, the only Nash equilibrium is the action profile where only the nodes at even depth vote.

The number of nodes at even depth (which, by Proposition 8 are the voters of Gn) grows logarithmically with n: this is because the degree of the nodes in Gn is bounded, so increasing n means that we are automatically increasing the depth of the tree, every time by at least two new nodes.

Gathering all these facts, we obtain our main result.

Theorem 6. If Gn is a path, cycle, or tree of even branching factor, bounded max-degree and depth at least 2, Gn is wise.

7 Conclusions

We analyzed four variations on the theme of costly voting in an epistemic social choice scenario. Consistent with existing literature, we found that the addition of effort leads to Nash equilibria where voters are disincentivized to participate in the voting process, with dramatic effects for the asymptotic claims of the Condorcet Jury Theorem (CJT). These effects carry over even to refinements of the Nash equilibrium, such as strong Nash equilibria. Notably, we found that the asymptotic claim of the CJT can be salvaged, even in the worst case, on certain types of graphs representing agents' awareness of each other, i.e., their social networks.

There is ample space for future work, particularly with respect to mitigating the impact of effort: are there reasonable incentives to encourage sufficient voter participation, and thus ensure wise crowds, even in the presence of deterring factors such as costly information acquisition? Extending our results on social networks to more general classes of graphs is particularly appealing: simulations suggest that on random graphs the average number of voters at equilibrium is around n/2, though we leave this as a conjecture.

Acknowledgments

We thank the reviewers for their useful feedback. Davide Grossi acknowledges support by the Hybrid Intelligence Center, a 10-year program funded by the Dutch Ministry of Education, Culture and Science through the Netherlands Organisation for Scientific Research (NWO). Adrian Haret was funded by the NWO Customisable Collective Choice project.