Library / Team Selection Test for IMO /39 of 55

Team Selection Test for IMO

Combinatorics Difficulty 8.6 Shortlist Prove it Turkey

Let $N$ denote a society of voters where each voter is endowed with preferences over a set of alternatives $A$ with $|N| = n > 2$ , $|A| = m > 2$ . A preference profile $R$ is an $n$ -tuple of linear orderings on $A$ representing the preferences of voters on $A$ . Given some $k \in \{1, 2, ..., m\}$ , the $k$ -plurality choice rule chooses the alternatives achieving the highest vote after each voter assigns equal votes for all top $k$ alternatives in his preference ordering regardless of their ranking. Let $R$ and $R'$ be any two preference profiles and $a \in A$ . We say that $R'$ $a$ -dominates $R$ iff for every $i \in N$ , all alternatives which are ranked below $a$ in $R_i$ are also ranked below $a$ in $R'_i$ . The $k$ -plurality choice rule is said to be monotone iff for any $R$ and any $R'$ which $a$ -dominates $R$ , if $a \in A$ is chosen by the $k$ -plurality choice rule in $R$ , $a$ is still chosen in $R'$ . Assume $(m, n) \ne (3, 4)$ , prove that $k > \frac{m(n-1)}{n}$ is necessary and sufficient condition for the monotonicity of $k$ -plurality choice rule. (Semih Koray).

Solution

Let $k > \frac{m(n-1)}{n}$ . Since $\frac{kn}{m} > n - 1$ at least one alternative obtained all $n$ votes. Therefore, any chosen $a$ obtained $n$ votes in profile $R$ and by definitions obtains also $n$ votes in profile $R'$ . Thus, the condition $k > \frac{m(n-1)}{n}$ is sufficient for monotonicity.

Let $2 \le k \le \frac{m(n-1)}{n}$ . We construct a profile $R$ : for the first voter $a$ is the first, $b$ is the last. For the second, $b$ is the second, $a$ is the last. For all other voters, $a$ is the first, $b$ is the second. Each of $a$ and $b$ are not selected by exactly one voter. In our profile each alternative also is not selected by at least one voter. It is possible, since $n(m-k) \ge m$ . No alternative obtained $n$ votes, $a$ and $b$ are chosen by getting $n-1$ votes.

The only difference between profiles $R'$ and $R$ is that the first voter charged the positions of the second alternative and $b$ . Obviously, $R'$ $a$ -dominates $R$ , but $b$ obtained $n$ votes, $a$ obtained $n-1$ votes and is not selected. Thus, $k$ -plurality choice rule is not monotonic.

Let $1 = k \le \frac{m(n-1)}{n}$ . 1-plurality choice rule is monotonic if $n = 4, m = 3$ : if $a$ is chosen, $a$ obtained at least 2 votes, in any other profile $a$ also gets at least 2 votes and other alternatives also get at most 2 votes! In other cases an example similar to the example above shows that the 1-plurality choice rule is not monotonic. Done.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.