game theory

St. Petersburg Paradox

A new casino offers the following game: you toss a coin until it comes up heads. If the first heads shows on the N-th toss, you win 2N dollars. (Thus the payoff doubles with each coin toss that isn’t heads.) How much should you be willing...

Continue reading...

Envy-free Cake Division

Say you and a friend wish to share a cake. What is a “fair” way to split it? Probably you know this solution: one cuts, the other chooses. This is called a fair division algorithm, because by playing a good strategy, each player can guarantee she gets...

Continue reading...

Arrow’s Impossibility Theorem

Elections are democracy in action. People go to polls and express their preferences, and somehow we must aggregate the preferences of many individuals to make a joint decision. So the choice of voting method is very important. Is there an ideal voting method? According a...

Continue reading...

Vickrey Auction

Suppose you are hosting a silent auction to sell your antique car. The rules are: (1) prospective buyers bid for your car by placing their bids in sealed envelopes, (2) then after collecting all bids, you sell the car to the highest bidder for the...

Continue reading...

Deal or No Deal

On the TV show “Deal or No Deal”, a contestant is faced with a number of briefcases (26 in the US version) in which various amounts of money have been placed. The contestant is asked to select one to keep, unopened. Then the player plays...

Continue reading...

Two Envelopes Paradox

I have two envelopes, and inside each I have put some money. In fact, one envelope contains twice as much money as the other. I’ll let you select one envelope, which you can have after the game is over. But as soon as you select...

Continue reading...

Social Choice and the Condorcet Paradox

How should one select the winner of an election? If there are only two candidates, the answer is clear— choose the one who would win the most votes in a head-to-head election. But with three or more candidates, when each voter has ranked his or her...

Continue reading...

Rental Harmony

You and your college friends decide to rent a house together, and the N of you have found a house with N bedrooms. However, the house has rooms of different sizes, different features, and each of you have different preferences. Is it always possible to...

Continue reading...