If I know what program you’re running, I can come up with one that’ll beat it. That’s why the exact formulation of the game is important.
Fascinating thread.
If the money is the motivating factor, I think betting 2c is the best opening strategy. If you bet two cents, the other computer cannot play a winning strategy from there. Any amount it bets, you will be commited to betting one cent more. If it then raises the bet to $1, say, you will still be obliged to bet $1.01, cutting your loss in half, and the other computer losing a dollar. At this point, the other computer will lose money no matter what, so its previous move was a blunder. Assuming the computers don’t make blunders, the 2c opening bid should be enough to prevent the other computer trying to out bid you. Obviously it can’t bet over $1, as that would guarantee a loss, rather than breaking even. 2c opening bet leaves the opponent in a spot where whatever it bets you have positive expectation on you next bid, unless the computer bids over $1, in which case it loses money.
This is rational if the players are playing for the actual cash. If their motive is not the money (or points total, say), but rather a prize they get after beating the opponent by losing less, then they will have incentive to outbid the 2c because while they break even not betting, it gives the opponent 98c profit, which as far as you are concerned, is the same as you losing 98c. So here you would simply outbid each other to infinity, or the end of the available money, no matter how high the bidding goes, whoever wins will always lose less than their opponents, assuming they have outbid them by less than a dollar. Strategy for bidding gets complicated here if you know what the money limit is, but essentially the loser will be whoever bids within a dollar of the max bid. Then the other player will simply make the max bid, ensuring a lower loss than his opponent.
Of course that is when facing a computer, once your opponent is a human, all this goes out the window. Since you have no idea what they will do, you probably should not bet at all. If you bet 99c they will probably bet a dollar; as people tend to treat dollars frivolously. If you did the same bet with ten thousand, or some significant amount of money to the players, it becomes very hard to predict what people will do. Versus a computer, 2c should be enough to win the $10 000.
Caveat: It’s half three in the morning so this is probably all wrong. 
The most important question is whether this is a single auction, or one of a series. With a series, you can get information about the other players from the bidding itself, which allows for different strategies.
Here’s my take:
As long as each computer knows what the other will do, you either effectively have a game with collusion or a racing condition. In the case of collusion, assuming the computers swap turns going first each round, the result depends on how much money each has. Given infinite money, they will always even out for an even or infinite number of rounds, or the player who wins the first round will always win for an odd number (including one).
In the game with a racing condition, the only halting condition is a lack of funds, which would ordinarily mean the first to bid above the starting cash of the other player (or the same if they are evenly matched) would win. With matched funds, it’s entirely dependent on who goes first. (If they bid sequentially, it’s the person who goes first. However, the person going second could be programmed to jump ahead and win.) Otherwise, whoever has the most money always wins. If there are multiple rounds, once one computer is below the minimum bid (or at zero), the other’s money keeps increasing until there are no more rounds.
The only interesting scenario is collusion with a limited number of funds and multiple rounds, but the results are still entirely deterministic. As long as the amount of money remains twice the bid prior to the final bid, the game follows the rules of infinite money. Otherwise the one who does not bid loses in every game where this happens. The interesting part is trying to program it where the collusion condition is different in the even rounds, and the other computer can win back the money. Designing the simplest program (that doesn’t know what round or who goes first) that goes a certain number of rounds given any amount of money might actually be a bit of fun. But even then alternating starting players would even out the number of wins.
Not to say that thinking this out wasn’t fun, of course.
I’m not seeing any collusion going on. The computers never share the money after the auction ends - one of them gets the dollar and the other does not. So there’s no reason for a program to let its opponent win.
You have perfect information about what the other computer will do. Both computers are running the same program.
So one way of looking at it is that you are designing a program that will make a maximum profit for itself while playing against another version of itself.
But the way I look at it is that you’re really not trying to outwit the other computer. You’re trying to outwit the game.
OK so then your opponent bids 4 cents. He has now put you in the exact same situation that you put him in. You either have the choice of giving up or risking a continual raise to infinity. I’ll have to think about this more, but its starting to reminiscent of the halting problem. In the optimal strategy you shouldn’t bid if the result will be infinite escalation. But if you know your opponent is using an optimal strategy that won’t risk a rise to infinity than you should bid so as to get a bargain. Similar to the way to win at chicken is to take off your steering wheel and show it to your opponent. It doesn’t work too well if your opponent does the same thing.
With all this in mind, I am still leaning towards the bid 99cents and then stop strategy. If my opponent bids $1 just to put me at a disadvantage in the next auction, then it needs to be stipulated how much of a bankroll I have and how many auctions there will be. With a finite bank roll and a large number of auctions, the goal might be to reduce the opponent’s bankroll to the point that you can win every auction regardless of initial cost.
What’s your opinion of the X+99 strategy I described in Post #4? It would seem to be a means of halting a pattern of bid escalation.
The problem with that strategy is that it creates risk. Your goal is only to protect your own money not reduce your opponent’s. If you don’t bid, your money will remain safe albeit with no increase. If you bid a dollar in an attempt to cost your opponent money, you still won’t get any increase but you run the risk that there may be further bids and you will end up losing money.
There is indeed a no-bid equilibrium. But some further analysis reveals that this is not the only possible one. This piece isn’t exactly the American Economic Review, but it lays out the issues and had a nice articulation of the other equilibria.
That article looks to be addressing the issues we’re discussing here but I’ll admit I got lost in the technical language it used.
The statement of Theorem 1 answers the question you’re asking.
I’m still thinking about it, but it seems logical. But it’s only so in your scenario, where you’re already in the bidding process like it or not. If not, the best move is to bid a penny, I think. If the best move is not to join an infinitely escalating bidding war, I should bid first if I can, assuming everyone else knows that. The only winning scenario, assuming logical players, is to be the only bidder. Never willingly become the second bidder, since you have forced the first bidder to outbid you.
I think.
Okay. But “For a dollar auction game with stake v units and equal wealth w units for the players, the rational course of action is for player 1 to bid (w − 1) mod (v − 1) + 1 units, and for player 2 to drop out” isn’t completely clear to me. Is he saying the first player should make a one cent bid or a ninety-nine cent bid?
But if the best strategy is to avoid an infinitely escalating bidding war, then it could be a good strategic move to create such a situation. If you know that a rational opponent will drop out of a bid war, then you can end the bidding by starting a bid war.
In practical terms, suppose your opponent makes an initial bid of one cent. You respond with a bid of two cents. The two of you are now in an escalating bid war. Your opponent sees this and realizes the futility of continuing on, so he quits. You’ve now won the dollar for a two-cent bid and made a ninety-eight cent profit.
So one of the premises must be wrong. Either an initial bid of one cent is a bad strategy or there are situations where you should continue bidding even if both players have already bid.
Let your opponent win every auction at $.01 then take your cut of the earnings under the table. Or just agree to let each other win alternate auctions.
That would be clear collusion.
Even agreeing to take turns winning and not splitting the money from any individual auction would be collusion.
I’m having trouble parsing this. What’s not clear?
No you can’t, because if it was rational for you to deliberately enter a bidding war to drive your rational opponent out of the game, it must also be rational for your opponent to deliberately remain in a bidding war to drive you out of the game.
As the result of such a tactic is mutual annihilation, entering a bidding war cannot be a rational tactic against a rational opponent.
As I said, I’m not clear on what the quantity (w − 1) mod (v − 1) + 1 units comes out to.