8Feb/1017

## An information theory puzzle

My brother shared this puzzle with me this morning. He heard it on the radio but no solution was offered. Neither of us know what the answer is so I'm looking forward to one of you posting the answer in the comments. Here's the puzzle:

Bob and Alice are both millionaires. They're both curious to know who is richer but they don't want to tell the other one how much money they have. Without engaging a trusted third party, how can they both know who is richer?

I wonder if the solution has something to do with public and private keys and/or authentication.

So, what's the answer?

.mau.February 8th, 2010 - 09:13

first of all, could we assume that they are honest? If so, we may cheat in this way:

Both of them answer the question “Do I have more than 2 million dollars?” and go forward with 3, 4, … million until at least one of them says “no”. If just one answers “no”, the other one is the richer; otherwise we have to halve the interval repeatly until we obtain different answers.

Otherwise, I cannot manage to find a suitable trap function

Sue VanHattumFebruary 8th, 2010 - 09:38

I saw another problem like this one, and I can’t remember whether I solved it myself nor what the solution is. I do know it was a nice solution. The one I saw before went something like:

10 mathematicians are out to dinner, and want to know their average salary. Without anyone finding out anyone else’s salary, how can they do this?

I think they could each write something down. But what? Please note: I may have the conditions of the problem wrong.

.mau.February 8th, 2010 - 10:00

@Sue: with your statement the answer is possible indeed.

.

.

.

.

.

.

.

SPOILER:

.

.

.

.

They prepare ten plausible salaries, write them down in ten leaflets, and put them in an urn. Everyone then picks up a leaflet, sums the value with her own salary, and shows the result.

AsmorFebruary 8th, 2010 - 11:51

@.mau: Clever.

Here’s a possible solution for the problem in the post, about the millionaires.

First, an assumption; since they both confess to be millionaires, I’ll assume neither has more than $999,999,999.99

Now you get a series of 11 scales, and on each side of each scale you put a wooden box. Since all boxes are identical in weight, they are at equalibrium. The scales should be setup so that they will only show whether there is an imbalance, and not the magnitude of the imbalance. For example, set an obstruction just underneath each scale so that it can’t fall more than is necessary to show the imbalance.

Now starting with the least significant digit, each of the millionaires fills up an opaque bag with 9 marbles. The marbles are all the same size, but some are heavy (metal) and some light (wood). All heavy marbles weigh the same and all light marbles weigh the same. For each digit, the millionaires put that number of heavy marbles in the bag, and then fill the rest of the bag with light marbles.

When the bags are filled, the millionaires dump them in the appropriate scale. The scale then indicates which bag was heaviest, thus which digit was larger.

The millionaires repeat the process for all 11 scales. The most significant scale which is not balanced will indicate who has the most money. Then the millionaires take back the boxes and dispose of the contents privately.

AnonymousFebruary 8th, 2010 - 14:30

For the ten mathematicians one, *possible spoiler*, couldn’t they just write down a certain set of numbers of which the average is equal to their salaries? That way the one doing the additions on the calculator will find the average salary of everybody without necessarily seeing a single true salary.

ManuelFebruary 8th, 2010 - 16:02

@Anonymous: I think you have found the easiest solution, but it has to be ellaborated further. Say that the mathematicians use an arbitrary number of cards each, for example 3, and they write the 3 numbers whose average is their salary in 3 different cards. The 30 cards from the 10 mathematicians are then mixed together and the average is computed, which will be the correct average of all the mathematicians salaries. Very nice solution indeed.

I am going to think a bit more in the original problem of the millionaries to try and find a different solution than the one proposed by .mau., although I doubt there isn’t any that is more ellegant.

In any case, note that the problem won’t have a solution if both millionaries own exactly the same amount of money since they will know how much the other has (the same amount as themselves).

EnginerdFebruary 8th, 2010 - 17:19

Basically, what you need is a function which is monotonic but not easily reversible. A hash-type function H for which H(a) >= H(b) if and only if a >= b. Some quick googling seems to indicate that such functions exist, but I can’t give you a good reference without spending more than 5 seconds.

You could also find a way to use a “trusted third part” which isn’t a person. For instance, each person enters their net worth into a computer program, and the computer compares. This seems like a cop-out to me, if a trusted third party has to be a person than this would work.

spoilerFebruary 8th, 2010 - 18:24

http://en.wikipedia.org/wiki/Millionaire%27s_Problem

.mau.February 9th, 2010 - 01:21

@spoiler: unfortunately the Wikipedia entry does not provide an actual algorithm, or at least I cannot see it (it’s morning, here in Italy, so maybe it’s just the fact that I did not sleep much).

SebFebruary 9th, 2010 - 02:47

And here is a solution:

http://www.proproco.co.uk/million.html

ColinFebruary 18th, 2010 - 15:06

I like Asmor’s scales idea – if you were to combine that with Enginerd’s monotonic function – say, the logistic function L(x) = 1/(1+e^(-x)), you’d have a one-shot solution right there.

Alice crafts a weight of L(A) in some suitable units; Bob does the same with weight L(B). They weigh them on an old-fashioned balance, and whoever has the heavier weight gets to point and laugh at the other for all time :o)

AsmorFebruary 18th, 2010 - 15:25

@Colin

Ooh, that’s very clever! The lack of precision with the scales means that you can use a simpler function and not worry about how easy it is to reverse engineer the original value since you’ll never know the other person’s current value.

For that matter, we could make things even simpler. Let them each craft a weight of x micrograms, where x is their net worth. Compare and then discard weights. Using the earlier assumption that neither is a billionaire, that would put an upper limit of a kilogram on each person’s weight.

ZoaknuFebruary 28th, 2010 - 00:43

It is a problem with no information theoretic secure classic solution, any solution you give will be necessarily based in some computational complexity hypotesis. Quantumly and with the help of a trusted third party there are some very recent information theoretic secure solutions:

Yu-Guang Yang et al. Secure quantum private comparison. 2009

MathFebruary 28th, 2010 - 09:32

As no millionaire is going to say the truth, we assume both are going to lie each other, So It can be found who is richer than other.

consider A – alise

B – bob

Other way can be say, if A says I can buy 10 planes and B says I can buy 11 planes then, B is richer than A

ShaunMarch 2nd, 2010 - 13:59

As you may remember, I’ve been linking to your site from mine for a while. I just wanted to let you know that I have posted a short post on my math blog (sk19math.blogspot.com) that introduces and links to your site. I think you’re doing a great job with the site, and hopefully I can help drive some traffic your way. Cheers and all the best!

SK

conchisMay 31st, 2010 - 16:23

The usual solution to Sue’s puzzle, without allowing them to write anything down is: M1 adds a random number to her salary, and communicates the sum to M2, M2 adds her salary and communicates the sum to M3 and so on. Once M10 adds her salary and communicates the result back to M1, M1 subtracts the original random number and calculates the average. Voila!

Sue VanHattumMay 31st, 2010 - 19:36

Conchis, that is so elegant! (I’ll forget it again soon, though…) ;^)