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.

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!

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.