Prerequisites: Chapters 1, 3, 4, 5, and 6.
This is a continuation of Shubik Auction I. Remember that there, knowing the maximum number of moves in advance leads to the slightly disappointing solution that the player who will eventually not have the last move will not even start bidding, when playing optimally. But what happens if the number of possible bidding rounds is finite but unknown in advance? Or if then number of rounds is finite, but after every move the game could randomly end?
This chapter is mainly an exercise for simultaneou games with randomness, but it also discusses already the connection to games with nonperfect information, and even the connection to games with incomplete information.
What happens if we don't know in advance which player has the last move? Assume that there is still a maximum number of rounds, but the game could terminate after each round with a given fixed probability p. This makes the game fairer, more profitable for the auctioneer, and also much more interesting.
Of course, for p=0 we just get the non-random version discussed above. How does the backwards induction analysis change?
Let us look at a concrete example SHUBIK AUCTION(35,35,6,0.5).
The game tree is shown below, already with expected payoffs for the positions and
recommended moves obtained from backward induction analysis filled in.
In Beth's last position, she will bid 60. That implies that the expectations at this position
for Ann and Beth are -50 and -25. Therefore the expectations at the last random position
are the averages of (-50,25) and (-15,-40), namely (-32.5,-32.5).
Since -30 is larger than -32.5, Ann passes instead of bidding 50.
Proceeding this way, we get expected payoffs of 7.5 for both players
at the beginning of the game.
Note also that Ann plays slightly different than in the case without the possibility of a random ending. Like there, she will usually not bid, with the one exception of her very first move. What might be the reason for this change? Well, there is a large possibility that the game ends right after this first bid, and Ann gets the item, and bidding is still cheap at this very beginning.
Is it possible to try the analysis not only for concrete parameters,
but once and for all for arbitrary parameters A, B, and p?
Of course, for fixed n=6, the structure of the game tree remains the same,
and the payoffs can be expressed in terms of A and B, as shown below.
Ann's positions are labeled as A1, A2, A3, Beth's positions as B1, B2, B3, and B4,
and the random move positions as R1, R2, ... .
For instance, select the 6-rounds sheet and input A=35 and B=35. We get the chart below to the left. Obviously the lines jump at some values of p. In our example, these are around p=0.28 and around p=0.57. These are the values where Ann's or Beth's optimal strategies change. For p between 0 and 0.28 Ann will always pass and Beth always raise the bid. For p between 0.28 and 0.57 we get the same pattern as above for p=0.5: Ann bids 10, but doesn't try higher bids, whereas Beth always bids. For larger p, both will always bid. The probability for a sudden end is just high enough making daring a bid worthwhile. Note that Ann's strategy changes around p=0.28 and around p=0.57, but it is Beth's payoff that dramatically changes at these values.
If Ann values the item more, let's say A=45, Ann will obviously try harder to get the item. We get the chart above to the right, which now has 4 strategy patterns. For p between 0.45 and 0.55, Ann always bids, whereas Beth would pass on her 20 bid (while still prepared to bid 40 and 60, but of course, these positions will not be reached then). This strange behavior has to do with Ann bidding for smaller p, due to the higher worth of the item for Ann, whereas this middle level p is not promising enough payoff for Beth, given the relatively low worth of the item for Beth.
Let us play a different variant now, a variant where Nature, instead of deciding after every move whether the game should be terminated, makes this decision when to terminate the game at the beginning of the game, but doesn't tell this decision to Ann and Beth. So we have a maximum number of n moves, and the game starts with a random move deciding the actual number of moves that will be played. Further assume that with probability p1 this number will equal 1, with probability p2 this number will equal 2, and so on. Obviously this probabilities must add up to 1, p1+p2+...+pn=1.
Since this random move about the actual number of moves played is not revealed to Ann
and Beth, this game is a simultaneous game with randomness and imperfect information.
On the other hand, it is rather obvious that for appropriate parameters
p1,p2,...,pn this new game is just our SHUBIK AUCTION(A,B,n,p).
Since the probability that SHUBIK AUCTION(A,B,n,p) ends after the first round is p,
that it ends after the second move is p2, and so on, we have to select
p1=p, p2=p2, ..., pn-1=pn-1,
and pn=pn-1. Below is the extensive form of the game equivalent to
We can even describe this new, more interesting game as a game of incomplete information. We play at most n rounds, but it could be less. Note that incomplete information means that the extensive form is not fully known to the players.
However, in games of incomplete information players need "beliefs" about the structure of the game---without such beliefs, players would not be able to make any decisions. If we assume that both players have the same beliefs about how likely the length of the game is 1, 2, ... n moves, then we arrives exactly at the game of imperfect information discussed above. Only in case of different beliefs, we could not model the game in this way.
Again this game can be analyzed using an Excel sheet. The different payoffs for optimal play for a fixed example and variable probability p are shown below. Again, the probabilities where one or more of the players change their strategies are rather visible from the graph.
Of course, again it depends on the parameters A, B, and probably to a lesser extend on n. But note that p is no longer a parameter of the game, it is chosen within the game.
As can be seen from this chart, the Auctioneer should choose p slightly larger than 1/2 or slightly larger than 2/3 to obtain an expected payoff of almost 20 dollars.