The dessert problem (blind ballot remaining blind if non-unanimous) [closed]

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

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

Answer 15

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.

Answer 16

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.

Answer 17

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.