There is a fixed set $K$ with $k\geq 2$ elements. A relation $\geq$ on $K$ is called a weak ordering if it is transitive and complete (for each $x,y\in K$, either $x\geq y$ or $y\geq x$ or both).
There is a set $N$ of $n\geq 2$ weak orderings on $K$, and a number $m \leq n$. We would like to create a new weak ordering $\succsim$ on $K$ with the following agreement property:
$x\succsim y$ only if at least $m$ orderings in $N$ agree that $x \geq y$.
For what values of $m$ (as function of $n,k$) is it possible to create this $\succsim$?
- When $m=n$ this might be impossible even for $k=2$. As an example, suppose $K = \{x,y\}$, and the set $N$ contains $n=2$ weak orderings: one with $x\geq y$ and one with $y\geq x$. Then, with $m=2$, the agreement property implies that neither $x\succsim y$ nor $y\succsim x$ - but then $\succsim$ is not a complete relation.
- When $m \leq n/2$, this is possible for $k=2$. Suppose $K = \{x,y\}$. Since each ordering in $N$ is complete, it contains either at least $n/2$ relations for which $x\geq y$, or at least $n/2$ relations for which $y\geq x$ (or both). In the former case set $x\succsim y$, in the latter case set $y\succsim x$. The resulting relation is a weak ordering and it satisfies the agreement property.
- In general, when $m \leq n/k!$, this is possible, since by the pigeonhole principle, there exists an ordering of the elements that is contained in at least $n/k!$ relations in $N$, so we can make $\succsim$ equal to this relation.
Is it possible for $m > n/k!$? What is the largest $m$ (as a function of $n$ and $k$) for which this is possible?
EDIT: I think it is possible whenever $m \leq n/k$. Construct the new relation as follows.
If $x\geq y$ for more than $n (k-1)/k$ orderings in $N$, then set $x\succsim y$.
Add to $\succsim$, all the relations that follow from the existing relations by transitivity.
Complete the remaining relations arbitrarily in any way consistent with transitivity. By step 1, in all the remaining pairs, both $x\geq y$ and $y\geq x$ are agreed by at least $n/k$ base relations.
The relations added in 1 obviously satifsy the agreement requirement. We have to prove that the same is true for the relations added in 2. Indeed, suppose we have a chain of $l-1$ relations, i.e., $x_1 \succsim x_2 \succsim \cdots \succsim x_l$, where each of these $\succsim$ relations was added in step 1. So each such relation is agreed by more than $(k-1)n/k$ base relations. So each such relation is disagreed by less than $n/k$ base relations. So, at most $(l-1)n/k$ base relations disagree to at least one $\succsim$ relation. So, a least $(k-l+1)n/k$ base relations agree to all $\succsim$ relations. Since each base relation is transitive, at least $(k-l+1)n/k$ base relations agree that $x_1\geq x_l$. Since there are at most $k$ elements, $l\leq k$. Therefore, at least $n/k$ base relations agree that $x_1\geq x_l$, so the agreement requirement is satisfied.
QUESTION: is it possible when $m > n/k$?
Not a complete answer, but if $n=k$ and $m>1$, then it is not always possible.
Proof: Assume that $K=\{1,...,k\}$. Then for $N$ take the orderings defined by the permutations $$k(k-1)...21\\1k(k-1)...32\\...\\(k-1)(k-2)...21k$$ Assume for the contrary that we have a sufficient $\succsim$.
If $i\succsim i+1$ for some $i,i+1\in K$, then this only agrees with the permutation $$i(i-1)...21k(k-1)...(i+2)(i+1)$$ Since $m>1$, this does not suffice, which is a contradiction. It follows that $i+1\succsim i$ holds for all $i,i+1\in K$. By transitivity $k\succsim 1$. This only agrees with the permutation $$k(k-1)...21$$ Since $m>1$, this does not suffice, which is again a contradiction. We conclude that there is no sufficient $\succsim$.