Câu hỏi 102
Gọi $N$ là một tập thể cử tri, mỗi cử tri có sự ưu tiên đối với một tập các phương án $A$, với $|N| = n \gt 2$, $|A| = m \gt 2$. Một bộ ưu tiên $R$ là một $n$-bộ các thứ tự tuyến tính trên $A$, biểu diễn sự ưu tiên của các cử tri đối với $A$. Với mỗi $k \in \{1, 2, ..., m\}$, quy tắc chọn $k$-đa số chọn ra các phương án đạt số phiếu cao nhất sau khi mỗi cử tri cho số phiếu bằng nhau cho tất cả $k$ phương án đứng đầu trong thứ tự ưu tiên của mình, bất kể thứ hạng của chúng. Cho $R$ và $R'$ là hai bộ ưu tiên bất kì và $a \in A$. Ta nói $R'$ $a$-trội hơn $R$ khi và chỉ khi với mọi $i \in N$, mọi phương án xếp dưới $a$ trong $R_i$ cũng xếp dưới $a$ trong $R'_i$. Quy tắc chọn $k$-đa số được gọi là đơn điệu khi và chỉ khi với mọi $R$ và mọi $R'$ $a$-trội hơn $R$, nếu $a \in A$ được quy tắc chọn $k$-đa số chọn trong $R$ thì $a$ vẫn được chọn trong $R'$. Giả sử $(m, n) \ne (3, 4)$, chứng minh rằng $k \gt \frac{m(n-1)}{n}$ là điều kiện cần và đủ để quy tắc chọn $k$-đa số đơn điệu. (Semih Koray).