# Stuff

“This isn’t life. It’s just stuff.” -Lester Burnham

## A post about evolutionary psychology

with one comment

Evolutionary psychology is a field of science where the theory of evolution is used to explain different aspects of human behavior. This post is about evolutionary psychology.

Central thesis:

Human beings (and all other living beings) are machines designed by evolution to help molecules called genes create as many copies of themselves as possible. It all started around 3.5 billion years ago with a molecule that could react chemically with its environment and create a copy of itself. Over a period of time, it created several copies. But since no process can consistently be perfect for a long period of time, neither was the replication process and some random errors started creeping in. As a result, some copies ended up being slightly different from the original molecule, different not only in the molecular structure, but also in the way they replicated. Since all copies inhabited the same environment, there was a competition for the available resources. The molecules that could replicate faster, without using up a lot of resources managed to create more copies of themselves and thus survived. The others, because of the “food” being snatched away from them by the more efficient self-replicators, went extinct.

Time and again, another random error would create a new kind of molecule and thus a new kind of replication mechanism and the metaphorical sieve of nature would filter out the weaker ones letting only the faster, stronger and the more efficient ones to survive. The repeated cycle of random errors followed by a ruthless filtering procedure continued and billions of iterations later, one of the numerous mechanisms that emerged was called humans (by the same mechanism).

Our replication mechanism is very different and far more complex than the primitive one. It is no longer a mere chemical reaction. We start out as a molecule, the DNA, which multiplies in two different ways. The first kind of multiplication creates a carrier for the DNA itself. The carrier is an elaborate machinery equipped with state of the art tools that help it survive long enough that it is able to perform the second kind of multiplication. The second kind of multiplication then creates a new DNA molecule that then multiplies on its own and creates its own carrier. The exact features the carrier will have are encoded as instructions in the DNA.

We are all machines, not in a metaphorical sense. We really are machines. Our bodies have several similarities with a robot designed to accomplish certain tasks while interacting with the world. We have sensors that collect information about the surroundings, a processor that runs complex algorithms to process the information and take actions, and tools to implement those actions. We have primary and secondary memory to help us perform complex computations and learn from past feedback. We have our own power management system that extracts energy from the environment and supplies it to different parts of our body to keep it functioning. The only ways we are different from an existing robot is that we are more advanced in certain areas, have different objective functions and are made of meat.

Psychology, in a very broad sense of the word, is the study of the algorithm we use (let’s call it the Homo Sapiens Algorithm), consciously or unconsciously, in order to process the information we are constantly being fed by our sense organs and the information from the past that is stored in our memory. Evolutionary psychology tries to explain the algorithm and make useful predictions about it by using the fact that it was designed by evolution over a period of billions of years.

Thus here is the central thesis of evolutionary psychology summarised in two sentences:

Different aspects of human behavior are basically just different subroutines of the Homo Sapiens Algorithm (HSA). The only reason why a subroutine exists in the HSA now is because in our evolutionary history, the genes that encoded the instructions for creating the subroutine ended up building a carrier for themselves that was better at replication.

So, for example:

Why do we feel hungry?

The genes that programmed the feeling of hunger in our ancestors built better carriers for the obvious reason that whenever the carrier was at a loss of energy, it replenished it by getting more fuel. The carriers that did not have these genes were not alarmed by a lack of energy and thus died much before replicating.

Why do we like sex?

Sex is the main mechanism that leads to replication. The genes that made their carriers want to have sex survived longer because the carriers had sex and thus replicated the genes.

Why are we obsessed with sex?

Sex is really the main mechanism that leads to replication. Consider a subroutine that carefully chooses a potential mate, makes you want to have sex with them only in a way that will definitely lead to an offspring and that too only after a rigorous initial screening that conclusively proves that the mate is real. This subroutine will expend a lot of time and resources into unnecessary activities. Consider a different subroutine that allows misfirings but fills you up with an intense desire for sex. Given the central role played by sex in the grand scheme of things, the second subroutine will outperform the first one.

Why is it so difficult to eat healthy?

In the ancestral environment, food was scarce. Thus the best thing to do on finding food was to eat as much of it as you could. Fats were specially good, because your body could store them for a long time and provide you with a long term source of energy. Thus the genes that made us want to eat as much fat rich food as we could created carriers that were better suited to survive in the ancestral environment. In the last 10,000 years or so, the environment changed too fast for evolution to catch up. Thus the subroutines hardwired into us are almost the same. However, with an easily available supply of food and the lack of reasons to do physical exercises, the subroutine has become outdated.

Why do we like other people?

