“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?