Non-revealing maximum

Solution 1:

Construct a device in which participants insert pegs at a height corresponding to their age. Participants take turns entering a closed room with the device. The peg is inserted through an aperture which only allows access to one column of peg holes. After inserting the peg, the participant rotates the aperture to the next column. Construct the device with ratchets such that the aperture can only advance, and can only go around once, never coming back to the first column (this is a one-use-only device.) Then the participant leaves the room and the next takes his turn.

After everyone is done, the lid of the device is lowered as far as it will go. Its height corresponds to the maximum age of the group.

Afterwards, destroy the device. (Or put in a reset button which ejects all the pegs and resets the ratchet.)

If you are worried, make it so that many handles must be used simultaneously to lower the lid, to prevent an untrustworthy participant from lowering the lid prematurely to discover the maximum age so far.

Solution 2:

If the group consists of only 2 people, we can use the solution for Yao's Millionaires' Problem to solve this one. With that solution we can figure out who is older. Then the older person tells his age to the younger person. This doesn't reveal too much information, because for any good protocol the younger person gets to know the age of the other person, because he got to know the maximum age.

If the group size is larger than 2, and we can relax the requirements a bit, then I have a solution protocol. The relaxed requirements are: there is a chairman outside the group, and the group trusts this chairman with some aggregate information about the ages of some people (but they don't trust the chairman with their individual age).

The protocol consists of rounds. In each round at least one group member, who is not of the maximum age, is secretly eliminated. Every group member knows whether he has already been eliminated, but he doesn't know about the status of others. After each round the chairman announces a number, or he announces that the protocol is over. The last number announced is the answer (i.e. the maximum age). Each round goes like this: 1. The group (including eliminated members) and the chairman sit down to a round table in any random order. 2. The chairman picks two large random integers, writes them to a slip of paper, folds it, and passes it to the next person on the right. 3. This step is repeated for each group member. The next person reads the 2 numbers from the slip he has received. If the person is already eliminated, then he copies the numbers to a new slip of paper, folds it, and passes it on. Otherwise he picks a random positive integer coefficient, and adds his age multiplied by the coefficient to the first number, and adds the coefficient to the second number, writes the resulting two numbers to a new slip of paper, folds it, and passes it on. 4. The chairman receives the final slip, subtracts his own original random numbers, and divides the first result by the second result. The resulting ratio is a weighted average of the ages of the non-eliminated group members. 5. The chairman announces this weighted average, and declares that everybody not older than that is now eliminated. (This eliminates at least one person, the youngest of the non-eliminated ones.) 6. This is the end of the round. The protocol ends when the chairman has to divide by zero in step 4. The answer is the ratio he computed (and announced) in the previous round.

Having a chairman is indeed necessary. For example, if there was no chairman, but the first group member assumed that role (in addition to his normal duties in the protocol), too much information could be revealed. For example, let's assume that there are 3 people in the group, with the first one being the oldest, everybody has a different age, and the division-by-zero happens in the 4th round. In this case the first person can think like this: I got eliminated after the 3rd round, so in each round exactly one person was eliminated. So at the end of the 2nd round a single other person was eliminated. Based on the information I received as the chairman at the end of the 2nd round, I can compute both the coefficient and the age of that other person. I don't know who he is, but I know a non-maximal age value in the group. And that's too much information.