4
$\begingroup$

A deck of $N$ cards is used to play a 4-player game. The game begins with each player being randomly dealt 7 cards from the deck. They then take turns according to a set of rules, after which a single winner is crowned. The exact rules of the game are complex and not worth explaining in detail.

Certain cards in the deck are better than others, so the players decide to institute a pre-game draft to even out the variance. In the draft, each player is randomly dealt 7 cards face-down from the deck. Each player looks at his cards, chooses one to keep, and passes the remaining 6 cards face-down to the player to his left. After each player has done this, the process is repeated, this time each player choosing from the 6 cards received from his right, choosing one to keep, and then passing 5 to the player to his left. This is repeated until each player has chosen exactly 7 cards. They then proceed with the actual game.

Now suppose that the draft-version of this game has a unique Nash Equilibrium strategy, and let us imagine that 4 copies of this strategy play against each other. We can define two functions of cards that might be representative of their strength:

Expected-draft-position: The expected-draft-position of a card $c$, $\mathrm{EDP}(c)$, is the expected position in which $c$ is drafted, given that $c$ was dealt out in the draft. For instance, if a card $c$ is always the first card drafted, then $\mathrm{EDP}(c)=1$. If it is always the last card drafted, then $\mathrm{EDP}(c)=7$. Note that the average $\mathrm{EDP}$ over all $N$ cards must be 4.

Win-probability: The win-probability of a card $c$, $\mathrm{WP}(c)$, is the probability that the player that drafted $c$ will win the game, given that $c$ was dealt out in the draft. Note that the average $\mathrm{WP}$ over all $N$ cards must be 0.25.

Conjecture: $\mathrm{EDP}(x) < \mathrm{EDP}(y)$ iff $\mathrm{WP}(x) > \mathrm{WP}(y)$ for all cards $x, y$.

Question: Is this conjecture true? If not, are there some "minimal" assumptions we can make about the game rules so that it becomes true?

A little background: I am part of an online board game community, and the above two statistics are computed empirically from our game logs, which involve imperfect human players rather than Nash Equilibrium strategies. For certain pairs of cards, my conjecture does not hold, and I am personally convinced that this must indicate that players are drafting sub-optimally. I would like to be certain of this conviction via mathematical proof.

$\endgroup$
1
$\begingroup$

After discussion with bjorn, we arrived at the following counterexample. However, the part of my question where I ask about a minimal set of conditions to make the conjecture true remains open.


Counterexample

Consider a deck with N=28 cards, so that every card is dealt out in every game. The cards, $c_1, c_2, \ldots, c_{28}$, are positive real values, with $c_k = 1.0+k\epsilon$ for some positive $\epsilon \ll 1$.

Say player $i$ has drafted cards $S_i$. The game works as follows: the winner is randomly chosen, with player $i$’s chances of winning proportional to $p(S_i)$, where

$$ P(S) = \begin{cases} 10^{100},& \text{if } c_1, c_{28} \in S\\ \prod_{c\in S} c, & \text{otherwise} \end{cases} $$

The Nash Equilibrium strategy is clear: draft $c_1$ if necessary. Else, draft the highest available card. Clearly, at equilibrium, the $10^{100}$ bonus will never be obtained.

It is easy to see that $\mathrm{EDP}(c_1) < \mathrm{EDP} (c_2)$ and that $\mathrm{WP}(c_1) < \mathrm{WP}(c_2)$.

$\endgroup$
  • $\begingroup$ It's not that obvious that this is an equilibrium. The player dealt $c_1$ must weigh the risk of letting the next player win by passing $c_1$ against the huge disadvantage of keeping $c_1$ while everyone else probably keeps a very high card. If I had to guess, I'd think that the second effect dominates. But if so, your counterexample can easily be fixed by letting $c_{26}$ be the second bonus card and showing that $\text{EDP}(c_{26})\lt\text{EDP}(c_{27})$ and $\text{WP}(c_{26})\lt\text{WP}(c_{27})$. $\endgroup$ – joriki Aug 13 '15 at 18:42
  • $\begingroup$ The second effect's impact on your win probability will be capped by $\delta$, a constant that can be made arbitrarily close to 0 by choosing $\epsilon$ appropriately. $\endgroup$ – dshin Aug 14 '15 at 20:35
  • $\begingroup$ I see -- sorry, I misunderstood $P(S)$ to be a score determining the winner rather than the win probability. $\endgroup$ – joriki Aug 14 '15 at 22:25
0
$\begingroup$

