Decentralised Random Decision without Hashing and External Information

Heading for lunch with my colleagues

Having worked for my reserach assistant job in HKUST for almost 3 months, I now often lunch with my colleagues. Everyday, we have a decision to make: Should we have lunch at the business school canteen or the lowerground 7th floor (LG7) canteen?

Today on our way to the LG7 canteen, I told my colleague, “There is in fact a paper called Mental Poker, that allows players to play poker without a physical deck of cards. Similarly, we can randomly decide the restaurant in a decentralized fashion”.

“How?” my colleague asked. “I have an example” I replied.

The Simple Example

Consider 2 agents, and they have to choose option A or option B. Upon the need of a random binary decision, they follow the following steps:

1. They make an agreement on, if a given number is odd, pick option A, otherwise pick option B
2. Both of them then shout out an random integer at the same time.
3. Sum both numbers, and decide the option base on agreement from step 1

Clearly, the algorithm is scalable to N agents (assuming they can hear each others). I claim that the algorithm satisfy the following property for arbitary number of agents:

Equal

• No single agent determines or have more influence to the final decision

Indeed, the sum S can be represented by:

Where $u_n$ is the number decided by each agent. Since S is a function of u, all agents involve in the final decision. The decision is also determined with S mod 2, so all agents have their influence across all options, regardless of other agent’s information.

Trustable

• Each agent are convinced that the final decision is random From the perspective of any agent, say agent $i$, the sum will be:

Where $S’$ is the sum of integer provided by all other agents:

Clearly, if u_i is private to agent i, S' will be independent from u_i and agent i can believe that S is random. Likewise, S' is private against agent i, so other agents can be convinced that agent i has no control to S. More importantly, even if all other agents colloborates, the isolated agent can still trust that the decision is random.

Intrinsic

• The algorithm clearly relies only on information provided by agents. No external information is needed.

Problem of shouting out number together

“But how are we supposed to hear each other if we are shouting the numbers all at once? More importantly, if one of the agent delays shouting, its unfair to other agents.”, said my colleague.

Which is a very critical problem. So I furhter propose the following modificaiton to the stepts mentioned above to handle this problem:

For N > 2 number of agents:

1. All agents agrees on if a given number is odd, pick option A, otherwise pick option B
2. Agent n tells agent n+1 a random integer (agent N will have to tell agent 1)
3. Each agent report to all other agents the number they received
4. All agents check if the number reported by the next agent matches the number they provided
5. Sum all the numbers provided and make decision based on agreement from step 1.

When there are only 2 agents, this method wouldn’t work and hashing is required. Clearly, this proposed method satisfy the method mentioned above, but with a twist.

Robustness Note that the competition situation is removed from the algorithm, but the algorith is less robust. Which means if two agents (say agant n and agent n+1) are collusive, they can work together and attempt to report an integer in their favour after observing the number other agents reported. To improve the robustness, step 2 of the algorithm can be modified to have agent n tell agent n+1 and agent n+2 (or more) the integer they think of.

Parallel This algorithm is quick, as communication can be parallizied. Meaning that communicaiton in step 2 requires constant time, regardless of the number of agents. Step 4 can parallelized with distributed summation, which requires O(ln(N)) time complexity.

There you go, a simple algorithm for random decision without hasing or external information. With a lot more to discuss! In fact, each agent simply need to choose between 0 or 1, which effectively creates the same result. I look forward to try this algorithm out with my friends.

If you are interested in citing this post:

@article{hon2025decentralised,
  author = {Anson Hon},
  title = {A decentralised algorithm for random decision making without hashing and external information},
  year = {2025},
  month = {January},
  note = {Unpublished manuscript},
}