15
$\begingroup$

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:

enter image description here 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$.

$\endgroup$
  • $\begingroup$ This makes me think of stable marriage algorithms, would those be relevant? $\endgroup$ – Zachary Hunter Jan 5 at 11:16
  • $\begingroup$ @Zachary Hunter I don't immediately see the connection. The stable marriage problem concerns the matching of pairs from two sets. $\endgroup$ – Jens Jan 6 at 1:16
  • $\begingroup$ There is no strategy which works all the time. Suppose half the people rank the dinners one way, and the other half rank them the opposite way. Then there is no menu which works, since no dinner is preferred by a strict majority of people to any other. $\endgroup$ – Mike Earnest Jan 7 at 0:40
  • $\begingroup$ @Mike Earnest If half the guests rank one way and the other half rank opposite, there are two dishes which together have "1"'s for every person. Or did I misunderstand you? $\endgroup$ – Jens Jan 7 at 0:53
  • $\begingroup$ @Jens Yes, but a menu of those two dishes, x and y, would not work. For any other dish, z, it is not true that more than half of the guests prefer x to z, since it is only exactly half. $\endgroup$ – Mike Earnest Jan 7 at 16:13
4
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thanks. Your strategy appears to give an upper bound for $d$ (or $f_n(D)$ as you call it). Do you agree? Also, how do you know the strategy for $n$ odd won't result in ties? $\endgroup$ – Jens Jan 9 at 3:29
  • $\begingroup$ @Jens My strategy basically says you can succeed as long as $d$ is at least as those bounds. If a tie between x and y occurred, it would mean the number of people who preferred x to y would equal the number of people who preferred y to x. Those two numbers add up to $n$, implying $n$ is even (unless I am mistaken again). $\endgroup$ – Mike Earnest Jan 9 at 5:40
  • $\begingroup$ But look at my example in the OP. I know it has an even number of people, but it could easily be extended to $11$ people and $11$ dishes. Wouldn't every dish get the same rating in your system? $\endgroup$ – Jens Jan 10 at 0:20
  • $\begingroup$ Oh, I was confused as to what you mean by ties. In the case of a tie, you arbitrarily choose a dish $x$ to put on the menu. In your example, every dish gets 5 points, and $5\ge (D-1)/2=(11-1)/2$. Therefore, you arbitrarily choose some dish x to put on the menu, remove all the dishes x beats, then recurse. $\endgroup$ – Mike Earnest Jan 10 at 0:27
  • $\begingroup$ OK, I understand. Thanks. $\endgroup$ – Jens Jan 10 at 0:47
4
+100
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ So for this party of $D = 7, n = 14$, it requires $d = 3$ to satisfy the "more than half" condition. Can you construct a party where $d = 4$ menu items are required to satisfy the "more than half" condition? $\endgroup$ – Old Pro Jan 16 at 20:10
  • $\begingroup$ I didnt check this carefully but I believe you... What exactly is the cyclic structure you exploited? In other words, How is it obvious that e.g. $k=1$ works for {2,3}, {2,4}, {2,5}? I couldnt "see" that without tediously going through the 14 lists. $\endgroup$ – antkam Jan 17 at 2:45
  • $\begingroup$ Took me a long time to understand your notation, but I finally did. Each $7$ digit sequence is a person's ranking of dishes, with the highest ranked dish on the left and the lowest on the right. I then converted your notation to the one I used in my example, checked it, and you're right! No menu with $d=2$ is possible. A true counter-example. Well done!! $\endgroup$ – Jens Jan 17 at 2:53
  • $\begingroup$ @OldPro No, I don't. Do you think constructing a partyu where $d=4$ menu items are required to satisfy the "more than half" condition is easier than constructing a party where $d=3$ menu items are required to satisfy the "at least half" condition? I can't do that either. $\endgroup$ – bof Jan 17 at 4:04
  • $\begingroup$ @Jens Sorry, I thought the notation was intuitive. I should have studied your example and used the same notation, but I was too lazy to do that. Mea culpa. $\endgroup$ – bof Jan 17 at 4:07
2
$\begingroup$

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 g\in 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$.

