Friday, July 18, 2014

Low influence functions

It is quite nice to see theory and practice connect.
I've recently become interested in digital crypto-currencies - a hot topic about a market currently worth at least 8 billion dollars, and I would bet, will easily go to a trillion in the next decades.
I started thinking, `ahh, these theory people spending so much time and effort and obscure mathematical questions. I'm never going to do that again..'

But suddenly, this research on crypto-currencies brought me back to old papers that seemed too theoretical to me even when I was interested  100% only in theory.

Let me describe their subject a little through the following story.

Suppose there is a tribe with a council of 99 men that needs to choose
a new leader.

Everybody agrees that in the tribe, there are two members- Xena and Hercules,
that are the most deserving.
They have supernatural powers, and are half-gods.
Both seem to equally deserve the job, so it seems to make sense to just flip a coin
and decide who will be the new leader.
The problem is, who can we trust to flip this coin?
If we assign a particular member of the council, he might use some trick to make, say, Xena come out as the leader - like a coin that seems normal but has one side slightly heavier and almost always falls on that side.
Xena would agree with him in advance that if she gets elected she will do special favors for him
as the tribe leader.

So we don't want to assign the task of choosing the leader to any particular council member.
It seems better to have all council members flip a coin. Then, combine these 99 coin flips in some way.

How should we combine the coin flips?
Here is a very bad idea:
We will count how many coin flips came out heads.
If it is an even number - Xena will be chosen.
If it is an odd number - Hercules will be chosen.

Why is this a bad idea? Because the last person flipping a coin has total control of who will be chosen.
He counts out of the 98 flips so far if there is an even or odd number of heads, and according to that
can say heads or tails to ensure the decision he likes.

Here is a better idea:
We count again how many heads we had.
If it is at least 50 , Xena will be chosen.
If it is less than 50, Hercules will be chosen.
Now notice that when it's the turn of the last person, it is very likely the result has already been determined.
Specifically, only if exactly 49 of the flips so far came out heads, he can control the result.

Are there ways to combine the coin flips such that each player will have an even smaller chance of controling the result?
There are, and this has to do with what is called `low influence functions'.

A nice thing for me was that this paper of ours was mentioned in the Ethereum blog:

No comments:

Blog Archive

About Me

My photo

Hi! I am a computer science postdoc. For some reason google is not finding my new homepage so I added a link from this profile