17
$\begingroup$

A group of (possibly over-polite) people have just finished their meal at a restaurant. One of them asks, "Does anyone want dessert?" The table goes quiet.

Some of the people might want dessert. But nobody wants to say "yes" first, in case they are the only one, and look like a pig while making everyone else wait for them to eat alone. Equally, though, nobody wants to say "no" first, because it might put one or more people who haven't spoken yet off from saying a truthful "yes".

So the question is - is there any blind ballot system that has the property that:

  • During the voting process, nobody knows what anyone has voted,
  • If the vote is unanimously yes, everyone knows that,
  • If the vote is not unanimously yes, everyone knows that, but nobody knows who voted what or how many yes votes there were (or even if there were any or not)

and does not require an external arbiter or programmed device?

The classic "black balling" method doesn't work, because although the presence of a black ball in the bag shows that the vote is not unanimously yes, when the bag is revealed it is still possible to see if there are white balls present (ie, someone did vote yes).

$\endgroup$
9
  • $\begingroup$ Are scales or elaborate non-programed devices allowed? $\endgroup$
    – bobble
    Dec 26, 2022 at 22:49
  • $\begingroup$ Perhaps so? The difficulty is the set-up. For example, I did get the idea that you could have a system where each person was given a jar of liquid, and independently either poured their jar into a common tank which is out of sight or did not do so. If the vote is not unanimous nothing happens and no-one can see the tank level, but if the vote is unanimous the tank overflows out of the pouring hole. But then afterwards someone would have to drain the tank for the next vote, and if that person's not external, now they know if there was any water in it.. $\endgroup$
    – Mark Green
    Dec 26, 2022 at 22:56
  • 7
    $\begingroup$ It it ok if some subset of participants could later get together and combine information they received during the protocol to determine others' votes, as long as each one couldn't learn anything on their own? $\endgroup$
    – xnor
    Dec 26, 2022 at 23:27
  • 5
    $\begingroup$ Three logicians walk into a bar. The bartender asks, "Do all of you want a drink?" The first logician says, "I don't know." The second logician says, "I don't know." The third logician says, "Yes!" $\endgroup$
    – Wastrel
    Dec 27, 2022 at 14:11
  • $\begingroup$ I fail to see how the question solves the situation described in the story. The story seems to be only about not wanting dessert when they are the only one. The question doesn't answer whether there are 2 or more, only whether all of them want it $\endgroup$
    – Ivo
    Dec 29, 2022 at 8:37

17 Answers 17

12
$\begingroup$

I know nothing about the "black balling" method mentioned in the problem, but hearing the term got me thinking about an easy solution:

Put the same amount of quarters in a bag as there are participants. Pass the bag around and if your answer is yes then take one quarter out. If your answer is no then put a random number of quarters in a bag - the key here is you put as many quarters as you want in there. At the end of the vote if the bag is empty - it's a unanimous yes. If there are quarters in a bag, someone voted no, but you won't be able to tell how many no votes or yes votes there were, if any.

The only issue I see with this system is:

If there are less quarters in the bag at the end than there were participants to begin with. This would undoubtably mean that someone voted yes. However, you cannot make a rule that if you vote no you need to put at least the number of participants worth of quarters in there as that would mean that if the bag contains exactly the minimum then it would be obvious that only 1 person voted no. So, being the savvy participants that they are, the rule is unwritten and unspoken, but if you vote no you make sure your random number of quarters you put in there is greater that there were people to begin with. At the end of the vote nobody should be able to tell how many people voted no.

Edited to add:

Some people may take issue that the last person to vote will be able to tell there is only one coin left in the bag, so if he was voting no then he would know that every one else voted yes. To remedy this the bag could start with the number of participants worth of coins plus 20 coins, say; that way the last person will have a bag full of coins, short of counting them all while voting he won't know the exact amount. To make it hard to cheat you can put 100 extra coins in there, that would take a considerable amount of time to count.
Also if there was only 1 person voting no, then if the final count is revealed the person will be able to tell if he was the sole no vote or not. To remedy this the final count should not be revealed, if there is even a single extra coin in the bag at the end of the vote then the matter should be decided. After the vote is decided, the bag should then be passed around the participants once again and this time any random amount of coins from each participant should be thrown in or taken out. At the end of this procedure not even the sole no vote will be able to tell that he was the only one.

