In popular culture, there is much talk of social networks. Indeed, Facebook, Twitter, Foursquare, and Linkedin areÂ ubiquitous – how did we ever live without them?

One interesting property of these social networks or social graphs that isn’t talked about much is the concept of Majority Rule. While I haven’t seen much written about Majority Rule in social networks, we have all used the tools available to us: For Facebook, they have the Like button. For Twitter, there is the Retweet. For Digg, there’s the Digg button. And the same goes with every other tech company and their acquisitions.

One important note: votes can be explicit votes, such as the examples above. But, there are implicit votes also, such as how many times a YouTube video has been seen.

For Foursquare, the check-in can be both explicit and implicit. For example, when I take the kids to the park, my reason is to spend time with the kids. But, while I’m there I can choose to check-in.

But, there are cases where one chooses to go to a specific location for the sole purpose of checking-in. In that case, I consider that explicit. I imagine the commercial viability of Foursquare lies in the explicit check-in: purposely going to a location to check-in, then receive some reward from the place visited (coupon or whatever).

For the purposes of this post, we’re only talking about explicit votes.

So, how does Majority Rule work in a social system?

## The Physical World: Majority Rule and Social Graph

In the physical world, majority rule systems appear in electing government representatives, board of directors approval of new policies, and other like instances.

One property that exists in the physical world, but not so much in virtual social graphs, is that the members of the group involved in some voting process are to support and sustain the majority rule.

For example, if a government representative wins from a democratic process and obtains the majority of the votes, he or she wins. Â As a member of that group, I am to sustain and support that person, if I choose. Â What I don’t have control over, however, is that I become a recipient of that person’s decisions, such as the legislation of a new law.

Indeed, majority rule in the physical world means that we are affected in very real ways.

## The Virtual World: Majority Rule and Social Graph

Well, for virtual social graphs such as the Twitter or Facebook, if a majority rule is achieved, there is no contract to compel the members of that group to follow the majority rule. For example, as a member of the broad community of Facebook, if a fan page is Like’d 500 times, I have a choice to like or not to like. And, just because something is like’d a gazillion times, it still has no tangible affect on me.

What a majority rule does do, for me, is pique my interest. It createsÂ curiosity and, if I choose to clickthrough to the thing that has achieved majority rule (majority like’d or majority retweeted), then I might receive some utility such as laughter, entertainment, or joy.

So, what is it exactly that makes Majority Rule work in social systems?

## Properties of Majority Rule

There are three main properties of Majority Rule Systems:

**Option Equality**: The characteristics of choice A and choice B are the same. Â If the same amount of people vote for choice A, the results will switch.**Voter Equality**: Voter equality means that no personâ€™s vote is more influential than that of anotherâ€™s vote.**Sensitivity**: Sensitivity means that if the voting is tied and one more person votes, then the option he votes for wins.

One major presupposition in the notion of majority rule is that of choice. Social scientists call the method of choosing a social choice function. A social choice function is a rule for choosing between options where some of the citizens prefer one option and others prefer the other.

The majority rule system chooses one option over another when more citizens prefer the one option than the other. From this we get the definition of a social choice function (SCF):

SCF: C is a social choice function for options a and b and citizens V iff aâ‰ b, and V is finite and non-empty, and for all disjoint subsets A and B of V, C(A, B) equals {a} or {b} or {a, b}.

We also get the definition of the majority rule social choice function:

mrSCF: C is a majority rule social choice function for options a and b and citizens V iff C is a social choice function for options a and b and citizens V, and for all disjoint subsets A and B of V, C(A, B)={a, b} if Aâ‰ˆB, C(A, B)={a} if A>B, and C(A, B)={b} if B>A.

In addition to the definition of majority rule social choice function, we should formalize the definitions of the three properties of majority rule.

**Option Equality** (OE) can be defined thus:

OE: C satisfies option equality for options a and b and citizens V iff for all disjoint subsets A and B of V, C(A, B)={a} iff C(B, A)={b}.

**Voter Equality** (VE) can be defined as the following:

VE: C satisfies voter equality for options a and b and citizens V iff for all disjoint subsets A and B of V, if Aâ‰ˆB, then C(A, B)=C(B, A).