$\endgroup$
  • $\begingroup$ Interesting. I did notice that when I started computer simulation with $n \lt D$ I had to expand the number of $2$ dish combinations I needed to check before a solution was found, compared to the number of checks needed for $n \ge D$. $\endgroup$ – Jens Jan 17 at 1:09
2
$\begingroup$

For integer values of $D \ge 2$ and $n$ , it always possible to select a menu of $2$ dishes such that for any dish $k$ not on the menu, at least half the guests would be able to find some dish on the menu that they would prefer over dish $k$. (@bof has shown that you can construct a party with an even number of guests such that to satisfy "more than half" rather than "at least half" of the guests, you need $d=3$.)

Each guest has to strictly rank the dinners. We can convert the guest's rankings into a set of 2-dish rankings of dishes $d_i$ and $d_j$ where the guest prefers $d_i$ to $d_j$. We call $d_i$ the winner and note the vote as $W_{i,j}$. We note the set of all votes where $d_i$ was preferred over some other dish as $W_i$. Each guest casts $^DC_2 = {D(D-1)\over 2}$ votes: $D-1$ votes of $W_i$ for their first choice $d_i$, $D-2$ votes of $W_j$ for their second choice $d_j$ and so on. They always cast more $W_i$ votes than $W_j$ votes for any $d_i$ they ranked higher than $d_j$.

We collect all the votes in a bag $W$ (a bag, unlike a set, allows duplicate elements). There are $|W| = n{D(D-1)\over 2}$ votes in the bag, and we note the number of votes for $d_i$ over $d_j$ as $|W_{i,j}|$ and the number of wins for $d_i$ as $|W_i|$. Note that $|W_{i,j}| + |W_{j,i}| = n$ because every guest has to cast exactly one of those $2$ votes.

We put 2 dishes on the menu. The first dish, $a$, is the one with the most wins overall, $\max |W_i|$. The second dish, $b$, is the one most preferred over $d_a$, which is $\max |W_{i,a}|$. It turns out not to be important, but just in case you care, the minimum possible value for both $|W_{a}|$ and $|W_{b,a}|$ is $n{D-1\over 2}$.

What would it take for there to be a dish $k$ on the menu that the majority preferred over both $a$ and $b$?

For anyone to prefer $k$ over both $a$ and $b$, they would have had to rank $k$ higher than both, which means they would have had to cast only $W_{k,a}$ votes, and more $W_k$ votes than $W_a$ votes. We will call these guests $G_k$ and the number of these guests $|G_k|$.

Recall that we picked $a$ and $b$ in a way that guarantees $|W_k| \le |W_a|$ and $|W_{k,a}| \le |W_{b,a}|$.

Drat! Almost had it. I will try again later.

$\endgroup$
  • $\begingroup$ I'm encouraged that your findings agree with mine :-). I hope you'll keep looking for a proof of this (to me) very counter-intuitive result. $\endgroup$ – Jens Jan 15 at 0:56
  • $\begingroup$ @Jens This is much more intuitive to me than the Condorcet Paradox, which says a majority preference is not necessarily transitive. This is more like the return of sanity to majority preferences. If the group has a lot of agreement, then they can agree on favorite dishes for the menu. If the group cannot agree on a favorite for the menu, then it makes sense that they cannot agree that they like something else not on the menu better. $\endgroup$ – Old Pro Jan 15 at 3:11
  • $\begingroup$ Hmmm...maybe. I would still expect $d$ to depend on $n$ and/or $D$. What is so magical about $d=2$ that it appears to satisfy any combination of $n$ and $D$? Just can't get my head around it. $\endgroup$ – Jens Jan 15 at 3:30
  • $\begingroup$ @Jens You can have up to $n$ minority groups, but only $1$ majority group. What is magical about $d = 2$ is that it is the lowest integer $d$ for which $n / d$ people cannot form a majority. To me it is the fact that $d=1$ is not sufficient that is weird. Adding voters does not make it harder for a candidate to win an election, so it makes sense that $n$ is not relevant. Adding candidates/dinners does make it harder for any one to get a majority, so I would expect this to be worse with small $D$, but the strong law of small numbers takes care of that with $d=2$. $\endgroup$ – Old Pro Jan 15 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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