1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ It seems every bid must be a whole number of dollars? $\endgroup$
    – aschepler
    Commented Sep 5, 2020 at 23:08
  • $\begingroup$ I upvoted because this is a very interesting question, which I can not answer because I am totally unfamiliar with Nash equilibriums. In order to get knowledgeable mathSE help, I suggest that the OP edit his query by providing two pieces of information: (1) What is the background of the problem? If the problem is from a contest, which contest? If (instead) the problem is from a book &/or class, what theorems or previously (solved) problems has your book or class focused on that you think might be pertinent here? ... see next comment $\endgroup$ Commented Sep 6, 2020 at 2:22
  • $\begingroup$ (2) Re the previous comment, construing the background as tools, please try to use the tools to solve the problem. After doing so, please (also) edit your query to show this work. ...see next comment $\endgroup$ Commented Sep 6, 2020 at 2:24
  • $\begingroup$ Even if I was expert in Nash equilibriums, I (still) would withhold an answer. This is because the mathSE protocol wants the OP to provide background and show his work, before an answer is given. $\endgroup$ Commented Sep 6, 2020 at 2:26
  • $\begingroup$ I appreciate the feedback, and I've edited my post. Hope this helps. $\endgroup$
    – user815048
    Commented Sep 6, 2020 at 4:31

2 Answers 2

0
$\begingroup$

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).

$\endgroup$
3
  • 1
    $\begingroup$ Yeah, I've written out the expected net money gain/loss in terms of Alice's die result and Alice's strategy with a probability matrix. It's not pretty, and there are so many "ifs" (actually in the form of greatest-integer-functions) that I'm stumped how to approach a next step even with computer. $\endgroup$
    – aschepler
    Commented Sep 7, 2020 at 13:25
  • $\begingroup$ I appreciate your response, but I'm not convinced by the argument that a pure strategy is suboptimal just because Alice's EV would be negative. I believe that no matter what strategy Alice plays, her EV will be negative. Even if Alice's bid reveals nothing about her dice value, Bob still comes out with +EV (justification for this can be found in my comments to user2661923's response.). Then, any additional information from Alice's bid about her dice value can only help Bob, so I believe the game will always be in Bob's favor. $\endgroup$
    – user815048
    Commented Sep 7, 2020 at 20:48
  • $\begingroup$ In my post, I've edited in a solution that used a pure strategy and appears to be optimal. Though I do believe it's correct, I welcome any criticism. $\endgroup$
    – user815048
    Commented Sep 7, 2020 at 20:50
-3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks for your thoughts! As far as I know, a Nash Equilibrium is a strategy adopted by Alice and Bob such that neither one of them can do better by changing their strategy. As for the deception, I've also made the insight that Bob can do quite well if he assumes (possibly incorrectly) Alice is betting randomly. Then, $E(a, y)$ is independent of $a$, and is simply $y + 3.5$, since the expected value of Alice's dice is 3.5. By the analysis I edited into my original post, if we define $x = a - (y + 3.5)$, we can see Bob's analysis comes down to comparing $x$ with $-x - 1$. $\endgroup$
    – user815048
    Commented Sep 6, 2020 at 6:29
  • $\begingroup$ The maximum of the two will only be negative (i.e. both values are negative) for x between 0 and 1. This implies that at most only one value of $y$ will Bob's expected value, playing optimally, be negative, out of a total of 6 possibilities for $y$. That being said, however, for any kind of equilibrium solution, I don't expect Alice to be playing a completely random strategy. I'm not quite sure how that fits in. $\endgroup$
    – user815048
    Commented Sep 6, 2020 at 6:37
  • $\begingroup$ @user815048 I'm not sure (so you have to take this comment with a large grain of salt), but my instinct is that Alice can improve on the strategy of playing randomly. This suggests that you are oversimplifying the analysis. One (possible) justification of my instinct (there may also be other justifications) is that Alice may not want to grant Bob the leverage of being able to assume that $E(a,y)$ is independent of $a.$ Have you actually mathematically proven that Alice's best strategy is to bid randomly? $\endgroup$ Commented Sep 6, 2020 at 7:19
  • $\begingroup$ No, that's not the claim I'm making at all. Rather, regardless of Alice's strategy, if Bob assumes (even incorrectly!) that Alice is playing randomly, it seems that he can still come out with positive expected value. I'm sure Alice can mitigate this to some extent by not playing randomly, but I was addressing the conjecture you posed in the original response. This is also not to say Bob's optimal strategy is to suppose Alice is playing randomly, but rather, this is a lower bound for how well he can do. $\endgroup$
    – user815048
    Commented Sep 6, 2020 at 16:18
  • 1
    $\begingroup$ "Alice should practice deception" - a NE is a pair of strategies that are the best response to one another. It is assumed that Alice's strategy is known and Bob BR to her and vice-versa. If Alice "practices deception", she in-fact plays a different strategy... $\endgroup$
    – YJT
    Commented Sep 7, 2020 at 9:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .