And the Winner is Probably...

In Provably Probable Social Choice I talked about the Gibbard-Satterthwaite theorem and its somewhat depressing conclusion that no deterministic voting system can completely prevent dishonest/tactical voters from unfairly influencing elections. Also in that post, I compared this social choice theorem with a similar result in distributed computing, Byzantine Agreement. In both realms, it seems that randomness must be an essential ingredient in any full solution.

There are many good, efficient solutions to various distributed computing problems that are probabilistic in nature. But what about random voting? The very idea seems silly. But is it?

In fact there has been a good bit of recent research into probabilistic voting algorithms that is starting to yield some interesting results.  For example, weighted lottery voting basically puts all the votes into a hat and chooses one at random. The single ballot chosen determines the winner. Surprisingly perhaps, this simple probabilistic procedure may be a good way to elect legislatures with multiple representatives from multiple districts. One reason is that it is completely immune to tactical voting.

Suppose that, for a given weighted lottery election, candidate A has 60% of the votes, candidate B has 30%, candidate C has slightly less than 10% and candidate D has only a single vote. With this voting procedure, the favored candidate will probably win the election. But there is some chance A will lose in favor of B or C. And there is even a small chance that candidate D, with only a single vote, will win! I know what you're thinking — this isn't practical. But think what happens when we do this for each member of a legislature, say a hundred representatives, all elected from their individual districts using weighted lottery voting. In the end, the distribution of representatives will conform to the distribution of voters across all districts. Yes, there may be some anomalies in the state house, so to speak, but if you trust the laws of probability (and I do), the overall make-up of the legislature will reflect the opinions and expressed wishes of the electorate. Now, I don't know of anyone who has seriously suggested that weighted lotteries be used in real world elections, but it is nonetheless tantalizing to look at some of the practical advantages to be gained by doing so.

First, like most probabilistic algorithms in the field of distributed computing, this procedure is dirt simple. There is no tallying of votes, no backroom subjective judgement about which ballots to count and which to ignore, no arithmetic of any kind involved in determining who the winner is. You simply put all the ballots into a basket (physically or electronically), shake it up, and then have a good-looking spokesmodel choose the winner. This procedure will likely promote higher voter turnout. With most of the deterministic voting schemes in use today, a voter who finds herself in an extreme minority may decide to skip the whole voting hassle if she feels there is absolutely no way her vote will matter. With the probabilistic scheme, however, there is always a possibility her vote will not only matter, but completely determine the outcome of the election! Similarly, there will be higher candidate participation because this algorithm (unlike winner-take-all deterministic plurality algorithms) does not inherently favor a two-party system. It is always possible for a third party to win an election.

The most promising advantage of probabilistic voting schemes like this one is that they are impossible to "cheat." More precisely stated, the best way to get your favorite candidate to win is to actually vote for him. This is not the case with any deterministic voting algorithm if there are four or more candidates. You might say, well, cheating isn't very common because it's so hard for individual voters to devise effective cheating strategies. Not so. In fact, there is one kind of cheating that is especially widespread and particularly destructive: the gerrymander. Ruling parties, with the help of computer software, commonly re-draw district lines so as to minimize or completely remove the voting influence of those who would vote against them. This practice is completely legal, completely constitutional, and completely despicable. And it works solely because of our choice of voting systems. Perhaps the most egregious example of gerrymandering in the entire US occurs in my home town of Austin, Texas. In congressional District 25, shaped like the practice's namesake salamander, Austinites share a voting pool that stretches hundreds of miles to the South, all the way to the Mexican border. No one disagrees the only purpose for this strange arrangement is to cheat in the congressional elections. A probabilistic voting scheme, like weighted lottery voting, would completely eliminate the gerrymander. As long as districts contain an equal number of voters, as required by the Supreme Court, the ideological composition of the legislature will, with high probability, reflect the ideological distribution of the voters.

But this simple probabilistic voting scheme is only remotely practical for legislative-type elections, where the, perhaps, negative effects of an improbable choice of representative can be diluted by all the other members of the legislature. The method is ill-suited for executive elections where a single, powerful governor or president is chosen by chance. For those kinds of elections, you really want a probabilistic algorithm that usually honors the majority choice, if there is one, and steps in with a coin flip only when it needs to. One example of that sort of algorithm is called double range voting.

With this clever, though more complex, voting procedure, each voter casts two ballots (or one ballot with two sub-ballots), awarding preference points in a given range, say zero to five stars, to each of the candidates. The first range ballot is tallied to identify the first-, second-, and third-place winners. Usually, the first-place winner is chosen as the winner of the whole election and we're done. But there is a (tunably small) chance the algorithm will ignore the first-place choice and pick the winner to be one of the second- or third-place candidates instead. In that case, the second ballot is used to make the binary choice. Since binary choices are immune to the Gibbard-Satterthwaite limitation, there is no reason for voters to vote tactically on the second ballot, and since it isn't possible to know which candidates will be #2 and #3, the second ballot may just as well be a completely honest reflection of the voter's choices among all candidates. Obviously, this is not a mathematical proof, but I'm sure you get the idea. The outcome is, usually the majority candidate wins, but sometimes the second or third most favored candidate wins, and as reward for suffering this small uncertainty, the election becomes immune to tactical voting.

These and other probabilistic voting procedures all suffer the same drawback: lack of transparency. When the outcome of an election involves a random choice, how do you prove ex post facto that the choice was indeed random? If I randomly choose a number, say 42, how can I prove to you my choice was just as likely as any other integer? How do I prove that the good-looking spokesmodel didn't use sleight of hand to deliberately choose a certain ballot out of the basket? More practically, how do I prove that the computer-generated random selection was indeed, random? If I use a physical process to generate a random selection, like repeatedly flipping a "fair" coin, how can you be sure the coin was really fair? And for the deeply paranoid (or inquisitive) among us, how do we know there is even such a thing as randomness? Maybe everything in the universe is predictable, if you just have a big enough computer.