**Sensitivity **(S) can be formalized as follows:

S: C satisfies sensitivity for options a and b and citizens V iff for all disjoint subsets A and B of V, if C(A, B)={a, b}, then for every non-empty subset X of V-(AâˆªB), C(AâˆªX, B)={a}.

Now, let’s prove that Majority Rule satisfies the three properties above. In other words,

Theorem: C is the Majority Rule social choice function for options a and b and citizens V iff C is a social choice function that satisfies Option Equality, Voter Equality, and Sensitivity for options a and b and citizens V.

## Majority Rule – Proof

To prove this theorem, I must proceed in two phases. The first phase will contain the three properties of majority rule. The second phase will contain the three conditions of majority rule social choice function.

### Phase I

1.1 (OE) C(A, B)={a} iff C(B, A)={b}

1.2 (VE) If Aâ‰ˆB, then C(A, B)=C(B, A)

1.3 (S) If C(A, B)={a, b}, then for every non-empty subset X of V-(AâˆªB), C(AâˆªX, B)={a}

### Phase II

2.1 C(A, B)={a, b} if Aâ‰ˆB

2.2 C(A, B)={a} if A>B

2.3 C(A, B)={b} if B>A

The framework I’ve set-up allows me to show how the elements in Phase I satisfy the elements in Phase II. To do this, I will assume the elements in Phase II and prove the elements in Phase I.

Similarly, I need to show how the elements in Phase II satisfy those in Phase I. To do this, I will assume the elements in Phase I and prove the elements in Phase II.

I can prove the theorem this way because it is a bi-conditional statement (principle of transitivity). That is, if I assume the left-hand side, the right-hand side should follow. Similarly, if I assume the right-hand side, the left-hand side should also follow.

By showing how Phase I and II prove each other, I will ultimately show that the majority rule social choice function does satisfy option equality, voter equality, and sensitivity and hence demonstrate fairness and effectiveness.

**Phase I : 1.1**

Show that C(A, B)={a} iff C(B, A)={b}.

Proof: Assume that C(A, B)={a}; show C(B, A)={b}. If Aâ‰ˆB, then C(A, B)={a, b}. If B>A, then C(A, B)={b}. By process of elimination and cases, since C(A, B)={a}, A>B. So, C(B, A)={b}. Now, assume the other side of the bi-conditional, i.e., C(B, A)={b}; show C(A, B)={a}. If Aâ‰ˆB, then C(A, B)={a, b}. If A>B, then C(A, B)={a}. By cases and process of elimination, B>A. So, C(A, B)={a}. Q.E.D.

**Phase I : 1.2**

If Aâ‰ˆB, then C(A, B)=C(B, A).

Proof: Assume Aâ‰ˆB; show C(A, B)=C(B, A). So, C(A, B)={a, b}. Also, C(B, A)={a, b}. Hence, C(A, B)=C(B, A). Q.E.D.

**Phase I : 1.3**

If C(A, B)={a, b}, then for every non-empty subset x of V-(AâˆªB), C(AâˆªX, B)={a}.

Proof: Assume C(A, B)={a, b}; show that for every non-empty subset X of V-(AâˆªB), C(AâˆªX, B)={a}. Since Xâ‰ âˆ… and xâŠ†(V-(AâˆªB)), AâˆªX>A. If A>B, then C(A, B)={a}.

If B>A, then C(A, B)={b}. So, by the process of elimination and cases, since C(A, B)={a, b}, Aâ‰ˆB. Hence, AâˆªX>B. Consequently, C(AâˆªX, B)={a}. Q.E.D.

Thus, by proving Option Equality, Voter Equality, and Sensitivity, I have shown that they are derived from the notion of majority social choice function. But I am only halfway finished.

I now need to prove the elements in Phase II. Remember, that in doing so, I will be assuming the elements in Phase I.

**Phase II :Â 2.1**

If Aâ‰ˆB, then C(A, B)={a, b}.

