9
$\begingroup$

Let's say you have a finite directed graph, with no two nodes that point at each other. Can we assign each node a dice, so that each node beats the node it is pointing at.

This is easy for acyclic graphs, but it is possible for some non-acyclic graphs: see Nontransitive dice.

By dice, I mean any probability distribution the natural numbers (including those of infinite support). A dice beats another if the probability of it being higher than the other is more than a half.

Can we assign nontransitive dice to an arbitrary graph?

Also: Can this still work with certain infinite graphs?

$\endgroup$

1 Answer 1

10
$\begingroup$

It's possible for any directed graph that has no length-2 cycles. My algorithm is non-optimal, and requires $2e+2$ sides on each die, where $e$ is the number of edges in the graph. All dice not connected by an edge will be even competitors.

It would probably be more proper to define this as an inductive proof, but I'm just going to describe how you'd build it up an edge at a time.

Say your graph has $n$ nodes. Start out with $n$ identical 2-sided dice. Each having 0 on both sides will work fine.

Pick an arbitrary edge in the graph, specifying that $D_a$ should beat $D_b$. All the dice currently have $k$ sides, and satisfy the requirements for previously added edges, and unconnected dice are even. Find $m$, the maximum of all the faces on the dice. To $D_a$, add two faces with $m+3$. To $D_b$, add two faces of $m+2$. To all other dice, add two faces, one of $m+1$ and one of $m+4$. Repeat this procedure for all edges in the graph, winding up with $2e+2$-sided dice.

Now I need to show that this works. Let $p(x,y)$ be the probability that $D_x$ beats $D_y$ before one of these edge iterations, and let $p'(x,y)$ be the probability that $D'_x$ beats $D'_y$ after one of these edge iterations.

First look at $D'_a$ and $D'_b$. $D'_a$ has a $\frac2{k=2}$ chance of rolling $m+3$ and winning over any $D'_b$ roll. $D'_a$ can also win half the time when both dice roll numbers appearing on their old versions, which occurs with probability $\frac{k^2}{(k+2)^2}$. $$\begin{align} p'(a,b) & = \frac{k^2}{(k+2)^2} p(a,b) + \frac{2}{k+2} \\ & = \frac{k^2}{2(k+2)^2} + \frac{2}{k+2} \\ & = \frac{k^2 + 4k + 8}{2(k+2)^2} \\ & = \frac{(k+2)^2 + 4}{2(k+2)^2} \\ & = \frac12 + \frac{2}{(k+2)^2} \text{ so $D'_a$ beats $D'_b$.} \end{align}$$

Now look at $D'_a$ and some other $D'(x)$ where $x$ is not $a$ or $b$. There are six cases. Two cases where $D'_a$ rolls either an old number or $m+3$. Three cases where $D_x$ rolls either an old value, $m+1$, or $m+4$. $$\begin{align} p'(a,x) & = \frac{k}{k+2}\left[\frac{k}{k+2}p(a,x)\right] + \frac2{k+2}\left[\frac{k}{k+2} + \frac{1}{k+2}\right] \\ & = \frac{k^2}{(k+2)^2}p(a,x) + \frac{2k+2}{(k+2)^2} \\ & \text{Define $\epsilon$ so that $p(a,x) = \frac12 + \epsilon$} \\ & = \frac{k^2 + 2k^2\epsilon}{2(k+2)^2} + \frac{2k+2}{(k+2)^2} \\ & = \frac{k^2 + 4k + 4 + 2k^2\epsilon}{2(k=2)^2}\\ & = \frac12 + \frac{2k^2}{2(k+2)^2}\epsilon\\ \end{align}$$

Now we know that the sign of $p(a,x) - \frac12$ is the same as the sign of $p'(a,x) - \frac12$, so any previous dominance relationship between $D'_a$ and $D'_x$ is preserved.

Challenges between $D'_b$ and some $D'_x$ can be checked similarly, as can challenges between $D'_x$ and $D'_y$ where $x$ and $y$ designate dice other than $a$ and $b$.

$\endgroup$
3
  • $\begingroup$ Cool. Is there a way to do this so no two dice have the same side (just wondering)? $\endgroup$
    – PyRulez
    Jan 24, 2016 at 15:53
  • $\begingroup$ Oh wait, I see. Instead of $1$ and $4$, add $1+\epsilon$ and $4-\epsilon$ (which will maintain all necessary ties), and then multiply by a common denominator at the end. $\endgroup$
    – PyRulez
    Jan 24, 2016 at 15:56
  • 1
    $\begingroup$ That seems like it would work. You don't have to keep the numbers proportional, you just have to preserve their relations. So you could just iterate through all the faces from lowest to highest and replace them with integers. $\endgroup$ Jan 25, 2016 at 7:41

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.