Xrfgtjtk

While perusing old unanswered puzzle questions, I came across this one. I found it quite interesting, but a bit vague, so I've decided to recast it.

A party is to be held at a restaurant. The restaurant has the ability to make $D$ different dishes, but the menu for the party will be a fixed menu featuring just $d$ dishes, where $d < D$. To select which dishes should be on the menu, the $n$ guests are asked to rank all D dishes.

For which values of $D$, $d$ and $n$ is it always possible to select $d$ dishes such that for any dish $k$ not on the menu, more than half the guests would prefer one of the dishes in the menu over dish $k$?

Let's look at a concrete example. Suppose the number of possible dishes was $D=10$, the number of selected dishes was $d=3$ and the number of guests was $n=10$. The worst possible ranking I can think of (though I'm not sure it is the worst) is shown below:

The ranks are spread out so no guest ranks any dish the same.

I now selected the $3$ dishes marked in green so that the ranks of $1,2, 3$ were distributed among the guests as much as possible. Thus, only guest $10$ does not have one of the selected dishes in his top $3$.

If you now go through each of the unselected dishes, you will see that in every case a majority of the guests will have a higher ranked dish among the $3$ selected dishes.

So (assuming my worst case actually is the worst case!) with these values of $D$, $d$ and $n$, it is always possible to select such a menu.

Any input as to whether a worse case ranking is possible, would also be appreciated.

EDIT - Partial results

After fiddling with this question, I realize I should probably have asked "Given $n$ and $D$, what is the minimum required $d$ to fulfill the constraint?". Afterall, if a certain value of $d$ works, then so will any larger value of $d$.

My biggest problem, oddly, is how to know the worst possible ranking. To test conjectures, I need to test them against the worst case. But I'm not completely sure what that is, for a given $n$ and $D$.

Anyway, an initial result is that a menu is always possible if $d > frac{n}{2}$.

A second tentative result is that if $n = D$ then $d = 2$. E.g., if I select dish $1$ and $6$ in my example above, the constraint is fulfilled.

But this implies that if a $1000$ people ranked a $1000$ dishes, it would still be possible to select $2$ dishes that fulfilled the constraint. This doesn't seem right. But if I use the "worst case" scenario which I used in my example above, this is the result I get.

I'd appreciate if someone could post a counter-example. I suspect the problem is that my "worst case" is not the actual worst case.

EDIT2 - Outragous!

Further fiddling and computer simulation suggests the outragous claim that if $n ge D$ then still $d = 2$. This implies that if a $1,000$ dishes were ranked by a $1,000,000$ guests, we could always find just $2$ dishes which fulfilled the constraint! I must be doing something wrong.

As usual, counter-examples would be greatly appreciated.

EDIT3

So I've now done $10,000$ simulations with $30$ dishes and $60$ guests, where the guests ranked the dishes randomly, and in every case a menu of just $2$ dishes was sufficient. My confidence that $2$ dishes will always be sufficient for $n ge D$ grows. :-)

But a proof or counter-example would be nice.

Now to look at $n < D$.

Let $f_n(D)$ be the smallest menu size which always suffices for $n$ people and $D$ dinners.

When $n$ is odd, $f_n(D)lesssimlog_2(D)$.

When $n$ is even, $f_n(D)lesssim2log_{3/2}(D)$.

The notation $f(x)lesssim g(x)$ means that for all $epsilon>0$, $f(x)le (1+epsilon)g(x)$ holds for large enough $x$. Basically, it means less than or approximately equal to.

When $n$ is odd, here is a strategy to choose a menu. For every pair of dinners, ${x,y}$, award a point to the one which most people prefer. Some dinner, $x$, must win at least $(D-1)/2$ points. Put $x$ on the menu, and ignore all the other dinners $y$ such that most people prefer $x$ to $y$. We have added one item to the menu, while decreasing the number of dinners by half. Doing this about $log_2(D)$ times, we get a menu which works.

When $n$ is even, the same strategy does not quite work, because ties may occur. Instead, look at every triple ${x,y,z}$ of dinners. For each of the three pairs, for example, ${x,y}$, in this triple, award a point to that pair if the majority of people prefer one of ${x,y}$ to $z$. In each triple, there must be at least one point awarded (as many as three points could be awarded). Therefore, some pair must win at least
$$
frac{binom{D}3}{binom{D}2}=frac13(D-2)text{ points.}
$$
Add that pair of dinners to the menu, and ignore the dinners which were less preferred than that pair. We have increased the menu size by two, and decreased the number of dinners by a factor of about $frac23$. Repeating this $log_{3/2}(D)$ times, we get a menu of size $2log_{3/2}(D)$ which works.

I have no thoughts on a lower bound for $f_n(D)$.

You asked:

For which values of $D$, $d$ and $n$ is it always possible to select $d$ dishes such that for any dish $k$ not on the menu, more than half the guests would prefer one of the dishes in the menu over dish $k$?

Perhaps you meant to say "at least half" instead of "more than half"? The point of the example below is to show that it might make a difference. (This example is based on an idea from a comment by Rosie F.)