$\endgroup$
2
  • $\begingroup$ You could never put this into practice in reality, isn't that part of the restriction? $\endgroup$ Dec 29, 2022 at 23:23
  • $\begingroup$ @hedgedandlevered I wouldn't say "never". In my mind I was thinking of 10 people having dinner. It won't take long at all to throw 10 quarters in a small coin bag and pass it around, with people taking a quarter out under the table so no-one can see or throwing 4-5 extra coins in there. It is very doable. It was my first thought and there are ways to cheat, which I don't particularly like, so maybe I'll think of a more robust system. $\endgroup$
    – Amorydai
    Dec 30, 2022 at 4:53
8
$\begingroup$

I thought of this procedure:

A deck of cards is passed around. Without looking at the cards those who want dessert shuffle the cards, those who don't do the same but first flip over half of the pack. Shuffling is made under the table.
If any of the cards is upside-down, then the vote is no.

But there is a really simple way:

Whoever doesn't want dessert farts silently.

$\endgroup$
5
  • $\begingroup$ I had the same idea but with two cups and a clear and opaque fluid. I think shuffling under a table would be pretty hard. $\endgroup$
    – user9194
    Dec 28, 2022 at 0:47
  • $\begingroup$ There is a very small non-zero chance that a series of no votes and shuffling returns all the cards upright, which would be interpreted as a unanimous yes. $\endgroup$
    – user9194
    Dec 28, 2022 at 0:53
  • 2
    $\begingroup$ Yes. OK. But there is a much larger probability that a meteorite falls on the restaurant and they don't get any dessert. Ever. Accidentally forcing some people to eat dessert isn't the worst that can happen. $\endgroup$
    – Florian F
    Dec 28, 2022 at 1:11
  • $\begingroup$ This is prone to election fraud: the last voter can substitute a similar looking deck while "shuffling" under the table. $\endgroup$
    – Bass
    Dec 28, 2022 at 12:19
  • $\begingroup$ I was assuming a collaborative solution was asked. But the participants could sign a card each before starting. And the process can be repeated the other way round. And you can add the second method for safety. This being said, people being polite enough to not force a dessert on someone, but then cheat to do it anyway, but in a way nobody knows it, would they go to the restaurant together? $\endgroup$
    – Florian F
    Dec 28, 2022 at 17:04
7
$\begingroup$

To me, the key to this problem is to design a simple physical setup with the following properties:

The setup has two states, A and B. The system is initially in state A. One can take some action that will set the state to B, without revealing the prior state of the setup. Given such a setup, the protocol is simple: initialize the setup in state A, then give each person the option to secretly set the state to B, or take no action. Setting the state to B indicates saying no to dessert. If the final state is A, everyone said yes.

My proposed implementation of this setup is

A cup with a small, light object in it, such as a tiny scrap of paper. State A is the scrap of paper being in the cup. The action is to turn over the cup with one's eyes closed, then put the cup back down right-side-up. State B is the scrap of paper being out of the cup, on the table. To better conceal information, people who want dessert should lift the cup, not turn it over, and put it back down. The scrap of paper should be small enough that its weight is not noticable, and it doesn't make a noticable sound when it falls out of the cup. It should be large enough to not stick to the cup via static electricity.

I believe this protocol has all the desired information properties, and is easily implementable at a typical restaurant.