My next few posts will examine these kinds of questions from the points of view of computer science, physics, mathematics, and theology. Given the demonstrated importance of randomness in distributed computing and social choice, we should at least investigate whether it actually exists.

Democracy at Scale

Democracy is a flawed concept. Everybody knows it, and we have known it for many, many years. The principle problem with a pure democracy is, it doesn't scale. That's why large democratic institutions, notably the United States of America, are always something sort of like a democracy, but not quite. The U.S. is, of course, a republic. What's the difference between a democracy and a republic? James Madison explained it best in The Federalist #10.

The two great points of difference between a democracy and a republic are: first, the delegation of government, in the latter, to a small number of citizens elected by the rest; secondly, the greater number of citizens, and greater sphere of country, over which the latter may be extended.

The effect of the first difference is, on the one hand, to refine and enlarge the public views, by passing them through the medium of a chosen body of citizens, whose wisdom may best discern the true interest of their country, and whose patriotism and love of justice will be least likely to sacrifice it to temporary or partial considerations.

If that last part doesn't make your heart ache with nostalgia then you haven't paid much attention to U.S. politics for a long time. I personally cannot remember a time, and perhaps no one alive can remember a time, when the Congress of the United States consisted chiefly of citizens with enough wisdom, patriotism, and love of justice to refuse a lobbyist or vote against a good pork barrel spending bill in order to get reelected.

What happened? Are people fundamentally more corrupt than in the past? No, we are generally as selfish as always. The problem is, we have outgrown our system of government. Again. The brilliant idea of a republic, electing a small body of representatives who then govern among themselves by direct democracy (more or less), is inherently more scalable than pure democracy, but it also has its limits. Our numerous modern representatives — presidents, electors, congressmen, judges, mayors, city council members, constables (whatever those are) and so on — are often elected based not on their character, but on superficial bases like parentage, wealth, party affiliation, and hair style. That's largely because nobody has the time to really know and understand who these people are. And so we bestow enormous, disproportionate voting power to people based on silly criteria, including what they say they'll do in office, because we just don't have the time to examine their history to determine what they really believe in.

The answer, or at least one answer, can be found in the Ethosphere. Instead of voting for people to represent us, we might vote only on ideas, or their written embodiment that we call props. It's much easier to decide whether you are for or against an idea, a proposal, or a proposition, than it is to decide whether a complex person will be more or less likely to represent your own views. In order to scale, there will still be some citizens who have more voting power than others, but these representatives will be chosen based solely on their history of constructive participation in whatever society you both choose to be members. Citizens who write props that are eventually ratified by the voters at large will receive more voting power, as a side-effect of the normal activity of the group. Representatives can get elected only by constructive participation, not by campaigning.

This idea of conveying greater resources, in this case voting power or rep, to some individuals in order to increase the welfare of the entire group was first identified and discussed by a nineteenth century economist named Vilfredo Pareto. Pareto Inequality is exactly this somewhat paradoxical idea that the overall social welfare (measured by some metric) of a society can sometimes be increased by bestowing special powers or additional resources to small numbers of individuals.

The question now becomes, can a reputational voting paradigm like the one I discussed in Building Ethos out of Logos actually result in a Pareto inequality and benefit the group as a whole by allowing the votes of those individuals with higher reputations to count more than others? To try to answer that question, I wrote a simple simulation. For the geeks out there, I'll describe the details of the simulation in a separate post. In general terms, it mimics the activities of five independent populations with 10,000 members in each. Props are proposed by randomly-chosen members and each member then votes on them based on its own internal preferences. A graphical summary of the results can be seen below. You might want to click on the graph to see the full-sized version.

The three plots display a measure of overall displeasure or regret after each of 1,000 props have been considered, voted upon, and either ratified or not. Regret is the inverse of social welfare, so lower regret numbers mean the system is doing a better job of identifying the population consensus. Under ideal conditions, when every voter is fully informed and there is 100% voter turnout, the result is the blue curve, which shows very low average regret. In other words, pure democracy works great when everyone participates and they have all the necessary information to accurately vote their individual preferences. Unfortunately, this is rarely the case for large populations.

The red curve shows what happens under more realistic circumstances, where only 40% of the population votes and only 25% of them are fully informed. Notice the overall regret numbers increase significantly, meaning more voters are more unhappy with the election results. The regret measurements include all voters, even those who didn't vote and those who didn't really understand what they voted for/against. As in real life, everyone has an opinion, even those who are too busy, too lazy, or too ignorant to express it by voting.

The green curve introduces reputational voting for the first time. We leave turnout percentage and informed percentage at 40% and 25% respectively, but each voter gets a boost in its reputation when it authors a prop that is eventually ratified by the population at large. Its rep is decreased when one of its props is rejected by the voters. Of course, each voter votes its current reputation, so voters who have more success historically in capturing the consensus of the whole group will eventually have higher reps and, therefore, disproportionately high voting power. As the green plot shows, this strategy starts off no better than the realistic scenario, but gradually gets better (lower regret numbers) until it has more or less completely compensated for the low turnout and poorly informed electorate. Thus, reputational voting does indeed implement a Pareto inequality by benefiting the population as a whole when additional resources (voting power) are granted to a small number of individuals.

There are other practical advantages of reputational versus representational (e.g. republics) systems that the simulation cannot show. Reputation is dynamic and continuously computed, which leads to a more robust system. Term limits are no longer necessary because reps increase and decrease over time based on recent history of constructive participation. Even when populations have shifting consensus opinions, which often happens, the reputation system is robust enough to shift with them. Also, reputation is computed as a side-effect of doing real work, proposing and voting on ideas, rather than as the side-show beauty contests representative elections often become. As I discussed in "Jane, You Ignorant Slut", it seems nobler to discuss ideas than people.

In order to bring democracy to the Internet, we will need to teach it to scale. As the above simulation shows, reputational voting is a straightforward mechanism that can help us do that.

The Truth and Nothing But...a Good Story

A few months ago, a friend of mine who leans to the right politically shared a post on Facebook that started out like this:

Professor Joseph Olson of Hamline University School of Law in St. Paul, Minnesota, points out some interesting facts concerning the last Presidential election:

• Number of States won by: Obama: 19 McCain: 29
• Square miles of land won by: Obama: 580,000 McCain: 2,427,000
• Population of counties won by: Obama: 127 million McCain: 143 million
• Murder rate per 100,000 residents in counties won by: Obama: 13.2 McCain: 2.1

You may have seen this post, or even shared it yourself. By now, it is well known that it is a hoax, an urban legend, and almost every "fact" in it is false. By false, I mean provably incorrect, wrong, intentionally misleading, the opposite of the truth. A lie of the vicious variety. Thinking that my friend, an intelligent, honorable, well-educated man, must have just posted this Internet hoax without checking it out first, I commented on his post, helpfully (I thought) pointing out his mistake, including several links proving the thing is false.

But my friend simply deleted my comment and left the original post as it was, continuing to garner many "likes" from his like-minded friends. Incredulous, I commented again, this time asking, "Doesn't it bother you just a little that your post is utterly untrue?" His response was devastatingly brief, "Not one bit."

