I asked myself this question today, which is 10/11/02. Some background will clarify my motivation in asking this question. I live in Madison, Wisconsin, which is home to a large campus of the University of Wisconsin. With about 40,000 students, the streets fill with costumed, drunk crowds the night of Halloween. It's lots of fun.

However, this year Halloween falls on a Thursday, so there has been some uncertainty about when the large crowds will hit the streets and parties (most people do not typically get drunk during the week). Some people suppose the most celebration will occur on 10/26/02, the previous Saturday. Others figure it will be on Halloween itself, despite being a Thursday. Still others guess that most people will celebrate the Saturday after Halloween, 11/2/02. Most people want to hold their parties or go out on the night when most other people are holding their parties or going out. This is because very large crowds are festive, and people like festive things.

This situation raises an interesting question: ‘With no central planner to dictate when the celebrations shall occur, how can everyone collaborate to celebrate at the same time?’. If people are allowed to do things like take votes including everyone in the University, there are many solutions. However, it seems more tricky if you assume that each person can only communicate about the matter with a few others (their friends).

Suppose people do the following: each day, they ask all of their friends when they think the celebration will be. Each person responds with his or her ‘current opinion’. A person's current opinion on a given day is defined to be the mode of the current opinions of the friends they asked the previous day. On the first day, everyone starts with random current opinions.

Now we have defined a tangled system of recurrence relations, one for each person. You can imagine that this system of recurrence relations will cause people to come into agreement after enough time has passed. However, it is difficult to guess how long this would take, how dependent the necessary duration is on the initial conditions, how things depend on how many friends people have, and so on.

Filled with curiosity, I wrote this program. It works out the situation I described given some parameters. It lets you specify the number of people (nodes in the directed, unweighted friendship graph), the minimum and maximum number of friends each person shall have (minimum and maximum out-degree of each node in the friendship graph), the number of possible days for Halloween (number of states each node can be in), and how long to iterate, given as a number between zero and one inclusive. The simulation will stop when the number of people with the most popular opinion meets this portion of the whole (e.g., a value 0.75 runs the simulation until three-fourths agree). All the initial conditions, including the friendship graph, are chosen randomly at the beginning. Below are some of the results I got.

Whenever I ran it with 40,000 people, four to eight (inclusive) friends per person, and three possible celebration dates, the system reached 95% agreement after about nine days. Here is a graph displaying a representative case (the x axis is the iteration number, the y axis is the number of people who support a particular day (line color)):

Four to eight friends was an optimistic estimate, so next I tried it with one to five friends. In this scenario, it usually takes about 23 days to reach 95% agreement.

If we drop the maximum friend count to four, it tends to take just a few more days to reach 95% agreement.

Dropping the maximum friend count to three results in 95% agreement after about fifty days. That is not too surprising. We now have a feel for how the time the system takes to converge depends on the connectedness of the friendship graph.

The really interesting things happen when we have a maximum friend count of two. That is, each person may consult only one or two others each day (always the same one or two). At this point, the system becomes extremely chaotic and unstable. Although it does eventually reach agreement, it takes a *very* long time.

To make things even more chaotic, I did a simulation just like the previous one but with nine(!) possible days for the celebration. Furthermore, I waited until the system stopped completely. This took almost 70,000 days.