Fair continuous election algorithm in a limited set of users

Question

I have an election method in mind, don't know if already exists but I think there must be.

It is used in a finite set of users and continuous. Every round, somebody is picked randomly depending on the probability.

Initially everybody starts with equal probability. But with every round, the selected user's re-election probability will decrease (but will still be available to be elected nonetheless).

If everything goes extremely fair and every user who has not been elected before is elected one after other, an then when everybody is elected once, the probabilities of them will be equal again.

Example: John, Max & Sarah are 3 users.

Scenario1:

Initially: [ P(J)=%33, P(M)=%33, P(S)=%33 ] 

1st round, John is elected: [ P(J)=%10, P(M)=%45, P(S)=%45 ]

2nd round, Max is elected: [ P(J)=%5, P(M)=%5, P(S)=%90 ]

3rd round, Sarah is elected: [ P(J)=%33, P(M)=%33, P(S)=%33 ]

Scenario 2:

Initially: [ P(J)=%33, P(M)=%33, P(S)=%33 ] 

1st round, John is elected: [ P(J)=%10, P(M)=%45, P(S)=%45 ]

2nd round, John is elected again: [ P(J)=%2, P(M)=%49, P(S)=%49 ]

3rd round, Sarah is elected: [ P(J)=%5, P(M)=%85, P(S)=%10 ]

4th round, Max is elected: [ P(J)=%10, P(M)=%45, P(S)=%45 ]

The probability values above are not based on a strict constant, just given for better understanding the question.

The main idea, needs to be accomplished is to give a user fair election chance and still protecting the re-election chance(but smaller as his election count gets bigger)

Thanks in advance

Answer 1

I have never heard of a scheme like this (although I am not a poli-sci or voting specialist). Your idea is very cool though and prima facie appears to be fair. From a proabilistic viewpoint, you may want to run some Monte Carlo simulations of your scheme with different methods of updating selection probabilities. This will allow you to verify that the long-run fraction of times each person is chosen is in fact equal, as well as the recurrence time for each person.

If you are of a theoretical bent, then you may find this paper interesting.

Answer 2

Very interesting! So your idea is that everyone who was elected should have a reduced election probability compared to those who weren't elected. So here is an equation that gives you election probabilities which satisfy these requirements.

Suppose we have $i=1,2,\ldots, I$ candidates. There is one election every $t=1,2,\ldots$, where exactly one candidate is chosen. Define the indicator $e_{it}$, which is equal to 1 if candidate $i$ got elected at $t$, otherwise it is 0. The election probability of candidate $i$ at $t$ is now $$P_{it}=\frac{1+\sum_{x\neq i}\sum_{j=1}^{t-1} e_{xj}/(I-1)}{I+t-1}.$$ (The sum term in the numerator is the number of elections of all candidates but $i$. So if we sum this sum term over all candidates, then $\sum_i \sum_{x\neq i}\sum_{j=1}^{t-1} e_{xj}/(I-1)=t-1$, so the probabilities sum to 1.)

Intuitively, the more the other got elected, the higher is your probability to get elected.

Illustration: at $t=1$, we have $\sum_{x\neq i}\sum_{j=1}^{t-1} e_{xj}=0$, because nobody got elected yet, so $P_{i1}=1/I$, i.e., everybody has the same chance to get elected. At $t=1$, someone gets elected, so for the unelected at $t=2$ we have $$P_{i2}=\frac{1+1/(I-1)}{I+1}$$ and for the elected candidate we have $P_{i2}=\frac{1}{I+1}$, i.e., less.

Two nice features about this equation. First, everybody who has the same number of elections at $t$ has the same probability to get elected (what can be fairer?). Second, as you required, whoever has more election wins at $t$ has a lower probability to get elected at $t$.

The question is of course whether this can be applied? After all, people vote, and elections are not just decided by random draws. Do you plan to do this?