# Is a fair lottery possible?

I'm trying to come up with a scheme for a lottery where each individual has roughly the same chance of becoming the winner, regardless of the number of tickets one holds. So no individual should have an incentive to buy a second ticket, but even if they decide to do so, it should not gain them any significant advantage over any of the other players.

Ofcourse, the simplest solution would be to just refuse to sell them multiple tickets, but since all players are anonymous, I cannot differentiate between ticketholders and tickets, so that's impossible.

A working solution would be to increase the house-edge exponentially (or decrease the jackpot) as soon as a new ticket is sold, so that buying another one lowers the expected profit more than is gained by having an extra ticket. No rational player would want do that, unless they have no previous tickets. But the problem with that is that only a very small amount of tickets can be sold untill the house has 100% chance of winning, so in practice nobody will ever win.

Is there a better formula possible? By dynamicly changing parameters like the ticket-price, jackpot, or win-chance with every new ticket? The lottery does not have to be economicly feasible, its no problem if the organizer always makes a loss from it for example.

I have a feeling I'm asking for the impossible, but since the proposal above would work fine for very small groups, there should be a formula which works in larger groups too.

• Since such a lottery system cannot discriminate between one person having two tickes and two persons holding one ticket each, isn't the first always at an advantage for winning. If fair means having zero expected value, there is no problem. You flip a fair coin. Heads, nothing is paid out. Tails, twice the total price of tickets is paid out. – Michael Greinecker Jan 22 '14 at 13:17
• I haven't crunched the numbers, but here's an idea. Start with a set of unique ticket numbers, and every time a ticket is bought the organizers add some number of tickets with that same ticket number back into the pool. That way every ticket you buy increases the odds that you will have to split the jackpot with other players and hence reduces your expected payoff. – Paul Siegel Jan 22 '14 at 13:24
• I think you are indeed asking for the impossible. If the ticket buyers are anonymous and the system has no way of distinguishing whether two tickets are held by the same individual, then any scheme making it unprofitable for one user to buy multiple tickets will make it equally unprofitable for other users to buy tickets. So, any measure designed to discourage buying multiple tickets will subsequently discourage anybody from buying any tickets. – Emil Jeřábek Jan 24 '14 at 16:15
• This sort of lottery is very fair. Everybody loses! – Asaf Karagila Jan 24 '14 at 16:38
• Now that I think about it, the same argument applies to the solution for small groups you outline in the question. I believe your analysis is mistaken. On the one hand, you assume the players to be rational, but on the other hand, you assume that they base their decisions whether to buy on the expected gain under the condition that the jackpot will stay what it is now. However, since this condition is badly violated, the players would be foolish to do so. They will make their decisions based on the expected value of the jackpot after the whole lottery is finished. – Emil Jeřábek Jan 24 '14 at 18:03

With the various restrictions in place the answer to the question as asked seems to me to be 'no, there is no such system'.

It was said there is one prize to be distributed (one person to be selected) and it was also said the tickets could even be free. And, the lottery should be fair, so that different individuals have essentially the same chance to win they holding one or more ticktets regardless. And, of course the key point that one cannot distinguish tickets from individuals. However, the prize can be adjusted in the process.

So there are tickets $\{1, \dots, n\}$ distributed, and there is a partition of the set $\{1,\dots, n\}$ into disjoint nonempty sets $I_1, \dots, I_k$ corresponding to the tickets one individual holds.

As described the only thing the organizer of the lottery knows is $n$. But, they have no control over the $I_j$. It is impossible to assign winning propabilties $p(i)$ to the different tickets so that $\sum_{i \in I_j}p(i)$, the probability individual $j$ will win, is about equal for all $j$ and each possible choice of $I_j$, except $p(i)= 0$ or $n\le 2$.

Now, the above assumes that tickets are distributed and then some 'drawing' is done possibly following some complicated system.

If one does not insist on this there are of course ways to assign in a in some sense fair way one prize in a way that it is pointless or even bad to get more than one ticket (even if it is free).

The "unique is the winner" was already mentioned, one could also do "first come, first served" (the first ticket sold always wins).

Finally, in OP and in some answers something else is discussed, which in my opinion is not really "fair" in the sense of the question. Merely, these would be systems to make it unreasonable to get more than one ticket but still if somebody would they would be in some sense better of than the others in the same game. Yet, yes, I think there one could (in a certain formalization) show that one needs at least exponential decrease of expected win to make this work.

• I answer this in CW, since basically it is just long commentary and even more so commentary already made by others. – user9072 Jan 29 '14 at 15:28

Probably you can easily adapt the THE PACHIRA LOTTREE (proposed by Douceur & Moscibroda) to your needs. The authors state the postulate of the unprofitable Sybil attack which seems in agreement with your requirement of no gain from buying more tickets.

