Is there a finite family of functions such that the max of any two functions can be dominated by a third?

Question

Is it true that for every $t$ there is an $n$ and there exists a finite function family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different values) and for any $f_1, \ldots, f_t \in \cal F$ there is a $g \in \cal F$ such that $g > \max(f_1,\ldots, f_t)$ on

(weak form:) more than $n/2$ inputs,

(strong form:) $(1-\epsilon)n$ inputs (for some small $\epsilon>0$)?

I already don't know the answer for $t=2$, while for $t=1$ it is easy to give such a family. The question is an equivalent formulation of a problem regarding discrete voronoi games (see http://arxiv.org/abs/1303.0523).

Update: Wow, no answers even after the bounty, quite surprising. Meanwhile, Lev Borisov has observed in the comments that if the strong version is true, it is enough to prove it for $t=2$. Seva has posed a weaker (?) version of the problem: "Circular" domination in ${\mathbb R}^4$. The current best bound is due to Sam Zbarsky (see his answer).

Here are some somewhat related, potentially useful results:
https://arxiv.org/abs/1504.03602
https://arxiv.org/abs/1601.04146

Answer 1

I can achieve $t=2$, $n=21$, $|\mathcal{F}|=7$. Every pair from $\mathcal{F}$ is defeated by some other element on $11$ of the $21$ coordinates. For future answer's sake, I propose that we report these parameters as $(t,n,c,p) = (2,21,7,11/21)$. If I am not mistaken, this is the first $(2,n,c,p)$ anyone has reported with $p>1/2$.

Take $G$ to be the $21$ element sub group of $S_7$ given by maps $\mathbb{Z}/7 \to \mathbb{Z}/7$ of the form $x \mapsto ax+b$, with $a \in \{ 1,2,4 \}$. Let $G$ act on $\mathbb{R}^7$ by permuting coordinates. Let $\vec{v} \in \mathbb{R}^7$ have strictly increasing coordinates and let $A$ be the $7 \times 21$ matrix whose columns are the $G$ orbit of $\vec{v}$.

$G$ acts transitively on unordered pairs of distinct elements in $\mathbb{Z}/7$. So it is enough to check the claim for one unordered pair of coordiantes: Say $\{ 1,2 \}$. I find that, in $11$ of the $21$ columns of $A$, the $3$rd entry is greater than the first or second.

I tried this idea with some other permutation groups that are weakly $2$-transitive but not strictly $2$ transitive, but it didn't work for any of the others. (The trouble with strictly $2$-transitive is that for any pair $f$, $g$ in $\mathcal{F}$, we wind up with $f$ and $g$ tied, and $\max(g,h)$ can only be better than $g$, so $f$ never beats $\max(f,g)$.)

For the sake of more amusing conversations, I'll share the story I have in my head: This problem is about Arrow's voting paradox for $t$-faced candidates. Consider $n$ voters and $c$ candidates; the $i$-th coordinate of the $j$-th element of $\mathcal{F}$ is how well voter $i$ likes candidate $j$. If $t=1$, we are just pointing out that there may be no Condorcet winner. To imagine $t=2$, consider a $2$-faced candidate: when talking to voters who prefer $f$'s positions, she says what $f$ would say and, when talking to voters who prefer $g$'s positions, she repeats $g$'s slogans. The question is whether we can find a situation where every $2$-faced candidate loses to some sincere candidate (and by an overwhelming margin.)

Answer 2

For any $t$, we can get $p$ arbitrarily close to $\frac{2}{t+1}$ (in particular, for $t=2$, this gives $p=2/3-\epsilon$).

Take some large $N$ and let $n=(t+1)N$. For $a\in [t+1]$ and $b\in [N]$, define $h_{a,b}:[t+1]\times [n] \to \mathbb{N}$ by $h_{a,b}(c,d)=\big(a+c\pmod{t+1}\big)N+\big(b+d\pmod{N}\big)$ for any $d\in [N]$ and $c\in [t+1]$ (intuitively, $c$ and $a$ matter more, while $b$ and $d$ are used for tie-breaking). Let $\mathcal{F}=\{h_{a,b}\}$.

Given $f_1,\ldots,f_t$, let $a_i,b_i$ be such that $f_i=h_{a_i,b_i}$. A pigeonhole argument gives us that there must be some $a$ so that $a_i\not\equiv a+1 \pmod{t+1}$ for all $i$ and there is at most one $j$ with $a_j=a$. If there is no such $j$, we pick $g=h_{a,1}$. If such a $j$ exists, we pick $g=h_{a,b_j+1\pmod{N}}$. Then whenever $c=t+1-a$ or $c\equiv t-a\pmod{t+1}$ and $(c,d)\ne(t+1-a,N-b_j)$, we have $g(c,d)>\max(f_1(c,d),\ldots,f_t(c,d))$. Thus we get $p=\frac{2N-1}{(t+1)N}=\frac{2}{t+1}-\frac{1}{(t+1)N}$.

Answer 3

The question has been answered in this paper: Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, Kangning Wang: Six Candidates Suffice to Win a Voter Majority

In particular, they showed that if $\frac{1-\varepsilon}{1-\ln(1-\varepsilon)}\ge\frac2{t+1}$, then there is no such family $\mathcal F$.
For $\varepsilon=\frac12$, this gives that $t=6$ is enough.