$\endgroup$
5
  • $\begingroup$ What prevents the final voter from picking the scrap up from the table and putting it back in the cup? $\endgroup$
    – Bass
    Dec 28, 2022 at 12:23
  • $\begingroup$ What prevents the first no-voter from being found out? $\endgroup$
    – No Name
    Dec 28, 2022 at 14:53
  • $\begingroup$ You'd need to pass the cup around under the table and count on nobody being able to see the floor below it. $\endgroup$
    – Mark Green
    Dec 28, 2022 at 17:46
  • $\begingroup$ @Bass Every solution on this page is vulnerable to many "bad actor" attacks. For this to work without some serious cryptography (which exists, see my comment to the OP), I think you need to assume all players are acting in good faith. $\endgroup$ Dec 29, 2022 at 9:38
  • $\begingroup$ Not so with mine! The only thing you can do is falsely indicate that you don't want dessert, when you do. You can't even collude with someone to learn any information. $\endgroup$ Nov 13, 2023 at 22:33
7
$\begingroup$

Required: playing cards.

Setup:

One person takes the ace of spades and sets it face down in front of them, then shuffles the deck and deals everyone (including themself) a card, face down on the table. The remaining deck is placed in the center of the table. No one looks at their card at any point.

Voting:

The person with two cards inserts one card – the random card they were dealt for yes, the ace of spades (or whatever other card they were passed) for no – into the deck, then passes their remaining card (face down, so the recipient doesn't know what it is; they should just assume they get the ace of spades) to their left. Repeat this step until everyone's placed a card in the deck.

Results:

The remaining card is revealed. If it's the ace of spades, everyone voted yes. If it's not, someone voted no.

Edit to add a simpler version:

The first person places the ace of spades on top of the deck. Each person receives the deck and either does nothing (yes) or moves the top card to the bottom of the deck (no). After everyone's had the deck, the top card is revealed – ace of spades is a unanimous yes, anything else means there was a no vote. The deck can then be shuffled to obscure how many no votes there were.

$\endgroup$
1
  • $\begingroup$ simple and efficient. If there is more than 51 person, just add another deck without the ace of spade. $\endgroup$ Jan 24, 2023 at 12:48
5
$\begingroup$

My answer, based on liquid dyes:

You'll need two big, black mugs: a Vote Mug and a Discard Mug, both with some water inside of them (a random amount or everyone can secretly pour some, without looking how much is inside). You'll also need 2 small shot glasses for each person. Every person should have one shot of water and one shot of something staining, e.g. tomato juice. All the liquids, in total, should fit into one mug.

Every person shall, in turn, pour one shot into the Vote Mug and the other into the Discard Mug. They shall do it so that noone can see what liquid they are pouring where. They shan't look inside any of the Mugs, but if they try anyway, it's extremely hard to see colours inside of black mugs. Tomato juice is a NO vote, water is a YES vote.

After everyone has had their turn, pour off some of the Vote Mug liquid into a clear glass. If it's just water, order desserts. If it's any red, go without.

To clean up, pour all liquids into the Discard Mug and pour it out. Or drink it, if you want. Thanks to that, noone will be able to compare the colours of the liquids in the two mugs at the end.

$\endgroup$
1
  • $\begingroup$ My answer is similar, but has no discard mug. There can be no comparisons with my solution. 1 or all no votes reveal the same thing. $\endgroup$
    – user9194
    Dec 28, 2022 at 0:52
4
$\begingroup$

I propose a black box with something delicate and breakable.

It could be something like a thin glass piece in a sealed box. For a NO, the person will shake a box to break the object inside, for a YES, the person will not do anything. At the end, if the object is broken, it's not a unanimous YES, otherwise it is. This hides the number of YES/NO and if any YES votes were there.

$\endgroup$
2
  • 2
    $\begingroup$ I think a common object that would work for this is a glowstick: pass it around under the table, squeezing it for a 'no' vote. Then the last person shakes it to reveal the result (dark for 'yes,' glowing for 'no'). $\endgroup$ Dec 28, 2022 at 21:05
  • 1
    $\begingroup$ I agree, pretty much anything that has a state that is only observable through deliberate manipulation, can only change state once and maintains the new state would work. The hardest part is probably keeping it unobservable until you deliberately look. A box, a paperclip and a piece of tissue paper pasted over a hole inside the box. Anyone who poked the paperclip through the hole would break the tissue paper, etc. $\endgroup$
    – Bill K
    Dec 29, 2022 at 19:28
4
$\begingroup$

Give each person a shot glass of vinegar, and a shot glass of distilled water.

Set up a glass in the middle of the table, large enough to contain one shot from each of them. (For increased secrecy, you may also set up a discard vessel)

Each person adds one shot to the central glass;

  • Water if they want dessert
  • Vinegar if they do not

Once everyone has added their liquids, give them a good mix and then add some universal indicator. If the solution is pure water it will turn green, but if anyone has added vinegar the indicator will turn red/orange.

This system should work in theory for groups of a reasonable size, as even a 1:100 ratio of vinegar to water would still have a pH lower than 7

$\endgroup$
3
$\begingroup$

My attempt has a small flaw that may be correctable.

The first diner secretly picks a random number. The diners then proceed in order around the table, each whispering a number to the next. To vote yes, they repeat the number they heard from the previous diner (the first repeats the random number they picked), otherwise to vote no they make up a random number different from what they heard. The last diner whispers their number to the first. If this number is the same as the initial random number the first diner announces "yes," otherwise they announce "no."

This works because if everyone votes yes, then the initial number travels all the way around the table, but if anyone votes no then the result will be the random number chosen by the last person to vote no. There is a chance that they happen to pick the same number chosen by the first diner, but that probability can be made as small as possible by using large numbers.

However, this protocol has an issue: the first diner will learn if they are the only "no" vote, because the number they tell the second diner and the number they hear from the last diner will be the same. So far the only way I can think of to fix this is for the first and last diners to compare their numbers using a zero-knowledge proof (e.g. the socialist millionaire problem), but this is unnecessarily complex.

$\endgroup$
8
  • 1
    $\begingroup$ To remove the risk of a second No voter randomly picking the initial number, you can instruct that any No voter must pick a higher number than the one they heard. $\endgroup$
    – Ralph J
    Dec 30, 2022 at 5:12
  • $\begingroup$ To remove the risk of the first-and-only No voter learning that he was it, have "voter 2" pick a multiplier at random, which he privately gives to First and Last. They each multiply their numbers by that multiplier, and "voter 3" hears, privately, the product from First and then from Last, and announces "equal" or "not equal". Not knowing the multiplier that V2 picked, he won't know if he's the sole No, and nobody else hears more than one number. $\endgroup$
    – Ralph J
    Dec 30, 2022 at 5:19
  • $\begingroup$ @RalphJ Good suggestions! I think the second one works, but the first one leaks some (probabilistic) information about the number of 'no' voters. But if we choose large numbers then the probability of collision is negligible anyway. $\endgroup$ Dec 31, 2022 at 16:57
  • $\begingroup$ Agree - everyone using moderately large numbers each with several factors makes inferences about others' behavior less likely. Meaning that those who don't want their choice to be inferred, have motivation to use numbers /increments/multipliers like 120 - 240, instead of 3-5. $\endgroup$
    – Ralph J
    Dec 31, 2022 at 21:08
  • $\begingroup$ @RalphJ I don't know what you mean about numbers with several factors or increments, isn't the best strategy just to choose a number uniformly at random from the available range? $\endgroup$ Dec 31, 2022 at 21:59
3
$\begingroup$

I would use simple components which can easily to be assembled at the table:

A lamp, a battery, as many switches as there are people at the table, and enough pieces of wire to connect them all.

Make a loop going around the table, starting from the battery, going around the table where every person gets a switch, then to the lamp. Don't close the loop just yet. Ever person selects their preference in secret (hiding the switch under the table or under a napkin): set the switch to on if the person wants dessert, and to off if the person doesn't want dessert. Now close the loop. If everyone wants dessert, the lamp with be lit, else it stays off. Break the loop (so the lamp goes dark if it was on) and have everyone set their switch to off before collecting the gear.

$\endgroup$
2
$\begingroup$

This method required a liquid container with known volume where you can't see how much water is in there. A thermos bottle should do the job. I will assume the bottle has a volume of (n+1.5)*100 ml if there are n people at the table, this can be adjusted easily.

First you publically pour 100 ml of water into the bottle.

Now the voting process: You pass the bottle around. If your vote is yes you pour another 100 ml into the bottle, if your vote is no you do nothing.

After everyone has voted, you publically try to carefully pour another 100 ml of water into the bottle. If everyone voted yes, the bottle will overflow. If at least one person voted no, the additional 100 ml will fit without overflow.

Every voter will receive the bottle with some water in it. They may try to guess how many yes votes were before them by judging the weight but this is fairly inaccurate because the empty bottle has some unknown weight as well.

$\endgroup$
2
$\begingroup$

You need only two cups, water, and an opaque fluid. They can perform the following in front of each other and with items very likely already at their dinner table.

Put a small amount of water in one cup. Put a small amount of opaque fluid in the other cup. This is the pollutant that indicates a no vote. The first voter takes both cups, with the water in the left hand and the pollutant in the right, and votes under the table. He takes 10 seconds exactly regardless of vote, pouring the pollutant into the water for no or doing nothing for yes, making sure to disguise his vote by clinking the cups together repeatedly. He then passes the cups under the table to the next voter, making sure to put water in left and pollutant in right. This continues to the last voter, who then reveals the cups after his 10 seconds.

The result will be immediately clear (or opaque, lol) and only one's word could be used to determine any vote.

Am alternative using only water and two cups:

Water is put in both cups, but instead of pouring one specific cup into the other, a no voter pours one to the other and the other back to the first, thereby mixing both cups. A unanimous yes reveals water in two cups, but any number of no votes reveals water in only one cup.

$\endgroup$
1
$\begingroup$

You need a non-transparent candy dispenser, which can dispense a single piece of candy on press of a button. Find some in store or you can 3D print and assemble one.

Load it with Mentos or other candy with similar properties. You need one candy for each person present. Then you pass it around and everyin who wants to vote yes dispenses a single candy. After a round, open it without looking into it and drop into a glass of Diet Coke.

If anybody voted "no", then there will be at least one candy in dispenser and you will see famed Mentos-Cola reaction.

You can improve this method by using custom made dispenser which will be heavy enough that it would be impossible to detect presence or absence of pieces of candy by weight, cut slots so you would not have to open it before dropping into Coke, make a fake button, so a clicking noise or pressing motion wouldn't signal your vote, etc.

Or you can do something similar, but with some another reaction.

$\endgroup$
1
$\begingroup$

Everyone holds hands under the table. Here are the rules:

  1. Set a timer for the length of the game
  2. If you don't want dessert, wait a little while, then squeeze the person's hand to either your left or right, wait a little, then squeeze the other person's hand.
  3. If you receive a squeeze, you wait a little, then squeeze your other hand.
  4. Don't squeeze the same hand twice
  5. Don't wait through the end of the game

Any "no" will propogate to everyone, and nobody will know where it came from.

$\endgroup$
1
  • $\begingroup$ I'm pretty confident this method is perfect and should be selected as the correct answer as it doesn't even require anything external. It should even open the question back up as this is optimal. $\endgroup$ Nov 13, 2023 at 22:35
0
$\begingroup$

This is a variation of dye method

You start with X ml of water in a cup (X is number of participants). Each participant is given 2 1ml droppers. One filled with water and other with vinegar.

Voting

To vote "No", you must empty the vinegar dropper into the cup. To vote "Yes" you must empty the water dropper. At the end of voting you will have 2X ml of liquid in the cup.

Results

The cup is drunk at the end of voting. If it tastes of vinegar, one or more people have voted No. If there is no trace of vinegar, the vote is unanimous yes

Possible shortcomings

Number of No votes can be approximately guessed based on degree of "vinegarness" of taste

$\endgroup$
1
  • $\begingroup$ The "degree of vinegarness" problem can be removed my changing the vinegar to acid, with the result being determined by adding Litmus to the cup - it'll change color or not, no more so for a greater/lesser concentration of acid. $\endgroup$
    – Ralph J
    Dec 30, 2022 at 5:30
0
$\begingroup$

An easy answer that uses a deck of cards.

Separate the deck into red and black cards. Give each half-deck a shuffle, keeping them all face down. Give each person a single black card, still face down.

The vote

Pass the red half-deck around to each person. Secretly, under the table, each person places their black card face-down on the top of the deck for yes, or on the bottom for no.

The result

For N people, count down to the Nth card from the top and reveal it. If it’s black, the vote was unanimously yes. If it’s red then there was at least one no. Then shuffle the deck to hide the details.

$\endgroup$
-1
$\begingroup$

Inspired by this question on the DIY Stack.

You need a series of voting booths, one per participant, each voting booth contains a simple light switch. The switches are wired to a light bulb in series so all switches must be ON in order to turn the light on. (Optionally you can have one additional switch outside of the voting booths which will prevent accidents and/or cheating.)

The procedure is that all booths start in the OFF position. Everyone enters their individual voting booths and then either switches their switch to ON (to vote yes) or does nothing (to vote no). You can do this one at a time or all at once, whichever you prefer. If you have an extra safety switch then it is switch to ON after the last person is done voting. If all switches are ON then the light will light up, if any are off then it will not light up.

After voting is done then each person re-enters their same booth and makes sure their switch is in the off position--or optionally you could have some system where switches could be moved to off from the outside of the booths.

$\endgroup$
2
  • $\begingroup$ From the OP: "And does not require an external arbiter or programmed device" $\endgroup$
    – Sneftel
    Dec 28, 2022 at 12:39
  • $\begingroup$ @Sneftel There is no programming (unless you consider having light bulbs in houses to be programming). If this is an external arbiter, then so is "put coins in a bag" or anything along those lines. (Yes, this is less practical to do, but the OP has left it open for "elaborate non-programmable devices", which is what this is.) $\endgroup$ Dec 28, 2022 at 14:15
-1
$\begingroup$

Pass a piece of paper to your right, with a number X written on it, any number. Each person adds to the number on the first go-through. Cross out the previous sum and write the new sum anywhere on the paper. On the next go-through, each person subtracts their number, or if they want dessert, subtracts an additional 1.

X may be negative.

You'll end up with the number of votes. Everyone reveals if <= -2

To hide the number of votes, just require that it sum to a negative, rather than summing to negative 1

To determine if a unanimous yes has been established after hiding the number of votes but seeing that there was at least one yes, pass the paper around a third time if the sum <=-2, and everyone adds back the their random excess so that the sum of their three numbers is -1. if = number of participants, it is unanimous.

EDIT: guess we can do things without looking? Much easier then, instead of summing and all that, just write down 3 numbers between -5 and 5 that sum to 0 if you want dessert and any negative number if you don't want dessert, without looking. Then when everyone's done sum them.

$\endgroup$
5
  • $\begingroup$ I was thinking of a very similar scheme while coming up with my answer. I think this has the same problem in that the person who compares the final result to the initial number will be able to determine the exact number of votes. $\endgroup$ Dec 27, 2022 at 18:36
  • $\begingroup$ I was editing, not sure which version of the answer you're referring to, but the last paragraph should solve that issue. Then the first person would just get back some randomly large negative number after the second go-around, revealing no information regardless of anyone's choice $\endgroup$ Dec 27, 2022 at 18:39
  • 3
    $\begingroup$ Since you start with an arbitrary number X, at the end you need to subtract off X to determine if the sum of votes is positive or negative. The person who does that step will be able to tell if they are the only 'no' vote. $\endgroup$ Dec 27, 2022 at 18:43
  • $\begingroup$ In any information sharing scheme you use here where all participants contribute to the state, the final person, if it is the case that 1) they can break or not break unanimity based on how they modify the final state, and if 2) unanimity can be determined based on the final state, they will be able to modify the state of the final piece of information to reveal unanimity or not. Thus, they will always know if they are the lone dissenter. If they weren't, they would not be able to (within the rules) adjust the state to show unanimity. $\endgroup$ Dec 27, 2022 at 19:33
  • $\begingroup$ The above only applies when you have to look at final state. In the case where you do not, it's trivial... you simply pretend to look at the final state, and announce to the group that it is not a unanimous vote yes $\endgroup$ Dec 30, 2022 at 20:02

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