Puzzle #2 - Statistical Guesswork

2010-11-12T10:35:00.003-05:00

Alice secretly picks two different real numbers by an unknown process and puts them in two (abstract) envelopes. Bob chooses one of the two envelopes randomly (with a fair coin toss), and shows you the number in that envelope. You must now guess whether the number in the other, closed envelope is larger or smaller than the one you’ve seen.

Is there a strategy which gives you a better than 50% chance of guessing correctly, no matter what procedure Alice used to pick her numbers?

While you may think that it is paradoxically defined or has no answer, it turns out that it’s a perfectly valid problem and the answer to it is “Yes.” In fact, there are at least two possible answers to this question that both satisfy the objective.

Puzzle #1 - Later but Younger

2010-11-10T11:35:00.002-05:00

Two children were born to the same mother in the same room of the same hospital on the same day of the same year. One was born at 1:37 am the other at 1:53 am. Interestingly, however, the child born at 1:53 am is considered to be the eldest. How is this possible?

Programming Puzzle - N-Bit Array Permutation

2009-06-18T10:22:00.004-04:00

Here's a programming puzzle that came out of an interesting experience working on a recent project of mine.

You have an N-bit (boolean) array, where N is odd, for which you must produce all possible permutations of bits. Write a function that can produce the sequence of all possible n-bit permutations, with the following restrictions:
The first value in the permutation sequence must consist of all zeros.
The last value in the permutation sequence must consist of all ones.
Each n-bit permutation must vary by only one bit from the prior permutation.
No duplicate permutations must be produced.
No permutations should be omitted from the sequence.
Generating each permutation should require constant time.

This seemingly simple problem requires some careful thought to solve correctly. Look for the solution in the coming days on my blog.

Is City Traffic an Example of the N-Person Prisoner's Dilemma?

2009-06-10T15:38:00.015-04:00

Many people have had the unpleasant experience of driving in rush-hour traffic in a major metropolitan area. A common frustration mentioned by many drivers is the inconsiderate, and often unsafe, habits exhibited by drivers in traffic. It's quite typical to see cars crossing into the intersection in an attempt to squeeze through before the light changes - ultimately blocking cross traffic. Other cars pass through red lights indiscriminately or attempt to merge across multiple lanes of traffic. Drivers that follow the rules are often pressured by drivers behind them by honking (and sometimes cursing). Furthermore, drivers taking a right turn from the cross-ways lane cut ahead of these individuals to "sneak" in to traffic. These and other driving behaviors clearly slow the pace of traffic for everyone - not to mention raising tempers and frustration levels.

So what does this infuriating behavioral issue have to do with the prisoner's dilemma (PD)? Well, let's start by defining the prisoner's dilemma - the classic formulation is credited to Albert Tucker based on the prior work of Merrill Flood and Melvin Dresher in 1950.

Two suspects are arrested by the police. The police have insufficient evidence for a conviction, and, having separated both prisoners, visit each of them to offer the same deal. If one testifies (defects from the other) for the prosecution against the other and the other remains silent (cooperates with the other), the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both remain silent, both prisoners are sentenced to only six months in jail for a minor charge. If each betrays the other, each receives a five-year sentence. Each prisoner must choose to betray the other or to remain silent. Each one is assured that the other would not know about the betrayal before the end of the investigation. How should the prisoners act?

Based on the rules of the dilemma, the optimal outcome for both prisoners together is to stay silent and serve the six months sentence in prison. However, each prisoner can improve his own outcome by testifying against the other - so long as the other prisoner stays silent. If both prisoners reason this way and testify against the other, the results are far less desirable - each ends up serving a 5-year sentence. The PD scenario can be generalized to include N-persons - in which case the payoff and costs are spread across all participants. Based on empirical and statistical research, it has been concluded that about 40% of pairs of individuals will ultimately choose to betray each other.

The Prisoner's Dilemma game illustrates the challenges created in situations where there is a lack of trust amongst the participants. Isolating the participants is necessary to ensure that they act primarily in their own self-interest - without knowledge of the others' choices. Furthermore, the cost/benefit structure of the game creates a strong incentive for an individual participant to betray the other if there is a reasonable chance that the other individual will not betray them.

So back to the situation of city traffic. Each driver has the choice to follow the rules of the road - letting cars merge appropriately, turning only when there's room, and patiently waiting their turn to move through intersections only when they are confident that can completely pass through. When everyone cooperates, the time it takes for all drivers to pass through traffic approaches the optimal limit imposed purely by driving conditions¹ (number of vehicles, how long the lights are, road conditions, etc). Unfortunately, when everyone cooperates, the value of "cheating" increases - since an individual driver can reduce his own time in traffic at the expense of everyone else. Unfortunately, when enough drivers choose to cheat, the time it takes for everyone to pass through traffic actually goes up.

This seems like a clear analogy to the n-person PD problem - the temptation of the individual driver to cheat offers a potential benefit (when there are few cheaters) - but can result in a significant cost (when cheating is common). Furthermore, those who choose not to cheat, incur a greater cost than those who do - their commute through traffic is longer than that of the cheaters and they bear the (social) pressure from other impatient drivers.

The prisoner's dilemma demonstrates what happens when decisions are imposed on a group of individual in a scenario where trust and benefit are placed in opposition. If you trust the other participants in a PD you can choose to cooperate and minimize the cost for the entire group. However, because you can increase your individual benefit by cheating, there is an incentive to compete rather than cooperate.

Social pressures and consequences can alter the cost/benefit matrix for PD scenarios. If there is a social relationship between the individuals that lasts beyond the PD situation, the decision of whether to compete or cooperate can be vastly different. You are more likely to choose to cooperate with people that you know you're going to have to deal with in the future. Conversely, you're more likely to choose to cheat when you can ignore the identity of the victims - it's generally well accepted that anonymity increases crime. The scenario of city traffic is interesting because it affords many individuals a significant level of anonymity, which helps to explain why we observe so many people behaving badly in traffic.

There has been some question as to whether the traffic scenario is truly a case of the N-Person PD problem. A paper published in Oxford Economic Papers journal in 2005 by Mary Sissons Joshi, Vijay Joshi, and Roger Lamb describes an empirical sociological study conducted on 551 car owners in Oxford. Each was presented with three pairs of alternatives designed as traffic versions of the four outcomes of the PD scenario. Each respondent stated which alternative in each pair they preferred. According to the study, only 2% of the group chose the outcomes which correspond to the full set of preferences which fit the PD scenario. The plurality or respondents (48%) selected a set of preference which more closely fit an assurance game.

1. We assume for the sake of the argument that there are no accidents or other obstructive behaviors at play.

Ideas and Observations

Puzzle #2 - Statistical Guesswork

Puzzle #1 - Later but Younger

Programming Puzzle - N-Bit Array Permutation

Is City Traffic an Example of the N-Person Prisoner's Dilemma?