Tag: O(log n)

Using text analytics to prevent O(log n) failure of democratic institutions

In this article, we discuss an Achilles’ heel present in many democratic institutions.  We claim that many democratic institutions can be made to fail in ‘log n’ time (exponentially fast) if patronage (nepotistic) networks are allowed to grow unfettered.

We then support the claim using real-world examples of the failure of democratic institutions (political and otherwise) and discuss why such failure has not been observed in polity in India.

We also look at how text analytics can be used to detect (and consequently enable steps to be taken to prevent) such failures.

The Weakness

In democratic institutions, voting mechanisms are used to confer upon one individual (from a field of eligible candidates), powers and responsibilities as specified in the charter of the institution.

In some cases, the powers that accrue to the elected individual are so great that they enable him to use them to ensure his or her re-election.  There are two methods available to such an individual.

The first is to pay off the electoral college and secure re-election.  This method is an O(n) algorithm.  The quantum of resources required to secure re-election is proportional to the number of people who need to be suborned.  So, this method only works in cases where electoral colleges are small (for example, in the case of committees deciding job appointments).

A faster method of suborning large numbers of people exists.  The establishment of a hierarchy of patronage can leverage the dynamics of social networks to speedily (in log n time) corrupt very large numbers of people.

It works like this:  The person who is elected to head the country appoints as immediate subordinates only people who are on account of tribal or ethnic affiliations expected to be loyal to him/her. This appointment is often accompanied by a monetary exchange in the form of a bribe paid by the appointee to secure the post.  Such a monetary exchange helps cement the loyalty since the person making the payment becomes dependent on their superior’s continuation in power to recoup the money spent. In other words, the immediate subordinates are forced to invest in their superiors’ careers.

The subordinates so appointed in turn appoint people loyal to themselves to positions below them, in order to recover their investment in the person above them and so on.  Very soon, the entire government machinery becomes beholden directly or indirectly to the person at the top for their jobs and has a vested interest in keeping the person at the top in power.

In some countries, this effectively transforms the democratically elected ‘president’ into a dictator for life. 

Example 1

The first example of such failure is possibly (and I am just illustrating a point – no disrespect intended) the government of Cameroon.  The President of Cameroon has been in power since the 1980s.  The President is impossible to replace in spite of rampant corruption and economic mismanagement because all the tribal chiefs and officials in Cameroon are beholden to the President.

All these officials and chiefs try and recoup their investment by rent-seeking behavior (you will need their good offices if you wish to do any business in Cameroon).

The resulting economic climate doesn’t necessarily encourage the growth of entrepreneurship or investment in Cameroon.

Example 2

Iraq for many years was ruled by a dictator who had managed to suborn an entire political system.  Iraq once had a participatory democratic system.  But the use of patronage by Saddam led to Iraq coming under totalitarian rule.

Similar failures can be seen in post WW2 Libya and Syria, and in Stalin’s Russia.


One common feature of many of the countries where such failure has occurred is that they have hierarchical social structures in which respect and obedience can be commanded by people higher in the hierarchy from people lower in the hierarchy.

Cameroon has a culture of veneration of elders and tribal leaders.  So do the countries of the Arab world.

India also has somewhat similar cultural traits.  So, it is very interesting to see that a similar process of deterioration of democracy has not been observed in India.

One explanation is that India was saved by its own heterogeneity.  India is made up of distinct linguistic regions and ethnic groups.  It would be impossible for tribal and ethnic hierarchies to span India’s many linguistic and ethnic boundaries.

So, even if one province has failed, that would not trigger failure in neighboring provinces, and the regional despot would not be strong enough to change the Indian constitution.

Examples of such failure can arguably be observed to have happened already in Karnataka and in Tamil Nadu.  In Karnataka, a couple of mining barons managed to become ministers in the government and managed to exercise a lot of control over it for a number of years. Had Karnataka been an independent political entity, they might at some point have attempted to change the constitution to give themselves more power and possibly unlimited tenure.

In the state of Tamil Nadu, the ruling politicians are suspected of building patronage networks around themselves in order to facilitate rent-seeking behaviour.  If Tamil Nadu had been an independent political entity, I suspect that it might have lost its democratic character, since the number of people below the Chief Minister with a vested interest in keeping him/her in power would have become too big to permit free and fair elections to take place.

But what is interesting is that in India, though democracy could have failed at the level of the states (controlled by politicians who had suborned a large part of the mechanism of government) the possible failure did not take place or proved reversible.  That is probably because no kinship networks extend to all parts of India.

The fragmentation must have protected the constitution and the electoral system.  That in turn allowed constitutional and legal frameworks and electoral politics to correct the failures.

In Karnataka, the corrupt mining barons and the Chief Minister who supported them ended up behind bars.  In Tamil Nadu, some family members of the corrupt Chief Minister ended up behind bars.  In both states, the parties that had engaged in corruption were voted out of power.