At this point I could have unfriended and written this guy off as just another whacked out Republican. But a few weeks later another friend, this time a left-leaning one, shared a news article in which Ann Romney is quoted as saying, "I mean really, all this wanting to be equal nonsense is going to be detrimental to the future of women everywhere." This time, my friend quickly realized this was a vicious fabrication (humorless satire isn't satire at all, just a lie). He posted a retraction and removed the original link. But instead of just saying, "I screwed up, please ignore," he said, and I'm paraphrasing here, the fact that so many people believed the article is an indication that it might be true, and in any case we should carefully consider the attitudes and positions of a potential First Lady before choosing her husband as president. In other words, if enough people find something to be plausible, it is likely to be at least partly true.

So it seems, on both sides of the political spectrum, we don't let the facts get in the way of a good story. And we never have. If you are a fan of Atlas Shrugged, Animal Farm, 1984, Lord of the Flies, The Republic, The Holy Bible, or almost any great work of literature, you know that a good story woven around a fictional set of "facts" is just as effective at shaping opinions, if not more so, than any dry set of statements, numbers, and statistics that have only the slightest advantage of being true. People are moved to action by narratives, not facts.

In Conflict, Compromise, and Consensus, I stated, "If one argues for an idea, or fights for it, it should be out of conviction the idea is righteous and true." In response to this, my good friend Dr. Russell Turpin points this out:

Among the most seductive of fallacies are the notions that believing something that is true must be advantageous, and conversely that believing what’s false is detrimental.

Well said. A good story is often more valuable than the truth. And facts are relative to the times and communities in which they are found. Ethics, however, are not -- at least not in my view. It is universally unethical to tell a good story based on facts you know to be false within your community. It is wrong to wield the terrible power of argumentation or war in defense of something you know to be a falsehood, even if it is to your advantage to do so.

Nevertheless, facts are rarely the best way to win an argument or an election. When faced with the necessity to choose between two alternatives in the real world, my favorite modern religious allegory, "The Life of Pi," supplies the answer in its final paragraphs. Which story makes you happiest?

Provably Probable Social Choice

There is a strong theoretical similarity between computer networks and people networks. Here we will discuss a surprising fact that has been proven to be true for both human and computer networks.

Without a coin to flip, there is no safe way for independent entities to reach consensus! 

The previous chapter contained a light treatment of a fairly heavy theoretical topic in computer science, Byzantine Agreement (BA), and an exploration of how randomness is an essential requirement in overcoming certain impossibility results in distributed computing. As it turns out, there are some tantalizingly strong similarities between the theory of distributed agreement and the theory of social choice (SC).

Recall that the BA problem setup involves a number of distributed processes each of which starts out with an initial value for some variable. We might call this initial value the "authentic" or "honest" value of a process, because all properly functioning processes will honestly report this value to all others. The goal of any BA algorithm is to allow the processes to vote for their authentic value and to compute, eventually, a global value in such a way that two straightforward requirements are met:

1. If all well-behaved processes have the same authentic value, then the global consensus value must be that value.
2. If the well-behaved processes do not all agree on the same authentic value, they must still agree on some global value; it doesn't matter which one.

To make it more interesting, the problem allows for the possibility of faulty processes that do not honestly report their authentic value choices but rather attempt to game the system to influence the agreed upon result, or to prevent any agreement from being reached. If we place no constraints at all on the types of failures the faulty processes can experience, then we may as well assume the nefarious nodes are consciously trying to thwart our algorithm and that they have complete access to all the information they need to do so.

Already we can start to see similarities between BA and SC (voting) problems. We have a number of independent processes (voters), each of which has its own preferred value (candidate) and they must report (vote) in order to agree on (elect) a global winner in a fair manner. Some of the entities may be faulty (dishonest) and instead report (vote) strategically, using information about partial results to unfairly game the system in favor of their authentic choice.

Terminology note: The social choice literature seems to use the terms "strategic voting" and "tactical voting" interchangeably to mean voting for some candidate who is not your authentically preferred one in order to try to influence the election in your favor. Here we will use "tactical voting" because it describes better what's actually going on.

A very interesting question to ask for both BA and SC is this: Is it possible to devise an algorithm in which the non-faulty (honest) processes (voters) can overcome the evil impact of one or a few faulty (dishonest) ones so they cannot unfairly influence the result?  Not surprisingly, many mathematicians have examined this and similar questions and, perhaps surprisingly, the answers have been rather discouraging.

In the area of Byzantine Agreement, it was proven in 1985 that, for any practical scenario (where, e.g.,  message delivery times are unpredictable) there is no deterministic algorithm that will prevent even a single faulty process from influencing the results of the agreement. All the great work and research to find solutions in this area depends on randomness in some way to solve this important problem.

So what about the Social Choice arena? Around the same time (1984) Michael Dummett published several proofs of a decade-old conjecture now called the Gibbard-Satterthwaite theorem which is about voting algorithms used to select one winner from a group of three or more candidates based on voters' preferences. To paraphrase, the theorem states that for any reasonable scenario (where, e.g., there are no blacklisted candidates and the winner is not chosen by a single dictator) there is no deterministic algorithm that will prevent even a single tactical voter from influencing the results of the election. Sound familiar?

There is a more well-known, but in some ways less interesting, result in social choice called Arrow's Impossibility Theorem that has a lot in common with the G-S theorem discussed above. Dr. Kenneth Arrow received the Nobel Prize in Economics for his work related to this theorem in 1972. Professor Nancy Lynch received the Knuth Prize in 2007, in part for her seminal work on the impossibility proof for Byzantine Agreement. Yet, as near as I can tell, neither discipline has cited the other in all these years, despite the striking similarities of the problems and results and the huge amount of research activity associated with the two independent fields.

Don't get me wrong. I'm not saying these two canonical problems are identical, or even that there is a common underlying body of theory (though I believe there very well might me). But even the differences in the problem statements are illuminating and may indicate areas for further research in one field or the other. For example, the BA problem statement requires every non-faulty process be able to independently compute and verify the agreed upon value. There is no central authority to tabulate votes in BA, whereas in SC, it is typically assumed the independent voters submit their preferences which are then tallied in one place by a trusted central authority. But would it be a useful requirement for each voter in a SC scenario to be able to independently verify the results of an election? I believe this could be the basis of a reasonable formal definition of election transparency, a very useful property of real elections.

There are also areas where the typical formulations of SC problems are actually more stringent than BA. Remember the validity requirement for BA is, if every non-faulty process begins with the exact same initial value, then the algorithm must choose that value. If even one good process has a different value, then a correct BA algorithm is free to choose any value at all, as long as everyone agrees with it in the end. For SC, however, we must agree to elect a candidate based on more flexible requirements. An alternative validity rule might be, if a plurality of non-faulty processes have the same preferred value, the algorithm must choose that value. Or more generally, the algorithm must choose the winning candidate such that voters are the least unhappy about the result. This suggests some interesting extensions to the BA problem, such as Synchronous Byzantine Plurality.  I have no idea whether that problem has been studied or results reported in the literature, but reasoning by analogy (always a tricky thing to do) with the Gibbard-Satterthwait theorem, I would guess that synchronous BA with a plurality rather than unanimity constraint would be impossible in a deterministic way.

Despite all the interesting complexities with these two fields of study, one can definitively say that no completely robust solution to either BA or SC is possible without randomness. Faulty and/or malicious participants can always overwhelm honest participants to influence agreements and elections.  Without a coin to flip, there is no safe way for independent entities to reach consensus!

Voting Variants - Harmonic Range Voting

Although Ethosphere could implement many different voting procedures and allow a teamspace to choose from among them, there is a method which is a combination of IRV and RV that seems well-suited to the online venue. We will call the method Harmonic Range Voting (HRV). The word "harmonic" is borrowed from mathematics -- it is the name of the arithmetic series 1 + 1/2 + 1/3 + 1/4 +... whose connection with the algorithm will become apparent. First, let's see how the procedure works.

The HRV ballot closely resembles the IRV ballot. It is a list of candidates in rank order, with the first choice candidate at the top. The list is divided by a dotted line. Any candidates listed below the line are considered to be either not suitable or of unknown merit. Candidates above the line are all deemed suitable, and their position on the list reveals their relative desirability in the opinion of the voter. This sort of ballot ranking is easy to implement as a drag-and-drop interface, and it transitions nicely from single-choice to multi-choice elections, and more generally, handles additional alternate props well. For a single-choice election, a yea vote is equivalent to placing the prop above the line while a nay is like placing it below the line. New alternate props are initially placed below the line, allowing the voter to consider them and, if desired, drag them above the line into their proper ranking.

Although this is essentially a ranked voting method, like IRV, the method of calculating a winner is more like RV. We assign the first place candidate a score of 100. Second place votes are only 1/2 as potent as first place votes, so they are given a score of 50. Third place votes are 1/3 as potent as first place votes, they get a score of 33.333.., and so on. Thus the harmonic series. From a mathematical and theoretical point of view, this is just RV with discrete ranges based on rank. But it does eliminate, or at least reduce, two of the drawbacks of RV mentioned above. First, it is not necessary to choose a subjective merit score for candidates. You just need to decide which one you like best, which one second best, etc. Also, the paradox of electing a candidate that receives no first place votes is avoided, even in degenerate cases like the one outlined in the previous post. The harmonic series ensures no candidate can win unless it has at least a few (>2) first place votes. Similarly, no candidate can be elected strictly on the basis of third place votes unless there are at least a few first or second place votes for that candidate.

Protection of Minorities

The goal of Ethosphere is to encourage larger, more vibrant teamspaces over smaller, fragmented, stagnant ones. An effective, but undesirable, way to reach consensus is to eject all members who don't agree with the majority, or make them unhappy enough so they leave on their own, perhaps to start smaller, more cohesive teamspaces. Such balkanization of teamspaces works against the overall utility of the Ethosphere and, in the limit, results in single-member teamspaces that are pointless and completely without influence. Therefore, we wish to select voting and consensus mechanisms that do not needlessly alienate the losing supporters of a contentious vote or series of votes. Rather, we want the procedure itself to help lead the team toward a kernel of consensus that maximizes the "happiness" of all the members while still allowing props that have significant majority support to be ratified.

The HRV procedure is one way in which this may be accomplished. By blending together IRV, which favors extremist candidates, and RV, which strongly favors centrist props, we have a voting algorithm that admits compromise solutions, but only when they are needed, like when the leading choices are strongly polarized and balanced.

Voting Variants - Range Voting

Range Voting (RV) and its variants, including Approval Voting (AV) and Score Voting (SV), asks voters to rate each candidate independently within a given range or scale, like one to five or zero to ten, or for AV, 0 or 1. RV ballots are more expressive than either IRV or plurality, allowing members to express rather complex opinions. For example, I might want to say something like, candidate A is my slight preference, and either B or C would be okay with me, but D would be a total disaster in my opinion. On a scale of 0 to 100, I might assign candidate A a 100, B and C an 80, and D a zero. There is no requirement that the scores need to add to anything, or even that every candidate receives a score at all.

Calculating the winner of an RV election is straightforward. One simply adds the scores for each candidate across all voters. The candidate with the highest score percentage wins.

Pros and Cons

RV in the form of "star voting" has been used a lot recently on the Internet for things like rating movies (Netflix) or buyers and sellers (eBay). Reality TV uses RV when a show allows the same caller to vote multiple times for a candidate; the score for each candidate is just the number of votes it receives. It does not have as much of a track record in the political arena as either plurality or IRV. Like everything else, it is still vulnerable to strategic voters who know or think they can predict partial results about the election before they cast their votes.

From a technical viewpoint, RV does somewhat better against the standard criteria used by experts to judge voting procedures. It is both "consistent" and "summable," for example. Unlike IRV, it fails the "majority" criteria in that it does not always elect a candidate that clearly has a majority of first place votes. On the other hand, the concept of first place vote in RV is somewhat ambiguous, since you may assign your favorite a 100 and your second favorite a 10, while someone else says their second favorite is a 90, indicating there's not much difference between the two. In this example, there's a strong and a weak first place vote. Due to the simpliciy of the vote counting procedure, RV is also more transparent than IRV.

There is a practical drawback of RV that could be very important in the context of the Ethosphere. Many people have a hard time assigning a numerical value to something as subjective as the fitness of a given candidate. I know when a doctor asks me to rate my pain on a scale of 1 to 10 I often choose to respond with a verbal assault instead of a thoughtful opinion. This difficulty can result in some voters assigning 100 to their favorite candidate and not bothering to rate the others. This tactic, of course, degrades to simple plurality voting if enough members choose to adopt it.

Unlike plurality and IRV, RV tends to favor the centrist candidates a little more. Take an example similar to the one discussed in the IRV post. Candidate A receives a score of 100 from 51% of the voters while candidate C receives a score of 100 from only 49%. Both "parties" are comfortable with the centrist candidate, B, so it receives a score of 80 from all voters. In this case, RV will elect B, the compromise candidate. RV supporters claim this is a good thing because it minimizes a metric called "bayesian regret," a measure of how unhappy the teamspace as a whole will be with this outcome. In simple terms, it means the RV result produces the least unhappiness amongst the group. On the other hand, it should be pointed out that the winner ended up being a candidate that was nobody's first choice.

I'm Not Elitist, Just Better Than You

For ease of exposition, my discussions of voting methods often make a very common assumption, that every member has exactly one ballot and that all first place votes, for example, have the same voting power for every member. The One Member, One Vote (OMOV) principle does not hold in the Ethosphere, however. Instead, a member's influence in an election is proportional to its reputation within the teamspace. This may initially seem unfair, undemocratic, or even elitist. Here's where I argue it is none of those things. In fact, this merit-based system of vote apportionment is more fair, more democratic, and less elitist than many existing electoral systems in place today, and certainly those used within the U.S.

The U.S. constitution, which generally does not dictate voting methods for representatives, senators, or any other office, does in fact spell out a rather strange method to be used to elect the country's president and vice-president. The electoral college has not scaled well as the country has grown, and today it is legitimately maligned as being, well, unfair, undemocratic, and elitist. Why did the founders, who were otherwise so prescient and wise, spell out this terrible electoral procedure for what is arguably the most important office in the new country? The answer to this question, like so many similar ones about why the constitution was written the way it was, can be found in a series of props published by a highly reputable, pseudonymous author whose alias was @publius.

In The Federalist #68, @publius explains why the framers thought a few, reputable individuals would be better suited to electing the president than the entire electorate via direct vote.

A small number of persons, selected by their fellow-citizens from the general mass, will be most likely to possess the information and discernment requisite to so complicated an investigation.

In fact, the founders' important distinction between a republic and a democracy was based, at least in part, on the desire to ensure that important views and decisions of the general population are refined and enlarged...

...by passing them through the medium of a chosen body of citizens, whose wisdom may best discern the true interest of their country, and whose patriotism and love of justice will be least likely to sacrifice it to temporary or partial considerations.

-- The Federalist #10

But this idea of choosing electors and representatives whose decision-making power far exceeds an ordinary citizen, even a well-informed and highly-involved one, hasn't worked out all that well in many cases. In the last presidential election, who was the elector from your district? What were her qualifications? Did you help choose her, or was that done by the party machinery? Are you the least bit confident that her "patriotism and love of justice" were sufficient to warrant the trust you placed in her?

The founders were right in that the balance between ethical, expert representation and direct participation is an important one, and a difficult one to get right. Too far in the latter direction and you end up with "confusion of the multitude," as @publius called it. Too far in the former direction and you get tyranny.

In the Ethosphere this balance is struck using member reputation. Members who have proven to the team they are capable of participating constructively have greater reps, and therefore their votes count more than others'. Everyone participates, but stability and fidelity of the teamspace as a whole is more certain, as it is guided by those who are knowledgeable and who may best discern the true interest of the teamspace. Yes, some members' votes count more than others, just as in the electoral college and other representational elections of the U.S. The difference is, the apportionment of voting power in the Ethosphere happens continuously and organically as a result of day-to-day interactions. A member's rep has nothing to do with its user's success or fame in the real world, or in any other context (teamspace) for that matter. Voting power is not influenced by one's race, family name, bank balance, religion, or party affiliation -- only by the pseudonymous member's reputation within that teamspace.

I believe Alexander Hamilton, John Jay, and James Madison understood the wisdom of merit-based reputation and anonymous attribution when, writing as @publius for a few months starting in the Winter of 1787, they convinced the people of New York to ratify the U.S. Constitution. And I believe the deeper question they sought to examine in those articles is still being pondered.

It has been frequently remarked, that it seems to have been reserved to the people of this country, by their conduct and example, to decide the important question, whether societies of men are really capable or not, of establishing good government from reflection and choice, or whether they are forever destined to depend, for their political constitutions, on accident and force.

-- The Federalist #1

Voting Variants - Instant Runoff Voting

A great deal of interesting work and research has gone into the study of voting procedures over the years. There are many different ways to vote and to tally those votes. I will try to summarize the high points of several of these voting methods in this and subsequent posts. Remember that all these boil down to the same thing for simple, single-choice votes, so the differences between algorithms only matter for multi-choice elections.

Instant Runoff Voting (IRV) and its variants, including Single Transferable Vote (STV), require a voter to rank the multiple candidates in preference order. The Ethosphere GUI can facilitate that kind of voting using a simple drag-and-drop interface, allowing a member to arrange all the candidates in the desired order, favorite on top. It is not necessary that each member rank all candidates, allowing for the possibility that new alternate props can be added after the member has already voted.

Calculating the winner of an IRV election is somewhat complicated and, if done by hand, time consuming. In Ethosphere of course, it will be done by computers so this isn't much of an issue (but see the transparency discussion in Pros and Cons below). Basically, it works like this. First, the first place votes are tallied for each candidate. If one of the candidates has enough first place votes to exceed a defined threshold, say 51% simple majority, that candidate is declared the winner in the first round and the election is over. However, if no candidate receives a majority of votes, no clear winner can be declared and the race goes to a runoff election. Rather than going to the trouble and expense of conducting a second election, we use the ranking information on the original ballot to break the tie (hence the name, instant runoff). First, the candidate who had the lowest number of first place votes is eliminated, and the ballots of all members who voted for it are re-examined. For just those ballots, we take the second place choices and add them to the first place totals of the remaining candidates. This process is repeated until one of the candidates has the required majority.

Pros and Cons

IRV has a reasonable track record of use in practical, political elections throughout the world. Australia and Ireland have both used this method for many years. Many U.S. states and local governments use IRV for local or specialized elections. The Academy Awards for motion pictures also uses it. (Coincidentally, the Oscars are being broadcast tonight.) The practical, real world results from these various experiments have been mixed. It is undoubtedly better than plurality voting, but it's still vulnerable to strategic voting, of course. Duverger's Law, which says that plurality voting systems will always, eventually result in a two-party division of candidates, does not seem to apply to IRV, although in several real world cases it has resulted in just two viable political parties emerging.

Of the dozen or so standard criteria by which experts typically judge voting systems, IRV fails a couple of them, sometimes leading to unexpected, and unwanted behaviors. For example, IRV is not "consistent," meaning that if the membership is divided into two parts and votes counted separately, even if the same candidate wins in both sub-elections it may not be the winner when the votes are combined together. A different but related drawback is that IRV is not "summable," meaning it is not tractable to count votes in a sub-group, say a precinct, and pass the totals up to be combined at a central election office or some higher tier.

Like plurality voting, IRV tends to favor the more extreme candidates over the more moderate ones. Suppose there is an IRV election where candidate A has 51% and candidate C has 49% of the first place votes, but candidate B, the moderate candidate, has 80% of the second place votes. In other words, most of those members who favor candidate A and most of those who favor candidate B would all be okay with candidate B if it came to that. IRV would still declare A as the winner in the first round. In this admittedly contrived example, nearly half the members would be very unhappy with the result, having lost to their least favorite candidate by only a small margin. In Ethosphere, more so than real life, it is easy for unhappy members of a teamspace to secede and form their own teamspace. Of course, this tendency is undesirable and counter to one of the important goals of the system.

An equally serious practical drawback for this method is its subjective impact on transparency of an election. Explaining why a particular candidate prop won an election is somewhat difficult if there were two or three, or more, rounds of instant runoff required. Imagine explaining that candidate A won because, "More members ranked candidate A as their third choice and candidates X or Y as first or second, and candidates X and Y received the fewest first and second place votes."

Attack!

There are many trust and reputation systems on the Internet today, and some are more robust than others in protecting themselves from ill-intentioned users. There is already some research available on robustness of reputation systems and the types of attacks they must defend against. Another goal of the rep system in the Ethosphere is to thwart most of the more common shenanigans that nefarious users can inflict. Here are a few of the infamous ones.

Sybil Attacks

Named after the (largely fictional) book by Flora Rheta Schreibe (1973) about a woman suffering from multiple personality disorder, this exploit is carried out by having a single user create many, perhaps thousands of, different aliases within the Ethosphere. In fact, multiple personality disorder is an advantage here, allowing a single user to diversify his personality and identity in order to function efficiently in diverse, unrelated teamspaces. It is the idea of reputation in the Ethosphere that helps ensure this beneficial feature does not lead to chaos and instability.

Although it is free and easy to create new aliases, each alias begins life with a rep of zero. Any influence exerted by such a "newbie" alias is limited to what it can convince other reputable members to do, members with non-zero reps. There is no voting or other numerical advantage in having numerous alises. While it is conceivable for a user to obtain non-zero rep shares for each of many different aliases within a teamspace, having a thousand aliases with reps of 1.0 each is no better than having one alias with a 1,000 rep share.

Collusion

A coordinated effort by many teamspace members, especially if they are owned by the same user (see above), might be used to unfairly influence voting and decision making. However, it wouldn't really be unfair unless such collusion could be used to artificially inflate the reputation of some or all the colluding members. The Ethosphere is designed to avoid all such possibilities by ensuring that rep shares cannot be granted from one member to another without some equivalent cost to the granting members. In all cases where a recommendation or accommodation from member @foo can cause an increase in the rep share of member @bar, such shares are actually transferred from @foo to @bar rather than being created out of nothing. For example, if @foo "likes" a comment made by @bar, a single rep share is transferred from @foo to @bar. This makes it impossible for members to collude to unfairly boost the reps of others.

It is still possible for subjective collusion to occur, where several cooperating members, perhaps belonging to the same user, all write valid but different comments in support of or against some prop. The plurality of support or opposition, rather than the merits of the arguments, might be more convincing to some. However, if there are indeed many different arguments for or against something, perhaps that should be a valid consideration.

Persona Breaks

This exploit is sometimes called a playbook attack. The basic scenario is, a member may behave well and participate constructively for some period of time, building up a high rep share, but then change abruptly with the intent to unethically influence or cause damage to the stability of a teamspace. Of course, this exploit can occur in real life also, either by design or through natural processes. For example, a person of great influence such as a prime minister, president, or CEO can experience a sudden mental break, an emotional crisis, a religious epiphany, or just a simple change of opinion, causing others who have developed a trust relationship to suddenly feel alienated or betrayed. In such cases, our only goal is that Ethosphere be no more vulnerable than real life.

There are other potential causes of reputational discontinuity in Ethosphere that we do attempt to address. For example, logins can be hijacked and passwords can be lost or stolen, enabling someone else to pretend to own an alias. It is even conceivable that valuable, high-rep aliases may be sold or traded in real life, causing an ownership change and, perhaps, a persona break. To protect against these kinds of exploits, Ethosphere allows members of a teamspace to challenge an alias in two different ways, if they become suspicious of a break. First, members can perform an action known as a auth challenge, which will cause the framework to require the user of an alias to re-enter her password and re-authenticate her identity. In more extreme cases, the members of a teamspace may see fit to perform an ID challenge for a "misbehaving" alias. An ID challenge will cause the framework to validate the user's email address before he can continue.

Re-Entry

Reputation systems that allow negative scores are vulnerable to re-entry exploits where a low-scoring entity simply leaves the system and re-invents itself as a new alias. The Ethosphere avoids this by starting all new aliases entering a teamspace with a zero rep and not allowing the rep to ever be negative. A zero rep means the alias has no numerical influence whatsoever within that teamspace. Although there are some punitive reputational transactions that can decrease one's rep, such punishment cannot accumulate beyond the zero point.

Denial of Service (DoS) Attacks

DoS exploits are notoriously difficult to defend against, and there are many potential ways for evil doers to cause the Ethosphere service to experience slow or even curtailed operation. Protection against one incarnation of this exploit, bots pretending to be aliases, can be provided by using "captchas" in the login process to try to distinguish between human (good) and robotic (bad) users.

Do We Have Consensus?

Voting and consensus are at the heart of the Ethosphere. It will be essential to choose the right voting algorithm(s), focus on transparency, and build and maintain a high level of trust in the consensus mechanics. The goal is that every user will come to trust the system so that, even after losing a contentious vote, there is confidence that the outcome of the procedure was, in fact, a true reflection of the will of the team, taking into account the relative reputations of the members.

This will be a tall order, given how little trust there is in the real life voting procedures and mechanisms currently used to decide issues and elect leaders throughout the world. There are major issues, both technical and political, with these real world systems, many of which Ethosphere has a unique opportunity to remedy given the benefits of its smaller scope, electronic nature, and years of research and thinking about the nuances of social choice.

In particular, the Ethosphere improves upon many other social choice systems in at least four major ways:

1. Voting Algorithms - We will choose a voting method that is less susceptible to strategic/dishonest voting and fairer with respect to minority opinions.
2. Rational Representation - Member reputation provides an excellent opportunity to balance the need for involved, knowledgeable electors with a fully-participatory, direct democracy.
3. Protection of Minorities - The temptation of factions to secede from a teamspace because of a losing, perhaps contentious, vote will usually be outweighed by the benefits of staying with the team.
4. Transparency - Every vote can be examined and audited by any member.

Voting Algorithms

There are basically two types of decisions that will often need to be made in Ethosphere: single choice and multi-choice decisions. A single choice decision asks the question, is this prop acceptable to a majority of the members of a teamspace, where "majority" means reputational majority. A multi-choice decision is involved in choosing from among a number of alternate props.

The single choice, yea/nay votes are the easiest to get right, in so far as the voting algorithm is concerned. Almost any algorithm, including the crusty and hopelessly broken plurality method in use today in the U.S. and many other places, reduces to something that works just fine for single-choice elections.

Multi-choice elections are mathematically and socially more challenging for the voting mechanisms. There is a ton of research and opinion about voting procedures and consensus algorithms, going all the way back to the ancient Greeks and including such luminous names as Plato, Daniel Bernoulli, Daniel Webster, Thomas Jefferson, James Madison, Bertrand Russell, and John von Neumann. Ironically, it seems completely impossible for experts, even professional mathematicians, to reach consensus on what is the best way to reach consensus.

There are literally dozens of different algorithms and hundreds of variations in use today. Rival web sites devoted to one method or another contain pages and pages of calculations, simulation results, and oratory wherein otherwise rational mathematicians and social scientists argue like school girls over who has the cutest boyfriend. But they all seem to agree on one thing: the first-across-the-bar plurality procedure still being used today in many places is one of worst, if not the worst possible choice.

The Ethosphere draws from two of the leading contenders among modern voting procedures: Instant Runoff Voting (IRV) and Range Voting (RV). We will describe each of these briefly in future posts, but if you wish to learn more about them and you don't mind sifting through a whole lot of silly bickering along the way, you should visit www.fairvote.org and www.rangevoting.org which are maintained by the respective advocacy groups.

For both these voting procedures, the ballot is a little different from, and slightly more complicated than, the simple one-chit-for-my-favorite type of ballot we are used to seeing in plurality elections.

Strategic Voting

These voting algorithms are vulnerable to so-called strategic, or dishonest voting whereby, given advanced information about the relative strength of the candidates, a member can sometimes help its preferred candidate more by ranking them in a way that doesn't reflect the member's actual preferences. Obviously, this is an undesirable characteristic, but unfortunately there is a kind of uncertainty principle for voting systems, called Arrow's Impossibility Theorem which essentially says all voting systems are vulnerable to this kind of strategic voting to some degree at least. In other words, voting theory is a branch of game theory. So be it.

Because of this, the Ethosphere should discourage dissemination of information about a vote's partial outcome before it is closed. In fact, it should not be possible for any member to know who has voted, or how, until the vote is finished and the winner is determined. Of course, this doesn't prevent unofficial, but perhaps accurate, polling of members via messaging or email. Those annoying pundits, pollsters, and prognosticators who hover around real-life elections will likely evolve in the Ethosphere as well.

Pull the Curtain and Vote

Voting in Ethosphere (and any other online venue for that matter) must take into account a troublesome but unavoidable fact of Internet life — members/users can lie about who they really are. A senator can pretend to be an ordinary citizen, a law enforcement officer can pretend to be a teenage boy, and a middle-aged, married American man can pretend to be a gay girl in Damascus. Elections in Real Life (RL), especially in the US, require us to pull the curtain, as it were, to carefully obfuscate the connection between a person's true identity, his satnam, and the ballots he casts.

Facebook, among others, is discovering how difficult it is to ensure that user logins are associated with real, authentic people and that each person has only one such login. While other social networks, notably Twitter, allow users to have as many pseudonyms, aliases, as they wish and do not try to enforce authenticity with RL identities. There are advantages and disadvantages to each approach. Apart from the technical impracticality of verifying users' true identities, there are some unexpected bonuses in allowing members to assume an alias, or many aliases, that can never, as a matter of principle, be traced back to the owner's true name.

But the only way to be able to maintain a trust relationship, including consensus building and voting, with such pseudonymous members is to associate and maintain a reputation of some sort for each persona. The Ethosphere does this using a straightforward mechanism. Each member has an associated rep, which is simply a non-negative real number. A member that happens to be a part of more than one teamspace will have a different rep in each space. Upon first joining a new team, a member's rep within that team is initialized to 0.0. Reps cannot be directly manipulated, but they can be bumped (increased) or busted (decreased) as a result of certain activities within a teamspace. In general terms, a member's rep increases as a side-effect of constructive participation within the teamspace.

The degree of influence a given member has within a teamspace is directly proportional to its rep. To be precise, when a member casts a vote for a prop within a teamspace, her vote counts only so much as her current rep within that teamspace. Older, established members contribute stability and robustness to the society, but nothing prevents new members from building up their own reps and, eventually, exerting their own guidance and influence. Ethosphere is a pure meritocracy.

By allowing pseudonyms with their associated reps (let's call those pairs personae), and diligently protecting the connection between a persona and a real life identity, we have effectively moved the curtain. Online elections can now be completely transparent, publishing exactly which persona voted for which prop, fostering trust in the electoral machinery and the voting algorithms. But at the same time, nobody will ever know that, for example, Jim Dutton voted yea or nay on a given prop. As with Twitter aliases, members will feel freer to express themselves and their opinions without fear of reprisals or embarrassment from their RL friends and families. Unlike Twitter, Ethosphere personae are more likely to show restraint and consideration in their teamspaces to preserve and improve their reps, and thus their future influence.