• I read the paper, and one very promising sentence is ""An important property is that no participant can increase its odds by pretending to have multiple identities." But its way too complex for me too understand, I hoped there was a simpler scheme possible. – Muis Jan 24 '14 at 12:49
• I’m not quite sure this is really applicable. The model they are using is that the participants contribute something to the system, and their meaning of the Sybil attack property is that no participant can increase their odds by splitting their contribution among multiple identities. If you fix the amount every identity contributes (e.g., 1 identity = 1 ticket), you do increase your odds by creating multiple identities, and it’s essentially one of their design goals (the “value proportional to contribution” requirement from section 3). – Emil Jeřábek Jan 24 '14 at 14:17
• @Emil Jeřábek You are quite right that the key here is to define this “something” which is contributed to the system by the participants. We should try to choose this “something” in such a way that it is impossible for a single person to contribute more than one unit of it. E.g. we can imagine giving at pre-specified moments of time CAPTCHA tasks with only 5-10 seconds to solve them.At the same moment we give a different task to every ticket. If we receive a good solution we can be almost sure that it was solved by the human. – Waldemar Jan 24 '14 at 19:47
• @Emil Jeřábek (continued) Moreover, we can assume that it is almost impossible for a single person to solve 2 such tasks in such a short period. Receiving too large proportion of wrong answers from a given ticket eliminates this ticket from the lottery. The real benefit of the proposal by Douceur & Moscibroda is that we incentivize current participants to invite more people to enter the system. – Waldemar Jan 24 '14 at 19:47
• @quid Basically, I agree with your point. However, I read the question in such a way that the key assumption is “all players are anonymous”. I interpret the conclusion that “I cannot differentiate between players and tickets” as something not having to be universally valid. Moreover, in my interpretation the no. of tickets is equal to the no. of participants but we do not identify personal details of the participants (as with the ID cards), so all players are really anonymous. Maybe my interpretation is not in accordance with the OP’s intentions. – Waldemar Jan 27 '14 at 14:12

I think that The simple lottery is an answer to your question. Since I have no background in the game theory, I certainly omit some details and the COMMENTs section below might be far from correct.

On second thought, also The unique-is-the-winner lottery below would be a solution, too.

=THE SIMPLE LOTTERY=

For the purpose of discussion I present more variants of the lottery.

THE GAME. Suppose we have $n=100$ players each of which chooses to buy $x=x_i$ tickets, each of which costs 1 dollar, where

• (v3) $x\in \{0,1,2,3\}$
• (vI) $x\in \{0,1,2,\dots\}$
• (vR) $x$ is a non-negative real number.

The lottery is made with each ticked having equal probability to win the price of $P=202.0202 \dots > 1$ dolars so that $i$-th player wins with probability $x_i/\sum_j x_j$.

ASSUMPTIONS. The number of players is well known. Some game-theory related assumptions might be needed like that the players are inteligent, their goal is to maximize gain expectation (average over probability, in the linear fashion), the actual move of each player is secret while other information is well known etc. In particular I consider the player's goals uniformity and their public knowledge to be sensitive. (If there are players with different goals like keep-what-I-have-with-certainty or get-maximum-or-noghing, the game might possibly get disbalanced).

THE STRATEGY. A game-theoretical result like a Nash equilibrium theorem provides us (I hope; at least in the variant (v3)) with an optimal strategy for each player. Case (vR) lacks compactness and might be a problem. (vI) is somewhat more compact.

The optimal strategy will be generally a mixed (i.e., probabilistic) strategy. Because of the symmetry, the mixed strategies of individual players will be the same.

