Prerequisites: Chapters 1, and 3.
You are probably familiar with so-called "English auctions", where players bid for an item. The one with the highest bid gets the item, and must pay his or her bid for it. There are many versions dealing with the details, for example whether bidding increments are required, or whether the players must bid in a special ordering (usually they do not have to).
English auction is rather easy to analyze. Each player bids as long as the bid is below the worth of the item to him or her, but will not go above that.
In an attempt to make more money for the item, the auctioneer may come up with the following rules:
SHUBIK AUCTION(A,B,n): Two players, Adam and Bob, bid sequentially for an item. The bids must increase in increments of 10 dollars. Adam starts by either bidding 10 dollars or by passing (in which case Beth can get the item for 10 dollars but can instead pass as well). If Adam bids 10 dollars, Beth can bid 20 dollars or pass, and so on. After one player passes, the other player gets the item for her highest bid, but different to ordinary auctions, the other player still has to pay her highest bid but gets nothing in return. There is a fixed maximum number n of rounds. The item has a worth of A dollars for Ann and of B dollars for Beth.
Why do we need a fixed maximum number of games? Without that restriction, we would not have a finite game---the bidding could go on and go on. Remember that "finite" was also a requirement in Zermelo's Theorem---backwards induction cannot be applied in infinite games. But of course, a limit of the number of rounds may seem reasonable at the end. After 100,000,000 rounds the game will be finished anyway, since the players will have died. But what's important is that the number of rounds is known at the start of the game, since 100,000,000 or 100,000,001 makes indeed a difference.
Class activity: Play SHUBIK AUCTION(100,100,50) by auctioning a dollar to two students, with increments of 10 cents.
On first sight, this version looks advantageous for the auctioneer. Since he gets the sum of the highest and second highest bid, shouldn't he make more money than with the ordinary English auction? This first impression may also have been confirmed by the class experiment. Usually, when the required end after the 50 rounds isn't emphasized too much, people bid and bid until both are above the worth of the item for them. But this impression will not be confirmed by the analysis. It turns out that players should play differently, and that optimal play is not obvious without a little thought.
Below, the game tree/extensive form for SHUBIK AUCTION(25,35,9) (the item is worth $25 to Ann and $35 to Beth, and the maximum number of rounds equals 9) is shown.
Using such a game tree and backwards induction, each version of the game can be analyzed. But we can even analyze all versions of the game at once.
Last move: As usual with backwards induction, we have to start with the position having only end positions as successors. This is when the player supposed to choose in the last round decides whether to bid or to pass. This player could be both Ann or Beth, depending on whether the number of rounds is even or odd. So let's call her just the "end player". Since the difference to pay is just 20--- the end player pays 10·n if she bids and 10·(n-2) if she passes--- but since she gets the unit in one case, but not the other, the end player would bid in the last round provided the worth of the unit to her is more than 20 units, which we will assume here.
Second last move: Next we consider the position in the round before the last round. The player deciding there, the non-end player, knows that the end player would bid in the last round and get the item. If the non-end player would raise her bid, she eventually would just have to pay 20 units more, so she would not do it.
Third from last move: In the round before that, the end player has to decide. Knowing that the non-end player would pass in the next round, the end player would raise her bid.
Proceeding in this way, the conclusion is that the non-end player will always pass, whereas the end player is always prepared to raise her bid, if the item is worth at least 20 units to the end-player. Depending on the parity of the number n of rounds, we get the following two cases:
The case where the item is worth less than 20 units for a player is also easy to analyze. Such a player would never raise her bid. Knowing that the other player would bid in the next round provided that other player values the item more than 20 unit, the low-value player would not even bid in the first round. But if both players value the item less than 20 units, the player starting would bid and get the item provided it is worth at least 10 units to her.
Therefore this auction is a desaster for the auctioneer provided the players play optimally. The auctioneer gets nothing for even n, and 10 units for odd n, independent on how much the unit is worth (again assuming it is worth at least 20 units to the end-player.
What if there are three or more players, but still only the two with the highest bisd have to pay, and of course still only the one with the highest bid gets the item? Then of course, some players will not have to pay anything at the end, even though the placed bids, and this might encourage .......
The Wikipedia article [http://en.wikipedia.org/wiki/Dollar_auction] on the game describes it without a limitation on the number of moves, and calls it a paradox. But here of course, a formal discussion of infinite games would be worthless, since if we look at this game, nothing really happens. If two players start bidding, then they will continue bidding, and bids will get higher and higher. But no harm is actually done, since the players will just continue to bid forever and will never have to pay.