Selecting a menu

Solution 1:

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)\lesssim\log_2(D)$.

When $n$ is even, $f_n(D)\lesssim2\log_{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 $2\log_{3/2}(D)$ which works.

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

Solution 2:

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 $n\gt1$ and $D\gt2$. 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,6\quad\quad\quad\quad0,2,3,4,5,6,1$$ $$1,2,6,3,4,5,0\quad\quad\quad\quad1,3,4,5,6,0,2$$ $$2,3,0,4,5,6,1\quad\quad\quad\quad2,4,5,6,0,1,3$$ $$3,4,1,5,6,0,2\quad\quad\quad\quad3,5,6,0,1,2,4$$ $$4,5,2,6,0,1,3\quad\quad\quad\quad4,6,0,1,2,3,5$$ $$5,6,3,0,1,2,4\quad\quad\quad\quad5,0,1,2,3,4,6$$ $$6,0,4,1,2,3,5\quad\quad\quad\quad6,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\}$.