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. 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,  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.
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.
 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.
 There seems to have been a lot of oral tradition passed around at Los Alamos, which rather makes sense in retrospect.