tag:blogger.com,1999:blog-10393738777699154932024-03-13T17:47:29.926-05:00Distributed Computing and Societal NetworkingExploring collaboration, consensual wisdom, online voting, and the future of virtual societies.Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.comBlogger41125tag:blogger.com,1999:blog-1039373877769915493.post-62609997951562065472014-05-03T16:25:00.002-05:002015-11-14T16:40:18.645-06:00The Divine Random in Mathematics<blockquote><i>I am the rock, you the stone,<br />
Together we ballast reality.<br />
Steady toward uncertain destiny,<br />
Whither the sheets above us are blown.<br />
</i></blockquote>Until fairly recently, 1931 to be exact, scientists and mathematicians believed we would someday find a theory that explains everything. By "theory" I mean a Formal Axiomatic System (FAS). A FAS is simply a relatively small set of given facts, axioms, from which a much larger set of <i>theorems</i> can be proven "by mechanical means." The axioms in a FAS are so basic that we believe them to be true without the need for further justification. A famous and straightforward example of a FAS is the small set of axioms provided by Giuseppe Peano at the end of the 19th century to formally define the natural numbers. The <a href="http://www.encyclopediaofmath.org/index.php/Peano_axioms">Peano axioms</a>, in English, are as follows:<br />
<ol><li>The natural numbers contain the number 1.</li>
<li>Every natural number has a successor, the next natural number.</li>
<li>The number 1 is not the successor of any natural number.</li>
<li>Two different natural numbers cannot have the same successor.</li>
<li>If a set contains the successors of each of its members and the number 1, then it contains all the natural numbers.</li>
</ol><p>From this small set of seemingly obvious "facts" and using the mechanical rules of logic, all of number theory can be derived. Addition, multiplication, prime numbers, prime decomposition and the Fundamental Theorem of Arithmetic, are all consequences of the five Peano Axioms listed above. Or, to look at it the other way round, the Peano Axioms constitute a very efficient compression of the entire body of number theory.<br />
<p>And that is how mathematics works. Every branch of it — geometry, algebra, analysis, etc. — can be boiled down to a similar compression of a very large body of theorems into a relatively small set of axioms. Unlike other sciences such as physics, biology, chemistry, or computation, mathematics is unconstrained by the laws of the universe in which we find ourselves living. It is purely an invention of man, limited only by our evolving intellect. We invented the game and control the rules. Surely, there are no fundamental reasons why we couldn't develop a mathematical Theory of Everything (ToE), a FAS from whose axioms one can derive by mechanical means all that is true.<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: center; margin-bottom: 1em; margin-right: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDECQD258GLLgQlIUpu7qfYxC1rfa2erN1IP0MJDAsMOHPAUo0kYe4ylTUALfDCdwwq711xfIJKNgxe4m2AaebYRuiKSZ2GC97S7zYGyawYs4BNww2_WQJ158Yc6QMxPgjGwXNQZ_Yhyphenhyphenk/s1600/Einstein-Godel.jpg" /><br />
</td></tr>
<tr><td class="tr-caption" style="text-align: center;">Albert Einstein and Kurt Gödel</td></tr>
</tbody></table>That is what pretty much every mathematician believed until 1931 when a 25 year-old Austrian post-doc named Kurt Gödel shocked everyone by proving that mathematics, that wholly man-made "queen of sciences," suffers from the same kind of fundamental limitation <a href="http://www.consensualwisdom.com/2013/08/the-divine-random-in-physics.html">Heisenberg had discovered in physics</a> five years earlier and <a href="http://www.consensualwisdom.com/2013/12/the-divine-random-in-computing.html">Turing would find for computation</a> five years later. Gödel's meta-theorem proved there is a shoreline beyond which vast shoals of truth exist that the lighthouse of pure mathematics cannot illuminate.<br />
<p>More specifically (and much less metaphorically), Gödel showed that for any FAS that is at least as rich as the Peano Axioms described above, and for which the axioms are not self-contradictory, there will be theorems expressible in the language of the FAS that are true, but un-provable from the axioms. That is, any consistent FAS is necessarily incomplete. Pure mathematics is not sufficient to account for a ToE. Truth, with a capital T, is incompressible. There will always be a theorem, perhaps infinitely many, whose shortest expression is the theorem itself. The only way to prove such theorems is to add them to the set of axioms!<br />
<p>Like other impossibility meta-theorems, e.g., Heisenberg's Uncertainty Principle in physics and Turing's Undecidability result in computing, Gödel's Incompleteness Theorem identifies a fundamental limit on our ability to know things, in this case using the tools of mathematics. As we have seen for physics and computing, beyond these boundaries lies randomness, and the same appears to be true for math as well. Our simple working definition of randomness, that it be universally unpredictable, can be made more precise in the realm of mathematics. Namely, something is mathematically random if there exists no FAS (with a finite set of axioms) from which it can be derived. A random number, in particular, is a number whose digits cannot be predicted within the framework of mathematics. Such a number is irreducible — the shortest possible way to express one is to write down all its (infinitely many) digits. If we can agree that a <i>name</i> for something is just a finite sequence of symbols that represent it, these numbers are necessarily <i>nameless</i>. Even numbers like <b>π</b> and <b>e</b>, which are transcendental, their digits never repeat, have <i>names</i> — <b>π</b> and <b>e</b> are the names we have given to two specific infinite real numbers that can be computed in two very specific, and finite, ways. Mathematically random (aka irreducible) numbers are even weirder than transcendentals. So weird that it becomes reasonable to ask, do such numbers actually exist, and if so, can you show me one?<br />
<p>It's actually pretty easy to see that irreducible numbers, numbers that cannot be derived within any FAS, do indeed exist. However complex pure mathematics may become, it must eventually have a finite set of axioms from which all theorems, including those showing the existence of certain numbers, can be mechanically proved. A finite set of axioms can be used to derive an infinite set of theorems, just like a finite alphabet can generate an infinite set of names. But in both cases, the infinity of derivations is a <i>countable</i> infinity — there are only as many of them as there are integers. On the other hand, there is an uncountably infinite number of real numbers, which is a bigger infinity. So if you match up numbers to name/theorems, you will always have more of the former than the latter. In other words, there must be an (uncountably) infinite number of irreducible numbers. This is a so-called <i>diagonalization</i> argument that can be made formally rigorous, but is never very satisfying. What we'd really like to do is hold one of these odd beasts in our hands and examine it up close.<br />
<p>One obvious way to generate such a number is to appeal back to physics. We could simply flip a fair coin and write 0 for heads or 1 for tails, and continue doing that to generate as many bits as desired. Assuming we trust the fairness of our fair coin, the bits (digits) of such a number would be universally unpredictable — every bit is a completely separate "fact" and there is no shorter description of how to obtain them other than the number itself. But is there a way to do this while staying within the confines of pure math?<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-bottom: 1em; margin-right: 1em; text-align: right;"><tbody>
<tr><td style="text-align: left;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJ4Swag3F3iJ7a4L5ujRk3048cYxJG1S-Ut8j0jFBGmTM9UIdjyyVUegoo8yP-W35nfsv7CZBEKtWksmjrO3PCQ0PObIbxJ38_ywJ8TanpagYgf_95mC_GLup7UwpJMHs39L1yY_-F7us/s200/Omega.jpg" /><br />
</td></tr>
</tbody></table>Around the time The Beatles brought bangs to America, in 1966, <a href="https://ufrj.academia.edu/GregoryChaitin">Dr. Gregory Chaitin</a> found an answer to this question when he discovered what he called the <a href="http://plus.maths.org/content/omega-and-why-maths-has-no-toes">Omega Numbers</a>. Each <b>Ω</b> (there are infinitely many) is <i>definable</i> but completely <i>irreducible</i>. Like <b>π</b> and <b>e</b>, <b>Ω</b> is a transcendental number, but unlike it's more well-behaved cousins, <b>Ω</b> cannot be computed by any algorithm. The smallest possible expression of its digits are the digits themselves. Furthermore, those digits are normally distributed — every digit appears approximately the same number of times — no matter what base (decimal, octal, binary, hexadecimal, etc.) one might choose to represent it. <b>Ω</b> is mathematically random. To me, the most fascinating thing about <b>Ω</b> is that it sits at the nexus of Gödel's incompleteness and Turing's undecidability, telling us that the oceans of randomness beyond mathematics and computing are, in fact, one and the same — the Divine Random.<br />
<p>Chaitin defines <b>Ω</b> using the terminology and formalism of Turing (which, if you'll recall, is still within the realm of pure mathematics) by first choosing a suitable formal programming language and initializing an estimate of <b>Ω</b> to zero. For Chaitin's purposes, this means the language must be <a href="http://en.wikipedia.org/wiki/Prefix_code">prefix-free</a> so that programs are self-delimited. We then enumerate every possible string in the language. For each string we ask, a) is the string a syntactically correct program with input data appended, and b) does that program halt when supplied with the input data? If the answers to both a) and b) are Yes, we add the following quantity to our estimate: 1/2<sup>|p|</sup>, where |p| is the number of bits required to represent the program in the chosen language. If not, we just continue combing through all possible strings looking for legal, halting programs.<br />
<p>Does such a procedure produce a well-defined number? Absolutely! It is surely possible to lexically enumerate all possible strings, every string is either a legal program+data or not, and every legal program+data either halts or it doesn't. In fact, Chaitin showed that the resulting number, <b>Ω</b>, is a real number between 0 and 1. The catch, of course, is that it is impossible to compute such a number because, as Turing proved, it isn't possible to compute the answer to the halting problem in full generality. In a certain sense, each bit of <b>Ω</b> is chosen by flipping a mathematical coin — heads the program halts, tails it doesn't — whose outcome is universally unpredictable and uncomputable.<br />
<p>So what does it look like, you must be asking? Well, I can't say. As with other objects we have encountered floating in the sea of randomness, <b>Ω</b> can be seen only by its faint, hazy outline. We can begin to estimate <b>Ω</b> but we can never know more than a finite number of its digits. Moreover, it is impossible to compute how accurate our estimate is, how close or far away it is to the actual number. <b>Ω</b> will always remain fuzzy, its properties uncertain beyond some degree of magnification, much like the properties of physical objects governed by Heisenberg's Uncertainty Principle. Chaitin put it best in his excellent and accessible little monograph <a href="http://www.amazon.com/Meta-Math-Quest-Omega-Vintage-ebook/dp/B001M5JVM0/ref=sr_1_1?s=books&ie=UTF8&qid=1399148500&sr=1-1&keywords=gregory+chaitin"><i>Meta Math! The Quest for Omega</i></a>:<blockquote><i>So fixing randomness in your mind is like trying to stare at something without blinking and without moving your eyes. If you do that, the scene starts to disappear in pieces from your visual field.<br />
<br />
The harder you stare at randomness, the less you see of it!<br />
</i></blockquote>Even if we can't know exactly what it looks like, the very existence of <b>Ω</b> proves, or at least strongly suggests, Gödel's incompleteness meta-theorem. There are indeed theorems, and numbers, that cannot be compressed, that cannot be derived by any effective procedure from a smaller set of axioms. And we know that mathematics is limited in this way because Turing showed us there are limits to what any effective procedure, aka computer program, aka Finite Axiomatic System, can accomplish. No matter how clever we humans are or will become, there are barriers to our knowledge that cannot be scaled. Tantalizingly, the answers are out there, floating around as random numbers. <b>Ω</b>, for example, solves the halting problem for every possible program. And it exists; it's out there, we just aren't allowed to see it. Similarly, there exists a random number whose binary bits answer every conceivable yes/no question that can be posed in a given language, including questions like, "Is <a href="http://en.wikipedia.org/wiki/Goldbach's_conjecture">Goldbach's conjecture</a> true?" Science can't give us all those answers. Physics, mathematics, and computation theory are well-honed tools, but they cannot carve all the universe.<br />
<p>We are now approaching the point at which you might begin to understand why I call it, The Divine Random.<br />
Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-74081972480891582202014-02-17T18:12:00.000-06:002014-02-18T16:59:15.110-06:00CreationThis chapter concerns the second time I created something smarter than me. The first such occasion, the birth of my only son, was not entirely my doing as my wife had a rather significant contribution too. But the second creation was all mine. It was a computer program that played the strategy board game <a href="http://www.mathsisfun.com/games/reversi.html">Othello, also known as Reversi</a>. (Note, the link provided leads to a different implementation of the game.) I wrote it as a semester project while doing research at the Artificial Intelligence Laboratory at the University of Texas at Austin.<br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: center; margin-bottom: 1em; margin-right: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" src="http://innovationmanagement.se/wp-content/uploads/2012/02/five-examples-of-co-creation.jpg" /><br />
</td></tr>
</tbody></table>I did this because back then, and still today, I was interested in finding answers to some deep questions about the nature of creativity and the creative process. Where do new ideas come from? What makes an idea clever? Imaginative? Inventive? How do humans create new things and can we program computers to do it too? And most generally, how does the Universe create order out of chaos?<br />
<p>It is clear that new ideas are not just mechanically derived from old ones, at least not the really good new ideas. There is usually a spark, a creative aha moment during which something completely new is dredged up from a place where few of us ever go. Ideas can be encoded as (possibly infinite) numbers, and we know (see <a href="http://www.consensualwisdom.com/2013/12/the-divine-random-in-computing.html">The Divine Random in Computing</a>) that not all numbers can be computed by any effective procedure. That means there are infinitely many new ideas, most of them in fact, that cannot possibly be derived from what we already know. One must assume that at least some of these infinitely many ideas are good ones. A good truly random number generator will, eventually, produce all possible numbers, including quite a few that encode good ideas. So there we have an answer to our questions: just wait around for the next good idea to come around on the random number generator. As we'll see in a later chapter, it can be shown that a random number exists that encodes the correct answers to all possible yes/no questions expressible in a given language. A single number that contains the answers to all our questions certainly seems to qualify as a good idea.<br />
<p>Of course, that's not very practical. The probability of our random number generator producing the answer to everything, or even a single good idea, in our lifetimes is minuscule, to say the least. And besides, we probably wouldn't recognize a good idea if it presented itself at our front door and brought nachos. It would be like working on a jigsaw puzzle, picking up a random piece and declaring, "Eureka! I've discovered something wonderful." A jigsaw piece or an idea isn't a great find unless it fits within the existing framework we have already constructed and understand. The greatest ideas are not just the ones that are unexpected and fresh, but also the ones that are most tightly constrained, by the rules of mathematics, art, language, etc. But randomness must play a role in the creative process. The close proximity between madness and creativity, genius and weirdness, eccentricity and insanity, has long been known and commented upon by philosophers and humorists through the ages. Genius, it seems, is the exact right admixture of crazy and constraint.<br />
<p>With all those general ideas about creativity, I set out to build a computer program that could surprise me by having a good idea, one that I myself had not built into its code. I chose to write a program that played Othello for several reasons — the rules are simple, the game is easy to play but non-trivial, and perhaps most importantly, I wasn't very good at it. Most of the Othello program consisted of my own implementations of several well-known game playing algorithms that had been and continue to be used for computer strategy games. At its core was the so-called <a href="http://ai-depot.com/articles/minimax-explained/">mini-max tree search algorithm with alpha-beta pruning</a>. The linked article has a pretty good explanation of what that is. Basically, it's a formalized way to imagine what will happen in the future. If I do this, my opponent will probably do that, after which I can do this other thing, and so on. Because a computer can do those kinds of things really quickly, it can enumerate through all possible legal moves it has to choose from at any point in the game, and through all the legal moves its opponent would have, through many levels of what-ifs. But the decision tree for Othello, like the ones for Chess and Go, is too big for any computer to completely traverse all the way down to the bottom (at which point it can simply ask which of my current moves leads to a win many moves down the road). So the computer stops searching the decision tree at some arbitrarily-chosen depth and simply looks at the resulting board positions asking itself which ones seem to be the most advantageous for it. This last bit is heuristic, of course. It's a guess based on who has how many pieces remaining and how they are distributed about the board. Game programmers call this a <i>static evaluation function</i>.<br />
<p>There are many, many different types of static evaluation functions for the game of Othello, from simple linear combinations of cell contents (0=empty, 1=mine, -1=opponent's), to more sophisticated heuristics based on pattern-matching. I chose a paradigm that looked for a certain fixed set of patterns on the board and weighted those patterns, when they occurred, to produce a simple number that could be compared against other positions. The choice of static evaluation function thus boiled down to a vector of small integers. Choosing the proper weights for the evaluation vector to make the program play well required deep insights into the game's winning strategies; insights I did not have. And despite its look-ahead capability, the quality of the game's play against me was very sensitive to the choice of static evaluation vector — for some vectors I could beat the program nearly every time, while others were more difficult to win against. Using trial and error, I was not able to find a vector that would make the game play consistently better than me, a poor player.<br />
<p>And then the light bulb came on. Why not have the computer play against itself, using different static evaluation vectors (SEVs), and search for the best one? To do this, I coded the following search algorithm. First, I randomly generated several thousand SEVs to form an initial population of alternatives. I let the computer randomly choose two of those SEVs and play a game, one strategy against the other. Each SEV also had a merit score attached to it, and when an individual SEV won a game against an opponent, the program would increment the winner's merit score and decrement the loser's. In this way, the computer would eventually filter through the initial population and find the best strategy found there.<br />
<p>But what if there was a really great idea, a winning strategy, that did not happen to be one of the few thousand initial, random SEVs? I needed to somehow interject new blood, fresh DNA into the gene pool in order to do a more thorough search of the whole space of all SEVs. To do that, I wrote a second process, in addition to the competition process described above, to periodically generate new individuals. But I didn't just pick a random puzzle piece and cry Eureka! Instead I had the computer choose two different individuals, randomly but with a distribution that favored SEVs with higher merit scores, and combine the vectors in a way that borrows from biology. To combine two SEVs, the computer chose a random position along the vector and split both parent vectors at that point. A new child vector was created by choosing the first segment of one of the parents and the second segment of the other parent and then, with small probability, adding or subtracting one from a randomly selected value on the vector. In biology, this is called chromosomal cross-over with mutation. Once a new individual SEV was created in this way, the individual with the lowest merit score in the entire population was "killed off" and replaced with the new offspring, who was then available for further competition and breeding.<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-bottom: 1em; margin-right: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" src="http://www2.estrellamountain.edu/faculty/farabee/biobk/Crossover.gif" /><br />
</td></tr>
</tbody></table>Once the competition and the breeding processes were chugging along, new strategies were being created and the computer played one game after another with itself. I allowed it to run all night, and all day the next day, and all that week, searching for that good idea, that winning strategy that I could not have taught it even if I'd wanted to. Every once in a while, I would interrupt the search to play a game against the current best strategy evolved so far. At first, the randomly-chosen strategies were pretty terrible. After only a few hours, I found I could still beat the computer regularly and with little effort. After a day or two, it became noticeably more difficult to win, and I found I had to concentrate more carefully to avoid the strategic tricks pulled by the computer. After four days, the computer began to win regularly, and after about a week, I found I could no longer win even a single game against the computer program that I myself had created. Now let me assure you, that is a spooky feeling, to be outsmarted by one's own creation. It was definitely a Frankenstein moment for me.<br />
<p>The type of search algorithm I used in the Othello game is known as a <a href="http://en.wikipedia.org/wiki/Genetic_algorithm">genetic algorithm (GA)</a> because it mimics natural selection. GAs typically include most of the elements I've described above: a competition process, a breeding process that uses genetic operators like cross-over and mutation, and a fitness function or merit score. Randomness plays a vital role in the successful operation of any GA, but it isn't just a random search. Applying the fitness function to select competitors and breeding partners ensures the algorithm as a whole behaves as a kind of a algorithmic ratchet, always making progress toward a more fit population. Random variation together with deterministic filtering, survival of the fittest, is the hallmark of GA. Another common characteristic is the distinction between a genome and a phenome. In the Othello example, the genome was the Static Evaluation Vector, which resembles DNA in function. The phenome, the organism itself, is the rest of the game playing machinery — the mini-max tree search with optimizations and the codified rules that prevent the game making illegal moves.<br />
<p>And so you see, evolution exists. It is, as they say nowadays, a thing. I've touched it, implemented it, and watched it create things that surprised me. Evolution is not simply a random number generator, but rather an algorithm that systematically trolls the vast ocean of randomness to make steady progress in the direction of survivability. It is not just a way to create useful new ideas and individuals, it may be the <i>only</i> such algorithm we know of. And so it worries and frustrates me to see results like the recent <a href="http://www.pewforum.org/2013/12/30/publics-views-on-human-evolution/">Pew poll on the Public's View of Human Evolution</a> that suggests more and more people do not believe that biological evolution is a thing.<br />
<p>To be sure, random mutation without the rational, mechanical ratcheting of natural selection would make no progress at all. The probability of producing something useful, or more useful, from such a coin flip process is unimaginably small. But randomness <i>is</i> the seed of creation, the origin of species. It is the essence of humanity and certainty its antithesis. When a man is entirely reduced to numbers, he ceases to be alive.<br />
<p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com2tag:blogger.com,1999:blog-1039373877769915493.post-2051215810643540192013-12-31T16:42:00.000-06:002015-11-14T16:46:33.735-06:00The Divine Random in Computing<blockquote><i>We'll find all its secrets and make them our own;<br />
A yarn to weave and be woven. <br />
We'll choose among the least likely chosen<br />
And build a castle stone by stone.<br />
</i></blockquote><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" height="175" width="330" src="http://technewspedia.com/wp-content/uploads/2012/06/5097_alanturing2-660x350.jpg" /><br />
</td></tr>
<tr><td class="tr-caption" style="text-align: center;">Alan Turing - Superhero</td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Courtesy technewspedia.com)</td></tr>
</tbody></table>Hollywood seems enamored these days with the superhero story. Movies about Thor, Spiderman, and Superman, all have basically the same plot. In his youth, our hero discovers a unique ability, a superpower, which he then uses to save the world from an evil arch-villain in violently dramatic fashion. Later, the very people whose lives he spared begin to fear his superpower and persecute him for his eccentricities. The superhero becomes despondent and, eventually, turns to the only being who has the means to end his suffering — himself.<br />
<p>Of course, there are no superheroes in real life, but there was a man whose biography pretty much mirrors the superhero story — the British mathematician <a href="http://www.biography.com/people/alan-turing-9512017">Alan Turing</a>. Turing discovered his superpower, a genius for mathematical logic and computing, at the age of twenty-four when, as a graduate student, he published a paper entitled, "On Computable Numbers, with an Application to the <i>Entscheidungsproblem</i>.” I'll have more to say about the ideas in this paper later, but suffice to say that Turing's result is one of the most profound triumphs of rationality. Turing took his superpower into World War II and used it to battle the Nazis. He designed a computer called the "Bombe" that he and his team used to crack the German <i>Enigma Code</i>, thus freeing Allied shipping and supply lines from the dreaded U-Boats and saving England from the arch-villain Adolph Hitler.<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" height="240" width="320" src="http://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/Bombe-rebuild.jpg/640px-Bombe-rebuild.jpg" /><br />
</td></tr>
<tr><td class="tr-caption" style="text-align: center;">Replica of Turing's 'Bombe' Code Breaker</td></tr>
<tr><td class="tr-caption" style="text-align: center;">(Courtesy Wikimedia)</td></tr>
</tbody></table>After the war, Turing returned to his studies, published his dissertation, and initially received well-deserved gratitude at home and abroad. Ultimately, as the superhero plot dictates, his fellow citizens became suspicious of Turing's research and perhaps a bit jealous of his intellect. More troubling for Turing, the Brits, whom he had helped rescue from Fascism, were creeped out by his sexual preferences — Turing was gay. The British courts convicted him of gross indecency and sentenced him to a regimen of hormone injections designed to completely suppress his sex drive, not knowing what side-effects that might cause. Turing, a fan of fairy tales like Sleeping Beauty, became depressed, and one morning in 1954 (coincidentally the year of my birth) his housekeeper found him dead with a partially eaten, cyanide-laced apple on his bedside table.<br />
<p>Turing's remarkable 1936 paper defined both the beginning and the end of a new branch of mathematics — computation theory. In the first third of the paper, he formally defined a simple but robust computer now called a Turing Machine (TM). In the second third of the paper he proved that his little machine is <i>universal</i>, that it is capable of performing any computation any other computer can perform. In fact, any machine that can reasonably be called a computer, past or future, laptop or supercomputer, is no more powerful than a simple TM. Modern computers may be and generally are faster in performing some computations, but however elaborate they may be, a TM can accomplish the same thing, eventually. Turing's goal in this was to find an intuitive but formal definition of the phrase "by mechanical means," a phrase that is used quite a lot in mathematics and science.<br />
<p>If Turing had stopped and published the first two thirds of his paper, it would still have been an incredible achievement. It provides us with a universally applicable, easy to understand definition of what we mean by the word "algorithm", an orderly, step-by-step, procedure for doing something like verifying the proof of a mathematical theorem. Turing conjectured that we mean a computer program, specifically a Turing Machine, and today most mathematicians agree with his conjecture. Any effective method for doing something, any method that does not require ingenuity or creativity, exists if and only if there is a TM whose steps encode that method. That's an amazingly general concept which is widely known as the <a href="http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis">Church-Turing Thesis</a> (Church was Turing's teacher, among many other accomplishments).<br />
<p>But Turing didn't stop after <i>just</i> defining what computation means in a formal sense. The final section of his paper went on to prove there are problems, infinitely many of them, that are not soluble by any TM, and therefore no deterministic procedure exists for finding all the answers. In particular, he proved there are infinitely many real numbers whose digits cannot be computed by any TM, or by any mechanical means whatsoever. I wish I could give you a concrete example of such an uncomputable number, but I cannot, and no one can. Turing proved they are out there, but to provide a finite recipe for producing one of them is fundamentally impossible! It turns out to be quite difficult to identify individual objects floating in the sea of randomness, and when we do find them they're often fuzzy and difficult to crisply discern.<br />
<p>Though we are unable to provide a recipe to produce all the digits of any given uncomputable number, Turing did define a specific problem that he proved could not be solved by any algorithm — the <a href="http://en.wikipedia.org/wiki/Halting_problem">Halting Problem</a>. Is it possible to write a compiler that, given the source code and input data of any other program, will tell us whether the program will ever halt on that input data? The answer is, no such program can possibly exist because it would lead to a logical paradox akin to the "everything I say is a lie" conundrum. Much has already been written about the halting problem, so I won't dwell on it here. It will, however, come up again when we talk about randomness in mathematics.<br />
<p>Our working, <a href="http://www.consensualwisdom.com/2013/08/the-divine-random-in-physics.html">informal definition of a random number</a> is any number that is (i.e. whose digits are) universally unpredictable. We've seen that nature provides copious examples of quantities whose measures at the nano-scale are random in this sense. Turing's result shows there are numbers that cannot be computed by any finite algorithm and the Church-Turing Thesis allows us to extend that to mean such numbers cannot be produced by any effective procedure whatsoever. In other words, the shortest, most compact way to describe such a number is to simply list all its digits!<br />
<p>Now you may think these unnameable, unspeakable numbers are rare and difficult to find, and you'd be half right about that. But they are most assuredly not rare. In fact, if you threw a very, very sharp dart and hit the real number line, the probability of hitting such an unnameable number is 1. There is a countably infinite number of nameable numbers, but an uncountably infinite number of unnameable ones. <a href="http://en.wikipedia.org/wiki/Gregory_Chaitin">Gregory Chaitin</a>, an American mathematician and computing theorist whom we will talk more about in the chapter on randomness in mathematics, has a name for these real numbers whose shortest possible exact descriptions are the numbers themselves. He calls them <i>algorithmically random</i>, but admits the concept may actually be the best definition of randomness in all its generality.<br />
<p>In physics, we began with the ambition to discover a small set of general principles with which all the universe could be explained, only to find that most of the universe is in fact beyond human grasp. Now, in the more orderly and man-made world of computation, we find that almost everything is uncomputable. There are infinitely many numbers, infinitely many problems, for which even the most powerful and sophisticated computer will be all but useless. Random numbers, in the sense discussed here, cannot be computed and can only come from some source outside the computer.<br />
<p>Turing completed his PhD dissertation at Princeton after the war. While accepting his own conclusion that some problems, like the Halting Problem, were just not tractable, he still wondered what a computer would look like if it could solve such problems, if it could somehow perform magic. In his dissertation, he augmented his TMs to include an "oracle," a magic device that could answer certain unanswerable questions. For example, a <i>Halting Oracle</i> was assumed to be able to discern, somehow, whether any given TM will eventually halt or whether it will run forever. Surprisingly, he found that such super-Turing machines are still limited in their abilities. A super-TM augmented with a halting oracle, for example, still suffers an inability to solve the Halting Problem as it applies to super-TMs. Modern computer scientists still use the idea of oracles to study the limits of computing. A <i>random oracle</i>, a function that always generates the same truly random number when given the same input, is widely used as an ideal cryptographic hash function. In <a href="http://www.consensualwisdom.com/2013/11/teaching-robots-to-sneeze.html">Teaching Robots to Sneeze</a>, we examined how to build what we might call a <i>truly random oracle</i>, which has no input parameters.<br />
<p>Last week, nearly sixty years after his suicide, Queen Elizabeth II granted Alan Turing a <a href="http://www.theatlantic.com/technology/archive/2013/12/alan-turings-body/282641/">posthumous pardon for his supposed crimes</a>. I've noticed that much of the reporting and discussion of this important event has focused on Turing's accomplishments and discoveries, which I find slightly ironic given that he spent so much of his short life contemplating the undiscoverable, the unknowable. Legendary superheroes often have a quiet place, a lair, in which to meditate and seek inspiration. Superman had his Fortress of Solitude, Batman his Batcave, and Alan Turing had the Divine Random.<br />
Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com2tag:blogger.com,1999:blog-1039373877769915493.post-56861292621416602702013-11-17T14:54:00.000-06:002013-11-18T08:33:10.588-06:00Teaching Robots to SneezeModern digital computers are not designed to do unexpected things. When they do occur, these are usually called "failures."<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-bottom: 1em; margin-right: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlNx9Ldy1_HR4EnX808gSQiOwxUhyphenhyphen1bGD8iuYSTwr9StwUYVOb1VWDETbwLdbzJz1C0-RCi05faOd-XS5VphPaOnziIyPC_RNxrKdvlc3VARU6zLFbnleKPhgtJcmqAfqAFzGyBAWSylk/s1600/robot_sneeze.jpg" /><br />
</td></tr>
</tbody></table>But, as I discussed in <a href="http://www.consensualwisdom.com/2013/08/the-divine-random-in-physics.html">The Divine Random in Physics</a>, sometimes it's highly desirable, even necessary, to do something that is universally unpredictable. Or, in other words, to compute a truly random number. Even the phrase is possibly an oxymoron, because if you can compute something, or program a computer to compute it, can that ever be <i>truly</i> random? (I will discuss the relationship between computability and randomness in more detail later on.)<br />
<p>Now, if you've written much software, you may be wondering what the big deal is. After all, every operating system and pretty much every programming language has built-in functions called <b>random()</b> or <b>rand()</b> that generate random numbers for you using deep, complex mathematics that, thankfully, we programmers don't need to understand in order to use the functions. Unfortunately, despite their names, these functions do not produce random numbers in the sense that we have used the term here. In fact, the numbers computed by these so-called <a href="http://en.wikipedia.org/wiki/Pseudorandomness">pseudo-random number generators (PRNGs)</a> are completely, 100% predictable. They do have a sometimes useful property called statistical uniformity or <a href="http://en.wikipedia.org/wiki/Statistical_randomness">statistical randomness</a>, but they are in no way <i>truly</i> random. Think of the successive digits of the number <i>pi</i>, which are statistically random, but easily predictable by anyone who can divide the circumference of a circle by its diameter.<br />
<p>The extensive use of such PRNGs in commercial and government cryptography products has caused immeasurable harm, the extent of which is only just beginning to emerge. A few weeks ago, it was revealed that the default and recommended PRNG algorithm, whose formidable name is Dual Elliptic Curve Deterministic Random Bit Generator, used by many commercial companies in the US and abroad contains a <a href="http://arstechnica.com/security/2013/09/stop-using-nsa-influence-code-in-our-product-rsa-tells-customers/">backdoor vulnerability</a> that was deliberately inserted by its inventor. That inventor, the US National Security Agency or NSA, now has the capability to predict pseudo-random sequences for any software that uses the tainted PRNG. If this doesn't seem all that important to you, consider this. According to the <a href="http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=all">New York Times article</a>,<br />
<blockquote class="tr_bq" style="border-left: 3px solid grey; padding: 5px;"><span style="background-color: white; font-family: 'lucida grande', tahoma, verdana, arial, sans-serif; color: grey; text-align: left;">The agency has circumvented or cracked much of the encryption, or digital scrambling, that guards global commerce and banking systems, protects sensitive data like trade secrets and medical records, and automatically secures the e-mails, Web searches, Internet chats and phone calls of Americans and others around the world...<br />
</span></blockquote>Incidentally, the tainted algorithm was adopted so widely, despite its known origins in the NSA, because another US government agency, the <a href="http://www.nist.gov/">National Institute of Standards and Technology, NIST,</a> blessed it as a standard and recommended that it be used wherever possible. Government contractors and vendors supplying cryptography products to the federal government were then required to be certified, which certification included the requirement to use a certain PRNG algorithm.<br />
<p>PRNGs aren't all bad. There are many applications, e.g. Monte Carlo simulation and automated testing, where a repeatable stream of statistically random numbers is just what the doctor ordered. But there are other uses, cryptography being one, for which only the best, genuinely random, numbers will do. Another area where universally unpredictable, truly random numbers are highly desirable is for UUIDs - Universally Unique IDentifiers - used, for example, in massively scalable digital storage clusters that have global namespaces. Here, each stored object, and there may be billions or trillions of them, is assigned a UUID that is different from every other object's UUID. Not only that, it is different from every other UUID ever used or that ever will be used. Thus the term "universal." Such UUIDs become the <i>true names</i> for these objects, in the sense discussed in <a href="http://www.consensualwisdom.com/2011/03/satnam-and-other-dangers.html">Satnam and other Dangers</a>.<br />
<p>There are several different <a href="http://tools.ietf.org/html/rfc4122">ways to generate UUIDs</a> that are guaranteed to be unique. Most of these involve some sort of centralized naming authority. For example, the namespace for Internet URLs is ultimately managed by the Internet Assigned Numbers Authority, IANA. But deterministically generating UUIDs in this way is slow and requires a great deal of cooperation. And did I mention there's still some pseudo-government entity controlling the namespace? <br />
<p>An alternative approach, using large, truly random numbers for UUIDs, can't <i>guarantee</i> uniqueness, but it can make it very, very unlikely that two different objects will receive the same UUID (a "collision"). And if the calculable probability of a collision of truly random UUIDs is smaller than the probability of an undetected hardware or software failure in the deterministic algorithms (see <a href="http://www.consensualwisdom.com/2011/01/provably-probable-is-better-than.html">Provably Probable is Better than Probably Provable</a>), then the truly random approach has an important practical advantage over the "deterministic" ones. Namely, each process in a distributed network can, in theory, generate UUIDs independently of every other process; no cooperation with other processes or with a central naming authority is required.<br />
<p>Which brings us, finally, to the main topic of this chapter. How can we program a modern digital computer to do something that is universally unpredictable — truly random? How can we teach a robot to sneeze?<br />
<p>Consider the following programming problem. We have four server-class computers, no keyboards or mice attached, all plugged into the same power strip. The servers are all identical - same hardware, same memory, same peripherals. All are networked together through a single network switch. The power strip is switched on so that all four computers start at the same moment and they all boot the exact same operating system, say Linux, and then synchronize their clocks. They then auto-execute an application program whose sole task is to generate a 128-bit truly random number and share it with the other servers. Each server stores the four numbers generated in this round, then compares its number against all previously recorded ones. If its generated number is different from every other number ever generated by any of the servers, it reboots itself and the whole process starts over again. If there is <i>ever</i> a duplicate number generated, an alarm goes off, lights flash, sirens wail, and the V.P. of Engineering gets a frantic phone call in the middle of an otherwise relaxing and much needed vacation in Taos, New Mexico.<br />
<p>There are several different ways to solve this problem, and some are better than others. A naive (meaning terrible) approach would be to simply look around the system to find "random" or unpredictable values, then hash them together to form a candidate number. Simply scrambling the value of the real-time clock would generate a number that is statistically unique across reboots, but every server would likely generate the same value, since their clocks are synchronized. You could mix in other more or less random values, like the serial numbers of peripherals, if available, or the MAC addresses of the network interface cards. But these numbers are static across reboots, so the same machine would find the same values each time and from them generate the same candidate number. Also, these numbers are unique only if you trust the central naming authorities, usually manufacturers associations, that assigned them. Specifically in the case of MAC addresses for NICs, manufacturers are assigned blocks of numbers they then use in serial fashion for their network cards. Since our servers come from the same manufacturer and perhaps the same batch, there is a good chance the MACs are very close to one another. Contrary to common belief, MAC addresses can also be reused over time.<br />
<p>A better all-around approach is to use measured timings for hardware-related events, which relies in one way or another on detecting and measuring small discrepancies (a.k.a failures) in the hardware. The Linux operating system (and most commercial Unix variants) includes a <a href="http://www.pinkas.net/PAPERS/gpr06.pdf">random number generator like this in its kernel</a>. This mechanism measures tiny variations in interrupt timings in various hardware drivers, including keyboard, mouse, hard disk, and network drivers, to accumulate an "entropy pool" of randomness. When an application wishes to use a random number, it simply reads from a special device called /dev/random and asks for some number of bytes of randomness. If there is sufficient entropy in the pool at the time of the request, the kernel returns the requested number of bytes of randomness and reduces the pool by the same number of bytes. If there is not sufficient entropy yet, the read from /dev/random will block until enough randomness accumulates.<br />
<p>The word <i>entropy</i> here is an allusion to <a href="http://en.wikipedia.org/wiki/Entropy_(information_theory)">Claude Shannon's idea of entropy in communication theory</a>. The actual calculation of this supposed measure of randomness in the Linux random number generator is somewhat mysterious and ill-understood. Even though the source code for it is publicly available, there seems to be no good explanation for why it might work, in theory. Nevertheless, it is clear that the best sources for randomness are the human interfaces; the keyboard and mouse. Ironically, the best way for a robot to do something unexpected is to ask a human! For our sample network of servers, which is based on a real world cluster of storage servers I once helped design, there are no human interfaces from which to draw randomness. Analysis has shown that other sources, notably hard disk drivers, are very poor sources of randomness, generating something like one bit of entropy per minute of operation. It seems the Linux random number pool is exceedingly shallow, which is once again ironic given that we know randomness is not a kiddie pool in the middle of our otherwise deterministic universe, but rather a <a href="http://www.consensualwisdom.com/2013/08/the-divine-random-in-physics.html">vast ocean of unpredictability surrounding us all</a>.<br />
<p>There is a way to draw randomness directly from that ocean by using specialized devices called <a href="http://en.wikipedia.org/wiki/Hardware_random_number_generator">Quantum Random Number Generators</a>, QRNGs. As the name suggests, these devices tap into quantum-level phenomena, including the mother of all weirdness, <a href="http://www.sciencedaily.com/releases/2010/04/100414134542.htm">quantum entanglement</a>, to pull randomness from between the grid lines of the rational universe. Unfortunately, these devices are generally not a part of standard, off-the-shelf, computers like the ones we have conjectured for our example network. Given the importance of this kind of functionality for effective cryptography, that's a little odd, don't you think? If I were a conspiracy theorist, I would suspect the NSA has had a part in this omission.<br />
<p>But the sad fact is, to solve our proposed puzzle using only commodity servers, we cannot rely on fancy QRNGs, at least not today. The question now boils down to this: How can we tap into the realm of quantum-level events using ordinary hardware? <table cellpadding="0" cellspacing="0" class="tr-caption-container" style="center: right; margin-bottom: 1em; margin-right: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" src="http://kasap3.usask.ca/images/photos/Photo-p510.GIF" /><br />
</td></tr>
</tbody></table>One answer my colleagues and I came up with is to measure the tiny irregularities in the heartbeat of every digital computer, the CPU clock. This clock is derived from a very mundane source: a physically vibrating quartz crystal — basically an atomic tuning fork. Most modern CPUs use a <a href="http://en.wikipedia.org/wiki/Crystal_oscillator">crystal oscillator</a> that vibrates in the neighborhood of 30-80 million times per second and that signal is then multiplied electrically to produce a clock frequency of three or four billion cycles per second, which is the rate at which the computer can execute its simplest instructions. Although modern crystal oscillators are highly stable in their frequencies, things like temperature, humidity and external vibrations do cause small variations to occur, and when the frequency is multiplied by electrical circuits, so is the noise. That's usually okay, since CPUs are remarkably tolerant of lower or higher clock frequencies — most will run just fine at half the clock rate and can generally be overclocked a bit to run faster. But if we could measure these small variations in the vibrational frequency of chemical bonds between individual atoms of a crystal lattice, that would be a good source of quantum randomness. The challenge there is, how can a computer measure variations in its own heartbeat without some sort of external reference?<br />
<p>Luckily, there is a second clock within most every modern computer, one that uses an independent crystal oscillator as its frequency source — the real-time clock or RTC. It is quite important for different computers within a network to agree on what time it is, or at least on how long a second is. To do this, most computers use a much lower-frequency, and less noisy, crystal oscillator operating down near the 100-thousand cycles per second range to measure the passage of time. Of course, this second crystal is subject to the same kind of noise as the CPU oscillator, though less so because of its lower frequency. But that's good for our purposes! We can simply count how many CPU clock cycles occur within each RTC cycle, subtract successive samples and contribute the least-significant few digits to the entropy pool. Conceptually, this sampling can be done by executing a simple instruction loop a few million times and asking the RTC how long it took to complete. Given the realities of things like hardware interrupts and process scheduling, the details are of course more complicated, but the solution remains practical and it works for almost any commercially-available digital computer.<br />
<p>Computers do exactly what we tell them to do. When they don't, we typically think of it as a failure. But <i>unexpected</i> does not always mean <i>faulty</i>. Not only is it useful for software developers to <a href="http://www.consensualwisdom.com/2011/02/plan-to-fail.html">plan to fail</a> when designing complex systems, it is sometimes necessary to actually elicit and embrace failures, to swim briefly in the ocean of randomness. Randomness, one could argue, is at the very core of humanity and human creativity, and it isn't possible to <i>program</i> a computer to do something completely unexpected. To teach a robot to sneeze, we must allow her to surprise us.Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com2Bee Cave, TX 78738, USA30.306098 -97.95237680000002530.251264 -98.033057800000023 30.360932 -97.871695800000026tag:blogger.com,1999:blog-1039373877769915493.post-58937648369568319492013-08-28T10:23:00.000-05:002015-11-14T16:48:02.695-06:00The Divine Random in Physics<blockquote><i>A place where gently blowing semi-trees<br />
Stand constant in the changing sands, <br />
And pretty birds flying flawless paths<br />
Sing palindromic melodies<br />
</i></blockquote>A while back, I sat in a conference room with a group of smart software engineers discussing randomness. Our new distributed software product relied very heavily on being able to generate <i>truly</i> random numbers on generic digital computers, a surprisingly hard problem as it turns out. The question had arisen, how sure were we that the numbers we generated were really, truly random? And by the way, what the heck does that actually mean?<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" height="240" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhjfA0PmJkeLToPAAYfRGcrkC7ybJlSqCiGLbJwFMpqGCRvhThKF7crSZXhqhBe_ovIrA6hiCyCQb64-X8UCgLNgZ4ZtLo25TesR4HMxhA0nibnS-CGqMMlcSGwKu8DQ67GoSNwA2YjVaI/s320/Galaxy_Question.jpg" /><br />
</td></tr>
<tr><td class="tr-caption" style="text-align: center;">Star System Arp 194 (Courtesy NASA)</td></tr>
<tr><td class="tr-caption" style="text-align: center;">The Question Mark Galaxy</td></tr>
</tbody></table><p>Someone posited that a truly random number might be one that is <i>universally unpredictable</i>, a definition I quite liked. But instead of saying I liked it, I flippantly suggested there might be no such thing, that given enough information and a big enough computer, we might possibly predict the outcome of any conceivable physical process. Two members of my team (defensively, I will point out they both hold PhDs and very large brains) immediately spoke up to point out how wrong I was and exclaimed in unison, "Bell's Theorem!" I was simultaneously mortified that I had made such a mistake and proud that not one but two members of my team knew enough about quantum metaphysics to correct me. In hindsight, it isn't surprising that it was the concept of randomness that took us so quickly from a mundane discussion of Bug 1356 to the esoteric nuances of life, the universe, and everything. Here's how we got there.<br />
<p>Randomness, as a natural phenomenon, was discovered in 1927 by a young German physicist named Werner Heisenberg. Prior to that time, the universe was completely predictable, or at least that's how we viewed it. Physicists from Newton to Einstein all believed if we just looked hard enough we would find the rulebook of the universe, the answer to everything. And even if that answer were more complicated than, say, 42, it would still be possible to predict the outcome of any physical process, as I had suggested in the engineering meeting. The most brilliant minds the human race had produced all rejected the idea that the universe might be a giant game of chance. Albert Einstein famously rejected it explicitly. Then came the <a href="http://plato.stanford.edu/entries/qt-uncertainty/">Heisenberg Uncertainty Principle</a>.<br />
<p>The Uncertainty Principle basically says, certain pairs of properties of physical objects — simple things like where it is and how fast it's going — cannot be simultaneously measured with perfect precision. The more carefully you measure the position of, say, an electron, the less certain you can be about its velocity at that same moment. If you are very, very, very careful measuring the position, then whatever number you observe for the velocity is essentially meaningless; it is random beyond a certain number of decimal places. Now this limit on how accurate one can be with these combined measurements is quite negligible for larger objects like bowling balls or BBs, but for small things like electrons and photons it makes a difference. The combined limit on our accuracy of measurement is determined by <a href="http://en.wikipedia.org/wiki/Planck_constant">the reduced Plank constant</a> which is about 35 decimal places of accuracy. Beyond that, physical properties are universally un-measurable. This can be understood by thinking about how one's measurements affect the object being measured. Measuring the position of an electron involves shining a light on it, and a more accurate measurement requires shorter bandwidth, higher energy photons. When the electron is impacted by the high-energy photon, its velocity is affected, thus introducing randomness.<br />
<p>And that is the way it was presented and talked about at first, as a limit on experimental accuracy. The Quantum Physics textbook I used in college, the 1974 edition of <a href="http://www.amazon.com/Quantum-Physics-Molecules-Solids-Particles/dp/047187373X/ref=sr_1_1?ie=UTF8&qid=1377643788&sr=8-1&keywords=quantum+physics+resnick+eisberg"><i>Quantum Physics</i>, by Eisberg and Resnick</a>, explained the Uncertainty Principle by saying, "our precision of measurement is inherently limited by the measurement process itself [...]." Albert Einstein, and many other prominent contemporaries of Heisenberg, believed there must still be an underlying set of "hidden variables" that control the universe and provide precise, deterministic answers to any question, even if we were forever limited in our ability to experimentally verify those answers due to the Uncertainty Principle.<br />
<p>Einstein, together with his colleagues Boris Podolsky and Nathan Rosen, even wrote a famous paper in which they, almost mockingly, proved that Quantum Mechanics must be wrong, or else the world as we know it would be a truly strange place. To do this, they assumed only two seemingly obvious things about the world. First, that objects have intrinsic properties like position and velocity, even when no one is measuring them. This they called "reality." And second, that measurements of reality in one place and time cannot instantaneously affect other, far away realities, a property they called "locality." Einstein, Podolsky and Rosen basically said, who would want to live in a world where reality and locality did not hold. In other words, they believed our friendly, orderly universe could not possibly be intrinsically random.<br />
<p><b>But they were wrong.</b><br />
<p>In 1964, <a href="http://en.wikipedia.org/wiki/Bell's_theorem">Professor John Stewart Bell proved a result</a> that some have called, "the most profound discovery of science." The unassuming title of his brilliant paper, <i>On the Einstein Podolsky Rosen Paradox</i>, referred back to the "paradox" outlined by Einstein and his pals. Bell proved that the universe is in fact fundamentally, inherently, inescapably random. More precisely, he showed that no deterministic theory based on hidden variables could possibly explain all the observed results of Quantum Mechanics. And if that means there is no such thing as reality or locality, then so be it. Either the principle of reality or the principle of locality (or both) does not apply in our universe! A strange place indeed.<br />
<p>And so my brilliant colleagues were right. Heisenberg's Uncertainty Principle is not just a limit on how accurately we can measure things. It's a limit on what we are allowed to know about the universe in which we live. There are physical quantities that are universally unpredictable. At the very foundation of our familiar physical world, lies the Divine Random.<br />
Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com5tag:blogger.com,1999:blog-1039373877769915493.post-76695946407354377562012-11-01T17:37:00.000-05:002012-11-01T17:37:28.048-05:00Truth Dealers<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgc2ZMe169iS7xedyCs6uNBKytywajG5sglpk7dCHozgaluXg_fMLa8EGSPVcUk9AurBfNqH2zUCZusGyYbCJVSw_sylDBQstVBtC1Chr1ysCLcK4xxpqLTWlKCs2JEzbrs5RHRSyWZXcc/s1600/LordOfWar.png" imageanchor="1" style="clear:left; float:left;margin-right:1em; margin-bottom:1em"><br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgc2ZMe169iS7xedyCs6uNBKytywajG5sglpk7dCHozgaluXg_fMLa8EGSPVcUk9AurBfNqH2zUCZusGyYbCJVSw_sylDBQstVBtC1Chr1ysCLcK4xxpqLTWlKCs2JEzbrs5RHRSyWZXcc/s320/LordOfWar.png" /></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i>I sell to leftists and rightists.<br />
I'd sell to independents but they're not the most regular customers.</i></td></tr>
</tbody></table></a></div>There will always be war and politics. Just as the ready availability of weapons escalates and prolongs wars, the ready availability of information escalates and prolongs political battles.<br />
<p>As the 2012 U.S. election season draws to a close, there have been many possible reasons proffered for why this one seems to have been particularly, historically divisive. The battle lines between Democrats and Republicans have grown deeper, wider, and more extensive than for any other election — at least any I can remember. This, despite the facts that, 1) the two parties have nearly identical ideologies, and, 2) most voters do not fully support the published platforms of either party.<br />
<p>One of the reasons I've heard suggested to explain this latest battle in the ideological war that began, really, back in the photo-finish election of 2000, is that we have somehow lost our respect for the truth. He who tells the biggest whopper gets the most votes. In <a href="http://www.consensualwisdom.com/2012/05/truth-and-nothing-buta-good-story.html">The Truth and Nothing But...A Good Story</a>, I wrote about how partisan lies often spread like wildfire through the Internet, propagated by people who are either too lazy to check the validity of the facts, or too cynical to care. In the latter days of the campaigns, this overt dishonesty isn't limited to the Internet, with TV and radio ads now <a href="http://swampland.time.com/2012/10/30/romneys-inaccurate-auto-rebuttal/">claiming things</a> that are blatantly, provably, unequivocally false.<br />
<p>What's more maddening, nobody ever seems to want to retract these lies once they're caught. The phenomena of "doubling down" and "tripling down, basically repeating the original lie louder and to a broader audience, has become epidemic. Why? Because it works! And here's how...<br />
<p>Think of political operatives as carnival barkers. Their job is to draw attention to a certain set of facts that favor their candidate. But the facts themselves may be dry and boring without some dramatic context. "See the man with no stomach!" they scream. The actual fact is, there's a skinny guy who can suck in his gut to the point where his spine is visible from the front, still worth the price of admission perhaps (if you're interested in such oddities), just not as catchy and seductive as the shouted hook would have you believe. Some customers, after viewing the side-show, may complain about the lie, pointing out the original claim was misleading and blatantly, provably, unequivocally false. "Pants on fire!" they exclaim. But who cares? They have witnessed something they probably wouldn't have seen otherwise, and the carnival has their $1 so everybody's happy. Meanwhile, the barker continues to shout even louder, "See the man with no stomach!"<br />
<p>Even carnival barkers have legal restrictions that prevent them going too far in making false claims and false implications. Under certain circumstances, their utterances can be considered to be advertising, which is regulated by the Federal Trade Commission and by similar state agencies. Under penalty of law, advertisers are not allowed to make false claims, or even misleading ones, about their products or their competitor's. The FTC defines false advertising to include the following:<br />
<blockquote class="tr_bq" style="border-left: 3px solid grey; padding: 5px;"><span style="background-color: white; font-family: 'lucida grande', tahoma, verdana, arial, sans-serif; color: grey; text-align: left;">means of advertisement [...] which is misleading in a material respect; and in determining whether an advertisement is misleading, there shall be taken into account (among other things) not only representations made or suggested [...] but also the extent to which the advertisement fails to reveal facts material in the light of such representations.<br />
</span></blockquote><div class="separator" style="clear: both; text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Sideshow_at_the_Erie_County_Fair.JPG/1280px-Sideshow_at_the_Erie_County_Fair.JPG" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" height="240" width="320" src="http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Sideshow_at_the_Erie_County_Fair.JPG/320px-Sideshow_at_the_Erie_County_Fair.JPG" /></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i>See the Mormon with no heart!<br />
Marvel at the Kenyan who fooled the world!</i></td></tr>
</tbody></table></a></div>In this campaign cycle, there have been many, many political ads, including the one linked above, that clearly would have violated FTC laws if the product being sold had been, say, soap instead of a candidate for political office. Why do we hold carnival barkers and purveyors of dish soaps to a higher standard of honesty than our presidential candidates? The answer is, the First Amendment to the Constitution of the U.S. The courts have held that political ads cannot be considered to be advertising. They are political speech, which is protected under the First Amendment. As a result, it is legal for anyone to tell any political lie, however outrageous, as loudly and often as they wish.<br />
<p>And, honestly, how else could it work? We certainly don't want the government telling us which political claims we should believe and which ones we should discount. The problem is really a practical one stemming, ironically, from the success the FTC has had in their enforcement of truth in advertising. I've heard people say things like, "There must be some truth in that political ad, otherwise they wouldn't let it be shown on TV." This "nanny expectation" is completely unfounded when it comes to the strange world of political advertising and no comfort whatsoever can be drawn from it. (Interestingly, the truth-in-advertising expectation does not seem to extend to the Internet, even though the same FTC laws apply there as on traditional broadcast media.)<br />
<p>Legally, practically, and in every other sense, it is the responsibility of each individual voter in the U.S. to research campaign ads they may find compelling to discover whether they are indeed truthful; a daunting task. The only reasonable alternative is to rely on a trusted source to do the fact checking for you. There are now legions of so-called fact checkers, and nearly every claim made by every major political candidate is combed over, investigated, parsed and re-parsed to try to determine whether it is true, false, or somewhere in between. Campaigns often shoot for that middle ground, the grey area where claims can still be sensational, provocative, even mildly misleading, without actually being so blatantly false as to reflect poorly on the candidate's public character and facade of honesty. They seem to follow some sage advice I received early in life.<br />
<blockquote class="tr_bq" style="border-left: 3px solid grey; padding: 5px;"><span style="background-color: white; font-family: 'lucida grande', tahoma, verdana, arial, sans-serif; color: grey; text-align: left;">How does one become a good liar?<br />
Tell the truth <i>almost</i> always.<br />
</span></blockquote><p>The truth is a fluid and relative thing these days. It depends on whom one chooses to believe. Even things we once called "facts", things like, "this person was born in the U.S.," or, "this person is a Christian," or, "this person never cheated on his taxes," all are now written in various shades of grey. It's not that we treasure the truth any less than before; if anything, just the opposite is the case due to increased skepticism. It's not that there are too few facts; the Internet, among other things, now provides a treasure trove of information about every conceivable topic.<br />
<p>The challenge, IMO, is that there are so many facts, so much information available to each of us. Facts are weapons in the political wars that currently rage in this country, and fact checkers are the arms dealers who make money selling to both sides of the conflict. Like weapons, there are high-quality facts and low-quality ones. Facts purchased from the "fact checkers" at Fox News or MSNBC are somewhat more likely to jam on you in the heat of battle or blow up in your face like a crude IED. But these aren't the really dangerous ones. The reputable arms dealers, the neutral fact checkers and think tanks sell large quantities of durable, usable information to either side for a price. In political skirmishes these days, you cannot be lulled into a false feeling of security because you are armed with the facts. The other guys are probably packing heat as well, just as much as you and maybe more. Standing up to declare victory because truth is on your side is a sure way to become a bloody casualty.<br />
<p>I am not advocating that fact checkers be outlawed, of course. Nor am I saying that free and open information is bad. The NRA has the right idea, facts do not kill candidates, ideologies kill candidates. An IED in the hands of a radical ideology can do more damage than an aircraft carrier in the hands of a civilized one. Wars and political debates are won not with weapons or facts, but by leaders who know what they are defending, whose loyalties are steadfast, and whose vision extends far beyond the next battlefield.Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-38902609299993964822012-09-15T20:07:00.000-05:002012-09-16T14:23:51.449-05:00Consensual Wisdom<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjm3l3ONmcLjV8Ev0noDQCRPeRVgAH7hKUk_FMPd5jOHvGFw_68BYm50ZB0hUYExH0WQFwfFMUVYmRH9BW3kn14M-eFIdB3l8TH3ZSnGIsqSylOm9JNumS2Ku8wAw625ReuFE6qsXsf88s/s1600/riots.png" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="225" width="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjm3l3ONmcLjV8Ev0noDQCRPeRVgAH7hKUk_FMPd5jOHvGFw_68BYm50ZB0hUYExH0WQFwfFMUVYmRH9BW3kn14M-eFIdB3l8TH3ZSnGIsqSylOm9JNumS2Ku8wAw625ReuFE6qsXsf88s/s400/riots.png" /></a></div>I have a theory that almost all of us agree on almost everything. But we're wired somehow to zero in on the things we <i>disagree</i> about, however minor they may be, and debate/argue/fight over them. It seems the larger our base of common understanding, the more intense the disagreements over the details. Sunnis and Shiites, Christians and Muslims, Republicans and Democrats, kill each other (figuratively and sometimes literally) over the smallest ideological differences, despite their enormous shared premise. As a result, we ignore the big problems that challenge us all and focus instead on the minutiae of our dissonance.<br />
<p>But what if there were an environment where we were rewarded for finding our kernel of consensus? A game, say, where the rules guide us toward addressing the problems we all agree exist. An economy where one becomes individually wealthy only by taking actions that benefit everyone. A society that can grow as large and diverse as necessary and still make progress toward common goals.<br />
<p>I'm not talking about Utopia here. I'm just asking, is there a set of rewards and punishments, however artificially enforced, that will lead a group of people to focus on their considerable shared world view rather than their comparatively tiny differences? <br />
<p>Science, politics, and religion all have enormous edifices of consensual wisdom. Evidence and ideas that diverge from or seem to contradict those shared bodies of knowledge induce different reflexes in each discipline. Religious thinkers tend to reject them, scientists embrace them, and politicians use them as leverage. That's all fine, but the incessant preoccupation with what makes us different tends naturally to fragment us, to balkanize our churches, our research disciplines, and our societies until, in the limit, we will be left completely harmonious but quite alone. Social entropy will be at its maximum.<br />
<p>None of our institutions have evolved mechanisms of inclusion, systems that seek to expand groups by including more and more people who actually disagree with us. It's so rare that you may not even see the point in doing so. Maybe I am being hopelessly naive here, but it seems to me that recognizing our kernel of consensus, the common knowledge, shared problems, and joint solutions becomes more and more valuable as the size of the union gets larger, even if the intersection becomes smaller; particularly so if my hunch is correct that almost all of us agree on almost everything.<br />
<p>Perhaps I'm wrong though. Maybe, if all the religions of the world were to somehow identify their kernel of consensus, it would turn out to be trivial; something stupid and obvious like, we all have an ethical core and we should all give ourselves permission to obey it. But wait. Is that really so trivial? I, of course, don't know what the intersection of all our beliefs would be, but imagine the incredible power inherent in being able to make a statement like that! "We, the combined theological intelligentsia of the entire planet, believe the following to be true..." Imagine the societal and spiritual benefit that might ensue from simply communicating that consensus, whatever it turns out to be. I believe that benefit might far outweigh whatever good comes from arguing about who has the coolest prophet and whether we should utter its name or view its likeness.<br />
<p>I don't mean to pick on religion here. In many ways science is even less concerned with consensus and more obsessed with the deltas and outliers. That's what they do for a living, and it's what makes it so difficult for societies to choose courses of action based on reason and scientific consensus at a point in time. Many scientists believe it isn't their jobs to even try to identify consensus among themselves, rather they should provide politicians and decision-makers with all the possible alternatives and let <i>them</i> make decisions about what, if any actions to take. I think this is an abdication of their social responsibility. We are left to guess, infer, and in many cases, attempt to obfuscate scientific consensus on important topics.<br />
<p>Is the Earth's climate changing at a rate unprecedented in recorded history? I think I'm safe in saying almost all climate scientists agree that it is. Is this climate change anthropogenic (caused by human activities)? Maybe there's a consensus answer to that question, maybe not. Does evolution exist? Absolutely it does, in the same sense that <i>quicksort</i> (a well-known sorting algorithm) exists. Is it sufficient to explain the diversity of life on the planet? Without inviting criticism and controversy, I can't say whether there is a scientific consensus on that question. My point is, there are no conventional mechanisms in science for reaching and communicating conventional wisdom. Claiming that no consensus exists because one or a few scientists disagree is fallacious. Consensus does not require unanimity. It does, however, require a collaborative mechanism of discovery and refinement.<br />
<p>No, I'm not having a Kumbaya moment. My advanced age guarantees I have a healthy daily dose of skepticism and pessimism. The <a href="http://en.wikipedia.org/wiki/2012_diplomatic_missions_attacks">events of the past few days</a> have done absolutely nothing to make me suddenly feel optimistic about our ability to live together without killing each other for nonsensical reasons.<br />
<p>But even with all this negative energy swirling around today, I'm left with an intellectual curiosity about the central question of this post: Now that the Internet has given the world a way to communicate instantly, can we also find a way to agree?Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com11tag:blogger.com,1999:blog-1039373877769915493.post-71767939374219090502012-08-21T20:05:00.001-05:002015-11-14T16:49:24.291-06:00Introduction to The Divine Random<blockquote><i>Come travel with me, far from now and here,<br />
To a niche carved into entropy.<br />
A perfect island, in a magic sea,<br />
Where only miracles and fools are feared.<br />
</i></blockquote>Does true randomness truly exist?<br />
<p>We know that randomness is useful, essential even, in solving a number of important <a href="http://www.consensualwisdom.com/2011/01/provably-probable-is-better-than.html">problems in distributed computing</a>, <a href="http://www.consensualwisdom.com/2012/07/and-winner-is-probably.html">social choice</a>, and <a href="http://www.consensualwisdom.com/2011/03/satnam-and-other-dangers.html">identity</a>. It is also the case that truly comprehensive solutions to those problems require true randomness, not the <a href="http://en.wikipedia.org/wiki/Pseudo_random">more limited kind</a> one typically finds in digital computing.<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" height="240" width="320" src="http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Mandel_zoom_14_satellite_julia_island.jpg/320px-Mandel_zoom_14_satellite_julia_island.jpg" /><br />
</td></tr>
<tr><td class="tr-caption" style="text-align: center;">A Julia Island<br />
(Courtesy <a href="http://en.wikipedia.org/wiki/File:Mandel_zoom_14_satellite_julia_island.jpg">Wikimedia Commons</a>)</td></tr>
</tbody></table>The question of whether such universally unpredictable events actually exist in our universe gets very deep very fast. It quickly bumps up against some of the most enigmatic and fundamental principles of physics, mathematics, computation, and theology. Together, these principles define the boundary of the known universe. And by that, I don't mean just the limit of what we know today, to be extended as we learn more tomorrow. I mean the absolute limits of science and reason, beyond which we can <i>never</i> venture, no matter how clever we are.<br />
<p>For a long time, I've been fascinated with a set of theorems that seem to define that boundary. They include the following:<br />
<ul><li><b><a href="http://en.wikipedia.org/wiki/Heisenberg_uncertainty">Heisenberg's Uncertainty</a></b> (Physics) — There is a limit to how accurately we can measure the properties of physical objects.<br />
</li>
<li><b><a href="http://en.wikipedia.org/wiki/Bell%27s_theorem">Bell's Inequality</a></b> (Physics) — That limit applies not just to our ability to measure things accurately, but to our fundamental ability to <i>know</i> things about physical objects.<br />
</li>
<li><b><a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems">Gödel's Incompleteness</a></b> (Mathematics) — Any attempt to explain everything using a small(er) set of axioms is doomed to be either unfinished or wrong.</li>
<li><b><a href="http://en.wikipedia.org/wiki/Turing%27s_halting_theorem">Turing's Undecidability</a></b> (Computing) — There are infinitely many problems that cannot be solved by any digital computer.</li>
<li><b><a href="http://en.wikipedia.org/wiki/Chaitin%27s_constant">Chaitin's Irreducibility</a></b> (Computing & Mathematics) — Almost every number (probability = 1) is "random" in the sense that it cannot be computed by an algorithm that is much shorter than the digits of the number. That is, the shortest <i>name</i> for the number is the number itself. Randomness exists in mathematics as well as physics!</li>
</ul><br />
I will talk more about these ideas and theorems in later posts in this series (informally of course - please don't confuse me for a real physicist or mathematician). For now, notice the last word in their names. Each of them expresses a negative. Each of them tells us something about what we <i>cannot</i> do, where we <i>cannot</i> go, what we <i>cannot</i>, under any circumstances, know.<br />
<p>Intuition suggests these five principles, despite their different fields of application, are somehow related. In fact, they seem to be exactly the same, or at least stem from the same underlying phenomenon. Namely this:<br />
<p>Fundamental randomness exists. It isn't just a small wart on our logical world, but rather an unfathomable ocean surrounding it. We cannot ever know what goes on in this ocean of randomness. We can only glimpse the shape of the coastline of our little island of reason, as the theorems and principles listed above begin to illuminate.<br />
Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com3tag:blogger.com,1999:blog-1039373877769915493.post-79922328654134616372012-07-19T14:52:00.000-05:002015-11-30T15:41:42.969-06:00And the Winner is Probably...<br />
In <a href="http://www.consensualwisdom.com/2012/03/provably-probable-is-still-better.html">Provably Probable Social Choice</a> 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 <i>any</i> full solution.<br />
<p>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?<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://www.cartoonaday.com/images/cartoons/2010/10/Voting-slot-machine-598x833.jpg" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="833" width="598" src="http://www.cartoonaday.com/images/cartoons/2010/10/Voting-slot-machine-598x833.jpg" /></a></div><p>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, <a href="http://digitalcommons.law.yale.edu/cgi/viewcontent.cgi?article=1963&context=fss_papers">weighted lottery voting</a> 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.<br />
<p>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.<br />
<p>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.<br />
<p>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 <a href="http://upload.wikimedia.org/wikipedia/commons/thumb/2/24/TravisCountyDistricts.png/400px-TravisCountyDistricts.png">congressional District 25</a>, 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.<br />
<p>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 <a href="http://rangevoting.org/PuzzRevealU2.html">double range voting</a>.<br />
<p>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.<br />
<p>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 <i>ex post facto</i> 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.<br />
<p>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.<br />
Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0Austin, TX, USA30.267153 -97.743060830.047568000000002 -98.058917799999989 30.486738 -97.4272038tag:blogger.com,1999:blog-1039373877769915493.post-13799383677879149412012-06-06T12:13:00.000-05:002012-08-31T16:54:16.271-05:00Democracy at ScaleDemocracy 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.<br />
<br />
<blockquote class="tr_bq" style="border-left: 3px solid grey; padding: 5px;"><span style="background-color: white; font-family: 'lucida grande', tahoma, verdana, arial, sans-serif; font-size: 11px; line-height: 14px; text-align: left;">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.<br />
<br />
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.</span></blockquote><p>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.<br />
<p>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 <i>say</i> they'll do in office, because we just don't have the time to examine their history to determine what they <i>really</i> believe in.<br />
<p>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 <b>props</b>. 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.<br />
<p>This idea of conveying greater resources, in this case voting power or <i>rep</i>, to some individuals in order to increase the welfare of the entire group was first identified and discussed by a nineteenth century economist named <a href="http://en.wikipedia.org/wiki/Vilfredo_Pareto">Vilfredo Pareto</a>. <i>Pareto Inequality</i> 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.<br />
<p>The question now becomes, can a reputational voting paradigm like the one I discussed in <a href="http://www.consensualwisdom.com/2012/02/building-ethos-out-of-logos.html">Building Ethos out of Logos</a> 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.<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjumIFPm5ZNzuMutiUlW-IPABlZq0ikcwMVej9X72ApE_NfH4Le9Hf8mUb6_JmlJ4I6-4k-m_s4FtDjsrZt-D2zAgs8sZmrA7-cydD2P6AV0Vsstm-SqBnESPylSC3VdYrBY73rqzXrEOw/s1600/rep_voting.jpeg" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="293" width="500" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjumIFPm5ZNzuMutiUlW-IPABlZq0ikcwMVej9X72ApE_NfH4Le9Hf8mUb6_JmlJ4I6-4k-m_s4FtDjsrZt-D2zAgs8sZmrA7-cydD2P6AV0Vsstm-SqBnESPylSC3VdYrBY73rqzXrEOw/s400/rep_voting.jpeg" /></a><br />
<p>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.<br />
<p>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 <i>all</i> 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.<br />
<p>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.<br />
<p>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 <a href="http://www.consensualwisdom.com/2012/03/jane-you-ignorant-slut.html">"Jane, You Ignorant Slut"</a>, it seems nobler to discuss ideas than people.<br />
<p>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.<br />
Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-89632636098129407952012-05-10T15:09:00.000-05:002012-05-11T13:56:36.046-05:00The Truth and Nothing But...a Good Story<div class="separator" style="clear: both; text-align: center;"><img border="0" height="340" width="480" src="http://i1186.photobucket.com/albums/z376/laclavicie/life-pi-movie.jpg" border="0"></div><p>A few months ago, a friend of mine who leans to the right politically shared a post on Facebook that started out like this:<br />
</P><blockquote class="tr_bq" style="border-left: 3px solid grey; padding: 5px;"><span style="background-color: white; font-family: 'lucida grande', tahoma, verdana, arial, sans-serif; font-size: 11px; line-height: 14px; text-align: left;">Professor Joseph Olson of Hamline University School of Law in St. Paul, Minnesota, points out some interesting facts concerning the last Presidential election:<br />
<ul><li>Number of States won by: Obama: 19 McCain: 29</li>
<li>Square miles of land won by: Obama: 580,000 McCain: 2,427,000</li>
<li>Population of counties won by: Obama: 127 million McCain: 143 million</li>
<li>Murder rate per 100,000 residents in counties won by: Obama: 13.2 McCain: 2.1</li>
</ul></span></blockquote><p>You may have seen this post, or even shared it yourself. By now, it is well known that <a href="http://www.factcheck.org/2009/01/unreported-stats/">it is a hoax</a>, 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.<br />
</p><p>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."<br />
</p><p>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 <i>might</i> 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.<br />
</p><p>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 <i>Atlas Shrugged, Animal Farm, 1984, Lord of the Flies, The Republic, The Holy Bible</i>, 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.<br />
</p><p>In <a href="http://www.consensualwisdom.com/2012/04/conflict-compromise-and-consensus.html">Conflict, Compromise, and Consensus</a>, 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 <a href="http://rturpin.wordpress.com/page/2/">points this out</a>:<br />
<blockquote class="tr_bq" style="border-left: 3px solid grey; padding: 5px;"><span style="background-color: white; font-family: 'lucida grande', tahoma, verdana, arial, sans-serif; font-size: 11px; line-height: 14px; text-align: left;">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.</span></blockquote><p>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.<br />
</p><p>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?<br />
</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com4St Kitts and Nevis17.357822 -62.78299817.115336 -63.098855 17.600308 -62.467141tag:blogger.com,1999:blog-1039373877769915493.post-47826373043499997442012-04-11T14:21:00.002-05:002012-04-17T12:15:20.180-05:00Conflict, Compromise, and Consensus<p>The art of war and the art of debate are morally reprehensible courses of study. The first produces mercenaries and the second politicians. If one argues for an idea, or fights for it, it should be out of conviction the idea is righteous and true. The awesome weapons of war and argumentation should never be wielded for personal gain or self gratification.</p>
<div class="separator" style="float: right; text-align: center;">
<img border="0" height="240" width="300" src="http://upload.wikimedia.org/wikipedia/commons/thumb/4/42/Old_senate_debate.jpg/300px-Old_senate_debate.jpg" /></div>
<p>Yet, this sort of rhetorical gamesmanship, where the object is to win the argument rather than advance society, is the most common form of political discourse today, and not just amongst politicians. It is an insidious, recreational form of what I call <i>collaboration by conflict</i>, wherein members of a group choose to engage each other specifically to find and argue about points of disagreement, however minor. In its non-recreational form, this type of collaboration can lead to positive societal advancement - think about the US Civil War or the civil rights movement - but usually at great cost and lingering dissatisfaction. More often than not, collaboration by conflict leads instead to splintering and balkanization of the group, even when the victors and the vanquished agree on almost everything! Catholics and protestants, Shi'ites and Sunnis, democrats and republicans, are <i>far</i> more alike in their ideologies than they are different. Yet, enormous human energy and (at least in the first two dichotomies) human lives have been wasted exploring the comparatively tiny differences.</p>
<p>A second type of collaboration is <i>collaboration by compromise</i>. If you and I have opposite ideas about something, we could seek a third alternative that is equally undesirable to both of us. Any well-functioning political body (insert oxymoron joke here) typically works using this form of collaboration. While it can produce a comfortable and stable society, collaboration by compromise generally does not result in great advances.</p>
<p>Finally, there is <i>collaboration by consensus</i>. If you and I have opposite ideas about something, we could seek a third, more fundamental alternative that we both strongly agree about and work to realize that idea. As an (admittedly over-trivialized) example, there is no overwhelming consensus among US citizens about abortion rights. Some believe it is a women's rights issue and that the mother should have complete discretion as long as the baby remains a part of her body. Others believe the moment there is even the potential for a human life to develop, it becomes the responsibility of society to protect and preserve that potential. And of course there is a whole spectrum of opinions in between those extremes. We citizens of the US could continue to battle it out over this issue, collaborating by conflict and enduring all the resultant costs and casualties. Or we could compromise again, as the Supreme Court did in Roe v. Wade, by choosing an arbitrary boundary and ensuring everyone is morally insulted in some cases. Or we might table this difficult and divisive fight and instead agree to work to reduce the number of unwanted pregnancies. And we might decide to expend all those resources we would otherwise have used arguing about abortion rights to instead streamline the adoption process and increase the pool of families who are willing and able to adopt. Collaborating by consensus, we can focus more of our time, money, and energy accomplishing the things for which there is widespread consensus, instead of wallowing in our differences and looking for another fight.</p>
<p>Truthfully, all three types of collaboration are needed to support any significantly meaningful society, online or offline. Ethosphere supports all three. More often than not though, the main goal of an Ethosphere collaboration is not to <i>win</i>. Nor is it to "split the baby" by finding compromises that nobody fully supports. Instead the goal is to find the <b>kernel of consensus</b> among a group of people on a given topic.</p>
<p>It is true, leaders don't seek consensus; they shape it. But don't mistake the day-to-day functioning of a society with leadership. And by all means don't try to conflate the role of government with the role of leader. It is not the responsibility of the US Congress, for example, to influence our opinions, rather to discern what those consensus opinions are and act on them.</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-8716124094980393282012-03-14T15:57:00.000-05:002014-04-08T13:56:20.925-05:00"Jane, you ignorant slut."<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3d6J_pxY0q2tBhCJXtciWo9JVHrXXf5acWWmrmnATXHDoJg0KyhsZ33XPUgLmNXM6aFRsQMGZPqFRtNFSuJ6if2e4_6Pb2AxIiCiDkB-XTLGtCEC-GccGNfMZ0bQ9TqLIA2eONzKiGIs/s1600/janecurtainweekendupdate.gif" /></td></tr>
<tr><td class="tr-caption" style="text-align: center;">"Dan, you pompous ass."</td></tr>
</tbody></table>Remember the '70s when phrases like that in an SNL sketch were so outrageous, so over the top, they actually were kinda funny? Today, of course, those old Point / Counter Point sketches seem more prescient than outrageous, as "serious" news commentators routinely say things like this with the same calm, deliberate, faux intellectual deadpan Dan Aykroyd and Jane Curtin used back then. And it's not just talk radio where this occurs.<br />
<br />
Most major online news outlets and blogs now allow readers to comment on op-ed pieces they publish. If you've ever read any of those commentary streams, you know they can quickly degrade into name calling and personal attacks, especially on those sites that allow commentators to post using anonymous pseudonyms. The grandiose idea that thousands of readers could contribute something constructive and positive to a thoughtful online conversation has been, to date, one of the most miserable failures associated with the Internet since its inception.<br />
<br />
Nick Denton, the founder of Gawker Media and owner of a bunch of popular blogs, <a href="http://www.cnn.com/2012/03/11/tech/web/online-comments-sxsw/index.html?iref=obnetwork">makes no bones about it</a>. He says, "It's a promise that has so not happened that people don't even have that ambition anymore. The idea of capturing the intelligence of the readership — that's a joke."<br />
<br />
Why has this laudable Internet ambition been such an abject failure, and what, if anything can be done to fix it? I have spent the past few months reading thousands of comments attached to articles on a wide variety of topics. To be sure, the effect is often depressing and sometimes frightening. But I do not think the reason this hasn't worked is a lack of intelligent people out there. On the contrary, I see many well-reasoned, well-written posts, some making points with which I agree and some with which I disagree. People still remember how to disagree with one another without ripping each other to shreds with <i>ad hominem</i> attacks. The trouble is, the constructive comments are often submerged in a cesspool of vile language, deliberate disinformation, intellectual immaturity, and troll bait.<br />
<br />
I have developed a few tricks that help me leaf through the commentary streams quickly, identifying the comments that may have value and skipping the ones that probably should not have been written in the first place. One such trick is based on a quote often attributed to Eleanor Roosevelt, <br />
<blockquote><i><b>"Great minds discuss ideas, average minds discuss events, small minds discuss people."</b></i> </blockquote>I've found you can quickly scan a post to determine whether the author is going to talk about ideas, events, or people. The first category are usually interesting, the second sometimes interesting, and the last almost never. Here are some examples from the commentary stream on the CNN article I linked above. <br />
<dl><dt><b>Ideas</b></dt>
<dd><i>@veggiedude</i> - Siri (and IBM's Watson) has shown how well artificial intelligence can work. The solution is to employ a Siri type moderator to decide whether to post or not post the comments from the users. This way, a machine is in control, and there is no one to get mad at - unless a person 'enjoys' getting mad at a machine. </dd>
<dd><i>@maestro406</i> - Allow a "squelch" option. Everyone has the right to post, but that doesn't mean I have to read every comment from every poster. I should be able to block individual posters on my computer.</dd>
<dt><b>Events/Examples</b></dt>
<dd><i>@swohio</i> - And the funny thing is, so many news sites have switched over to making people log in using Facebook in order to leave comments, stating it will help facilitate more mature, reasonable, and engaging discussion/comments. Sad to say, it hasn't at the sites I used to comment on where they've switched over to that system.</dd>
<dd><i>@GloriaBTM</i> - The most enjoyable board I've posted on were IMDB around 2005-07, both because of the format, variety of topics, and the way it was moderated. (I'm not sure what it's like now...) We were able to have real conversations about current events, science, religion (and yes, movies), without have to wade through so much muck. Most importantly, posters whose posts were repeatedly deleted for violating T&C had their accounts deleted, fairly quickly. Yes, people could create new accounts, but it did slow the nastiness down.People could also IGNORE certain posters. It was brilliant. You just click ignore and you don't have to see them ever again.I found the format easier to navigate than any other board I've been on. Each thread could collapse (truly collapse, unlike here, where it still takes up space, though the message is blanked). Then you could quickly scroll through and find your conversation and open that thread. </dd>
<dt><b>People</b></dt>
<dd><i>@Tzckrl</i> - STOOPID! R u kidding? Palin and Santarum 2012! Anyone who don't think so is a twerp! </dd>
<dd><i>@TommiGI</i> - South by Southwest is a joke and Nick Denton is the punchline.</dd> </dl>Another, sometimes more reliable, trick is to jot down the aliases of commentators who post useful or interesting comments and then scan for other comments by those same aliases. Of course, this is made more difficult if users are allowed to choose arbitrary, anonymous handles each time they log in. As <i>@swohio</i> indicates above, the recent tendency of other sites to require Facebook logins in order to try to enforce authenticity has had mixed results. While that approach doesn't seem to help moderate the crazies, as you might think it would, it does at least provide a consistent screen name for posters so that you can more easily spot the ones who have had a better track record in the past. <br />
<br />
In <a href="http://www.consensualwisdom.com/2012/02/trust-me-im-hamsterofdoom.html">Trust Me, I'm @HamsterOfDoom</a> I talked about how a framework like the Ethosphere can help develop and maintain trust relationships with pseudonymous identities. By maintaining a numerical ranking, a <i>rep</i> as I call it in the Ethosphere, that reflects the degree to which an alias has contributed constructively to the community in the past, we can more easily filter out the noise while still allowing open participation. The trolls can still troll, but their influence in the group will be limited.<br />
<br />
Another possible approach, proposed by Nick Denton in the linked interview, could have a similar impact. <br />
<blockquote><i>The answer? Denton said his sites are planning to post some stories that allow only a hand-picked, pre-approved group of people to comment on them. That, he said, would make the comment section an extension of the story and allow people [...] to have their say without fear of being piled onto by others.</i> </blockquote>The fundamental difficulty with this approach is that someone else, the publisher?, anoints an elite few who may participate in the conversation. This is counter to the original goal of open participation and violates an unwritten Internet law just as much as requiring authentic logins would. A better solution is to allow the participants themselves to choose who should have proportionately greater influence, in a dynamic and ongoing fashion. In <a href="http://www.consensualwisdom.com/2012/02/im-not-elitist-just-better-than-you.html">I'm Not Elitist, Just Better Than You</a>, I discuss how and why this is done within the Ethosphere.<br />
<br />
Do you think pseudonyms + reputation could be a possible solution to this problem? Are there other self-policing, self-organizing ways to do this?Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-15782118733470710502012-03-08T14:34:00.000-06:002014-02-13T12:19:04.372-06:00Peer PubsThe land of academic publishing and peer-reviewed journals is a strange land indeed. The business is dominated by a handful of publishing companies, notably the big four: Elsevier, Springer, John Wiley & Sons, and Informa. And don't think its just a niche market; those companies make tons of money and are hugely profitable. In the first quarter of 2011, Wiley made over $250 million with a profit margin of 43%! The largest of the four, Elsevier, <a href="http://www.economist.com/node/18744177/">made over $1.1 billion in 2010 and 36% of that went straight to the shareholders</a> as profit. Wow. How in the world can there be such a giant market for publications like <i>The Journal of Small Ruminant Research</i> ("The official journal of the International Goat Association")? And why is it such a profitable business?<br />
<div class="separator" style="clear: both; float: right; text-align: center;"><img border="1" height="200" src="http://www.elsevier.com/framework_products/images/95/622895.gif" width="150" /></div>Well, here's how it works. These refereed journals are periodic anthologies of scholarly papers and articles on fairly narrow topics (like goat research). They are written, understandably, by academics and researchers and they often document painstaking research and, sometimes, groundbreaking results in thousands of different fields of study. To ensure the accuracy, novelty, and relevance of these results, a long-standing peer review process has evolved in which highly reputable members of the same research community review, accept, or reject submissions. The collections are planned and organized usually by an editor, who is also a member of the same research community, like, for example, the community of researchers in the field of parallel and distributed computing.<br />
<br />
Great!, you say. We want these smart, creative researchers to make gobs of money because they are actually adding huge value to our body of knowledge and, eventually, our economy as well. Out of those billions of dollars, how much does the author of one of these articles get paid? Well, nothing typically. They probably are getting a salary from a university or corporate research lab, and publishing research is considered part of their jobs, so they rarely get paid anything by the publishing companies. And besides, they get their name on the papers and enjoy all the fame and glory that comes from publishing a well-prepared, carefully researched treatise on ruminant husbandry or, ahem, byzantine agreement.<br />
<br />
So what about the reviewers, whose names do not go up in lights? Yeah, they don't usually get paid either. Again, it's an expected part of their jobs. The editors? Nope. It is such an honor to be asked to edit a series or even a volume of these prestigious publications that members of that same research community (heck, let's just call it a teamspace) do it for free. So basically, all the intellectual heavy lifting required to produce one of these journals is born by the teamspace itself with little or no monetary compensation expected.<br />
<br />
The publishers keep all those $billions for themselves. But surely they provide some useful service, right? The answer is, they used to. In the old days, before the Internet, the publishers handled typesetting, copy editing, printing, distribution, and promotion (marketing). But today, either that stuff is being done by the teamspaces themselves (typesetting, copy editing, promotion) or simply isn't required anymore. We love the Internet! It makes things cheaper for us consumers and more readily available to all of us. Since the hard work of peer-reviewed publishing is being done free of charge by all those various teamspaces, and since printing and distribution costs have essentially disappeared, I bet you think those journals and the research papers they contain can be had for a song now. Right?<br />
<br />
Think again. A year's subscription to the Elsevier journal pictured above, just twelve issues, will <a href="http://store.elsevier.com/product.jsp?issn=07437315">cost a library about $1,200</a>. And that's the online cost! The publishers simply turn a switch to give you access to somebody else's hard work and they charge you $100 per month per journal for that. University libraries must buy hundreds, perhaps thousands of these subscriptions and most researchers have little choice in the matter because they are required by their employers to publish in certain journals. The kind of open access we've come to expect on the Internet doesn't exist for these types of works, because the publishers make the authors sign over copyrights, again without compensation. And then to pour salt on an already infected wound, the publishers spend some of that unearned revenue to lobby congress to pass vile, anti-competitive, anti-Internet laws with sickeningly misleading titles like the Research Works Act (RWA), the Stop Online Piracy Act (SOPA), and the Protect Intellectual Property Act (PIPA).<br />
<br />
To state the obvious, the international research community is composed of a bunch of really smart folks, and they won't allow this situation to persist for too much longer. Already, nearly 8,000 of them have signed a petition, a bill of rights really, called <a href="http://thecostofknowledge.com/">The Cost of Knowledge</a>, pledging to boycott Elsevier's publications. And there appears to be stirrings of a <a href="http://blogs.discovermagazine.com/crux/2012/02/21/its-not-academic-how-publishers-are-squelching-science-communication/">broader revolt</a> against this ridiculous status quo in the blogosphere.<br />
<br />
Most researchers agree that the only real value-add provided by the publishers in this scenario is to provide a framework in which peer review can take place. Not that they actually <i>do</i> the reviews, that's done by the peers themselves. But they provide a framework, a societal network where researchers on any particular topic can socialize, collaborate, swap critiques and comments, reach consensus about which papers to publish in a given issue, and recognize and honor those members who have contributed in a positive way to the body of knowledge. It turns out, reputation is big in academia. Does this framework sound familiar?<br />
<br />
The land of academic publishing will, almost inevitably, evolve into something like the Ethosphere. There's little doubt about this, in my opinion. To phrase it another way, an Ethosphere teamspace as I've described it in this blog is nothing more nor less than a topical, peer-reviewed, online publication without the parasitic middlemen.<br />
<br />
In the Ethosphere, perhaps knowledge needn't cost so much after all.Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com2tag:blogger.com,1999:blog-1039373877769915493.post-33737742005228103572012-03-06T11:59:00.005-06:002012-03-06T11:59:00.658-06:00A Random StorySo randomness and probabilities are inevitable parts of any discussion of distributed consensus. Just how comfortable are we with the fact that our daily choices must be guided, at least in part, by the laws of probability?<br />
<br />
When we get behind the wheel of an automobile or strap ourselves into an airplane seat, we are literally trusting our lives to the laws of probability. Since we can't know everything about the pilot of the airplane or the other drivers on the road with us, we wrap ourselves every day in the comfortable knowledge that, with high probability, we will survive to see another day.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://farm8.staticflickr.com/7155/6551148595_f24e135340.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="213" src="http://farm8.staticflickr.com/7155/6551148595_f24e135340.jpg" width="320" /></a></div>
<br />
<br />
But when it comes to computer programs and programmers, we are much more demanding. We expect computers to be deterministic. Period. They perform exactly the same instructions over and over and any deviation from that determinism we call a "bug" or a "fault." We demand that our family photos be kept safe even in the eventuality of multiple, byzantine faults. When you check yourself into a hospital, the chances that an accident or mistake will lead to the loss of your life are quite a bit higher than the chances that an accident or mistake will result in the loss of that kitty cat picture on Facebook. (Small caveat: I totally made that up.)<br />
<br />
The fact is, we accept that the universe is stochastic but demand that computers be deterministic. Here's a true story about how I once forced a customer of mine to face that bias and, I hope, start to change his attitude a bit.<br />
<br />
While I was at Caringo (they probably still do this) we would periodically conduct training classes for customers of our products, which includes CAStor, a scalable, distributed object storage solution. I would typically join the students and instructors for lunch one day to answer any technical questions they had about the products. During one such training class, I learned from the instructors that one of the students was being vocally skeptical about one of the foundational assumptions we had made in the product.<br />
<br />
CAStor can store billions, even trillions of distinct data objects, each of which has a universally unique identifier (UUID) associated with it. Other similar products on the market generate these UUIDs in a deterministic fashion that necessarily involves a central naming authority - an expensive and fragile solution IMHO. CAStor's innovation in this area was to instead use a large truly random number for these UUIDs, removing the requirement for a central authority and significantly simplifying the generation and management overhead.<br />
<br />
Using this mechanism, the chances that two distinct objects will be assigned exactly the same UUID are very, very, very (to the 42nd power) small. But it is possible and, of course, it would be a bad thing if it happened, which is exactly the objection being raised by our skeptical student. I mean, we're talking about computers here, and he expected a deterministic guarantee that such a collision is not possible.<br />
<br />
So I expected a question along these lines during our meet-the-architect lunch. But it didn't come. At the end of the lunch, after we'd all finished our deli sandwiches, I decided to bring up the topic myself. I went into the kitchen of our corporate offices and retrieved a wine glass that had been sitting on the top shelf collecting dust. Back in the training room, I tapped the glass with my pen to get everyone's attention and, without saying a word, placed the glass into my empty lunch sack, twisted it shut, and put it on the conference table. Then I picked up a heavy metal power strip and, again without a word to the class, pounded the sack with the power strip until the glass was thoroughly shattered.<br />
<br />
Everyone moved away from me there in the training room. The instructors, whom I hadn't warned about this, considered calling building security.<br />
<br />
After a brief pause for effect, I picked up the lunch sack and began shaking it vigorously. Then I asked, "Who here believes the glass will spontaneously reassemble itself if I keep shaking the bag?"<br />
<br />
No one answered. So I upped the ante.<br />
<br />
"What if I continue shaking it like this all day? All year?" Nobody answered.<br />
<br />
"What if I continue shaking the sack for the rest of my life? Who believes the glass shards will accidentally find their way back in the exact same configuration they started in to reform the wine glass?"<br />
<br />
Finally, the troublemaker student answered. He timidly said, "Well, it <i>could</i> happen."<br />
<br />
"Exactly," I said. "It could happen. And if any of you believe it actually will, I recommend you should not buy our product." And I left the room.<br />
<br />
I'm happy to report that our "troublemaker" student became a big believer in our product and is still a customer.Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-30141292557648684112012-03-04T11:59:00.104-06:002014-11-14T13:27:56.191-06:00Provably Probable Social ChoiceThere 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.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://images1.wikia.nocookie.net/__cb20120210203361/breakingbad/images/thumb/9/9d/1x02_-_Coin_flip.jpg/640px-1x02_-_Coin_flip.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="225" src="http://images1.wikia.nocookie.net/__cb20120210203361/breakingbad/images/thumb/9/9d/1x02_-_Coin_flip.jpg/640px-1x02_-_Coin_flip.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i style="font-size: medium; text-align: -webkit-auto;">Without a coin to flip, there is no safe way for independent entities to reach consensus!</i> </td></tr>
</tbody></table><br />
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).<br />
<br />
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:<br />
<ol><li>If all well-behaved processes have the same authentic value, then the global consensus value must be that value.</li>
<li>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.</li>
</ol>To make it more interesting, the problem allows for the possibility of <i>faulty</i> 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.<br />
<br />
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.<br />
<blockquote><i><u>Terminology note</u>: 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.</i> </blockquote>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.<br />
<br />
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 <b>no deterministic algorithm</b> 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.<br />
<br />
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 <a href="http://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem">Gibbard-Satterthwaite theorem</a> 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 <b>no deterministic algorithm</b> that will prevent even a single tactical voter from influencing the results of the election. Sound familiar?<br />
<br />
There is a more well-known, but in some ways less interesting, result in social choice called <a href="http://en.wikipedia.org/wiki/Arrow's_impossibility_theorem">Arrow's Impossibility Theorem</a> 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.<br />
<br />
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 <i>election transparency, </i>a very useful property of real elections.<br />
<br />
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 <i>Synchronous Byzantine Plurality</i>. 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.<br />
<div class="separator" style="clear: both; text-align: center;"></div><br />
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. <b>Without a coin to flip, there is no safe way for independent entities to reach consensus!</b>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-71581805864091489862012-03-03T11:59:00.000-06:002012-03-03T11:59:00.094-06:00Mobs, Teams, and Etho-Activism<p>With the right process and tools, a group of smart, hard-working people can be wiser and more productive than the sum of its parts.</p><p>A group of people can become a mob or a team.</p><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnqAXdAFd4v08jjIrSklEkbfe0OOGrMvnC6NCXztCPYYysV8PLY6sW26ZxeHthkUxbhNRbsjCqXCCVM5AyX98lC2JPQglciGB45WTbvmSAo6MxsAD8qb4kBP4o2FAYNZuUNXYt0sT9WlE/s1600/MobTeam.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="270" width="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnqAXdAFd4v08jjIrSklEkbfe0OOGrMvnC6NCXztCPYYysV8PLY6sW26ZxeHthkUxbhNRbsjCqXCCVM5AyX98lC2JPQglciGB45WTbvmSAo6MxsAD8qb4kBP4o2FAYNZuUNXYt0sT9WlE/s400/MobTeam.png" /></a></div><center><i>One of the first Slamball teams, the Chicago Mob</i></center><br />
<br />
<p>A mob is collectively motivated by fear, superficiality, and competitiveness. Mobs are <i>destructive</i>. There are many examples of mobs; the ones in the U.S. Congress are particularly dangerous today.</p><p>A team is collectively motivated by productivity, consensus, and respect. Teams are <i>productive</i>. I have made my career building highly functional teams out of smart, opinionated, socially and ideologically diverse individuals.</p><p>The difference between a mob and a team is the right process and tools to reward productivity, reason, and consensus and to discourage divisiveness, grandstanding, and indulgence.</p><p>The difference is the Ethosphere.</p><p>With the 2012 U.S. election year upon us, there will be a great deal of discussion about national politics over the next few months. If these discussions take place, as they typically do, in coffee shops, bars, and in comments on news web sites, nothing whatsoever will come of them. Yes, it'd be great if each of us would use such discussions to formulate and refine our views and then send the result to our representatives and electors. But who has the time for that? And it's only one voter's opinion anyway.</p><p>What if, instead, there were an easy way for you and a few of your like-minded friends to have those discussions online, capture the results, and automatically email your collective resolutions to the appropriate representatives? Now it's not just one voter's opinion, but 5 or 15 who agree on something.</p><p>Even better, invite some of your non-like-minded friends to the team. Diverse opinions make for more lively discussions and with the Ethosphere machinery leading you toward and rewarding consensus, your team's collective decisions will likely be more well-rounded and, ultimately, hold more weight with their intended audience.</p><p>It will be a while before Ethosphere becomes the de facto mechanism for cities, municipalities, or even neighborhood associations to deliberate and make decisions. In the mean time, the same sort of bootstrap strategy described above can be used to get a few people working together and sharing their results with the empowered decision makers.</p><p>Suppose you and your neighbors want the neighborhood park cleaned up or new art placed in the lobby of your building. All you need is to start a Ethosphere teamspace and send email invitations to a few of your neighbors. Someone drafts a simple document with the details, costs, etc., of the plan, and you all discuss, comment, and perhaps amend it until everyone agrees, and then the proposal is emailed to the HOA board. Next time an issue or request comes up, the same HOA teamspace can be used, a few more neighbors are invited to join, and pretty soon, most of the official business of the HOA is happening online in the most efficient, and least taxing way possible. The physical HOA meetings become a mere formality.</p><p>The Ethosphere is not about supporting existing political power structures like HOAs and municipal governments. It is about supporting the people who are disenfranchised by those existing institutions. The governance structures that have evolved in the physical world are archaic, time-consuming, and worst of all, exclusionary. The Ethosphere is specifically designed for the Internet as a single set of consensus mechanisms that scales to support online activism at all levels, from neighborhoods to nations.</p><p>The real target market isn't the HOA itself, it is the much larger group of folks who are annoyed or angry at their HOA boards but who don't have the time or organizational resources to do anything about it.</p><p>It's about <i>activism</i>, not governance, initially anyway. At first, <b>Ethosphere's authority will stop any time it bumps against a lawyer</b>. Existing bylaws and rules will not allow it to be used in any official capacity. But the solution to that is not to perpetuate these broken, non-scalable physical mechanisms. The solution is to support and encourage online activism around these official structures and let nature take it's course. If it works as well as I think it will, then somebody will soon write a set of bylaws that will grant Ethosphere teamspaces legal authority as governance mechanisms at some level.</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-36282923977410956872012-03-02T11:59:00.001-06:002012-03-02T11:59:00.290-06:00Privacy Through Multiplicity<p>Internet privacy is a big deal and will become an even bigger deal as web-based software to track clickstreams and collect personal information continues to become more effective. As an Internet user, I don't want web sites to be able to conspire to build and maintain a complete picture of my online activities. I want to be able to protect personal information about myself (e.g., credit card #, home address, business email, demographic info) from the prying eyes of web sites that I may casually visit. It would seem that Ethosphere would provide the ultimate in user privacy, since the privacy directive prevents a web site administrator (or anyone else) from discovering the true identity of a persona. However, this may not be enough.</p><div class="separator" style="clear: both; text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/Barack_Obama_inauguration_party_crowd.jpg/320px-Barack_Obama_inauguration_party_crowd.jpg" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="213" width="320" src="http://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/Barack_Obama_inauguration_party_crowd.jpg/320px-Barack_Obama_inauguration_party_crowd.jpg" /></a></div><p>Suppose I always use the same persona, named @UncleAlbert, within Ethosphere. During the day, @UncleAlbert works as a trusted financial advisor, but he is also interested in hang gliding and, being a single person, occasionally hangs out in a singles-only online club. @UncleAlbert also buys books from amazon.com, rents movies from netflix.com, and he owns a laptop he bought on ebay.com. By simply tracking @UncleAlbert's interests and activities on the Internet, an observer could learn a great deal about the person who "owns" @UncleAlbert in RL. The privacy directive would not allow disclosure of the person's real home address or age or gender, but it would still allow some pretty powerful inferences to be made regarding his or her lifestyle and buying habits.</p><p>Within the Ethosphere, this sort of inference-by-clickstream invasion of privacy could easily be thwarted by simply using many different personae. For example, if I create a new persona each time I log on to the network (assuming persona creation is cheap and easy), there would be no way for anyone to connect the behavior of one persona with any of the others, and each persona would therefore be completely anonymous. Unfortunately, this strategy would also make any kind of long term relationship, including business and commerce, impossible. Who would trust or choose to associate with an anonymous persona? <b>Privacy is not the same as anonymity.</b></p><p>It is necessary, it seems, for personae to have associated, recognizable characters or personalities that persist across logins. Nobody would trust financial advice from @UncleAlbert (nor be willing to pay for it) without some kind of credentials or track record that indicates he knows what he's talking about. Moreover, if the system maintains that reputation and provides it to clients or even competitors in the financial community, this doesn't really seem to raise any privacy concerns (even though it might possibly be professionally harmful to @UncleAlbert). If a client chooses to record some praise or criticism of Al's work, it seems fair to @UncleAlbert and to other clients and potential clients that this bit of information be made available to them. On the other hand, if the system maintained and provided information about @UncleAlbert's other interests, say hang gliding, to clients or competitors, this does seem to violate reasonable privacy expectations (even though it might not harm @UncleAlbert in any way).</p><p>There is a basic tension between maintaining a persona's privacy and its identity. It may be that the best compromise is to compartmentalize one's personality and create several personae, each one representing an independent aspect of the real person. If @UncleAlbert is my financial advisor persona, then perhaps @buzz represents the hang glider enthusiast and @rex is the wild and crazy single guy. Each of these three personae might be individually known, recognized, and perhaps trusted in three separate socio-economic contexts, without compromising the privacy of any of them or their common owner.</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-28250005340017683922012-03-01T11:59:00.017-06:002012-03-01T11:59:00.288-06:00Voting Variants - Harmonic Range Voting<p>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.</p><p>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.</p><p>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.</p><h3>Protection of Minorities</h3><p>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.</p><p>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.</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com5tag:blogger.com,1999:blog-1039373877769915493.post-47820221469994382382012-02-29T11:59:00.049-06:002012-02-29T11:59:00.819-06:00Building Ethos Out of Logos<p>The Ethosphere, in addition to preserving the privacy of the personae within it, should also be responsible for maintaining a sort of interaction history for them. Over time, this interaction history comes to represent the character or <i>ethos</i> of the individual persona. Ethos is one of the three elements of Aristotle's theory of rhetoric, and it means appealing to a speaker's character or reputation. This is where Ethosphere gets its name. Aristotle's other two elements, logos and pathos, refer to appeals to logic and emotion, respectively.</p>
<p>Lacking any connection with the real world credentials of a persona's owner, its ethos becomes an important factor in almost every interaction with other personae. Any trust relationships that evolve over the lifetime of a persona will be based on the persona's ethos. Whether or not @uncle_albert can find work as a financial advisor as well as how much he is able to charge for his advice all depend on how successful and honest he has been in past financial transactions with other persona. In many ways, a persona's ethos embodies and denotes its identity more so than its alias. As in RL, one can imagine a persona changing its name to something completely different and yet still being recognizable solely by its ethos.</p>
<p>Importantly, a persona's ethos, or rep as we've previously called it, is not directly manipulable by the persona, but rather it is maintained by Ethosphere based upon the persona's history of constructive interaction within a teamspace. "Constructive interaction" can mean all sorts of things, but here's a brief set of examples that hopefully help clarify the specifics of what I mean.</p>
<h3>Rep Transactions</h3>
<p>These example transactions may influence an alias's rep within a teamspace. A rep is a single floating point number that represents a member's ethos within a given teamspace. I will use the term <i>rep share</i> or simply <i>share</i> to mean a single point, 1.0, of rep for a member.</p>
<p>Note that any transaction where one or a few members can cause another's rep to be bumped or busted always comes at a cost to the members initiating the transaction. This is called a <i>share transfer</i> and it's implemented this way to guard against members colluding to artificially inflate or deflate the reps of others. Transactions that result from consensus of all the members of a teamspace do not have a cost associated for the voting members, but rather result in some number of new rep shares being created. These are called <i>share grants</i> and they will generally result in dilution of every member's rep share, just like issuing shares of corporate stock or additional currency.</p>
<p>Any member can put up a prop. There is no cost or reward associated with doing so. Likewise, any member can write a comment on a prop being considered for ratification. Rep shares are earned only when others in the teamspace recognize a positive contribution to the team. In rare cases, rep may also be lost when others reprimand a negative or destructive activity.</p>
<dl>
<di><b>Teamspace Creation (+20 share grant)</b></di>
<dd>When a teamspace is initially created, its founders receive an initial grant equivalent to the "founders' shares" of stock commonly issued in private corporations. This has the effect of bootstrapping the rep system within a teamspace since, as you may have noticed, nothing can happen in an Ethosphere teamspace unless there is at least one reputable member to vote and Like other other members' work. If there are multiple founders of the teamspace, the founders' rep shares will be divided equally among them.</dd><br />
<di><b>Prop Acceptance (+5 share transfer)</b></di>
<dd>Once a prop has been published by any member, there is a relatively short period of time during which other members can choose to accept the prop for consideration by the larger membership. Acceptance of a prop does not imply it has been adopted by the teamspace, but rather that some reputable member has declared it worth the effort to read and evaluate. There is no penalty involved if a member puts up a prop that is not accepted. It costs 5 rep shares to accept a prop. These shares can come from one or several members. If there are several, the cost of acceptance is shared amongst them. Upon acceptance, the sponsor of the prop receives 5 rep shares in recognition of his/their work. If there are several sponsors, the 5 shares are divided evenly among them. A member cannot vote to accept a prop unless it has a non-zero rep share. A member may choose to accept its own prop, thereby essentially paying for consideration of the prop. However, if any member who votes for acceptance is also a sponsor of the prop, then no sponsor receives any rep share benefit from the acceptance; only the cost is incurred.</dd><br />
<di><b>Comment Like (+1 share transfer)</b></di>
<dd>A member can "like" another member's comment on an accepted prop. One rep share is transferred from a reputable "liker" to the "commenter." Although the potential reward for sponsoring a prop may seem much higher than for writing a comment, one would expect commenting to be the most important mechanism for building reputation within most teamspaces. That's because a single well-thought out and well-phrased comment can be "liked" by many members, costing each of them only one share but accumulating perhaps significant rep for the commenter.</dd><br />
<di><b>Comment Dislike (-1 share transfer)</b></di>
<dd>A member may also "dislike" a comment written by another member if they disagree with the comment or feel it is unfair in some way. As with the comment "like", the member who expresses its dislike of another's comment is charged one rep share, but here the commenter is also charged one share.</dd><br />
<di><b>Comment Censor (-1 share transfer)</b></di>
<dd>A censor works just as a dislike, but in addition a vote is cast to remove the comment altogether and replace it with a short statement to the effect that the comment was deemed unsuitable. If there are a sufficient number of such votes (say, 5), the comment is censored and removed by the teamspace.</dd><br />
<di><b>Prop Ratification (+20 share grant)</b></di>
<dd>If a prop is ratified by the team, as many as 20 new rep shares may be granted to the sponsor(s) of the prop. There is no penalty if a prop is not ratified within the allotted time period. If there are multiple co-sponsors, the granted shares will be divided equally among them. The actual number of rep shares granted depends on the outcome of the ratification vote. If the prop was ratified unanimously, the sponsor(s) will receive the full 20 rep shares. If it was ratified with only a 51% majority of the total teamspace rep, the sponsor(s) will only receive 51% of the 20 shares, or 10.2 rep shares.</dd>
</dl>
<p>This simple framework could result in a robust reputational economy within active teamspaces, with reputation being transferred from older, more established members to newbies, and new reputation being created as fresh members begin to collaborate and write new props. It may also be desirable to allow reps to decay over time in order to ensure current participation and reduce the impact of highly reputable members who disappear unexpectedly, perhaps because of a RL calamity of some sort.</p>
<h3>Dictators and Ruling Parties</h3>
<p>Initially, the founder of a new teamspace is the only member with rep shares. He is therefore a dictator, and nothing can happen within the teamspace without his vote and approval. One could imagine someone deliberately hogging all the power by never Liking anyone else's work and never voting to ratify anyone else's Props. Although this is possible within the Ethosphere, it doesn't seem very likely to happen because such a teamspace would be singularly boring for pretty much everybody. All the dictator's "subjects" would simply leave and go join a more vibrant, balanced teamspace someplace else and the dictator would be left with, essentially, an over-complicated personal blog.</p>
<p>Similarly, you can envision a sub-group of members who agree to form a ruling clique, Liking only each other's work and ratifying only each other's Props. Again, this would be pretty uninteresting for those members who are not in the ruling party, and they would just leave unless there were some external reward, like receiving a paycheck, for their continued contribution to the teamspace.</p>
<p>As undemocratic and dysfunctional as these unbalanced power structures may seem at first, there are many RL organizations in which such lopsided teams are common, and highly functional. For example, open source software projects often have "benevolent dictators," high-rep individuals who have disproportionate influence in approving designs and code contributions contributed by other members. The bylaws of commercial corporations typically create a hierarchy of ruling classes, the board of directors, the compensation committee, the executive team, etc., within those teamspaces.</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com7tag:blogger.com,1999:blog-1039373877769915493.post-9900755314081522702012-02-28T11:59:00.007-06:002012-02-28T11:59:00.492-06:00Voting Variants - Range Voting<p>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.</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://encrypted-tbn3.google.com/images?q=tbn:ANd9GcSNnbPIQ9gMGaYRiAy3TMZb1SYI1GneapmZqTSWrm2r-u83zvZtVQ" imageanchor="1" style="clear:right; float:right; margin-left:1em; margin-bottom:1em"><img border="0" height="202" width="249" src="https://encrypted-tbn3.google.com/images?q=tbn:ANd9GcSNnbPIQ9gMGaYRiAy3TMZb1SYI1GneapmZqTSWrm2r-u83zvZtVQ" /></a></div>
<p>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.</p>
<h3>Pros and Cons</h3>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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 <b>nobody's first choice.</b></p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com2tag:blogger.com,1999:blog-1039373877769915493.post-44655608729863117682012-02-27T11:59:00.026-06:002019-02-19T12:50:47.466-06:00I'm Not Elitist, Just Better Than You<div class="separator" style="clear: both; text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/James_Madison.jpg/220px-James_Madison.jpg" imageanchor="1" style="clear:left; float:left;margin-right:1em; margin-bottom:1em"><img border="0" height="268" width="220" src="http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/James_Madison.jpg/220px-James_Madison.jpg" /></a></div><p>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.</p><p>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 <a href="http://en.wikipedia.org/wiki/Electoral_College_(United_States)">electoral college</a> 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 <a href="http://en.wikipedia.org/wiki/Federalist_Papers">series of props</a> published by a highly reputable, pseudonymous author whose alias was @publius.</p><p>In <i>The Federalist</i> #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.</p><blockquote><i>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.</i> </blockquote><p>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... <blockquote><i><p>...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.</p>-- The Federalist #10 </i> </blockquote><p>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?</p><p>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.</p><p>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.<br />
</p>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.</p><blockquote><i><p>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.</p>-- The Federalist #1</i> </blockquote>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-84178451974132243032012-02-26T11:59:00.036-06:002012-02-26T12:59:10.930-06:00Voting Variants - Instant Runoff Voting<p>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.</p><p>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.</p><p>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.</p><h3>Pros and Cons</h3><p>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. <a href="http://en.wikipedia.org/wiki/Duverger%27s_law">Duverger's Law</a>, 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.</p><p>Of the dozen or so <a href="http://en.wikipedia.org/wiki/Voting_system">standard criteria</a> 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.</p><p>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.</p><p>An equally serious practical drawback for this method is its subjective impact on transparency of an election. Explaining <i>why</i> 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."</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com0tag:blogger.com,1999:blog-1039373877769915493.post-60393362122992549972012-02-25T11:54:00.001-06:002012-02-25T12:30:14.507-06:00Attack!<p>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 <a href="http://persons.unik.no/josang/papers/JG2009-STM.pdf">some research</a> 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.</p>
<h3>Sybil Attacks</h3>
<p>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.</p>
<p>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.</p>
<h3>Collusion</h3>
<p>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.</p>
<p>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 <i>should</i> be a valid consideration.</p>
<h3>Persona Breaks</h3>
<p>This exploit is sometimes called a <i>playbook attack</i>. 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.</p>
<p>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.</p>
<h3>Re-Entry</h3>
<p>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.</p>
<h3>Denial of Service (DoS) Attacks</h3>
<p>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.</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com4tag:blogger.com,1999:blog-1039373877769915493.post-26796850601187164422012-02-24T11:39:00.010-06:002012-02-24T12:06:32.586-06:00Do We Have Consensus?<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpPrhyphenhyphenrU6-aeZiw1aSa5ax6A2wk3balHHldrE_Pg5kGPVGRKO87cF8jwRxRQvIlhUKOQ6wYed1fzF5AdMKG71zjOaJekT8Amw0bAD6MRx2NkuMEJv7rhYM_xsklY-XHASnIKGF5oNMdqw/s1600/ShakingHands.png" imageanchor="1" style="clear:left; float:left;margin-right:1em; margin-bottom:1em"><img border="0" height="160" width="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhpPrhyphenhyphenrU6-aeZiw1aSa5ax6A2wk3balHHldrE_Pg5kGPVGRKO87cF8jwRxRQvIlhUKOQ6wYed1fzF5AdMKG71zjOaJekT8Amw0bAD6MRx2NkuMEJv7rhYM_xsklY-XHASnIKGF5oNMdqw/s200/ShakingHands.png" /></a></div>
<p>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.</p>
<p>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.</p>
<p>In particular, the Ethosphere improves upon many other social choice systems in at least four major ways:
<ol>
<li><b>Voting Algorithms</b> - We will choose a voting method that is less susceptible to strategic/dishonest voting and fairer with respect to minority opinions.</li>
<li><b>Rational Representation</b> - Member reputation provides an excellent opportunity to balance the need for involved, knowledgeable electors with a fully-participatory, direct democracy.</li>
<li><b>Protection of Minorities</b> - 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.</li>
<li><b>Transparency </b> - Every vote can be examined and audited by any member.</li>
</ol></p>
<h3>Voting Algorithms</h3>
<p>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 <i>majority</i> 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.</p>
<p>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.</p>
<p>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.</p>
<p>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 <i>the</i> worst possible choice.</p>
<p>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 <a href="http://www.fairvote.org">www.fairvote.org</a> and <a href="http://www.rangevoting.org">www.rangevoting.org</a> which are maintained by the respective advocacy groups.</p>
<p>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.</p>
<h3>Strategic Voting</h3>
<p>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 <a href="http://en.wikipedia.org/wiki/Arrow's_impossibility_theorem">Arrow's Impossibility Theorem</a> which essentially says <i>all</i> 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.</p>
<p>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.</p>Jim Duttonhttp://www.blogger.com/profile/06293311386552614976noreply@blogger.com4