So, failure through networks of patronage might be difficult to engineer in India because of the extremely heterogeneous nature of its society (a result of size and diversity).


Why would someone intending to build a patronage network only elevate kith and kin to positions of power?

As in, why did the dictators in Iraq and Syria choose to pack the governing organizations with people from their own community or tribe?

One possible answer emanates from the work of George Price (http://www.bbc.co.uk/news/magazine-24457645), who showed that altruism exhibited towards close relatives can have concrete benefits for a selfish individual.

I quote from the article:

Price’s equation explained how altruism could thrive, even amongst groups of selfish people.

It built on the work of a number of other scientists, arguably beginning with JBS Haldane, a British biologist who developed a theory in the early 1950s. When asked if he would sacrifice his own life to save that of another, he said that he would, but only under certain conditions. “I would lay down my life for two brothers, or eight cousins.”

Here is the Wikipedia page describing the Price equation (http://en.wikipedia.org/wiki/Price_equation).

So, it is possible that the elevation of kith and kin minimizes the possibility that the people so elevated might one day turn against their patron (they might be more likely to exhibit non-selfish behavior towards their patron).

Detection using Text Analytics

One is tempted to ask whether it is possible to detect at an early stage the process of failure through patronage of a democratic system.

The answer is yes.  It appears to be possible to build a protective mechanism that can uncover and highlight the formation and growth of nepotistic patronage networks.

The BBC article on nepotism in Italy examines research on the detection of nepotism in Italy, and I quote:

Prof Perotti, along with others, has published revealing studies of university teachers, showing the extraordinary concentration of surnames in many departments.

“There is a scarcity of last-names that’s inexplicable,” says fellow academic, Stefano Allesina. “The odds of getting such population densities across so many departments is a million to one.”

Take the University of Bari, where five families have for years dominated the dozens of senior positions in Business and Economics there. Or consider the University of Palermo, where more than half the entire academic population has at least one relative working within the institution.

I happened to find one of Allesina’s papers titled “Measuring Nepotism through Shared Last Names: The Case of Italian Academia” on the internet.

Here it is:  http://www.plosone.org/article/info:doi/10.1371/journal.pone.0021160

I quote from the paper:

Both types of analysis (Monte Carlo and logistic regression) showed the same results: the paucity of names and the abundance of name-sharing connections in Italian academia are highly unlikely to be observed at random. Many disciplines, accounting for the majority of Italian academics, are very likely to be affected by nepotism. There is a strong latitudinal effect, with nepotistic practices increasing in the south. Although detecting some nepotism in Italian academia is hardly surprising, the level of diffusion evidenced by this analysis is well beyond what is expected.

Concentrating resources in the “healthy” part of the system is especially important at a time when funding is very limited and new positions are scarce: two conditions that are currently met by the Italian academic system. Moreover, promoting merit against nepotistic practices could help stem the severe brain-drain observed in Italy.

In December 2010, the Italian Parliament approved a new law for the University. Among other things, the new law forbids the hiring of relatives within the same department and introduces a probation period before tenure. The analysis conducted here should be repeated in the future, as the results could provide an assessment of the efficacy of the new law.

This analysis can be applied to different countries and types of organizations. Policy-makers can use similar methods to target resources and cuts in order to promote fair practices.

The analysis that Allesina performed (a diversity analysis of last names) is a fairly easy text analytics task and provides a clue to the solution to the problem.

Such an analysis can unearth nepotism and allow steps to be taken to prevent it.

Extensions of the method can also be used to determine if, as in the case of Iraq and Syria, a certain community or ethnicity or family has taken over or is beginning to take over the governing mechanisms of a country.

And if the problem is identified early enough, it might give the constitutional, legal and electoral institutions of a democracy a fighting chance at protecting themselves and lead to a correction of the failure.


Algorithms to combat poverty

Causes of Extreme Poverty

An excellent study of poverty and its causes may be found in a book by the name of “The End of Poverty” by Jeffrey Sachs.

One of the examples that Jeffrey uses to explain the phenomenon of extreme poverty is a family farming a plot of land that is too small to feed it.

Because the plot is too small to even feed the family, there is no excess food to sell, and consequently, no way to build up any savings.

Without savings there is no way to make any investments that could result in more crops (like fertilizer) or in developing other skills (like education).

So, a family on a very small plot of land ends up trapped in a cycle of poverty – one that it cannot escape the cycle without external aid.

Extreme Poverty in India

Could such a scenario ever materialize in India?  Could a family ever come to have so little land that it does not suffice for its own needs?

It seems so.

In India, by tradition, land is divided equally among children.  So, as the population grows, the average size of land farmed by a family decreases.

The danger is also difficult to spot ahead of time.

When a person inherits a plot of land too small to support a family on, (s)he is usually already an adult and it is too late for him/her to leave farming for another profession.

That is a model that could explain both the huge disparities in income and the widespread poverty that exist in India.

In some other parts of the world, land holdings are inherited by only one child of a farmer, usually the first-born.  The other children need to “go out into the world” to “earn their fortune” by becoming apprenticed to a tradesman, or by becoming a soldier, or by entering the priesthood.

In such a system (which is called primogeniture), there is a built-in safety mechanism that guards against the danger of  land holdings becoming too small for a family.  In each generation, the land only feeds as many people as it did the generation before.  So, there is always a guaranteed surplus of money with which to pay for the training of other children into other professions.

With the Indian system of inheritance, on the other hand, all of the children of a well-off land-owner could find themselves inheriting holdings that are too small, at a time when they are too old to go back to school.

Whatever be the cause of the problem, it seems reasonable for us to assume that as of today, there are around 400 million people living in abject poverty in India because they have plots of land so small that they cannot feed a family, and no skills other than that of a farmer.

Education as the Solution

One solution to the problem would be some form of retraining to equip the 400 million people with skills that would enable them to obtain alternate employment (by that I mean just anything that does not include laboring on a farm).

The government admits that between 300 and 400 million people in India are illiterate (they cannot write or read).  The number of the innumerate is probably far higher.

The most straightforward solution seems to be to pool some money and set up a number of schools for people in rural areas, staffed with teachers.  Supposing we knew what to teach and were able to find the teachers, would we have solved the problem?  Let’s do the math (starting with some assumptions).

Assume we have 1000 teachers, and that each of them can teach a class of some 100 pupils.

Assume further that it takes 3 years to train a person into a new profession.

With this setup, how many years will it take to retrain 400 million students?

The answer is …

12,000 years.

Now that must come as a shock to some.  What if we instead had 100,000 teachers?

It would still take us 120 years, not counting the time it would take to train 100,000 teachers.

Lack of Government Investment in Education

We played a bit more with the numbers to see what would happen if the government doubled the annual allocation for education.  The allocation for education in 2011 was 11 billion dollars.

For another 11 billion dollars, the government could hire just around another 1 million teachers (assuming an annual salary of around 5 lakh rupees per annum) and solve the problem in around 12 years (not counting the number of years of training the teachers would need).

In fact, the total allocation for education across the board in India has been of the order of 3.5% of GDP.  Most Western countries, with far higher per-capita incomes than India, allocate approximately 8% of GDP to education.  India in reality needs to allocate somewhere close to 10% of its GDP to education.

And just as a digression, every time you read in the news that the Indian government is about to import military equipment for between 5 billion and 11 billion USD – Dr. Manmohan Singh’s government paid that sort of money for Sukhoi fighters in 2011, for an aircraft carrier and planes for it in 2012 and for 10 military transport planes in 2013, while Mr. Modi’s government paid a similar sum for six submarines in 2014, and for 36 fighter planes in 2015 – take a moment to pause and think about the amount of money that is being misspent, because that money is comparable to the federal education budget of India, and a better use for that money would have been education.

So, one obstacle in the way of prosperity in India, is that the government of India refuses to spend the money collected as taxes from Indians on education for Indians.

The Difficulty of Skills Planning

Another problem is that appointing more teachers may make people more literate, and even numerate, but not necessarily more employable.

The reason is that the skills that make a person employable are not just basic reading and writing skills.

Higher skills that would enable the students to earn money – perhaps engineering skills or a craft (a friend of mine recently helped out with a government program that taught web development skills at scale) – would be needed.

One problem with a brute-force approach is that there would be no feedback from the market in the beginning as to what skills would be needed and in what quantities.

An investment would have to be made blindly in teachers equipped to teach certain skills, and it would only be decades later that we would know if we had picked the right skills in the right quantities.

So, there is a chance that this method wouldn’t work out very well for the students in terms of equipping them with marketable skills.

Apprenticeship and Skills Development

But is there another way to skill up such a large number of people?

Well, it turns out that there is.  And the method was used in Europe for hundreds of years.

It is called apprenticeship.

Consider a system where one person trains a small number of people, say 10 people, and each of them in turn trains another 10 people.    Assume further that these ten trainees work for the trainer and get paid while they are being trained.

This is how people learnt a trade in Europe for hundreds of years.

Under this model, if each person trains only once and then needs train people no more, 1 becomes 11 in 3 years.  11 becomes 111 in another 3.  111 becomes 1111 at the end of nine years.  In about thirty years, all 400 million people would have been completely retrained, with no massive initial financial investment and with market forces deciding at every stage what skills might be needed most in the coming years.

So, you have an algorithm that can reskill a large number of people at scale in about 30 years.

The Complexity of an Algorithm

Why does one method work so much better than the other?

The brute-force method of skilling people (using traditional schools and a large number of teachers) is what we call an algorithm of complexity O(n).

What that means is:  should the size of the problem double, the time to solve the problem also doubles.

Apprenticeship is what we call an algorithm of complexity O(log n).  In an algorithm of this sort, when the size of the problem grows exponentially, the time to solve the problem only gets multiplied by the exponent.