COMMENT. Though this is not important, I choosed the particular values so that, I guess, (some of) the optimal mixed stragies of the players are actually pure strategies of bying $x=2$ tickets. I think so because assuming(!) the other players play pure strategy of buing $a$ tickets and if I buy $x$ tickets, the outcome expectations is $E(x)=e(x)-x$ where $e(x) = \frac{P x}{(n-1)a + x}$ is win expectation and $x$ is the investment in the tickets. I consider the variant (vR). The graph of $e(x)$ is an increasing hyperbola with $e(0)=0$ and $\lim_{x\to \infty} e(x) = P = 202.0202\dots$. If $e'(0)\le 1$ (that is, $a \ge P/(n-1)$) I will buy $x=0$ tickets. But this is not the equilibrium since the strategy is not optimal to other players (their expactations are $E_i=P a/((n-1)a) - a = P/(n-1) -a \le 0$ and each of them should consider to buy e.g. $0$ tickets instead). Otherwise the best pure strategy is to buy $x$ tickets where $e'(x)=1$ ($E'(x)=0$), which means $x=x_0 = \sqrt{(n-1)a}(\sqrt{P}-\sqrt{(n-1)a})$. For the equilibrium strategy we have $x_0=a$, which leads to $x_0=a=P(n-1)/n^2$. If players play like that, the lottery maker gets $P(n-1)/n$ dolars and gives away $P$ dolars, thus paying price $P/n$ for attracting playres to participate in the procedure. BTW, if $n=1$ and I am the only player, I invest one cent in the tickets and get full $P$. Now back the mixed strategies: If think of changing my pure $x_0$ ticket strategy to some mixed strategy, I see the utility function is concave which makes the pure $x_0$ strategy best among all mixed strategies. And more generally, if the strategy of other players is fixed (arbitrarily, mixed), then the utility function is strictly concave (because an average of strictly concave functions), making some pure strategy the optimal strategy. (This even sounds as a proof that the equilibrium strategies for (vR) are pure.) For variants (v3) and (vI), this suggest the optimal would be to mix the two integer values that are next the calculated $x_0$.

=THE ZERO LOTTERY.=

(For the sake of completness I have to note that also the zero lottery seems to be a solution to your problem. The rules are "No one wins." Then, obviously, the chances are equal. That is to clear that you wish to get positive probability that someone wins. May be you wich that probability to be $1$.)

=THE UNIQUE-IS-THE-WINNER LOTTERY=

This lottery has nonzero probabity of no-winner, but it is simpler and more accessible. Moreover, it can be repeated until a winner is found.

We have $n$ players which have option to by $0$ or $1$ tickets, which costs one dolar. A player wins $P=100$ dolars if he is the only one who bought the ticket. Of no one boght the ticket, no one wins. If at least two tickets were sould, no one wins.

COMMENT. Silly player like me chooses to buy a ticket with probability $1/n$. More clever one perhaps buys with probability proportional to $P$. Even clever player will estimate the price of the game to be about $P/n$, hence, for large $n$, he buys with probability smaller than $P/n$. For smaller $n$ he only observers the lottery is likely to repeat several times and he has no idea what the optimal strategy is.

• It seems your solution requires to know how many players participate, and I only know how many tickets are sold, because i cannot distinguish between tickets/players, nor limit the amount of tickets per player. So am I correct that your solution is unusable then? – Muis Jan 27 '14 at 11:02
• I think we need more precise mathematical formulation of the problem. What is known about the number of players/people. Is it finite or infinite? We have to deal with probability space somwhere. Maybe you have to specify that? What is your question, mathematically ? – Jan Kolar Jan 27 '14 at 11:26
• @Muis some already told you this is impossible with all these restrictions; except if the expected gain is 0 throughout. – user9072 Jan 27 '14 at 13:55
• @Muis yes it discourages them, but then if somebody would enter twice they would still have a higher chance than somebody else that has just one ticket. This is not "fair" IMO. So, it is not quite clear what you want. But this unique-wins to me seems to match what you want, but since you seem not to like it, I am at a loss what you want. – user9072 Jan 27 '14 at 23:50
• @Muis the idea of Paul Siegel seems mainly like a "practical" implemenation (for the context of what one might consider as an actual lottery) of your decrease prize exponentially. However again it does not seem at all true that with two tockets one will have roughly the same chance as with one ticket. Even more so, if I buy ticket one and two than holding each of them gives me an edge over somebody holding the third ticket. And, I do not see why the unique-wins is limited to two players. It allows in some sense an arbitrary number of players just they might not buy a ticket. – user9072 Jan 28 '14 at 21:15

One can perhaps pick the winner by elimination. The algorithm would be :

1. Pick a ticket at random and eliminate the holder.
2. Repeat (1) until only one ticket is left.

In this scheme, players who buy more tickets would also have a higher chance of being eliminated. An issue with the scheme could be to determine the identity of the holder of the ticket which is picked for elimination in each step. The holder does not have an incentive to identify himself/herself.

This scheme is similar to method is Peter Rindal's answer except that you do not eliminate based on personal characteristics.

• The purpose of the scheme is to make cloning useless, since I cannot tell who is a real holder and who is a clone of that holder. With the solution above the holder with the most clones will probably win. – Muis Jan 29 '14 at 14:45

How about something simple: make the tickets expensive (say 1000 Euros) and set the prize to be worth slightly less than two tickets (say 1950 Euros). There is incentive to participate and there is no incentive to buy more than one ticket.

• This would make the expected gain negative as long as at least two tickets are available for sale, so nobody would participate. – Emil Jeřábek Jan 29 '14 at 12:18
• To be more precise you have to make some assumptions regarding the risk aversion of the participants. Emil implicitly assumed that they are risk-neutral which may or may not be a realistic assumption. If they are risk-averse, Emil's conclusion is even stronger. – Waldemar Jan 29 '14 at 12:21
• You're right Emil, but any lottery system that claims not to distinguish a person holding all the tickets from a person holding one ticket has to be cookey con game and this seemed to me one way to pull it off. – alvarezpaiva Jan 29 '14 at 12:35
• The ignorance of the masses is of course limitless, but I’d wager a guess that a successful scam would call for something less obvious. – Emil Jeřábek Jan 29 '14 at 12:47
• I think that scam is called "securitization" :-) – alvarezpaiva Jan 29 '14 at 13:16