Dice Auction Optimal Strategy

1.7k Views Asked by At

Suppose two dice are rolled, and Alice and Bob are playing an auction-style game on the sum of the two dice. The first dice roll is shown to Alice, and the second one is shown to Bob. Then, Alice proposes a bid. Bob, after hearing Alice's bid, proposes his bid. The winner of the auction (whoever bids higher) must pay the loser the value of the winning bid, and the loser pays the winner the sum of the two dice.

Example Game: Suppose Alice is shown a die roll of 4, and bids $\$10$. Bob sees a $5$, and in response, bids $\$11$. Then, Bob, the "winner" of the auction, pays Alice $\$11$ and Alice pays Bob $\$4 + \$5 = \$9$. The net gain for Alice is $2, and Bob loses the same amount in a zero-sum fashion.

I'm looking to find the Nash Equilibrium of this game.

Per the comments, I've edited background and my own thoughts on the problem so far.

Background - I've been trying to self-study game theory, and I've been reading about auction types and different types of payouts. Auction game payouts tend to have a "punishment" feature for betting excessively high, so that participants are incentivized to keep their bids relatively small. This had me thinking--what if we designed a zero-sum payout so that the winner pays the loser, but the loser pays the value of the item. I proposed this to a colleague, and while he wasn't able to solve it, he helped me reformulate the problem so that issues of randomness and incomplete information are also relevant--making this an even more interesting problem.

Progress - As mentioned in my original post, I've taken to looking at Bob's perspective. Bob is missing only the value of Alice's die, but even without that information, Bob decides if he wants to win the auction or lose the auction by betting higher or lower than Alice's bid.

If Bob decides that he wants to win the auction, then he will be paying his bid to Alice, so it's optimal to bet $a + 1$, where $a$ is Alice's bid. On the other hand, if he thinks it'd be more optimal to lose the auction, it doesn't matter what he bets--either way, he bets lower than Alice, so he gets Alice's bid, but pays Alice the sum of the two dice. For convention, we can simply say he bets $\$0$. Thus Bob only has two choices.

But, thinking about Alice's strategy is harder, and I've formulated it into a minimax problem. Define $E(a, y)$ to be the expected value of the sum of the dice given Alice's bid $a$ and the roll on Bob's die $y$. Then, we can expect Bob to bet $a + 1$ if $E(a, y) - (a + 1) > a - E(a, y)$, and 0 otherwise. Bob will always choose the larger of the LHS and the RHS, so we want to choice a strategy for Alice such that the max between the LHS and RHS is minimized.

Edit:

Here's the best solution I could come up with. Consider Bob's perspective, where he essentially has two options: betting $\$a + 1$ and winning optimally, or betting $\$0$ and losing the auction. Note that the expected value of the sum of the two dice from Bob's perspective is $E[X+Y | a] = E[X | a] + E[Y | a] = E[X | a] + y$.

As the payouts are structured, Bob will bid $a + 1$ iff $E[X | a] + y - (a + 1) > a - (y + E[X | a])$, and 0 otherwise. The expected value of Bob's winnings will be the max of the LHS and RHS of the inequality.

Next, we define $k = a - E[X | a]$. All 6 values of Bob's dice are equally likely, so we can say that Bob's expected earnings will be $$E[B] = \frac{1}{6}\sum_{y=1}^{6}max(k - y, -k + y - 1).$$

Alice wants to minimize $E[B]$ wrt to k, so we have a minimax problem. With some analysis, I was able to show that this value is minimized when $3 \leq k \leq 3.5$, with $E[B] = 1$. Take $k = 3$ as one strategy. Then, recalling that $k = a - E[X|a]$, one simple strategy that yields $k = 3$ is for Alice to simply bet $\$3$ more than the dice roll she sees (assuming that Bob knows this is her strategy.)

This yields an expected loss of $\$1$ for Alice each game, which seems to be supported by a Python simulation.

2

There are 2 best solutions below

6
On

Very nice editing of the query. The following long-winded reaction can not in any way be construed as an answer. However, it is so long-winded, that it would be ridiculous to present it as a series of comments,

Look at the situation from Alice's viewpoint, and assume that Alice rolls an $n$, where $n \in \{1,2,3,4,5,6\}.$ My initial (blind) instinct is that Alice's optimal strategy is to bid $(n+3)$ 50% of the time and $(n+4)$ 50% of the time, with Bob (presumably) assuming that she will follow this strategy.

This means that at any given point, Bob doesn't know whether her bid represents $(n+3)$ or $(n+4)$, but he assumes that it must be one of those two. I think the first issue to consider is whether Alice should practice deception, and if so, how often. An example of this would be Alice rolling a 6 and bidding 7, rather than bidding 9 or 10.

A different deception strategy would be that 10% of the time, Alice will pretend that her roll is 2 less than it was (unless she rolled a 1 or 2) and similarly 10% of the time, Alice will pretend that her roll is 2 more than it was (unless she rolled a 5 or 6). My (blind) conjecture is that Bob can defeat any attempts at deception by pretending that Alice never tries to deceive. This blind conjecture may well be wrong.

Remember, I have no knowledge of Nash equilibriums. From this (ignorant) perspective, you would have to calculate Bob's expected profit assuming that Alice never tries to deceive. You would then have to conjure various strategies that Alice might adopt to lessen Bob's profit. If you can actually find a way to alter Alice's strategy so that Bob's profit is lessened (assuming Bob sticks with the "Alice is not deceiving idea"), you then have to consider how Bob might alter his strategy to react to a possible alteration in Alice's strategy.

Further, you have to consider the possibility that Bob will start with one strategy, then (perhaps) vary it based on Bob's analysis of what Alice is doing. Similarly, you have to consider that Alice will start with one strategy, and then (perhaps) vary it (perhaps temporarily) based on Alice's analysis of what Bob is doing.

To get (and prove) a definitive answer (absent any knowledge of Nash equilibriums), you may have to write a computer program to test out various strategies that Alice &/or Bob may adopt.

3
On

I'm not sure there is a "nice" solution to this problem, as even such a simple-looking problem can actually have many parameters and considerations.

First, let's assume that the bids must be integers and that if Bob and Alice bid the same, one of them is chosen to be the winner by a flip of a coin (other tie-breaking rules can be considered, it doesn't matter much).

Clearly, Alice's strategy shouldn't be pure. If she plays pure, she reveals her information, and Bob, who has all the information now, can always make sure to bid the correct amount w.r.t to her bid and $X+Y$. Her payoff is strictly negative in this case.

Thus, Alice should play a mixed strategy, which means that for each $x\in\{1,\ldots,6\}$ she needs to decide on a distribution $p_x$ over $\{2,\ldots,12\}$, then randomize and bid accordingly. Bob, knowing the second roll $Y$ and Alice's choice $a$, needs to estimate the first dice (Probability of $i$ is $\tfrac{p_i(a)}{p_1(a)+p_2(a)+\ldots+p_6(a)}$) and then he can calculate the expected payoff of winning the auction, the expected payoff of losing and chose the best.

Given the $p$s his strategy is quite simple, but Alice has $60$ variables to work with and optimize her payoff. I'm not sure how to do it nicely and no "obvious" strategy comes up (part of the problem: Alice's bid is both payoff relevant AND tries to conceal information from Bob).