There are $ n$ voters and $ m$ candidates. Every voter makes a certain arrangement list of all candidates (there is one person in every place $ 1,2,...m$) and votes for the first $ k$ people in his/her list. The candidates with most votes are selected and say them winners. A poll profile is all of this $ n$ lists. If $ a$ is a candidate, $ R$ and $ R'$ are two poll profiles. $ R'$ is $ a-good$ for $ R$ if and only if for every voter; the people which in a worse position than $ a$ in $ R$ is also in a worse position than $ a$ in $ R'$. We say positive integer $ k$ is monotone if and only if for every $ R$ poll profile and every winner $ a$ for $ R$ poll profile is also a winner for all $ a-good$ $ R'$ poll profiles. Prove that $ k$ is monotone if and only if $ k>\frac{m(n-1)}{n}$.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
08.04.2008 14:11
anonymous1173 wrote: We say positive integer $ k$ is monotone if and only if for every $ R$ poll profile and every winner $ a$ for $ R$ poll profile is also a winner for all $ a - good$ $ R'$ poll profiles. Prove that $ k$ is monotone if and only if $ k > \frac {m(n - 1)}{n}$. $ k$ is not used in the defination of itself as a monotone so there is no reason to have a conddition defining $ k$ so is the problem correct or have i got it wrong????????? the second one is most probably
12.04.2008 20:42
i really cant understand the problem please help
17.04.2008 23:47
sorry, i can't understand your problem with this question. maybe it can be from my bad english but if you can ask your problem more clear i will try to explain. but i can say that, "the first $ k$ in voters' lists are selected. it is $ k$'s definition. Being monotone is a property of $ k$."
20.04.2008 17:03
03.06.2008 21:08
sorry, i did not realize that
05.06.2008 23:47
yes you are right. using kirkit's theorem in this problem is really sensible.
06.06.2008 18:49
What is Kirkit's theorem? Pierre.
07.06.2008 17:15
Ok, Kirkit's theorem does not exist, and this is only spam... Pierre.
04.10.2014 10:48
So what is exactly the number of winners in a particular profile?
04.10.2014 12:55
This statement is absolutely horrible. I do not think the problem itself is really difficult(i guess we will never know...), but the statement is absolutely unreadable making this problem impossible to think at, for me... If someone can rewrite it, or whatever, i would be really grateful for a statement in English.
04.10.2014 13:42
There are $n$ voters and $m$ candidates. Every voter makes his/her arrangement of all candidates (there is one person in every place $1,2,...,m$) and votes for the first $k$ people in his/her list. $k$ candidates with most votes are elected (we call them winners). Consider the candidate $a$ and two elections $R$ and $R^{\prime}$. The election $R^{\prime}$ is $(R,a)$-good if for every voter $v$, the candidates that are in worse position on $v$'s list than $a$ in the election $R$ are also in the worse position than $a$ in $R^{\prime}$. We say that a positive integer $k$ is monotone if for every election $R$ and every winner $a$ for $R$, $a$ is also a winner for all $(R,a)$-good elections. Prove that $k$ is monotone if and only if \[ k>\frac{m\left( n-1\right) }{n}. \]
05.01.2020 01:02
Here is a cleaner problem statement: 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 voter's on $A$. Given some $k\in\{1,2,\dots,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'$. $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 $k-$plurality choice rule in $R$, $a$ is still chosen in $R'$. Assume $(m,n)\neq (3,4)$. Prove that, $k>\frac{m(n-1)}{n}$ is a necessary and sufficient condition for the monotonicity of $k-$plurality choice rule. Note: This problem has been proposed by Prof. Semih Koray of Bilkent University, Ankara, Turkey, whose one of primary research interest is in social choice theory; and electoral system. Note 2: For another Turkish olympiad problem regarding electoral system, which also happened to be proposed by Dr. Koray, see here.
05.01.2020 01:03
Here is a neat solution: