38
$\begingroup$

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

$\endgroup$
15
  • 1
    $\begingroup$ Exactly what do you mean by "taking all different values"? $\endgroup$
    – Seva
    Nov 10, 2013 at 10:41
  • $\begingroup$ Is $n$ assumed to be large in terms of $t$? (Otherwise, even the cases $n=1$ and $n=2$ seem to present a problem.) $\endgroup$
    – Seva
    Nov 10, 2013 at 10:52
  • $\begingroup$ Taking all different values means that for any i, j, k, l we have $f_i(k)\ne f_j(l)$. Btw, this condition is in fact redundant, so you can ignore it if you wish. $\endgroup$
    – domotorp
    Nov 10, 2013 at 13:49
  • 1
    $\begingroup$ Sorry, I just want to know if there is an n, I don't want all n's, I changed the first line. $\endgroup$
    – domotorp
    Nov 10, 2013 at 13:51
  • 4
    $\begingroup$ Just pointing out the obvious: a strong version for $t=2$ and arbitrary $\epsilon$ implies strong version for any $t$. $\endgroup$ Nov 18, 2013 at 0:35

2 Answers 2

27
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Magical - I wonder how you've found this or if anyone manages to extend/generalize it. $\endgroup$
    – domotorp
    Nov 27, 2013 at 20:01
  • 3
    $\begingroup$ Well, found mostly by luck. I wanted a weakly $2$-transitive group action which wasn't strictly $2$-transitive because that reduced from checking $\binom{n}{2}$ dominances to checking one. The easiest example I knew of was $\mathbb{Z}/((p-1)/2) \ltimes \mathbb{Z}/p$ acting on $\mathbb{Z}/p$ for $p$ a prime which is $3 \mod 4$. By good luck, the first parameters I tried worked. I guess it also helped that the Arrow story suggested many voters, few candidates; most people seem to be trying the opposite. $\endgroup$ Nov 27, 2013 at 21:00
  • 3
    $\begingroup$ A strategy for proving a bound of $3/4$, or maybe even $2/3$. Make a directed graph with $n$ vertices and an edge $i \to j$ if the majority of voters prefer $i$ to $j$. Call an edge $i \to j$ a STRONG edge if there is some $j'$ so that $i$ is preferred to $\max(j,j')$. Our hypotheses say there are a lot of strong edges. An easy lemma is that, if $p>2/3$, there are no strong directed triangles. If $p>3/4$, there are no directed triangles with two strong edges. Maybe we can show that this is impossible? $\endgroup$ Nov 28, 2013 at 2:02
  • 1
    $\begingroup$ This solution has the same parameters as the Oskar dice. Is it the same? $\endgroup$ Jun 27, 2020 at 12:13
  • $\begingroup$ @TobiasFritz Nice find! The intransitive dice problem is a special case of this one. If we have $d$ dice, let $X$ be the set of all possible outcomes of dice rolls. (So, if all dice are $6$-sided, then $|X| = 6^d$.) Build a $d \times |X|$ table where the $(i,j)$ entry is the value of die $i$ in roll combination $j$. Then a set of $t$-intransitive dice like Oskar constructed will also solve this problem. But I very much doubt there is a reduction in the other direction. $\endgroup$ Jun 27, 2020 at 12:47
20
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ What is $p$? (There is no $p$ in the original question.) What do you mean by "Given $f_1,\ldots, f_t$, let $f_i=h_{a_I,b_I}$"? (If $f_i$ are given, how can you define them?) $\endgroup$
    – Seva
    Feb 19, 2014 at 8:51
  • 3
    $\begingroup$ p is take from David Speyer's answer--it's the fraction of inputs on which g>max(f_1,...,f_t). I fixed the phrasing for the other question. $\endgroup$ Feb 20, 2014 at 22:02
  • $\begingroup$ Hi, I'm sorry but for some reason I've not seen your answer earlier. Very nice construction and this might even be the correct value. I hope it inspires some people to work on the problem. $\endgroup$
    – domotorp
    Sep 2, 2014 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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