It is clear why we like our romantic partners. The reason why parents like their kids is because they share genes with them. Thus the genes that programmed a subroutine that said, “Love your kids,” was good for the genes because with a high probability, the genes would also be present in the kids. It’s the same reason why we like our parents, siblings and other relatives. We also like people who we are not genetically related to. The reason for that is more complicated and I will not go into it. In short, a subroutine that said, “Like people that like you in return,” was also better for the carrier than a subroutine that said, “Don’t care about other people,” or “Actively work towards sabotaging other people’s interests,” or “Like every single person in the world,” because the first one was an evolutionarily stable strategy.

There are many other phenomena that can be explained in a similar way. For example:

• Why do we often find small things cute?
• Why do we feel physical pain?
• Why is the physical pain associated with a peck of dust falling into the eye so disproportionately larger than a peck of dust touching any other part of the body?
• What is anger? Why do we feel angry?
• What is laughter? Why do we find things funny? (This is actually very interesting.)
• Why do we like music? Why do certain specific sequences of notes have the ability to make us cry and the others make us rejuvenated?
• Why and when do we feel shy? How about embarrassed?
• Why do we fear public speaking so much?
• Why do we get curious? What is the meaning of the word “why”? What is the answer to life, the universe and everything?

and so on…

But this post is, for now, over.

Written by vinayakpathak

September 4, 2012 at 3:43 am

## Perfect matchings with a high stabbing number

Once upon a time, an idiosyncratic king set up a peculiar system for settling marriages in his kingdom. Once every year, he would invite all the couples that wished to tie the knot to a grand ceremony. Upon arrival, the couples would be taken to a large open area with chairs that were fixed to the ground spread all around and asked to get seated. The arrangements would be so made that the chairs would neither be surplus nor in shortage. Thus each individual would get exactly one chair and no more.

Finally, the king himself would arrive, examine the seated guests, draw one long line on the ground and stand on one of its two sides. That’s when the marriages would be decided. Couples where both partners were seated on the side of the line the king stood on would get married and couples separated by the holy line would be forbidden from seeing each other ever again.

The king wanted to slow down the recent exponential growth in population in his kingdom and so he wanted as few couples to be married as possible. Since he had complete knowledge of who wanted to get married to whom, he could, in principle, devise an evil arrangement of chairs and draw one really mean line that would separate most of the couples at the ceremony. On the other hand, the couples were allowed to collude with each other upon seeing the arrangement of chairs and decide who got to sit where. Thus perhaps they could formulate a clever strategy that would let most of them be on the same side as the king no matter what line he chose to draw?

Year after year passed by and the king, drawing upon the wisdom of the entire royal ministry, managed to hoodwink his people and successfully stalled most of the romance in his kingdom. The lack of expertise in computational geometry among the general public proved to be detrimental to them. The grand ceremony, having the flavor of a gripping puzzle, got the king addicted and very soon, by developing progressively sophisticated and elaborate strategies, he unknowingly brought his own kingdom to what could be described as extinction.

Centuries later, in the year 1989, two researchers, trying to design an efficient data structure to perform range searching queries on a point-set proved an interesting theorem. They weren’t aware that the theorem held the key to a centuries old conundrum that could have saved an entire kingdom from going extinct. What they proved essentially amounted to this:

“No matter what the arrangement of chairs, the couples can always collude with each other and compute an assignment of chairs to each individual, so that no matter what line the king draws and no matter what side he stands on, at least a polynomial number of them get married.”

In fact, they proved something even stronger. Their theorem does not so much depend on the fact that the shape the king draws is a line. Other geometric shapes, such as circles, rectangles, squares, triangles, can all be plugged into the theorem in place of “line” and the statement will still hold true.

As long as the shape satisfies the property that its dual shatter function is polynomial, the theorem works. The dual shatter function for a shape is the maximum number of cells one can get in a Venn diagram obtained by drawing $n$ of those shapes. For example, for the case of halfplanes (i.e., a line and one of its sides), one can easily show using induction on the number of lines that the dual shatter function is polynomial. Notice that when incrementally adding a halfplane to a partially built Venn diagram of halfplanes, the number of new cells created is equal to the number of cells this new halfplane’s boundary intersects. Since a new line can intersect an old line at most once, the number of cells it intersects is at most the number of lines already present. Thus the dual shatter function is $O(n^2)$. Simiarly, for any shape that satisfies the property that boundaries of two instances of the shape always intersect in a constant number of places, the dual shatter function is bounded from above by a polynomial.

Actually, the theorem does not just hold in the geometric setting. It holds for general set systems. Thus if the ceremony were organized in interstellar space with chairs occupying co-ordinates in three dimensions, or in some bizarre abstract space, a polynomial number of marriages could be saved as long as the shape chosen by the king had a polynomial dual shatter function.

(Bonus points if you can correctly guess the definition of stabbing number without looking it up.)

Written by vinayakpathak

July 11, 2012 at 3:54 am

Posted in TCS

## Another theorem of Turán

A graph with ${n}$ isolated vertices has a maximum independent set of size ${n}$ and a complete graph has a maximum independent set of size 1. As you increase the number of edges, you should get smaller and smaller maximum independent sets.

This intuition is quantified by a theorem by Turán that says that a graph with ${n}$ vertices and ${e}$ edges has a maximum independent set of size at least ${\frac{n^2}{2e+n}}$.

In particular, graphs with linear number of edges, for example, planar graphs, or graphs with max. degree bounded by a constant are guaranteed to have a linear sized independent set.

Note that the theorem only says that small number of edges guarantees a large independent set. The converse is not true, i.e., a large independent set does not imply a small number of edges. Example: complete bipartite graphs. They have ${\frac{n}{2}^2}$ edges and an independent set of size ${n/2}$.

Also, the theorem is constructive. So you can actually find the independent set in question in polynomial time.

Written by vinayakpathak

June 23, 2012 at 4:00 am

Posted in TCS

## What does your heart say?

with one comment

(I posted this a long time ago on GoodBlogs.com.)

Heart doesn’t say anything. It pumps blood to the rest of the body. When someone treats heart as something that takes decisions, they are using a metaphor. The question is, what exactly does the metaphor mean? What exactly does it mean to say, for example, that my heart told me to do something?

We can understand this if we understand the way our brain works. Our brain is a complex organ that takes in a lot of information from our senses, processes the information in a certain way, takes a decision and makes our body act based on the decision it has taken. One small part of the brain is called self-awareness. That very small part makes us aware of what the brain is doing. For example, when our eyes receive light waves from the environment and send them to the brain and then the brain processes them and understands that the thing in front of the eye is a tree, we aren’t aware of all the information processing the brain does. It’s only after several experiments in the lab using things like MRI scanners and other equipments that we have started to understand the mechanism with which the brain processes signals coming in from the eye.

There are several places where the brain does something without making us aware that it’s doing it. For example, we are excellent at recognising fake smiles from genuine smiles, but it was only in the mid-19th century that a guy named Guillaume Duchene understood the difference between the two. He identified that a genuine smile involves flexing two kinds of muscles – one near your mouth (zygomatic major muscles) and the ones near your eyes (orbicularis oculi muscles). If a person tries to give a fake smile, he generally flexes only the first one (i.e., the one near the mouth).

When we look at a smiling person though, we don’t really look at the two kinds of muscles one by one and see if both are flexed or not. We just look at the person’s face and we “get it”. We somehow understand that the smile is genuine (or fake).

Attraction between opposite sexes is a phenomenon that’s full of such examples. People get attracted to each other in weird ways. No one has ever been able to come up with a set of rules that predicts exactly when a person will feel attracted to another. But we all do get attracted. That’s also something that the brain does without making us aware that it’s doing it. People have started understanding it now, but we are still far away from a complete set of rules. An experiment was done in 1996 where some random men and some random women were taken, the random men were told to wear the same shirt for two days and in the end, the shirts were packed in different bags and given to the women. The women were then asked to open the bags, smell the shirts and decide whether they found the smell pleasant or offensive. Later, the immune systems of the women and the men were analyzed and it was found that women had prefered guys whose immune systems complemented theirs, i.e., was different from theirs. This makes sense from the evolutionary point of view because if the genes program the women to pick the men whose immune systems complement theirs, there will be a higher chance that the offspring will be healthy.

The point of all this is that when someone gets attracted to someone else, it’s very popular to attribute it to the heart, that their heart told them to be attracted. But it’s actually happening in the brain. It’s something that the brain does on its own without telling us that it’s doing it. So the hypothesis is that the phrase, “my heart says so,” is something that refers to a phenomenon where the brain does something without making us aware of it.

Written by vinayakpathak

March 30, 2012 at 11:59 pm

Posted in Uncategorized

## Being smart about distributing electricity

with one comment

It turns out that the conventional way of distributing electricity is all wrong. I am talking about electricity distribution of the kind government does from the power plant to the consumers.

One of the main issues is that all the resources, the cables, the transformers, the hubs and so on, are built in order to support the peak load. But the peak load is rarely reached. In 2009, for example, 15% of the generation capacity was used less than 88 hours per year in Massachusetts. 88 hours per year! Out of the 8760 hours that a year has. Obviously, we are doing a lot of work that’s not needed.

