What is the Millionaires' Problem, and how does Multi-Party Computation solve a variant of it?

The Millionaires' Problem (Yao, 1982): two (or more) parties want to know who is richer, without revealing how much each earns. MPC solves the "what's the average salary?" variant with a clever passing protocol — no participant learns any individual salary except their own.

The "secure average salary" protocol:

For N parties with private salaries a, b, c, …:

1. Alice picks a random r (large enough to hide individual salaries, kept secret).
2. Alice → Bob: r + a (her salary added to the random base).
3. Bob → Carol: (r + a) + b (Bob adds his own salary).
4. Carol → next: (r + a + b) + c.
5. … each party adds their salary in turn …
6. Eventually back to Alice: r + a + b + c + … + N-th salary.
7. Alice subtracts r and divides by N → the average.
8. She broadcasts the average to everyone.

What each party learns:

• ✅ Everyone learns the final average.
• ❌ Nobody (except themselves) learns individual salaries — because every number in transit is offset by r + (some prefix sum) which the next party doesn't know.

The two key security assumptions:

1. Honest behaviour — every party correctly adds their value (doesn't subtract or substitute).
2. No collusion — if two adjacent parties pool their knowledge, they could subtract and isolate the middle person's salary.

Real-world MPC systems relax both of these via cryptographic commitments + verifiable computation, but the textbook example illustrates the core idea: compute on shared values without revealing them.

More general MPC: allows any function f(x_1, …, x_n) to be computed where each party knows only their own input and the final output. Yao's protocol (1986) and the GMW protocol (1987) prove this is possible for every polynomial-time computable function. Modern MPC frameworks (MP-SPDZ, Sharemind, MASCOT) make this practical.

Tip: The "voting with paper slips" variant works similarly: each voter adds +1 (yes) or +0 (no) to a passed slip; only the final tally is revealed. Pen-and-paper MPC for binary voting.