Proof: Assume Aâ‰ˆB; show C(A, B)={a, b}. Since Aâ‰ˆB, by voter equality I get C(A, B)=C(B, A). Also, bear in mind the definition of a social choice function, namely, that C(A, B) must equal {a} or {b} or {a, b}. By option equality, C(A, B)={a} iff C(B, A)={b}. Yet, {a}â‰ {b}. So, C(A, b)={a, b}. Q.E.D.

**Phase II : 2.2**

If A>B, then C(A, B)={a}.

Proof: Assume A>B; show C(A, B)={a}. Sensitivity claims that if C(A, B)={a, b}, then for every non-empty subset X of V-(AâˆªB), C(AâˆªX, B)={a}. Let Aâ€™ be a subset of A such that Aâ€™â‰ˆB. Accordingly, by Phase 2.1, I get C(Aâ€™, B)={a, b}. So, C(A, B)={a}. Q.E.D.

**Phase II : 2.3**

If B>A, then C(A, B)={b}.

Proof: Assume B>A; show C(A, B)={b}. Sensitivity dictates that if C(A, B)={a, b}, then for every non-empty subset X of V-(AâˆªB), C(AâˆªX, B)={a}. Let Bâ€™ be a subset of B such that Aâ‰ˆBâ€™. By Phase 2.1, I get C(Bâ€™, A)={a, b}. But this means that C(B, A)={a}. So, by option equality, C(A, B)={b}. Q.E.D.

## Conclusion

We have proven both phases. The Majority Rule Social Choice function satisfies option equality, voter equality, and sensitivity. By satisfying these three properties, the majority rule proves to be both fair and effective.

Julien Couvreur says

Since you’re on this topic, you would probably be interested in Arrow’s impossibility theorem: http://en.wikipedia.org/wiki/Arrow's_impossibility_theorem

Greg says

Hey Pete, I enjoyed your abstraction of the notions of equity and sensitivity, and their logical equivalence with a majority rule social choice function. Just wondering if this couldn’t be proved slightly more easily with some different notation. I’m thinking the following: C is a function that returns the max of |A| and |B|. This set function which is essentially just \maximum\ then \obviously ;)\ respects switching the names of A and B, gives each voter 1 vote, and breaks ties according to a single vote. Conversely any set function which respects switches of names, gives each voter 1 vote, and breaks ties by a single vote is a maximum checker. To prove the claim in that sentence suppose it did something besides return the max of |A|and |B|, in which case it returned the min. Then in the event of a tie, you’d add one vote to, say A, declare it the winner, and then max would win, a contradiction. Am I missing something? In any case, great post. Love to see this type of high quality blogging on the ‘net. Regards. GP

Pete Abilla says

@Greg – I think you’ve found the Wittgenstein-ian (P and ~P) in my argument. Thanks for the feedback. How would you make my argument more cogent?

Jeff says

Hi, Pete

I confess to accepting your logic as correct without close examination because I want to mess with assumptions a bit, specifically that “voter equality” in these circumstances may be assumed socially optimal. You may have followed Errol Morris’s recent series of thought-provoking articles in the New York Times in which, among other things, he considers the “Dunning-Kruger” effect. Loosely put, D-K assert that empirical evidence shows that those who know less about a particular topic more greatly over-estimate what they know than those who know more (who over-estimate, too, just less). It seems to me that many large-scale internet-based voting systems are ripe for the kinds of problems caused by thought- and effort-free consideration by legions of those who know less. (If D-K effects are strong, this is a big problem for democracy based on first-past-the-post voting.)

So, what might we do instead? Leaving aside democracy, can we find ways to sieve for more knowledgeable opinion about trivia in large data sets without a priori insight into what constitutes knowledge? Perhaps surprisingly, the answer is yes – for certain kinds of data collected in certain ways – through use of cultural consensus analysis. CCA doesn’t work all that well for questions of personal preference but it’s Aces for characterizing shared perceptions of a thought world.

CCA is a relatively recent addition to cognitive anthropology, initially worked out to help put ethnographic field research on a more Western scientific basis. Notionally, CCA allows a researcher to tap information in patterns of response across respondents. In addition to culturally correct answers to each question (a cultural answer key), CCA provides a scalar estimate of each respondent’s cultural expertise.