Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

“Ostrogorski's paradox” describes a strange situation in which voters decide on candidates based on issues in platforms, but on each issue of the platform, the majority of voters disapprove of the majority winner.

What is the lowest possible approval rating for a majority winner?

Example

For example, if there are 3 issues, then the voters may divide into four camps: one camp of “all issues are important”, and three camps of “only this issue is important, the others detract from it.” A sample poll may reveal:

\begin{array}{r|rrr}\newcommand{\t}[1]{\text{#1}} & \t{Size} & \t{Issue 1} & \t{Issue 2} & \t{Issue 3} \\ \hline \t{Camp 0} & 40\% & \t{Yes} & \t{Yes} & \t{Yes} \\ \t{Camp 1} & 20\% & \t{Yes} & \t{No} & \t{No} \\ \t{Camp 2} & 20\% & \t{No} & \t{Yes} & \t{No} \\ \t{Camp 3} & 20\% & \t{No} & \t{No} & \t{Yes} \\ \hline \t{Favored}& & 60\%\t{ Yes}& 60\%\t{ Yes}& 60\%\t{ Yes} \end{array}

Candidate A looks at the polls and sees that $60\%$ of people support each issue, and so decides his platform is to support all three issues. Candidate B is contrary and decides his platform is to reject all three issues. The voters in camp 0 vote for A, obviously. The voters in camp 1 see that candidate B agrees with them on 2 out of 3 issues, and so vote for B. Similarly camps 2 and 3 vote for B.

Candidate B wins $60\%$ to $40\%$ a huge margin of victory! However, once in office, polls reveal that only $40\%$ of voters approve of his handling of issue 1. Similarly for issue 2 and 3. Nobody likes the majority candidate!

Formal problem

Let $I$ be a finite set (of issues), and $\mathcal{S}=\wp(I)$ be the set of all subsets of issues, so that each $S \in \mathcal{S}$ represents the issues that are supported. A voter profile is a function $\mu$ from $\mathcal{S}$ to the closed interval $[0,1]$ such that $\sum_{S \in \mathcal{S}} \mu(S) = 1$. An election is a subset $C=\{C_1,C_2\}$ of $\mathcal{S}$ of size 2 (the two candidates) along with a voter profile. The outcome $O(C_1,C_2,\mu)$ of an election is $$O(C_1,C_2,\mu) = \sum \left\{ \mu(S) : S \in \mathcal{S} ~\mid~ \left|S \oplus C_1 \right| \leq \left|S \oplus C_2\right| \right\}$$ where $S \oplus C_j$ is the symmetric difference of $S$ and $C_j$, that is, the set of elements where $S$ and $C_j$ differ. The approval rating of candidate $C_j$ on issue $i$ is $$A(C_j, i, \mu) = \sum \left\{ \mu(S) : i \notin S \oplus C_j \right\}$$ and the maximum approval rating of candidate $C_j$ is: $$A(C_j, \mu) = \max\left\{ A(C_j,i,\mu) : i \in I \right\}$$

What is the infimum of the maximum approval rating $A(C_1,\mu)$ given that $O(C_1,C_2,\mu)\geq \tfrac12$?

Partial result

Let $|I|=2n+1$ be large and set $\mu(I)=0.5$, $\mu(S) = \frac{1}{2 \binom{2n+1}{n}}$ if $|S|=n$, and $\mu(S) = 0$ otherwise; so that half of the voters support every issue and half support just under half of the issues. Let $C_1 = \{\}$ support nothing, and $C_2 = I$ support everything. Then $O(C_1,C_2,\mu) = 0.5$ but $A(C_1,i,\mu)$ is the sum of about half of the $S$ of size $n$: $$A(C_1,i,\mu) = \sum\left\{ \mu(S) : i \notin S, S \in \mathcal{S} \right\} = \frac{1}{2 \binom{2n+1}{n}} \cdot \binom{2n}{n} = \frac{1}{4} \cdot \frac{2n+2}{2n+1} \to \frac14$$

This is as bad as I could make it. Is it as bad as possible?

share|improve this question
1  
Great question :-) –  joriki Aug 12 '12 at 20:49
add comment

1 Answer 1

up vote 3 down vote accepted

Given any $I$, $\mu$ and $C$ with $O(C_1,C_2,\mu)\ge\frac12$, we can modify them as follows without changing the maximum approval rating. First, for all issues $i$ with $A(C_1,i,\mu)\lt A(C_1,\mu)$, we can let voters change their mind on this issue in favour of $C_1$ until $A(C_1,i,\mu)=A(C_1,\mu)$. This doesn't change $A(C_1,\mu)$, and it cannot decrease the majority for $C_1$. Next we can remove all issues on which the candidates agree from the issue set; these issues don't affect the majority, and since $C_1$ now has the same approval rating for all issues, they also don't affect the maximum approval rating. Further (this is just for convenience), we can flip all issues on which $C_1$ is in favour (by negating the question on the ballot) without any substantial change. So now we have $C_1$ against all issues, $C_2$ in favour of all issues, and $C_1$ with the same approval rating for all issues, and the maximum approval rating hasn't changed and the majority hasn't decreased. Since at least half the voters must agree with $C_1$ on at least half the issues it's clear that the maximum approval rating can't be below $\frac14$.

share|improve this answer
    
Looks good. In my first table, put a "How much support does $C_1$ get?" column that is $\mu(S) |S\oplus C_1| / |I|$ (so if they agree on 2/3 of the issue and there are 20% of the people that is 40/3 % support). Now the sum of the right column should be the average of the bottom row. To win, the right column has to sum to be at least 25% by your last sentence. –  Jack Schmidt Aug 12 '12 at 22:38
    
@Jack: I think you mean the sum of the right column should be the complement of the average of the bottom row? In the bottom row you counted how many agree with $C_2$, not with $C_1$. (In that case $C_1$ is B and $C_2$ is A.) –  joriki Aug 12 '12 at 22:45
2  
Oh yes, sorry. Bad numbering, A/B = C2/C1. At any rate, I like your proof: reduce to a system with some symmetry, then use the "sum of rows is sum of columns trick" on an appropriate table similar to the one above. :-) –  Jack Schmidt Aug 12 '12 at 22:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.