**Games of Consensus**

Reflections on ways to reinvent democracy, streamline decision making and accelerate the discovery of consensus.

I recall with some fondness a night in 1986 at Vassar College when I issued the following proclamation to one of the leaders of a student political group on campus:

The optimum government is that which minimizes suffering and maximizes freedom.

The individual (whose name I forget, and who doubtlessly now forgets me and our discussion) agreed. The two of us would have disagreed on nearly any matter political I think But we both agreed with the above proposition. I reasoned further claiming that one party usually champions one, while the other often champions the other. Might it be possible, I pondered, that we might actually have both in some utopia of the future?

My interest in such matters actually goes back a few years before that. Let me preface my remarks with some examples. It may give the reader a sense of what has led me to write what she is currently reading.

The household in which I was raised was headed by two rather patriotic parents, I think. They seemed to like the democratic process, and seemed willing to improvise a bit with that process as occasions warranted it.[1] When it was time for the kids to divide up a collection of marbles we took turns choosing, one marble at a time. If there was a piece of pie to be divided, one child would slice and the other would choose. If there was a dispute, we would flip a coin. How intrinsically fair it felt.

As a kid, I remember reading with delight in one of Martin Gardner's books about a generalization of the fair pie slicing process to N people. I told my Dad about it, and he said "yeah" that he had heard about it, [2] and then proceeded to tell me a couple of shortcomings of the proposed technique and suggested that I think about it some more.

As I wrote here "In grad school I came to the conclusion that if there were N faculty members and M grad students all getting together for a Friday afternoon get-together, it would take time proportional to O(2^N + M) to decide where to eat dinner." That relatively slow process made an impression on me. Nowadays when it is time for my family to make a decision on which video to watch on the one night a week we watch the tube, we exercise a linear-time algorithm. Ahh... the joys of being a parent. The particular process the parents have implemented in this case involves minimizing suffering more than maximizing freedom, but in this case (with only one TV) consensus is rather necessary.

So I wish to discuss a few ideas I've worked on over the years for maximizing freedom and minimizing suffering, and to explore whether or not any of those ideas might be useful toward discovering consensus in large groups. Here are a variety of types of situations in which approaches requiring consensus may require strategies different than your typical competitive outcome.

Let's start with the simplest of these situations: A group of N people is asked to select a single course of action for all members from among k alternatives.

- Consensus. All individuals agree on one alternative A.
- The random decision. One of the k alternatives, Ai, is selected with probability(Ai) = 1/k Provided the random process is truly random, then the outcome is, in some simple way, fair. It may be difficult though for any group to surrender its fate to randomness since people's preferences may be stronger than their sense of adventure It also has the disadvantage that a majority of people may be unhappy with the outcome, most of the time.
- The random weighted decision. Each of N individuals votes for a favorite alternative. If v(Ai) represents the number of votes that each alternative Ai receives, then Ai is chosen with probability v(Ai)/N . This has the advantage that even minority perspectives have a nonzero probability of adoption. The disadvantage is that the majority may be unhappy with the outcome and argue that the minority perspective was simply wrong to begin with. The technique while preserving integrity for minority perspectives, runs the risk of allowing discontent with the process whenever the majority does not win.
- The plurality vote + runoff election. This two-stage process begins with each person voting for one alternative. In the second stage, the two alternatives receiving the largest number of votes are then compared one against another in a run-off election.
- Recursive convergence. At stage one, each person votes for a favorite alternative. At stage J, all alternatives are sorted according to the number of votes they have received. The one alternative (or more in the case of a tie) receiving the fewest votes is eliminated. The remaining options are considered for stage J-1. Assuming that no perfect ties develop, then this process terminates in linear time.
- Sequential elimination of unacceptable options (Dailey family video algorithm). Individuals take turns eliminating options. This works better when k>N, since when N>k, some individuals have no opportunity to affect the outcome. In fact, it works best when k=mN+1 for some integer m>0, since in that case each individual exercises the same number of eliminations. The problem with this, as will be noted later, is that eliminations become more critical as the number of remaining choices approaches 1.
- Recursive elimination of unacceptable options. At stage one, each person votes for the alternative they most wish to eliminate. At stage J, all alternatives are sorted according to the number of votes they have received. The one alternative (or more in the case of a tie) receiving the most votes is eliminated. The remaining options are considered for stage J-1. Assuming that no perfect ties develop, then this process terminates in linear time.
- Enumeration of hybrid proposals. Each of the competing alternatives is viewed as an utterance. A simple grammar for those utterances is constructed which maximizes re-use of vocabulary. The N individuals take turns constructing hybrid proposals based on the collective grammar. Once k=mN+1 proposals (for some integer m>0) have been constructed, then one of the techniques 1-7 above is employed to narrow the options down to one.

k tasks are to be assigned to a work group consisting of N people.

Some of the tasks are desirable; some are, perhaps less than desirable. Not all people however are likely to view the desirability of the tasks in the same way. What some people think is fun (like math), others may find to be drudgery. What we seek, therefore, is a situation in which all tasks are assigned to someone, and people are allocated the tasks they most want to work on.

In the general case, this is like the 3-dimensional matching problem discussed by Garey and Johnson (in Computers and Intractability, 1976), or the "classical marriage problem" in which n unmarried men and n unmarried woman are to be paired such that each gets an acceptable spouse. As I have often pointed out in class it is good that our species has only two genders since the marriage problem for three genders is NP complete, while it is solvable in polynomial time for only two genders.

We may think of the task allocation problem as consisting of a weighted bipartite graph on k+N nodes in which the people nodes have weighted links to the task nodes.

An approach I have investigated from time to time over the years works as follows: build a p-regular graph among the N persons. Randomly assign t<p "turn markers" to the N people. Randomly deal the k tasks to the N people. In each turn, let M refer to the number of tern markers a person holds. A person must pass all turn markers they have to any of their p neighbors.. They may also pass up to M tasks to neighbors who are not receiving turn markers. The passing of tasks continues until equilibrium arises.

I'll work on my thoughts in this space over the next few weeks or months. In the meantime feel free to email me at david@dailey&sru?edu|s/@/\./;s/\&/@/;s/\?/./ but using proper grammar, please.

[1] Perhaps it was because both parents hung out a bit with folks like Stan Ulam and John von Neumann in the time leading up to and immediately following the end of World War II. In the one graduate course I had with Dr. Ulam (my Mom called him Stan, though I never did), I got a strong sense that that sort of play was rather common in those circles, at least it was to him and other combinatorists I have known before and after.

[2] There seems to have been a lot of oral tradition passed around at Los Alamos, which rather makes sense in retrospect.