Later you asked whether $d=2$ is always possible for $ngt1$ and $Dgt2$. In this example with $D=7$ and $n=14$, for any menu of size $d=2$, there is a dish $k$ not on the menu such that exactly half of the guests prefer one of the dishes on the menu to dish $k$, and exactly half prefer dish $k$ to both of the dishes on the menu. Calling the dishes $0,1,2,3,4,5,6$, the $14$ preference lists below. (The notation $0,1,5,2,3,4,6$ means that dish $0$ is preferred to dish $1$, which is preferred to dish $5$, which is preferred to dish $2$, which is preferred to dish $3$, which is preferred to dish $4$, which is preferred to dish $6$.)
$$0,1,5,2,3,4,6quadquadquadquad0,2,3,4,5,6,1$$
$$1,2,6,3,4,5,0quadquadquadquad1,3,4,5,6,0,2$$
$$2,3,0,4,5,6,1quadquadquadquad2,4,5,6,0,1,3$$
$$3,4,1,5,6,0,2quadquadquadquad3,5,6,0,1,2,4$$
$$4,5,2,6,0,1,3quadquadquadquad4,6,0,1,2,3,5$$
$$5,6,3,0,1,2,4quadquadquadquad5,0,1,2,3,4,6$$
$$6,0,4,1,2,3,5quadquadquadquad6,1,2,3,4,5,0$$
For instance, if the menu is ${0,1}$, we can take $k=6$; if the $14$ guests are asked to rank the dishes $0$, $1$ and $6$, then $3$ guests rank dish $0$ highest of the three, $4$ guests rank dish $1$ highest, and $7$ guests rank dish $6$ highest.

Likewise, it can be seen that $k=6$ also works for the menus ${0,2}$ and ${0,3}$. Cyclically, $k=0$ works for ${1,2}$, ${1,3}$, ${1,4}$; $k=1$ works for ${2,3}$, ${2,4}$, ${2,5}$; $k=2$ works for ${3,4}$, ${3,5}$, ${3,6}$; $k=3$ works for ${4,5}$, ${4,6}$, ${0,4}$; $k=4$ works for ${5,6}$, ${0,5}$, ${1,5}$; and $k=5$ works for ${0,6}$, ${1,6}$, ${2,6}$.

NOT AN ANSWER... but instead an intuitive argument why you cannot find counter-examples (to the $d=2$ conjecture) by randomizing with large $D$ and $N$.

The key is to observe that you are requiring that the menu $S$ satisfy a very weak (i.e. easily met) condition: $forall x notin S, exists$ a majority of voters $G$ s.t. $forall gin G, exists y in S,$ s.t. $g$ prefers $y$ over $x$. Lets say $S={a, b}$ has only two items, and consider some $x notin S$. Let $A$ be the set of voters who prefer $a$ over $x$, and $B$ be the set of voters who prefer $b$ over $x$. It is entirely possible that $A$ is a minority, and $B$ is also a (different) minority. However you are only requiring that $A cup B$ be a majority, which is a very weak condition.

Specifically, consider $N$ voters each of which has a completely random preference list, uniformly and independently picked from $D!$ possible permutations.

Now consider any random menu of two random dishes, $S = {a, b}$. I claim that there is a very high probability this random menu meets your requirement. Consider some fixed $c notin S$. There are $N$ voters, and the chance that a particular voter will rank $c$ above both $a$ and $b$ is $1/3$. The number of such voters is therefore $Binomial(N,1/3)$. However, for $c$ to invalidate the menu, such voters must form a majority, i.e. you are requiring $Binomial(N, 1/3) > N/2$. For large $N$ this is extremely unlikely.

Lets approximate with the Normal distribution. Here mean $mu = N/3$ and standard deviation $sigma = sqrt{2N/9} = sqrt{2N}/3$. You are requiring a distance of $N/2 - N/3 = N/6$ away from the mean, or $sqrt{N/8}$ standard deviations. There are various bounds for the tail of the Normal distribution and one such is: Proof of upper-tail inequality for standard normal distribution

Plugging in $x = sqrt{N/8}$ we get: Prob($c$ invalidates the menu $S$) $= P le {e^{-N/16} over k sqrt{N}}$ for some small constant $k$. So as you can see for large $N$ this probability $P rightarrow 0$ very rapidly.

Now of course this accounts for just one $c notin S$. For the menu to be valid it must pass the test for all $D-2$ such $c$. If I may be allowed some handwaving, the overall probability that the menu survives all such challengers $c$ is $Q = (1-P)^{D-2}$. So it depends on the relative growth rates of $P$ (based on $N$) and $D$. If $P sim 1/D$ then $Q approx 1/e$, but if $P ll 1/D$ (such as when $N = D$ grow together) then $Q rightarrow 1$, i.e. the random 2-item menu would meet your requirement with probability close to $1$.

As I said, this is not a proof, but this shows why your random searches with large $N$ and $D$ would be very unlikely to yield a counter-example to the $d=2$ conjecture (assuming counter-examples exist). In fact, this seems to suggest that it might be more fruitful to search for counter-examples at small $N$ (hence relatively large $P$) and large $D$.