4
$\begingroup$

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.

  1. If $x\geq y$ for more than $n (k-1)/k$ orderings in $N$, then set $x\succsim y$.

  2. Add to $\succsim$, all the relations that follow from the existing relations by transitivity.

  3. 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$?

$\endgroup$
  • $\begingroup$ I think this is a bit related to Arrow's voting theorem $\endgroup$ – P. Quinton Oct 12 '18 at 5:24
  • $\begingroup$ @P.Quinton Yes, it is, however, Arrow's theorem does not talk about partial agreement. $\endgroup$ – Erel Segal-Halevi Oct 13 '18 at 18:57
  • $\begingroup$ Minor mistake at the end: $l\leq k$, not $l\geq k$. More importantly, how do you know that for each $x,y\in K$ either $x\succsim y$ or $y\succsim x$? $\endgroup$ – SmileyCraft Oct 16 '18 at 22:16
  • 1
    $\begingroup$ Observation: Since we are looking for a worst case scenario, we can assume all the weak orderings are total orderings. This is because any total ordering is a weak ordering and any weak ordering contains a total ordering. $\endgroup$ – SmileyCraft Oct 16 '18 at 22:32
  • $\begingroup$ @SmileyCraft you are right, I added step 3: Complete the remaining relations arbitrarily in any way consistent with transitivity. $\endgroup$ – Erel Segal-Halevi Oct 17 '18 at 7:37
1
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Remarks: If $N$ can be a multiset, this also proves that, if $m>\lceil n/k\rceil$ it is not always possible. Just use every permutation $n/k$ times, and round in such a way that it adds up. The reason this is not a complete answer is because the OP proof that $m\leq\lceil n/k\rceil$ suffices is not complete, as it is forgotten to prove that $x\succsim y$ or $y\succsim x$ holds for all $x,y\in K$. $\endgroup$ – SmileyCraft Oct 16 '18 at 23:17
  • $\begingroup$ Looks good! I have now completed the proof of the upper bound, so it seems your result is optimal. $\endgroup$ – Erel Segal-Halevi Oct 18 '18 at 14:43

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.