Card drafting games are most often played one card per player per turn. As the exact rules are complex, it's most likely that the turns of the game are not independent and the cards a player receives differ in value depending on the other cards a player has. That is, the value of a specific card will be different to each player based on the other cards a player has. If this is the case and there are some combinations of cards that are worth more together, then we could easily find circumstances such that the conjecture EDP(x) < EDP(y) iff WP(x) > WP(y) is false. Each player can then be following a separate Nash Equilibrium strategy depending on the cards he has already drawn in the draft.

For the conjecture to hold true mathematically you would need the positional value of the cards to remain constant. Depending on the rules of the game this is possible, for example the conjecture would be hold if each turn of the game is played independent of other turns in the game, one card per turn. I see this as a trick-winning game where it is easy to identify where one card is better than another card.

$\endgroup$
  • $\begingroup$ There are definitely combinations of cards that are worth more together in this game. However, it is not obvious to me at all that this fact would imply that the conjecture is false. Can you produce a toy counterexample? $\endgroup$ – dshin Nov 3 '14 at 5:50
  • $\begingroup$ What is obvious to me is that there can be a situation where the Nash Equilibrium would draft x over y, and another situation where it would draft y over x. But I don't see how that would be incompatible with the conjecture. $\endgroup$ – dshin Nov 3 '14 at 5:53
  • $\begingroup$ "Each player can then be following a separate Nash Equilibrium strategy depending on the cards he has already drawn in the draft." - I think you might be confused here, I have assumed that there is a unique Nash Equilibrium. $\endgroup$ – dshin Nov 3 '14 at 5:55
  • $\begingroup$ Yes, I meant that the players would be following different strategies depending on the cards each player had drawn. In this instance there likely is a single best strategy to follow, but that strategy is dependent on the cards that are drafted. $\endgroup$ – bjorn Nov 3 '14 at 17:02
  • $\begingroup$ Because the cards a player has are not independent of one another, it becomes much harder to show that the cards follow a static positional valuation, which is needed for the conjecture to hold. $\endgroup$ – bjorn Nov 3 '14 at 17:05
0
$\begingroup$

Although it's heuristically reasonable, I don't believe there's any fundamental reason that your inequality must hold. Here's a made-up scenario that may provide a counterexample. Let the deck consist of a large number of irrelevant cards, plus three important cards: $A$, $B$, and $C$. Card $A$ increases your odds of winning slightly, regardless of what other cards were drafted. Card $C$ causes you to lose with certainty. Finally, card $B$ gives you an edge if card $C$ was not dealt at all; but if card $C$ is dealt and drafted (by anyone), card $B$ hurts your chances. Clearly no one will voluntarily choose $C$, so it'll go around the circle. Card $B$ becomes more attractive as you become more certain that $C$ wasn't dealt -- so as more cards are seen by you or are chosen by others, $B$ increases in value (unless you see $C$). Finally, since card $A$ is unconditionally advantageous, you will snap it up immediately (i.e., $\text{EDP}(A)=1$). I believe the win probabilities can be tweaked so that $B$ has a greater win probability than $A$, but is drafted later (when the drafter has a little more information about the other cards).

$\endgroup$
  • $\begingroup$ If B’s edge is so strong that WP(B)>WP(A), it may be correct to draft B ahead of A as a gambit. $\endgroup$ – dshin Nov 3 '14 at 19:16
-1
$\begingroup$

I don't think the answer can be fixed because if a player knows that the player on his right used a certain strategy and that all the players use the same thought process as him, he will improve his strategy accordingly. Over time, the previous player will get to know of his strategy and modify his accordingly, so will all the players after him. This will keep on repeating till the players realize that they can't outwit the other players. They will use the best strategy that works independently of the other players' decisions (and probably keep the best card with them every time).

I don't know about the math, but from a logical point of view, this should be the answer. It is the same reason why there can never be a perfect strategy that works against itself in card games like no-limit holdem poker.

$\endgroup$
  • 2
    $\begingroup$ There IS a perfect strategy in no-limit holdem poker. A strategy that, even if I told you exactly what it does in every situation, there is absolutely nothing you could change about it to improve it. John Nash proved it in 1950, it is quite a simple proof that can be understood with just an undergraduate level background in topology. Nobody knows what this strategy is, but we are as certain it exists as we are that 2+2=4. $\endgroup$ – dshin Nov 1 '14 at 13:21
  • $\begingroup$ Then I have no idea. Does a perfect strategy mean it can't be defeated or that it has the greatest probability of winning? Or something else? $\endgroup$ – ghosts_in_the_code Nov 1 '14 at 14:25
  • 1
    $\begingroup$ A set of strategies are in Nash Equilibrium if no player can adjust his strategy to improve his performance. $\endgroup$ – dshin Nov 1 '14 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.