However, we can’t really just cut down on the resources because if we do, those 88 hours of peak load will just blow everything up and we don’t want that to happen either.

Thus people have come up with an ingenious idea: control the electricity provided to the consumers such that they do not all get a large amount at the same time, thud reducing the peak load. This is done by a central hub that studies the usage pattern of different houses in the locality and schedules electricity to them accordingly. The hub can also ask the home owners to provide additional data. For example, people are usually flexible about exactly when they want to use power-consuming electric devices. So for example, the hub could ask the home owners to send a list of devices they want to use on a given day and the flexibility they are willing to accept. Next, the hub can decide the amount of electricity to provide to each house at a given time, the aim being to make sure that not many of the houses run heavy load devices at the same time.

Many other things can be done. Anything that can potentially bring down the peak load by 1-2% will save the governments a lot of money.

Written by vinayakpathak

March 28, 2012 at 11:26 pm

Posted in Uncategorized

## Opinions and How They Change

An individual forms opinions based on how he can himself assimilate the facts around him and also based on what opinions his friends and other people he interacts with hold. This makes things complicated and intriguing enough that this has been an active area of research since decades.

One question is, can we formulate simple enough models that match with the data we get from real life experiments? If we could, then we would get some insight into human behavior and a tool for making useful predictions.

The simplest model that has been studied is this:

An opinion is just a real number. Each person starts with an initial opinion. Next, in each time step, he looks at the opinions held by his friends and updates his own opinion to the average of his old opinion and the opinions of his friends. It doesn’t have to be a simple average. A person may have different trusts for different friends and thus he might want to take a weighted average instead. However the model doesn’t allow individuals to change the weights at any step. The weights chosen in the beginning have to be the weights always.

Using simple linear algebra tricks and borrowing known results from the Markov Chain literature, it can be shown that this kind of system converges to an equilibrium in most natural cases. An equilibrium here means a set of opinions for which the averaging step doesn’t lead to any change, i.e., for all individuals, the new opinion remains the same as the old one. In fact, it can be proved that the equilibrium that’s reached is a consensus, i.e., every individual has the same opinion.

An objection to this model that one might have is the simple representation of an opinion. Can it really be represented by just a single real number?

Anyway, DeGroot, the person who introduced this model also showed that the same thing happens if the opinions are drawn from any vector space and in each time step a person updates his opinion to some convex combination of the opinions of his friends (including himself).

That’s something.

The only issue is that in real life, people don’t reach consensus. So what’s going on?

Of course, the model seems too simple to resemble real life accurately. For one, the weights (or trust) we assign to people changes over time depending on various factors. For example, if a person seems to be changing his mind every minute, we will probably assign a lesser weight to his opinion.

Also, even though this process of repeated averaging has been shown to always converge to a consensus, we don’t really know the amount of time it takes to reach there. From what I know by quickly glancing through Bernard Chazelle’s new work on bird flocking, the time taken by a community whose size is close to the population of a country to reach a consensus is probably way more than the age of the universe.

Anyway. Friedkin and Johnsen modified this model a bit to make it more realistic. In their model, an individual has a fixed internal opinion that doesn’t change with time and during an averaging step, he takes a weighted average of the opinions of his friends (including himself) and the fixed internal opinion. Because the internal opinion can be different for different people, this system will obviously not reach a consensus always.

The system does have an equilibrium though and Friedkin and Johnsen proved that the equilibrium is almost always reached.

However, their model is different from DeGroot’s simpler model in a fundamental way. Let me explain.

Given a set of numbers ${a_1, \ldots, a_n}$, the mean is the number that minimizes the function ${(z-a_1)^2+\ldots +(z-a_n)^2}$. Thus the averaging step above can be seen as a step where a person is trying to minimize the cost incurred with respect to the cost function ${\sum_{j\in N(i)} (z_i-z_j)^2}$. Here ${N(i)}$ represents the neighborhood of ${i}$, i.e., the set of friends of ${i}$.

With the above definition of cost, we can measure the quality of a certain opinion vector. For example, we can say that the sum of costs incurred by each person is the social cost of the whole group. And then given an opinion vector, we can decide how good it is by measuring how far it is from the opinion vector that minimizes the social cost. In particular, we can measure the quality of the opinion vector that the group converges to in equilibrium.

The fundamental difference between DeGroot’s model and Friedkin and Johnsen’s model is that in DeGroot’s model, the equilibrium reached also minimizes the total social cost but in Friedkin and Johnsen’s model, it does not necessarily.

David Bindel, Jon Kleinberg and Sigal Oren prove in their FOCS ’11 paper that the situation is not that bad. Even though the total cost at equilibrium may not minimize the total social cost, it can be worse at most by a factor of 9/8. That’s pretty cool.

Written by vinayakpathak

November 13, 2011 at 5:12 am

Posted in TCS

## Building the perfect world in four extremely difficult steps

(I had written this for Goodblogs a long time ago.)

A perfect world would be one where everyone just did whatever they wanted to and lived happily doing that.

If tomorrow, everyone just decides to do whatever they want to, the world will turn into a chaos. For example, no one will want to clean the garbage and as a result, we will eventually rot in our own filth. To keep the world working, it is necessary that at least some people do things that they don’t particularly like doing. Can we repair this? In general, can we design a perfect world, a world where you never have to feel guilty, a world where you can just do whatever you feel like at any given moment and that will be the best thing to do for you and for the society? If yes, then what are the steps we need to take?

To understand this, we first need to understand what is the best thing for the society. There are things that are good for some people and bad for the others and there are things, that are good for the society right now, but in the long run, will lead to the decay of mankind. Let’s, for the time being, define ‘best’ as the thing that has the best average over people and over time. That is, we take the average happiness level of the world at this time and then take the average of this average over time. The best thing then, would be the thing that maximizes this average.

Once we have this out of our way, we can understand that the essential problem is to align what an individual feels like doing at a given moment and what’s the best thing to do for the society at that moment. Since our definition of ‘best’ depends on happiness levels of people, there are two extreme approaches to solving this problem. One extreme is to reprogramme the human brain so that it feels happy or sad in a more controlled way. This extreme is slightly trivial. All we need to do is to build the perfect mood enhancing drug and make it compulsory for everyone to take it. This will suddenly boost up the total happiness level of the world. The other extreme is to leave the human brain untouched and reengineer the world in such a way that whatever we want at this moment is made possible immediately. This is perhaps impossible. It’s easy to imagine an individual getting so angry at another person that he genuinely wants to kill him, or harm him severely in some other way. If then, this were made possible immediately for him, it would create more grief to the person being harmed than happiness to the person inflicting the harm. It’s similarly easy to imagine completely outrageous, or even physically impossible wishes that a person can make. One might have to break some laws of physcis to make that possible immediately. Since this approach seems impossible and the other extreme is kind of sad, the ideal should lie somewhere between the two extremes.

One possible midway approach is the following.

Step 1 – Build robots to do all the dirty work that no one in the world wants to do but is necessary to be done. This will leave out the kinds of work that at least some people in the world like doing. Let them do that work. But there might still be problems. The person who likes doing the work X might be living in Japan and the place where X needs to be done might be in Canada. Moreover, if we consider one person who likes doing X, then he may not want to do X all the time. The time when X needs to be done in Canada, he might be in a mood to go swimming with his kids.

Step 2 – Build a global work organizer. This will be some huge global device that will take the help of the internet. It will monitor what each person in the world is in the mood of doing right now and the things that need to be done at this moment in different parts of the world. Then, it will match the tasks to the suitable people. Since the world is such a large place, we can assume that what a random person wants to do at a given moment is useful for someone somewhere in the world and what’s useful for a given person is being wanted to be done by someone somewhere in the world. If there is some task, where this doesn’t happen, we already have step 1 to take care of it. Such things are already being done. There are several outsourcing services online for tasks that do not require physical presence. For example, Mechanical Turk and oDesk are websites that are designed exactly for this purpose. Even GoodBlogs is similar. The previous post I wrote was originally intended to be an email to my mother. But somehow somewhere in the world, there was a group of people who agreed to give me \$20 for it. However, building this global work organizer will still not build the perfect world. For that, we will need the next step.

Step 3 – Upgrade the human mind so that its emotions are in control. For example, no one should ever feel like seriously inflicting any harm on anyone else. Not just this, but one will also need to make sure to not inflict any harm on the future self. Even if everyone is full of kindness and love towards others, one still might want to smoke a cigarette and thus suffer with lung cancer later in life. If not, then one may simultaneously want to learn how to play the piano and to not practise, or, to get a girl and to not develop the skills to woo women etc etc.

Step 4 – Make learning easy. Even if we are the masters of our own emotions, have robot servants and are never forced to do something that we don’t want to do, there might be a situation where we want to learn something quickly but we can’t. For example, one one may be craving good food, but not know how to cook. Then it will be good to have a plugin that they can install on their mind to give them that feature in a few seconds.

Written by vinayakpathak

November 3, 2011 at 9:55 pm

Posted in Uncategorized