Maximal in-degree in directed voting graph

Question

Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about whose talk they would like to hear. (Everyone is modest, so no-one voted for their own talk.) Now, unfortunately, there were two talks receiving the maximum vote number, so a coin had to be tossed. - Informally speaking, I was wondering whether this dilemma situation would be less likely as $n$ grows. See formal version below.

Formal version. In this context, we define a directed graph $G=(V,E)$ to consist of a finite set $V$ and of a set $$E \subseteq (V\times V)\setminus\{(v,v):v\in V\}.$$ Given $v\in V$, we define the in-degree by $\text{deg}^-(v) = |\{a\in V:(a,v)\in E\}|$, and the out-degree is defined in a dual fashion. Let $\Delta^-(G)$ be the maximal in-degree.

In this question we only consider directed graphs $G=(V,E)$ with out-degree $\text{deg}^+(v) = 1$ for all $v\in V$ (everyone casts exactly 1 vote). Let ${\cal M}(G) = |\{v\in V: \deg^-(v) = \Delta^-(G)\}|$ be the number of vertices having maximal in-degree. (Trivially, ${\cal M}(G) \geq 1$.) Moreover, let $M_n$ be the expected value of ${\cal M}(G)$ where $G$ is an arbitrary graph with $V(G) = \{1, \ldots, n\}$ satisfying $\text{deg}^+(v) = 1$ for all $v\in V$.

Do we have $\lim\sup_{n\to\infty}M_n = 1$?

Answer 1

Let's do a back of the envelope computation for a slightly simpler problem (when voting for one's own talk is allowed). It doesn't seem like it matters too much, but formally it is a bit different. There will be no formal proof, just an "educated guess" anyway. We have $n$ numbered urns (talks) and $n$ balls (votes) and the question is what approximately is the probability that the maximum is unique when $n$ is very large. We can think instead of the independent Poisson distribution in each urn (a leap of faith occurs here), i.e., the probability that each urn has exactly $k$ balls is $\frac 1{ek!}$.

Suppose that the maximum is $K$ and it is unique. It means that there is an urn with exactly $K$ balls and every other urn has fewer balls. The probability of that is $$ \frac n{eK!}\left[\sum_{k=0}^{K-1}\frac 1{ek!}\right]^{n-1} $$ after which we have to sum over $K$ from $1$ to $\infty$.

Notice that it is the left Riemann sum for $nx^{n-1}$ on $[0,1]$ with fixed partition refining near $1$. The issue is that the partition interval lengths decay very fast near $1$ while $nx^{n-1}$ is pretty much the same as $ne^{-n(1-x)}$, so, reflecting about $1$, we arrive at the following situation:

We have the function $e^{-x}$ and take the right Riemann sum over some partition in which each next (to the right) interval is huge compared to the previous one. Then there is at most one interval of length comparable to constant (perhaps none) and it determines the probability up to $o(1)$. Thus, the upper limit should be $\max_{x>0} xe^{-x}=1/e$ and the lower limit should be $0$, so the tie is more likely than not in every case.

It is worth mentioning, however, that the current Earth population ($\approx 7.6\times 10^9$) is way too low to see that effect, so for any reasonably sized group of humans, you can safely say that the probability of tie is $50\%\pm 10\%$.

Answer 2

I threw together a quick Java program to calculate this for $N$ up to 10, and it actually seems to be more likely as $N$ grows, with a limit of slightly below $\frac12$:

N = 2 ties: 1, no ties: 0, ratio: 1.0
N = 3 ties: 2, no ties: 6, ratio: 0.25
N = 4 ties: 21, no ties: 60, ratio: 0.25925925925925924
N = 5 ties: 344, no ties: 680, ratio: 0.3359375
N = 6 ties: 6535, no ties: 9090, ratio: 0.41824
N = 7 ties: 129534, no ties: 150402, ratio: 0.46272719478737995
N = 8 ties: 2747073, no ties: 3017728, ratio: 0.47652520876262683
N = 9 ties: 63421784, no ties: 70795944, ratio: 0.4725291132926941
N = 10 ties: 1607637771, no ties: 1879146630, ratio: 0.4610660098567993

(Of course, it's entirely possible that with even higher $N$ the likelihood of ties decreases and eventually reaches 0. It's just much higher than I would expect.)