土产品的土产品

excerpts from my emails :

ACSSNL-Amsterdam will organize an inter-city badminton competition on 25th. There will be 8 teams. We want to divide them into 2 groups(A,B) in advance for some reason. Here is a very concrete problem we need to solve:

Given 8 participants, we want to find a fair way of randomly assigning them exclusively with the labels : A1,A2,A3,A4 or B1,B2,B3,B4. The condition is that these 8 participants can’t meet each other in advance and we need to do the "lottery" in a fair and observable/checkable way(preferably online).

Thanks to Fangyue(VU) Jens(CWI) and Mengxiao(CWI)

We have now 3 "solutions" (all involve Trusted Third Party, in the following call it TTP).

Let’s recall our requirements first:
a. Fairness: people get equal chance to get each label.
b. Verifiable: The procedure is checkable by public later.

We assume that TTP is trustworthy. And every team wants to win (to compete with weaker team and get to the final). There could be coalitions among teams given the above goal e.g Amsterdam and Groningen might want to be in different groups at the first round. We assume the knowledge of the capability of teams is known to all (there is a commonly known partial/total order of strongness.)

Please roughly verify the following procedures against the above assumptions and requirements.

"Solution" I. Time stamp by email(Fang yue, revised by Yanjing):

1 Select an email address which is only accessible to TTP, e.g. the email address of Chinese embassy.

2 Fix a time interval e.g. 12:00-12:10 on 16th, 2007 Amsterdam time.

3 The 8 team leaders have to send an unique empty email to the above email address within the above interval (if someone failed to do so
then redo the procedure).

4 After completing the above procedure. order the emails by time (checkable later by showing the email records of TTP) First will be
assigned A1, second A2…. last B4.

5 TTP release the original emails.

"Solution" II Random number guessing (By Jens)

1. TTP generate a random number X in an big interval of reals e.g.(1,1000000) and keep it secret.

2. for all i in [1,8], team i should send their own random guess of this number X_i to TTP’s private email address.

3. We order the absolute values of (X-X_i) and assign i with A1 if |X-X_i| is the smallest number and assign j with A2 if |X-X_j| is the second closest number etc…

4. TTP will release the email record to public later.

Solution III (By Mengxiao and his colleague) Use a publicly acessible random generator(website)

1 Fix a time interval  e.g. 12:00-12:05 on 16th, 2007 Amsterdam time.

2 Within the time interval, each team should generate a random integer in [11,99] and send to all the others.

e.g. 26 34  47  86  12  32  23 98

3 We order the teams by their numbers according to <= e.g. the team which submitted 12 is team 1, and… the team which submitted 98 is team 8
We then cancatenate them as a sequence: 1223263234478698

4 We go to this page http://www.random.org/sequences/?mode=advanced set smallest value 1 largest value 8 and use the above seqence number
as the persistent identifier to generate a random sequence of 1…8: e.g. input the above number we get 3 4 1 5 8 7 2 6

6 you can verify the generated number by redo the generation on the webpage.

The website has a secret algorithm to compute the sequenceand it is functional: with same input you get same result.

When I have time I will try to design a protocol on this issue, since it is highly related to my research…