A natural adaptive process for collective decision-making

Brandl, Florian; Brandt, Felix Article A natural adaptive process for collective decision-making Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Brandl, Florian; Brandt, Felix (2024) : A natural adaptive process for collective decision-making, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 19, Iss. 2, pp. 667-703, https://doi.org/10.3982/TE5380 This Version is available at: https://hdl.handle.net/10419/320250 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 19 (2024), 667–703 1555-7561/20240667 A natural adaptive process for collective decision-making Florian Brandl Department of Economics, University of Bonn Felix Brandt Department of Computer Science, Technical University of Munich Consider an urn filled with balls, each labeled with one of several possible collective decisions. Now let a random voter draw two balls from the urn and pick her more preferred as the collective decision. Relabel the losing ball with the collective decision, put both balls back into the urn, and repeat. Once in a while, relabel a randomly drawn ball with a random collective decision. We prove that the empirical distribution of collective decisions produced by this process approximates a maximal lottery, a celebrated probabilistic voting rule proposed by Peter C. Fishburn. In fact, the probability that the collective decision in round nis made according to a maximal lottery increases exponentially in n. The proposed procedure is more flexible than traditional voting rules and bears strong similarities to natural processes studied in biology, physics, and chemistry as well as algorithms proposed in machine learning Keywords. Probabilistic social choice, maximal lotteries, Markov processes, equilibrium learning, evolutionary game theory. JEL classification. C73, D70. 1. Introduction The question of how to collectively select one of many alternatives based on the preferences of multiple agents has occupied great minds from various disciplines. Its formal Florian Brandl: [email protected] Felix Brandt: [email protected] This material is based on work supported by the Deutsche Forschungsgemeinschaft under Grants BR 2312/11-12312/11-1, BR 2312/11-2, BR 2312/12-1, and BR 5969/1-1 and the Excellence Strategy EXC2047. The authors thank Stefano Allesina, Stergios Athanasoglou, Vincent Conitzer, Javier Esparza, Erwin Frey, Drew Fudenberg, Philipp Geiger, Umberto Grandi, Matthias Greger, Josef Hofbauer, Sean Horan, Johannes Knebel, Jean-François Laslier, Patrick Lederer, Hervé Moulin, Noam Nisan, Robert Schapire, Omer Tamuz, Nicolas Vieille, Jörgen Weibull, Peyton Young, and the participants of the COMSOC video seminar (March 2021), the International Conference on “New Directions in Social Choice” (St. Petersburg, July 2021), the Hausdorff Center for Mathematics Symposium (Bonn, August 2021), the seminar of the Center of Economic Research of ETH Zürich (Zurich, November 2021), the Nobel Symposium “One Hundred Years of Game Theory” (Stockholm, December 2021), the Microeconomics Research Seminar at the University of Hamburg (Hamburg, April 2022), the Economics Seminar at the University of Milano-Bicocca (Milan, May 2022), the Hi!Paris Symposium on Artificial Intelligence and the Social Sciences (Paris, June 2022), the 16th Meeting of the Society of Social Choice and Welfare (Mexico City, June 2022), and the Economics Seminar at Bielefeld University (Bielefeld, June 2022) for stimulating discussions and encouraging feedback. ©2024 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE5380 668 Brandl and Brandt Theoretical Economics 19 (2024) study goes back to the Age of Enlightenment, in particular during the French Revolution, and the important contributions by Jean-Charles de Borda and Marie Jean Antoine Nicolas de Caritat, better known as the Marquis de Condorcet. Borda and Condorcet agreed that plurality rule—then and now the most common collective choice procedure—has serious shortcomings. This observation remains a point of consensus among social choice theorists and is largely due to the fact that plurality rule merely asks each voter for her most preferred alternative (see, e.g., Brams and Fishburn (2002), Laslier (2011)).1When eliciting more fine-grained preferences such as complete rankings over all alternatives from the voters, much more attractive choice procedures are available. As a matter of fact, since Arrow’s (1951) seminal work, the standard assumption in social choice theory is that preferences are given in the form of binary relations that satisfy completeness, transitivity, and often antisymmetry. Despite a number of results that prove critical limitations of choice procedures for more than two alternatives (e.g., Arrow (1951), Gibbard (1973), Satterthwaite (1975)), there are many encouraging results (e.g., Young (1974), Young and Levenglick (1978), Brams and Fishburn (1978), Laslier (2000a)). In particular, when allowing for randomization between alternatives, some of the traditional limitations can be avoided and there are appealing choice proceduresthatstandout(Gibbard (1977), Brandl, Brandt, and Georg (2016), Brandl and Brandt (2020)). The standard framework in social choice theory rests on a number of rigid assumptions that confine its applicability: there is a fixed set of voters, a fixed set of alternatives, and a single point in time when preferences are to be aggregated; all voters are able to rank-order all alternatives; there is a central authority that collects all these rankings, computes the outcome, and convinces voters of the outcome’s correctness, etc. On top of that, computing the outcome of many attractive choice procedures is a demanding task that requires a computer, which can render the process less transparent to voters.2 In this paper, we devise an ongoing process in which voters may arrive, leave, and change their preferences over time, and collective decisions are made repeatedly at intervals. Voters are never asked for their complete preference relations, but rather reveal minimal information about their preferences by choosing between two randomly drawn alternatives from time to time. No central voting authority is required. The process can be executed via a simple physical device: an urn filled with balls that allows for two primitive operations: (i) randomly sampling a ball and (ii) replacing a sampled ball of one kind with a ball of another kind. More precisely, the process works as follows (see Figure 1). There is an urn filled with balls that each carry the label of one alternative. The initial distribution of balls in the urn is arbitrary. In each round, a randomly selected voter will draw two balls from the urn at random. Say these two balls are labeled with alternatives 1 and 2, and the voter prefers 1 to 2. She will then change the label of 1For example, plurality rule may select an alternative that an overwhelming majority of voters consider to be the worst of all alternatives. 2In some cases, computing the outcome was even shown to be NP-hard, i.e., the running time of all known algorithms for computing election winners increases exponentially in the number of alternatives (see, e.g., Bartholdi, Tovey, and Trick (1989), Brandt, Conitzer, Endriss, Lang, and Procaccia (2016)). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 669 Figure 1. Illustration of one round of the urn process ((i) and (ii)) and the main result (iii). the second ball to 1 and return both balls to the urn. Alternative 1 is declared the collective choice—or winner—of this round. After each round, with some small probability r that we call mutation rate, a randomly drawn ball is relabeled with a random alternative. We show that if the number of balls in the urn is sufficiently large, then the limit of the empirical distribution of winners is almost surely close to a maximal lottery—a randomized extension of the Condorcet principle that was proposed by Fishburn (1984)and enjoys many desirable axiomatic properties. How far the limiting distribution will be from a maximal lottery depends on r.Asrgoes to 0, the limiting distribution converges to a maximal lottery. We can, however, not set rto 0, as then almost surely, all alternatives except one will permanently disappear from the urn and the limiting distribution will be degenerate. Our proof not only shows convergence of the limiting distribution, but also that the probability that the urn distribution itself is close to a maximal lottery gets arbitrarily close to 1 and increases exponentially in the number of rounds. The winners of most rounds are thus selected according to approximate maximal lotteries. 1.1 Maximal lotteries and dynamic voting The basic idea of maximal lotteries is to avoid the Condorcet paradox—which lies at the heart of classic impossibility theorems—by extending the notion of a Condorcet winner to lotteries. A lottery pis a randomized Condorcet winner—or maximal—if for any other lottery q, a random voter is more likely to prefer the alternative sampled from pto that sampled from qthan vice versa.3The minimax theorem guarantees that maximal lotteries exist. Maximal lotteries also have a natural interpretation in terms of electoral competition (see, e.g., Myerson (1993), Laslier (2000b), Carbonell-Nicolau and Ok (2007)). In fact, maximal lotteries are precisely the mixed Nash equilibrium (or maximin) strategies of the symmetric two-player zero-sum game given by the pairwise majority margins of 3This comparison of lotteries induces a binary relation on lotteries whose maximal elements are precisely the maximal lotteries. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 670 Brandl and Brandt Theoretical Economics 19 (2024) the voters’ preferences. When interpreting the two players as parties and the alternatives as possible positions of the parties, this can be seen as a game of electoral competition in which two parties aim to maximize the number of voters who prefer their (mixed) position to that of the other party. For this reason, the social choice literature sometimes refers to the support of maximal lotteries as the bipartisan set (a term proposed by Myerson). Maximal lotteries are known to satisfy a number of desirable properties that are typically considered in social choice theory (see, e.g., Felsenthal and Machover (1992), Laslier (2000a), Rivest and Shen (2010), Hoang (2017), Brandl, Brandt, and Stricker (2022)). For example, Condorcet winners (i.e., alternatives that defeat every other alternative in a pairwise majority comparison) will be selected with probability 1, and Condorcet losers (i.e., alternatives that are defeated in all pairwise majority comparisons) will never be selected. No group of voters benefits by abstaining from an election, removing losing alternatives does not affect maximal lotteries, and each alternative’s probability is unaffected by cloning other alternatives. Maximal lotteries have been axiomatically characterized using Arrow’s independence of irrelevant alternatives and Pareto efficiency (Brandl and Brandt (2020)) as well as population consistency and composition consistency (Brandl, Brandt, and Georg (2016)). The dynamic procedure described above implements maximal lotteries while providing •myopic strategyproofness within each round •minimal preference elicitation and, thus, increased privacy protection •verifiability realized via a simple physical procedure •all-round flexibility. Myopic strategyproofness Each round’s decision is made by letting a randomly selected voter choose between two alternatives. Clearly, a voter who is only concerned with the outcome of the current round is best off by choosing the alternative that she truly prefers. If she also takes into account the outcomes of future rounds, however, she may be able to skew the distribution in the urn by choosing alternatives strategically.4 Preference elicitation Eliciting pairwise preferences on an as-needed basis has several advantages. First, it spares the voters from the cognitive burden of having to rank-order all alternatives at once. If the number of voters is large, it may well be possible that the urn process yields satisfying results without ever querying some of the voters. Second, rather than submitting a complete ranking of all alternatives to a trusted authority, voters only reveal their preferences by making pairwise choices from time to time.5 4Maximal lotteries, like any ex post Pareto efficient randomized choice procedure other than random dictatorships, fail to be strategyproof (Gibbard (1977)). The simple notion of myopic strategyproofness could be strengthened by discounting future rounds. 5Privacy can be further increased by letting voters draw their balls privately, announce the winner, and put two balls of the same color back into the urn without revealing the original color of the losing ball. Alternatively, the voters’ preferences can be protected completely by letting the voter publicly draw both balls, make one copy of each ball, and let her privately put back two balls of her choice. The collective decision in each round can then be made by drawing a random ball from the urn. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 671 Verifiability Previously, the deployment of maximal lotteries required that a central authority collects the preferences of all voters, computes a maximal lottery by solving a linear program, and instantiates the lottery in some user-verifiable way. The urn process allows these goals to be achieved via a simple physical device. Flexibility The urn process is oblivious to changes in the voters’ preferences, the set of voters, and the set of alternatives. Everything that has happened up to the current round is irrelevant. Since the process converges from any initial configuration, it will keep “walking in the right direction” (toward a maximal lottery of the current preference profile). If the preferences change slowly in the sense that only a small fraction of voters changes their preferences from one round to the next, collective choices will thus be made according to a maximal lottery for the current preferences in most rounds. This includes the case when the distribution of preferences converges. We also note some disadvantages of the urn process. The convergence of the distribution of winners to an approximate maximal lottery is an asymptotic result. In particular, for a finite number of rounds, there is a nonzero probability that the chosen alternative is subpar for a significant fraction of rounds, for example, because it is Pareto dominated. To bound this probability below an acceptable threshold, it may be necessary to run the process for an excessively large number of rounds. Second, ensuring that the limit distribution is sufficiently close to a maximal lottery could require an urn with a large number of balls. We address the first concern by showing that the probability for the distribution of winners to be far from the limit distribution converges to 0 exponentially fast in the number of rounds. The rate of convergence is also evident in computational simulations we ran for various parameterizations of the process. When the preference profile admits a Condorcet winner, we can give tractable bounds on the number of balls in the urn required to achieve a good approximation in the limit. This partially mitigates the second concern since it has been observed that most real-world preference profiles admit Condorcet winners (see, e.g., Gehrlein and Lepelley (2011)). The axiomatic characterizations of maximal lotteries not only imply that maximal lotteries satisfy desirable axioms, but also that any deviation from maximal lotteries leads to a violation of at least one of the axioms. Hence, a process that only guarantees an approximation of a maximal lottery will not enjoy the same axiomatic properties. However, rather than insisting on stringent axioms, one can relax them by only requiring them to hold in an approximate sense. For example, a natural notion of approximate Condorcet consistency would require that a Condorcet winner receives probability close to 1 whenever one exists. Since the empirical distribution of winners according to our process is almost surely close to a maximal lottery and maximal lotteries are Condorcetconsistent, the process is approximately Condorcet-consistent in the above sense. More generally, approximate maximal lotteries satisfy approximate versions of many of the axioms enjoyed by maximal lotteries such as population consistency, composition consistency, agenda consistency, and efficiency.6 6Details on how these statements can be formalized are given in an extended version of this paper (Brandl and Brandt (2021)). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 672 Brandl and Brandt Theoretical Economics 19 (2024) Maximal lotteries have been repeatedly recommended for practical use (Felsenthal and Machover (1992), Rivest and Shen (2010), Brandl, Brandt, and Georg (2016), Hoang (2017)). We believe that the benefits of the urn process described above extend the applicability of maximal lotteries. Rather than for traditional political elections, probabilistic rules like maximal lotteries seem more suitable for frequently repeated low-stakes elections where some degree of randomization may not only be tolerable, but even desirable. Two example applications that have been suggested for maximal lotteries are to help a group of co-workers with the daily decision where to have lunch and to select music for a party or a radio station based on the preferences of the listeners (Brandl, Brandt, and Georg (2016)). The transparency and the flexibility of the urn process seem particularly effective in the music broadcasting example. Agents come and go, they only need to select from a pair of songs rather than rank-order all of them, and individual preferences, as well as the set of available songs, can be changed at any time. Our theorem shows that the sequence of simple pairwise choices results in a socially desirable distribution of songs: the more songs are being played, the less likely it becomes that another distribution of songs would have been preferred by an expected majority of listeners. It is plausible that, over time, the preferences of the listeners change depending on the songs that have been played so far. These changes will be reflected immediately in the selection of future songs. 1.2 Applications beyond collective decision-making Interestingly, dynamic processes similar to the process we describe here have recently been studied in population biology, quantum physics, chemical kinetics, and plasma physics to model phenomena such as the coexistence of species, the condensation of bosons, the reactions of molecules, and the scattering of plasmons. In each of these cases, simple interactions between randomly sampled entities result in distributions that correspond to equilibrium strategies of symmetric zero-sum games. Since the definition of maximal lotteries and our dynamic process merely rely on this comparison matrix, describing with which probability one entity will be replaced with another in a pairwise encounter, our results are also of relevance to these areas. We discuss these connections, as well as those to equilibrium learning and evolutionary game theory, in more detail in Section 5. An alternative interpretation of our result can be used to describe the formation of opinions. In this model, there is a population of agents, each of whom entertains one of many possible opinions. Agents come together in random pairwise interactions in which they try to convince each other of their opinion. The probabilities with which one opinion beats another are given as a square matrix and, with some small probability, an agent randomly changes her opinion. In other words, the agents correspond to the balls in the urn, the opinions correspond to the alternatives, and there are neither voters nor preference profiles, as transition probabilities are given explicitly. Our theorem then shows that if the population is large enough, the distribution of opinions within the population is close to a maximal lottery of the probability matrix most of the time. Other models of opinion formation based on different processes were, for example, considered by DeGroot (1974), Holley and Ligget (1975), and Goel and Lee (2014). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 673 The process we describe approximately computes a mixed Nash equilibrium of a symmetric zero-sum game. This problem is known to be equivalent to linear programming. In fact, deciding whether an action is played with positive probability in an equilibrium of a symmetric zero-sum game is P-complete (Brandt and Fischer (2008,Theorem 5)), which, loosely speaking, means that the problem is at least as hard as any problem that can be solved in polynomial time. The urn process can thus be seen as a probabilistic algorithm that approximates polynomial-time computable functions. In contrast to traditional computing devices such as Turing machines, the urn process is based on unordered elementary entities that randomly interact according to very simple replacement rules.7 The remainder of the paper is structured as follows. After defining our model in Section 2, we state the main result (Theorem 1) and a rough proof sketch in Section 3.The fullproofisgivenintheAppendix.InSection4, we analyze the instructive special case of preference profiles that admit a Condorcet winner, which allows for a more elementary proof. In Section 5, we extensively discuss the connections between our work and results from equilibrium learning, evolutionary game theory, and the natural sciences. We also state a continuous version of our main result (Theorem 2) that may be of independent interest. 2. The model Let [d]={1, ,d}be a set of alternatives and let be the d−1-dimensional unit simplex in Rd,thatis,={x∈Rd ≥0:d i=1xi=1}. We refer to elements of as lotteries. By N={1, 2, }and N0=N∪{0}we denote the sets of positive and nonnegative integers, respectively. Throughout the paper, for a vector x∈Rkfor some k,|x|=k l=1|xl|denotes its L1norm. For δ>0andS⊂Rd,letBδ(S)={x∈:|x−y|<δfor some y∈S}be the δball around S. For a finite set S,wewrite|S|for the number of elements of S. Apreference relation is an asymmetric binary relation over [d].8By Rwe denote the set of all preference relations. Let Vbe a finite set of voters. A preference profile R∈RVspecifies a preference relation for each voter. With each preference profile R, we can associate a comparison matrix MR∈[0, 1]d×dthat states, for each ordered pair of alternatives, the fraction of voters who prefer the first to the second. That is, MR(i,j)=| {v∈V:ivj}|/|V|. This matrix induces a skew-symmetric matrix ˜ MR=MR−M R, which we call the skew-comparison matrix.9 7Related decentralized models of computation with applications to sensor networks and molecular computing are studied under the name “population protocols” in computer science (e.g., Angluin, Aspnes, Diamadi,Fischer,andPeralta(2006), Aspnes and Ruppert (2009)). While the urn process has the same modus operandi as population protocols, the input–output behavior is different. The input of population protocols is given by the initial distribution of balls in the urn and the output has been reached if all balls belong to a certain subset of types. By contrast, the input for our urn process is encoded in the matrix describing the replacement rules and the (approximate) output is given by the distribution of balls in the urn after sufficiently many rounds. 8Preferences need not be transitive or complete. The definition of maximal lotteries and the urn process we describe only depend on the fractions of voters who prefer one alternative to another. In particular, indifferences can easily be accommodated by randomly selecting which of the two balls will be relabeled. 9AmatrixMis skew-symmetric if M=−M. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 674 Brandl and Brandt Theoretical Economics 19 (2024) 2.1 Maximal lotteries A lottery p∈is a maximal lottery for a profile Rif ˜ MRp≤0. The minimax theorem implies that every profile admits at least one maximal lottery. By ML(R)we denote the set of all lotteries that are maximal for R. Most profiles admit a unique maximal lottery. For example, when the number of voters is odd and voters have strict preferences, there is always a unique maximal lottery (Laffond, Laslier, and Le Breton (1997)). Example 1 (Condorcet Winner). Consider, for example, 900 voters, 3 alternatives, and a preference profile Rgiven by the following table. Each column header contains the number of voters with the corresponding preference ranking. 300 300 300 112 233 321 Then MR=⎛ ⎜ ⎝ 02/32/3 1/302/3 1/31/30⎞ ⎟ ⎠and ˜ MR=⎛ ⎜ ⎝ 01/31/3 −1/301/3 −1/3−1/30⎞ ⎟ ⎠. The set of maximal lotteries ML(R)={(1, 0, 0)}only contains the degenerate lottery with probability 1 on the first alternative. This alternative is a Condorcet winner, i.e., an alternative that is preferred to every other alternative by some majority of voters. ♦ 2.2 Markov chains Let Sbe a finite set and let {X(n):n∈N0}be a discrete-time, time-homogeneous Markov chain with state space S.Thetransition probability matrix P∈[0, 1]S×Sof {X(n):n∈ N0}is given by Pp,p=PX(n+1)=p|X(n)=p for all p,p∈S. We will frequently write X(n,p0)for X(n)conditioned on X(0)=p0∈S and call p0the initial state. The period of a state p∈Sis the greatest common divisor of the return times with positive probability {n∈N:(Pn)(p,p)>0}.AMarkovchainisaperiodic if every state has period 1. Note that any Markov chain with P(p,p)>0forallp∈Sis aperiodic. A Markov chain is irreducible if every state is reached from any other state with positive probability. That is, for any two states p,p∈S, there is a positive integer nso that (Pn)(p,p)>0. If {X(n):n∈N0}is irreducible and aperiodic, it has a unique stationary distribution π∈S so that π=πP. 2.3 The urn process Consider an urn with N∈Nballs, each labeled with some alternative. Viewing balls with the same label as indistinguishable, we can identify each state of the urn with an element of the discrete unit simplex (N)={p∈:Np ∈Nd 0}.Fixamutation rate r∈[0, 1]. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 681 large enough, one should expect to find the random walk close to the tip of the pyramid most of the time.15 Recall that P(N,r)(p,q)is the probability of transitioning from state pto state q. Since πis a stationary distribution, we have πP(N,r)=π. Consider any partition of (N)into two sets. For the stationary distribution, the probability of transitioning from the first set to the second is equal to the probability of transitioning from the second set to the first since the probabilities of both sets are conserved. Applying this to the sets k−1 l=0Sland N l=kSlfor k∈[N], and noticing that the only transitions between the two sets with positive probability are from Sk−1to Skand vice versa, we get  p∈Sk−1 π(p) q∈Sk P(N,r)(p,q)= p∈Sk π(p) q∈Sk−1 P(N,r)(p,q).(1) That is, the probability of being in a state in Sk−1and transitioning to a state in Skequals the probability of being in a state in Skand transitioning to a state in Sk−1. Now observe that for p∈Sk,k∈{0, ,N−1},wehave  q∈Sk+1 P(N,r)(p,q)≥2(1−r)k(N−k) N21 2+α+r d N−k N=:uk, where the left-hand side is the probability of replacing a ball of type other than iby one of type iin state p∈Sk(moving up one floor in the pyramid). Similarly, we find that for p∈Sk,k∈[N],wehave  q∈Sk−1 P(N,r)(p,q)≤2(1−r)k(N−k) N21 2−α+rd−1 d k N=:dk for the probability of replacing a ball of type ibyoneoftypeotherthaniin state p∈Sk (moving down one floor in the pyramid). Plugging this into (1), we get σk−1uk−1≤σkdk.(2) All the terms in (2) are strictly positive if r>0. Let Nbe such that r Nd ≥21−r N2(we choose r>0 later). Then uk≥2(1−r)k(N−k) N21 2+α+2(1−r)N−k N2 ≥2(1−r)(k+1)(N−k−1) N21 2+α, where the last inequality uses 1 ≥1 2+α. Similarly, we find that for r≤1 dand k≤N(1− r α), dk≤2(1−r)k(N−k) N2 1−α 2. 15In the analysis of the general case, the number of balls of type iis replaced by the entropy of the urn distribution relative to a maximal lottery. The fact that the number of balls not of type imore likely than not decreases corresponds to the fact that the expected entropy relative to a maximal lottery decreases. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 682 Brandl and Brandt Theoretical Economics 19 (2024) Hence, with this bound on k,wehave dk uk−1≤1−α 21 2+α=1−α 1+2α=:β. Thus, by (2), σk−1 σk≤β<1. We have shown that the cumulative probability σkof the states Skdecreases at least as fast as the terms of the geometric series with parameter β from some k(close to N)downward. The maximal lottery for Ris the degenerate lottery with probability 1 on i.Forgiven δ,τ>0, we are aiming for a lower bound on Nso that the probability on states with at least a 1 −δfraction of balls of type iin the stationary distribution πis at least 1 −τ. That is, N  k=N(1−δ) σk≥1−τ. First observe that  k≥k0 βk=βk01 1−β≤τ(3) for k0≥log(τ(1−β)) logβ. For our bound, Nneeds to be large enough so that there are at least k0integers in the interval {(1−δ)N,,(1−r α)N}. The probability on states in Sk with k<(1−δ)Nwill then be below τby (3) and the choice of k0(since the bound on dkassumes that k≤N(1−r α)). Choosing r≤αδ 2and N≥k0 δ−r α ≥1 δlogτ(1−β) logβ achieves this. In Example 1, there are three alternatives and 900 voters. Alternative 1 is a Condorcet winner, as it is preferred to every other alternative by 600 of the voters (α=2 3−1 2=1 6, β=5 8). Suppose we want that at least 90% of the balls in the urn are of type 1 in at least 90% of rounds (δ=0.2, τ=0.1). Choosing r=αδ 2=1 60 , we need N≥70 balls in the urn. These calculations suggest that when a Condorcet winner exists, a reasonable choice of the parameters is N≥−1 δlog(τ)and 1 N≤r≤δ. 5. Discussion Since the urn process described in this paper only depends on the comparison matrix MRand the mutation rate r, it is connected to various problems unrelated to collective decision-making. In particular, the literature on equilibrium learning and evolutionary game theory has extensively studied dynamics based on payoff matrices and their convergence behavior. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 683 5.1 Equilibrium learning When interpreting ˜ MRas a symmetric two-player zero-sum game and maximal lotteries as equilibrium strategies, our result can be phrased as a result about a learning procedure for equilibrium play. Such procedures have been extensively studied in game theory; in particular, for zero-sum games, a number of simple and attractive procedures have been proposed. The earliest of these is fictitious play (Brown (1951), Robinson (1951)) and its variant stochastic fictitious play (Fudenberg and Kreps (1993)).16 More recently, the multiplicative weights update algorithm (e.g., Freund and Schapire (1999), Arora, Hazan, and Kale (2012)) and regret matching (Hart and Mas-Colell (2000), Hart and Mas-Colell (2013)) have been celebrated in game theory, optimization, and machine learning. When translating the multiplicative weights update algorithm to our setting, one obtains a dynamic urn process in which voters need to compare a drawn ball to all possible alternatives and adjust the distribution in the urn accordingly. It does not suffice to replace a single ball and the total number of balls does not remain constant. Also, the multiplicative weights update algorithm only guarantees convergence of the temporal average. The actual distribution does not converge, even for self-play in symmetric zero-sum games (Bailey and Piliouras (2018)). A notable subarea of machine learning is concerned with multi-armed bandits—a simple model of learning optimal sequential decisions when only very limited information is available (see, e.g., Bubeck and Cesa-Bianchi (2012), Slivkins (2019)). The theory of adversarial bandits is closely connected to learning in repeated multi-player games and it turns out that the prototypical algorithm for adversarial bandits, Exp3 (which stands for “exponential-weight algorithm for exploration and exploitation”), bears some similarities to the urn process we describe in this paper. Exp3 can be formulated as an algorithm that learns an equilibrium strategy of a symmetric zero-sum game in self-play by iteratively updating a probability distribution merely based on the payoff associated with two actions randomly drawn from the current distribution. Auer, Cesa-Bianchi, Freund, and Schapire (2002) prove strong bounds on the expected average regret and the average regret achieved by Exp3 after a finite number of rounds that imply that the temporal average of the distributions converges to a strategy close to an equilibrium. How close it gets to an equilibrium depends on a parameter that is roughly related to our mutation rate. Exp3 updates a probability distribution rather than the contents of a discrete urn and we are not aware of convergence results beyond the temporal average. The literature on equilibrium learning often focusses on minimizing regret rather than relative entropy with respect to an equilibrium distribution (see, e.g., Foster and Vohra (1999), Auer et al. (2002)). In our context, the regret of the urn distribution at round nis maxi∈[d](˜ MRX(N,r)(n,p0))i. It follows from Theorem 1that for sufficiently large n, the regret is close to zero with high probability. Our simulations show that the 16Hofbauer and Sandholm (2002) show that under stochastic fictitious play, players’ strategies and beliefs converge to a Nash equilibrium in several classes of games, including two-player zero-sum games. While best response dynamics are conceptually different from our urn process, their technical approach bears similarities to ours in that they use a deterministic process obtained as a solution to a differential equation to approximate a stochastic process. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 684 Brandl and Brandt Theoretical Economics 19 (2024) regret of the urn distribution converges faster than its relative entropy. This is interesting insofar as to approximately satisfy the desirable axiomatic properties of maximal lotteries, low regret is sufficient. It can be shown that a lottery has small regret if and only if it is a maximal lottery of a nearby preference profile. In other words, even if the urn distribution is still far from a maximal lottery, the distribution can perform almost as well as a maximal lottery. We have identified preference profiles where this effect is quite noticeable. 5.2 Evolutionary game theory The replicator equation in evolutionary game theory (see, e.g., Taylor and Jonker (1978), Schuster and Sigmund (1983), Hofbauer and Sigmund (1998)) describes how the distribution of different species changes continuously over time based on the individuals’ fitness. In its basic form, it states that the change in the relative frequency of a species equals the relative fitness of the species (that is, its fitness relative to the entire population) minus the change in the size of the entire population. When the fitness depends linearly on the relative frequencies of the species and the population size is constant, the replicator equation defines the continuous deterministic process y:R≥0→with fitness function f(r):→Rdbelow when setting rto 0. When r>0, this process corresponds to a continuous and deterministic version of the urn process described in this paper (see Theorem 2): d dt y(t)=f(r)y(t)and y(0)=p0,where f(r) i(p)=2(1−r)pi(˜ Mp)i+r1 d−pi. (4) Solutions of this equation for r=0 are connected to evolutionary stable distributions as introduced by Maynard Smith and Price (1973). A distribution of species is evolutionary stable if its relative fitness exceeds that of every other distribution in a fixed neighborhood of it. Hence, evolutionary stable distributions are attractors of the dynamics defined by (4)(withr=0) in the sense that they are limit points of solutions when the initial distribution p0is in the respective neighborhood. Mixed equilibria of zero-sum games such as rock-paper-scissors usually fail to be evolutionary stable. As a consequence, results that prove convergence of dynamics to equilibrium strategies either modify the underlying process or settle for weaker notions of convergence such as convergence of the temporal average. In the following paragraphs, we briefly discuss three results that are closest to ours.17 Knebel, Weber, Krüger, and Frey (2015) study a dynamic process that involves quantum particles and is equivalent to a deterministic version of our urn process. Leveraging 17An extended version of this paper gives a more complete account of the related literature (Brandl and Brandt (2021)). 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 685 a classic result from evolutionary game theory (Hofbauer and Sigmund (1998,Theorem 5.2.3)), they show that the temporal average of this process converges to an equilibrium strategy (i.e., a maximal lottery) of the zero-sum game induced by the transition probabilities between quantum states. Even though their model allows for mutations, Knebel et al. neglect mutations when analyzing the continuous process, which may cause the process to cycle around the equilibrium strategy without converging to it. Laslier and Laslier (2017) consider a discrete urn process that is similar to ours, but in which the number of balls in the urn increases over time. Given a binary comparison matrix that specifies which alternative wins against which alternative, they consider a process, in which three balls are drawn from the urn. Whenever one of three balls beats both other balls, a new ball of the same type is added to the urn. Otherwise, one of the three types is chosen at random and a ball of that type is added. Their main result shows that the distribution in the urn converges toward the (unique) maximal lottery of the skew-comparison matrix. Since the number of balls in the urn increases, convergence is generally very slow. Following earlier work by Allesina and Levine (2011), Grilli, Barabás, MichalskaSmith, and Allesina (2017) consider a dynamic process in population biology to explain the stable coexistence of multiple species. Based on Laslier and Laslier’s findings, Grilli et al. adapt the replicator equation to interactions of triples of individuals. In contrast to Laslier and Laslier, they keep the number of individuals constant and do not require the comparison matrix to be binary. They show that with a continuum of individuals, this process converges to an equilibrium strategy of the skew-comparison matrix. Without mutations (i.e., r=0), the deterministic process described by the differential equation (4) does not, in general, converge, but only approaches an orbit of constant entropy relative to a zero of the fitness function f(0). When introducing mutations, the limiting behavior of the process changes qualitatively (see Figure 3). As Theorem 2 shows, it then converges to a zero of the fitness function. A similar observation has already been made by Hofbauer (2011, Theorem 2.8). Figure 3. The continuous deterministic process y(t)solving (4) with r=0.01 on the left and r=0 on the right. For strictly positive r,y(t)converges to a zero of f(r)(see Theorem 2). For r=0, it approaches an orbit of constant entropy relative to a zero of f(r). The underlying skew-symmetric matrix ˜ Mis given by ˜ M12 =˜ M14 =˜ M24 =˜ M34 =1/3,˜ M13 =−1/9,and ˜ M23 =2/9. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 686 Brandl and Brandt Theoretical Economics 19 (2024) Table 1. Comparison of related models and results. Model Interaction Mutations Pop. Size Convergence Knebel et al. (2015) Continuous Pairs, det. NoaFixed Temporal average Laslier et al. (2017) Discrete Triples, det. No Increasing Distribution Grilli et al. (2017) Continuous Triples, stoch. No Fixed Distribution Theorem 1Discrete Pairs, stoch. Yes Fixed Fraction of rounds Corollary 1Discrete Pairs, stoch. Yes Fixed Temporal average Theorem 2Continuous Pairs, det. Yes Fixed Distribution aWhile Knebel et al. (2015) consider a discrete process with mutations, the continuous process they study has no mutations. Theorem 2. Let f(r)and ybe defined as in (4). If r>0,f(r)has a unique zero p(r)and y(t)converges to p(r)as t→∞.Moreover,ifrgoes to 0,thenp(r)converges to ML(R)in Hausdorff distance. Table 1summarizes the key differences between the above-mentioned results and ours. In comparison, the main contribution of our work is that we are able to show for a discrete (rather than continuous) process based on stochastic (rather than deterministic) interactions between pairs (rather than triples) that the distribution in the urn is close to a maximal lottery most of the time (rather than convergence of the temporal average). Methodologically, the approach we take to cope with the discrete process is related to that of Benaïm and Weibull (2003), who study more general population processes in n-player games.18 We believe that Theorem 2as well as Theorem 1and Corollary 1are of relevance to the natural sciences. In particular, a discrete model may describe the aforementioned natural phenomena more accurately than continuous ones. As Corollary 1shows, the expectation of the discrete process with a large number of individuals is a good approximation of the continuous process. Furthermore, the observation that convergence is only guaranteed if mutations occur with small probability and the number of individuals is large enough seems noteworthy. Appendix:Proofs As guidance for the reader, we outline the main steps in the proof of Theorem 1.Fixany δ,τ>0. 18In Benaïm and Weibull’s model, there is a population of Nindividuals for each player, and each individual plays a pure strategy. In each round, one individual can update their strategy based on the pure strategies of all other individuals. An update rule induces a deterministic process described by a differential equation similar to (4) below. They show that if Nis large, the distributions of strategies among the individuals of each role in this stochastic process approximate the deterministic process described by the differential equation. Our setting corresponds to a symmetric two-player zero-sum game and an update rule based on the comparison matrix ˜ M. The special properties of this instance allow us to make more precise statements about the behavior of the deterministic process, and, thus, of the stochastic process for large N. In particular, we show that the deterministic process converges and that its limit approximates a maximal lottery. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 687 In Appendix A,weconsider,foranyp∈(N), the expected value of N(X(N,r)(k+ 1, p)−X(N,r)(k,p)), which, conditional on X(N,r)(k,p), is independent of ksince X(N,r)is a time-homogeneous Markov process. Moreover, it is independent of Nsince the probability of replacing a ball of type jby one of type iis independent of N. Hence, these expected values induce a continuous function f(r):→Rd.Weconsider g(r):→Rdwith g(r)(p)=p+1 2f(r)(p)and show that it maps to .Ifr>0, g(r)has a unique fixed point p(r)(a zero of f(r)), which is close to some lottery in ML(R)for any small enough r. We choose r0so that p(r)is no more than δ 2away from ML(R)for all 0<r≤r0. Fixing such an r,letp∗∈ML(R)be a maximal lottery that is within δof p(r). Appendix Bstudies the following differential equation with p∈,t∈R≥0,and y(·,p):R≥0→: d dt y(t,p)=f(r)y(t,p) y(0, p)=p. (5) Asolutionto(5)isadeterministic process that can be interpreted as the stochastic process we consider with a continuum of balls. We show that the unique solution y(r)(·,p) of (5)convergestop(r)for any initial state p∈as tgoes to infinity and the convergence is uniform in p. This is done by showing that the entropy of p(r)relative to y(r)(t,p)decreases monotonically at a rate proportional to the square of the distance between p(r) and y(r)(t,p). Appendix Crelates the discrete-time stochastic process X(N,r)to the continuoustime deterministic process y(r). To this end, we extend the former to the real time axis by letting ¯ X(N,r)(t,p)=X(N,r)(k,p)for t∈[k−1 N,k N). Given any T>0, one can show that with probability close to 1, ¯ X(N,r)approximately satisfies the integral equation corresponding to (5)fortbetween 0 and T, and uniformly in p∈(N)if Nis large. Using Grönwall’s inequality, we show that with probability close to 1, ¯ X(N,r)(t,p)and y(r)(t,p) are close to each other for all tfrom 0 to T.19 However, for tlarger than T,theymay(and almost surely will) be arbitrarily far apart. To deal with this, we partition the time axis into consecutive intervals of length T and synchronize the deterministic process with the stochastic process at the beginning of each interval. More precisely, since y(r)(t,p)converges to p(r)as tgoes to infinity uniformly in p, we can find T>0suchthaty(r)(t,p)is no more than δ 4away from p(r) for all but possibly a 1−τ 2fraction of the interval [0, T]for all p. Moreover, we can choose Nlarge enough so that with probability at least 1 −τ 2, the distance between ¯ X(N,r)and y(r)is less than δ 4for all tin an interval of length Tprovided both processes start at the same point at the beginning of the interval. We chop up the time axis into intervals [0, T],[T,2T],. On the interval [(k−1)T,kT ],wecompare ¯ X(N,r)(t,p)to y(r)(t− (k−1)T,¯ xk−1),where ¯ xk−1=X(N,r)((k−1)T,p).Thatis,weresety(r)to the position 19In the language of functional analysis, this step corresponds to an approximation of an operator semigroup. Consider the operators (t)on probability measures on induced by mapping p∈to y(r)(t,p). Then {(t):t≥0}is an operator semigroup (that is, (s+t)=(s)(t)). On ((N)), we approximate (t) by (P(N,r))Nt. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 688 Brandl and Brandt Theoretical Economics 19 (2024) of ¯ X(N,r)at the beginning of the interval. In those intervals where the distance between both processes is never more than δ 4,¯ X(N,r)is no more than δ 4+δ 4=δ 2away from p(r) for all but a τ 2fraction of the interval. By the choice of N, the union of those intervals is almost surely at least a 1 −τ 2fraction of the time axis. Summing over all intervals, this is enough to conclude that ¯ X(N,r)is no more than δ 2away from p(r)at least a 1 −τfraction of the time. Since p(r)is no more than δ 2away from p∗, we can get the same conclusion with δin place of δ 2and p∗in place of p(r). Translating this statement back to X(N,r) gives the first part of Theorem 1. AA continuous vector field induced by the Markov chain In this section, we define a continuous mapping from to based on the expected urn distribution in the subsequent round for each state of the Markov chain. We then show that this mapping admits a unique fixed point corresponding to an approximate maximal lottery. Recall that {X(N,r)(n,p0):n∈N0}is a discrete-time, time-homogeneous Markov chain with state space (N)and transition probability matrix P(N,r)p,p=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 2(1−r)pipjM(i,j)+r dpjif i=j 2(1−r) d  k=1 p2 k+r dif i=j for p∈(N)and p=p+ei N−ej Nfor i,j∈[d]={1, ,d}with p∈(N). All other transition probabilities are 0. If r>0, it is irreducible and aperiodic, and, thus, admits a unique stationary distribution in ((N)), a probability distribution over urn distributions. We omit writing the initial state p0whenever it is convenient. For i∈[d], we calculate the expected change in the ith component of X(N,r)times N given that X(N,r)is in state p∈(N): NEX(N,r) i(n+1)−X(N,r) i(n)X(N,r)(n)=p =N p∈(N)p i−piP(N,r)p,p =2(1−r) j=i pipjM(i,j)−M(j,i)+r d j=i (pj−pi) =2(1−r)pi j=i˜ M(i,j)pj+r d1−pi−(d−1)pi =2(1−r)pi(˜ Mp)i+r1 d−pi. For the last equality, recall that ˜ M(i,i)=0 since ˜ Mis skew-symmetric. Based on this, we define the continuous function f(r):→Rdwith f(r) i(p)=2(1−r)pi(˜ Mp)i+r1 d−pi.(6) 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 689 Let g(r):→with g(r)(p)=p+1 2f(p)for p∈. We show that g(r)is well defined (that is, indeed maps to ) and has a fixed point. If r>0, this fixed point is unique and we denote it by p(r).Asrgoes to 0, p(r)converges to the set of maximal lotteries for the profile Rthat induces ˜ M.Wenotethatifr=0, g(r)has a unique fixed point if and only if there is a unique maximal lottery. Lemma 1. For r>0,g(r)has a unique fixed point p(r). Moreover, for every δ>0,thereis r0so that p(r)∈Bδ(ML(R)) for all r≤r0. Proof.Weverifythatg(r)maps to .Forallp∈,i∈[d]f(r) i(p)=2(1−r)p˜ Mp + r(1−i∈[d]pi)=0 since ˜ Mis skew-symmetric and p∈.Moreover, f(r) i(p)=2(1−r)pi(˜ Mp)i   ≥−1 +r1 d−pi≥−2pi. Thus, g(r) i(p)≥pi+1 2(−2pi)≥0. It follows that g(r)maps to .Moreover,g(r)is continuous since f(r)is continuous. Hence, by Brouwer’s theorem, g(r)has a fixed point p(r). Now let r>0. Then, for all p∈with f(r)(p)=0, we have for all i∈[d],pi>0, since pi=0impliesf(r) i(p)=r1 d>0. Hence, we can rewrite f(r)(p)=0as,foralli∈[d], 2(1−r)( ˜ Mp)i=r1−1 pid.(7) To show that f(r)has a unique zero, assume that f(r)(p)=f(r)(q)=0forp,q∈. We have 0=2(1−r)p˜ Mq+q˜ Mp =2(1−r) i∈[d] pi(˜ Mq)i+qi(˜ Mp)i (7) =r i∈[d] pi1−1 qid+qi1−1 pid =r d i∈[d] piqi−pi qi+piqi−qi pi =−r d i∈[d] (pi−qi)2 piqi≤−r d|p−q|2 2, where the first equality uses the skew-symmetry of ˜ M(hence, p˜ Mq =−q˜ Mp), the third equality follows from (7)andthefactthatpand qare zeros of f(r),andthelast two equalities are algebra. (The notation |·|2denotes the L2norm.) This sequence of 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 690 Brandl and Brandt Theoretical Economics 19 (2024) equalities implies that p=q.Hence,p(r)is the unique zero of f(r)for r>0. Since every fixed point of g(r)is a zero of f(r),g(r)has a unique fixed point. For the last statement, let δ>0. By (7), for all r>0andi∈[d], ˜ Mp(r)i=r 2(1−r)1−1 p(r) id≤r 2(1−r).(8) Suppose for every r0>0, there is r<r 0so that p(r)/∈Bδ(ML(R)). Then we can find a sequence (rn)going to 0 so that p(rn)/∈Bδ(ML(R))for all n. By passing to a subsequence, we may assume that p(rn)→p/∈Bδ(ML(R)),butfrom(8) it follows that ˜ Mp≤0sothat p∈ML(R), which is a contradiction. BProperties of the deterministic process In this section, we study a deterministic version of the stochastic process described by the Markov chain. We thus have a continuum of balls and continuous time, and we show that this process converges to the unique fixed point identified in the previous section. Function f(r)defined in (6) gives rise to a (first-order ordinary) differential equation for continuously differentiable functions from [0, ∞)to , that is, functions in C1([0, ∞),).Fory∈C1([0, ∞),)and p0∈,consider d dt y(t)=f(r)y(t) y(0)=p0. (9) We show that (9) has a unique global solution y(r)for all r>0andp0∈.Moreover, this solution converges to the zero p(r)of f(r)as tgoes to infinity. Since rremains fixed throughout this section, we frequently omit the superscript (r). The proof that (9) has a unique local solution with values in Rdis standard. Only the fact that the solution does not leave the domain of fand can, thus, be extended to a global solution requires attention. Lemma 2. For every p0∈,(9) has a unique solution y∈C1([0, ∞),)with y(0)=p0. Proof.Notethatfis Lipschitz continuous in a neighborhood of . It follows from the Picard–Lindelöf theorem that for any t0∈[0, ∞)and p∈, the system d dt y(t)=fy(t) y(t0)=p (10) has a unique local solution, that is, a solution y∈C1((t0−ε,t0+ε),Rd). We observe that ymaps to . First, by the same arguments as in the proof of Lemma 1,wehave d dt  i∈[d] yi(t)= i∈[d] fiy(t)=0 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 697 Lemma 8. Let α∈[0, 1].Let{Zn:n∈N0}be indicator random variables and, for n≥1, let Sn=n k=1Zk.IfP(Z1=1)≤αand for all n≥2,P(Zn=1|Sn−1)≤α,then Plimsup n→∞ Sn n>α =0. Proof. The proof uses the moment generating functions of the random variables involved. Let Zbe an indicator random variable with P(Z=1)=α. Then, for all n≥2and t>0, EetSn=EetZnetSn−1≤EetZEetSn−1, where the inequality follows from the assumption that P(Zn=1|Sn−1)≤αand Fubini’s theorem. Repeated application of this inequality and the assumption P(Z1=1)≤αgive that for all n≥1andt>0, EetSn≤EetZn. Now let β>α,n≥1, and t>0. Then, by Markov’s inequality, P(Sn≥βn)=PetSn≥etβn≤e−tβn EetSn. Combining the two preceding inequalities gives P(Sn≥βn)≤e−tβn EetZn=Eet(Z−β)n. Since E(Z−β)<0, we have, for sufficiently small t>0, that E(et(Z−β))<1. Hence, P(Sn≥βn)decays exponentially in nand so  n≥1 P(Sn≥βn)<∞. The Borel–Cantelli lemma thus gives that limsupnSn n≤βalmost surely. Since β>αwas arbitrary, we conclude that limsupnSn n≤αalmost surely as claimed. Putting together Lemma 4, Lemma 7, and Lemma 8, we show that ¯ X(N,r)is almost surely close to p(r)most of the time for large enough N. More precisely, for S⊂(N),let ¯ s(N,r) t(S)=1 tt 0 χS¯ X(N,r)(s)ds be the fraction of time ¯ X(N,r)spends in a state in S.Forδ>0, we consider the fraction of time spent in Bδ(p(r)).IfNis large enough, the limit of ¯ s(N,r) t(Bδ(p(r))) for tto infinity is almost surely close to 1. Lemma 9. Let δ,τ>0.Then,foreveryr>0,thereisN0such that for all N≥N0and p0∈(N), Plim t→∞ ¯ s(N,r) tBδp(r)≥1−τ=1. (19) 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 698 Brandl and Brandt Theoretical Economics 19 (2024) Proof.Letr>0. By Lemma 5, we can find η>0suchthat supy(r)(t,p)−p(r):t≥0, p∈Bηp(r)<δ 2. By Lemma 4, we can find T1>0suchthatforallT≥T1, supy(r)(T,p)−p(r):p∈<η. Let T0=2 τT1.Notethaty(r)is time-invariant, that is, y(r)(t,p)=y(r)(t−t0,y(r)(t0,p)) for all t≥t0≥0. Combining these facts, it follows that for every p∈, the measure of t∈[t0,t0+T0]for which y(r)(t,p)is in a δ 2ball around p(r)is at least (1−τ 2)T0.Wemay assume that T0is integral. By Lemma 7,thereisN0∈Nsuch that for all N≥N0, sup p∈(N) Psup 0≤t≤T0y(r)(t,p)−¯ X(N,r)(t,p)≥δ 2<τ 2. Now fix N≥N0and p∈(N). We upper-bound the fraction of time ¯ X(N,r)is further than δaway from p(r). To simplify notation, let tk=kT0and ¯ xk=¯ X(N,r)(tk,p). For n≥1, we calculate the expected number of intervals [tk−1,tk],1≤k≤n,sothat |¯ x(t,p)−p(r)|≥δfor some t∈[tk−1,tk].LetZ(N,r) kbe the indicator variable for the event that ¯ X(N,r)(t,p)and y(r)(t−tk−1,¯ xk−1)differ by at least δ 2on the time interval [tk−1,tk]given that both start at the point ¯ xk−1at time tk−1.SoZ(N,r) kis 1 if suptk−1≤t≤tk|¯ X(N,r)(t,p)−y(r)(t−tk−1,¯ xk−1)|≥δ 2and is 0 otherwise. Notice that {Z(N,r) k:k∈N0}satisfies the hypothesis of Lemma 8with α=τ 2.20 If Z(N,r) k=0, then tk tk−1¯χBδ(p(r))¯ X(N,r)(t,p)dt ≤tk tk−1¯χBδ 2 (y(r)(t−tk−1,¯ xk−1))¯ X(N,r)(t,p)dt +tk tk−1¯χBδ 2 (p(r))y(r)(t−tk−1,¯ xk−1)dt ≤τ 2T0. It follows that 1 nT0 k∈[n]tk tk−1¯χBδ(p(r))¯ X(N,r)(t,p)dt = k∈[n] Z(N,r) k=0 1 nT0tk tk−1¯χBδ(p(r))¯ X(N,r)(t,p)dt + k∈[n] Z(N,r) k=1 1 nT0tk tk−1¯χBδ(p(r))¯ X(N,r)(t,p)dt 20While the probability that Z(N,r) nequals 1 may depend on Z(N,r) kfor k<n,theboundof τ 2holds independently of Z(N,r) kfor k<nsince the bound obtained in Lemma 7is uniform in the initial state p. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 699 ≤τ 2+1 n n  k=1 Z(N,r) k. Applying Lemma 8to {Z(N,r) k:k∈N0}with α=τ 2gives P limsup n→∞ 1 n n  k=1 Z(N,r) k≥τ 2!=0. Hence, with the preceding inequality we get P(lim t→∞ ¯ s(N,r) tBδp(r)≥1−τ=Plim t→∞t 0 χBδ(p(r))¯ X(N,r)≥1−τ=1, which is (19). Theorem 1. Let δ,τ>0. Then there is r0>0such that for all 0<r≤r0, there are p∗∈ ML(R)and N0∈Nsuch that for all N≥N0and p0∈(N), almost surely lim n→∞ 1 nk≤n:X(N,r)(k,p0)−p∗≤δ≥1−τ. Moreover, there is C>0such that for all n∈N0, PX(N,r)(n,p0)−p∗≤δ≥1−τ−e−Cn. Proof. By Lemma 1, we can choose r0>0sothatp(r)∈Bδ 2(ML(R)) for all 0 <r≤r0. Let 0 <r≤r0and p∗∈ML(R)so that |p(r)−p∗|≤δ 2. Then, applying Lemma 9to δ 2,τ, and r,wegetN0∈Nsuch that (19)holds(withδ 2in place of δ). Hence, Plim t→∞ ¯ s(N,r) tBδp∗≥1−τ=1. (20) This is equivalent to the assertion in the first part of the theorem. The second statement follows by recalling the standard fact that the distribution of an irreducible and aperiodic Markov chain converges exponentially to its stationary distribution in the total variation norm (Levin, Peres, and Wilmer (2009, Theorem 4.9)). References Allesina, Stefano and Jonathan M. Levine (2011), “A competitive network theory of species diversity.” Proceedings of the National Academy of Sciences (PNAS), 108, 5638– 5642. [685] Angluin, Dana, James Aspnes, Zoe Diamadi, Michael J. Fischer, and René Peralta (2006), “Computation in networks of passively mobile finite-state sensors.” Distributed Computing, 18, 235–253. [673] Arora, Sanjeev, Elad Hazan, and Satyen Kale (2012), “The multiplicative weights update method: A meta-algorithm and applications.” Theory of Computing, 8, 121–164. [683] 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 700 Brandl and Brandt Theoretical Economics 19 (2024) Arrow, Kenneth J. (1951), Social Choice and Individual Values, first edition. Cowles Foundation, New Haven. Second edition, 1963. [668] Aspnes, James and Eric Ruppert (2009), “An introduction to population protocols.” In Middleware for Network Eccentric and Mobile Applications, 97–120, Springer-Verlag. Chapter 5. [673] Auer, Peter, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire (2002), “The nonstochastic multiarmed bandit problem.” SIAM Journal on Computing, 32, 48–77. [683] Bailey, James P. and Georgios Piliouras (2018), “Multiplicative weights update in zerosum games.” In Proceedings of the 19th ACM Conference on Economics and Computation (ACM-EC), 321–338. [683] Barberà, Salvador (1979), “Majority and positional voting in a probabilistic framework.” Review of Economic Studies, 46, 379–389. [678] Bartholdi, John III, Craig A. Tovey, and Michael A. Trick (1989), “Voting schemes for which it can be difficult to tell who won the election.” Social Choice and Welfare, 6, 157– 165. [668] Benaïm, Michel and Jörgen W. Weibull (2003), “Deterministic approximation of stochastic evolution in games.” Econometrica, 71, 873–903. [686] Brams, Steven J. and Peter C. Fishburn (1978), “Approval voting.” The American Political Science Review, 72, 831–847. [668] Brams, Steven J. and Peter C. Fishburn (2002), “Voting procedures.” In Handbook of Social Choice and Welfare, volume 1 (Kenneth J. Arrow, Amartya K. Sen, and Kotaro Suzumura, eds.), Elsevier. Chapter 4. [668] Brandl, Florian, Felix Brandt, and Hans Georg (2016), “Seedig. Consistent probabilistic social choice.” Econometrica, 84, 1839–1880. [668,670,672] Brandl, Florian and Felix Brandt (2020), “Arrovian aggregation of convex preferences.” Econometrica, 88, 799–844. [668,670] Brandl, Florian and Felix Brandt (2021), “A natural adaptive process for collective decision-making.” Technical report, https://arxiv.org/abs/2103.14351.[671,684] Brandl, Florian, Felix Brandt, and Christian Stricker (2022), “An analytical and experimental comparison of maximal lottery schemes.” Social Choice and Welfare, 58, 5–38. [670,678] Brandt, Felix, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, eds. (2016), Handbook of Computational Social Choice, Cambridge University Press. [668] Brandt, Felix and Felix Fischer (2008), “Computing the minimal covering set.” Mathematical Social Sciences, 56, 254–268. [673] Brandt, Felix, Patrick Lederer, and René Romen (2022), “Relaxed notions of Condorcetconsistency and efficiency for strategyproof social decision schemes.” In Proceedings of 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 701 the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS).[679] Brown, George W. (1951), “Iterative solutions of games by fictitious play.” In Activity Analysis of Production and Allocation, 374–376, John Wiley and Sons, Inc. [683] Bubeck, Sébastien and Nicolò Cesa-Bianchi (2012), “Regret analysis of stochastic and nonstochastic multi-armed bandit problems.” Foundations and Trends in Machine Learning, 5, 1–122. [683] Carbonell-Nicolau, Oriol and Efe A. Ok (2007), “Voting over income taxation.” Journal of Economic Theory, 134, 249–286. [669] Cover, Thomas M. and Joy A. Thomas (2006), Elements of Information Theory.JohnWiley &SonsInc.[691] DeGroot, Morris H. (1974), “Reaching a consensus.” Journal of the American Statistical Association, 69, 118–121. [672] Felsenthal, Dan S. and Moshé Machover (1992), “After two centuries should Condorcet’s voting procedure be implemented?” Behavioral Science, 37, 250–274. [670,672] Fishburn, Peter C. (1984), “Probabilistic social choice based on simple voting comparisons.” Review of Economic Studies, 51, 683–692. [669] Foster, Dean P. and Rakesh Vohra (1999), “Regret in the on-line decision problem.” Games and Economic Behavior, 29, 7–35. [683] Freund, Yoav and Robert E. Schapire (1999), “Adaptive game playing using multiplicative weights.” Games and Economic Behavior, 29, 79–103. [683] Fudenberg, Drew and Lorens A. Imhof (2008), “Monotone imitation dynamics in large populations.” Journal of Economic Theory, 140, 229–245. [678] Fudenberg, Drew and David M. Kreps (1993), “Learning mixed equilibria.” Games and Economic Behavior, 5, 320–367. [683] Gehrlein, William V. and Dominique Lepelley (2011), Voting Paradoxes and Group Coherence, Studies in Choice and Welfare. Springer-Verlag. [671] Gibbard, Allan (1973), “Manipulation of voting schemes: A general result.” Econometrica, 41, 587–601. [668] Gibbard, Allan (1977), “Manipulation of schemes that mix voting with chance.” Econometrica, 45, 665–681. [668,670] Goel, Ashish and David T. Lee (2014), “Large-scale decision-making via small group interactions: The importance of triads.” In Proceedings of the 5th International Workshop on Computational Social Choice (COMSOC).[672] Grilli, Jacopo, György Barabás, Matthew J. Michalska-Smith, and Stefano Allesina (2017), “Higher-order interactions stabilize dynamics in competitive network models.” Nature, 548, 210–213. [685,686] 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License 702 Brandl and Brandt Theoretical Economics 19 (2024) Hart, Sergiu and Andreu Mas-Colell (2000), “A simple and adaptive procedure leading to correlated equilibrium.” Econometrica, 68, 1127–1150. [683] Hart, Sergiu and Andreu Mas-Colell (2013), Simple Adaptive Strategies, volume 4 of Economic Theory. World Scientific Publishing Company. [683] Heckelman, Jac C. (2003), “Probabilistic Borda rule voting.” Social Choice and Welfare, 21, 455–468. [678] Hoang, Lê Nguyên (2017), “Strategy-proofness of the randomized Condorcet voting system.” Social Choice and Welfare, 48, 679–701. [670,672] Hofbauer, Josef (2011), “Deterministic Evolutionary Game Dynamics.” In Evolutionary Game Dynamics, volume 69 of Proceedings of Symposia in Applied Mathematics (Karl Sigmund, ed.), American Mathematical Society. 61–79. [685] Hofbauer, Josef and William H. Sandholm (2002), “On the global convergence of stochastic fictitious play.” Econometrica, 70, 2265–2294. [683] Hofbauer, Josef and Karl Sigmund (1998), Evolutionary Games and Population Dynamics. Cambridge University Press. [684,685] Holley, Richard A. and Thomas M. Ligget (1975), “Ergodic theorems for weakly interacting infinite systems and the voter model.” The Annals of Probability, 3, 643–663. [672] Knebel, Johannes, Markus F. Weber, Torben Krüger, and Erwin Frey (2015), “Evolutionary games of condensates in coupled birth–death processes.” Nature Communications, 6. [684,685,686] Kurtz, Thomas G. (1970), “Solutions of ordinary differential equations as limits of pure jump Markov processes.” Journal of Applied Probability, 7, 49–58. [694] Laffond, Gilbert, Jean-François Laslier, and Michel Le Breton (1997), “A theorem on symmetric two-player zero-sum games.” Journal of Economic Theory, 72, 426–431. [674] Laslier, Benoît and Jean-François Laslier (2017), “Reinforcement learning from comparisons: Three alternatives is enough, two is not.” The Annals of Applied Probability, 27, 2907–2925. [685,686] Laslier, Jean-François (2000a), “Aggregation of preferences with a variable set of alternatives.” Social Choice and Welfare, 17, 269–282. [668,670] Laslier, Jean-François (2000b), “Interpretation of electoral mixed strategies.” Social Choice and Welfare, 17, 283–292. [669] Laslier, Jean-François (2011), “And the loser is... plurality voting.” In Electoral Systems, Studies in Choice and Welfare (Dan S. Felsenthal and Moshé Machover, eds.), 327–351, Springer. [668] Levin, David A., Yuval Peres, and Elizabeth L. Wilmer (2009), Markov Chains and Mixing Times. American Mathematical Society. [699] 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License Theoretical Economics 19 (2024) Adaptive collective decision-making 703 Maynard Smith, John and George R. Price (1973), “The logic of animal conflict.” Nature, 246, 15–18. [684] Myerson, Roger B. (1993), “Incentives to cultivate favored minorities under alternative electoral systems.” American Political Science Review, 87, 856–869. [669] Rivest, Ronald L. and Emily Shen (2010), “An optimal single-winner preferential voting system based on game theory.” In Proceedings of the 3rd International Workshop on Computational Social Choice (COMSOC), 399–410. [670,672] Robinson, Julia (1951), “An iterative method of solving a game.” Annals of Mathematics, 54, 296–301. [683] Satterthwaite, Mark A. (1975), “Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions.” Journal of Economic Theory, 10, 187–217. [668] Schuster, Peter and Karl Sigmund (1983), “Replicator dynamics.” Journal of Theoretical Biology, 100, 533–538. [684] Slivkins, Aleksandrs (2019), “Introduction to multi-armed bandits.” Foundations and Trends in Machine Learning, 12, 1–286. [683] Taylor, Peter D. and Leo B. Jonker (1978), “Evolutionary stable strategies and game dynamics.” Mathematical Biosciences, 40, 145–156. [684] Young, H. Peyton (1974), “An axiomatization of Borda’s rule.” Journal of Economic Theory, 9, 43–52. [668] Young, H. Peyton and Arthur Levenglick (1978), “A consistent extension of Condorcet’s election principle.” SIAM Journal on Applied Mathematics, 35, 285–300. [668] Co-editor Federico Echenique handled this manuscript. Manuscript received 22 July, 2022; final version accepted 28 March, 2023; available online 19 April, 2023. 15557561, 2024, 2, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5380 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License