Skip to the content.

# Enigmatic Election

### 4/25/2021

Discussion welcome harold dot doran at gmail dot com

## A Solution

### Let's play this conceptually in a simple way as if there were multiple contestants to see who would have the best outcome. Begin with $$\mathbb{R}_{0 < x < 100} = \{x \in \mathbb{R}| 0 < x < 100\}$$ which is used to mean the value of the random draw, $$x$$, is any real between 0 and 100 and let $$g_i$$ be used to denote a guess by contestant $$i$$. Suppose there are $$i = \{1, 2, \ldots, N\}$$ total contestants and each contestant has a unique guess. Then, the winners are all of those in the set where $$A = \{g_i < x\}$$ but the winner with the best outcome is the contestant with the maximum value of $$g_i$$ in the set $$A$$, or the largest guess in the set of values less than $$x$$. So conceptually, we can think of everyone in the set $$A$$ as a winner, but we want to find the best (richest) winner and if we knew the value of $$x$$ the winner with the best outcome is the individual $$i$$ who guessed just under the value of the random draw. One way to approach the problem is to directly compute the expected value of the return for each possible value between 0 and 100. The uniform has a simple cumulative distribution function (CDF), so we know that if we were to guess $1.00, we would win 99% of the time, if we were to guess$5.00 we would win 95% of the time and so on. If the game were repeated say 1,000 times, then a $1.00 guess would only give a return of$990, but a $5.00 guess would give an expected return of$4,750! So, even though the expected occurence of winning with a $5.00 wager is less than a$1.00 wager, the average expected return on the $5.00 guess is bigger. We can sort of brute force our way through each calculation as $$p(x) \times x$$ where $$x$$ is the value of the wager with corresponding probability $$p(x)$$. The visual display shows where our expected return peaks. We observe that as we approach$50.00, our expected return goes up and as we go above $50.00 our expected return goes back down. More formally I suppose we could define our function: $$f(x) = x \left[1 - \frac{x}{100}\right]$$ and then differentiate the function: $$f(x)' = 1 - \frac{x}{50}$$ To find its peak (i.e., where the slope is 0) set to 0 and solve yields a peak at 50. So, now let's simulate and verify this thinking is accurate.  fife <- function(guess, k = 1000000){ value <- runif(k,0,100) win <- guess < value mean(win) * guess } result <- sapply(1:99, function(i) fife(i))   # The Price is Right ### 10/18/2020 ## Problem Statement ### The Price is Right (TPIR) problem stated here asks: Assume the true price of this item is a randomly selected value between 0 and 100. (Note: The value is a real number and does not have to be an integer.) Among the three contestants, the winner is whoever guesses the closest price without going over. For example, if the true price is 29 and I guess 30, while another contestant guesses 20, then they would be the winner even though my guess was technically closer. In the event all three guesses exceed the actual price, the contestant who made the lowest (and therefore closest) guess is declared the winner. I mean, someone has to win, right? If you are the first to guess, and all contestants play optimally (taking full advantage of the guesses of those who went before them), what are your chances of winning? The answer is effectively 0% for player 1 if both player 2 and 3 use the cut-off strategy and they are mean. Below I show that the actual probability depends on the value for $$\epsilon$$ and assumes players 2 and 3 collude to maximize thier potential gain. Specifically, the probability for player 1 to win is: $$P(g_1) = \frac{[(g_1 + \epsilon) - (g_1 - \epsilon)]}{100}$$ The idea below is that players 2 and 3 collude to force a boundary around the guess of player 1 making it such that player 1 can only be right if they choose the exact right answer, otherwise players 2 and 3 share the remaining win chances by eliminating player 1. Hence, as $$\epsilon$$ becomes smaller (but never 0), this forms a tight boundary such that the likelihood of a win for player 1 tends to 0. ## Some Exploratory Ideas and Existing Research in TPIR ### There is some previously existing research on this topic borrowing from game theory. Ben Blatt describes his approach for optimal Contestant Row here and provides a cheat sheet for many TPIR games here. The generalized optimal strategy, he writes, is for the last player to bid one dollar higher than the highest of any other bid made. This increases the chances that the last player will win to 53.8%. Let's refer to this as the "last player approach", or LPA. Scott Rick describes a "cut-off" strategy here, which strategizes in a way that precludes another player from winning at all. In the current context, we don't have any information about the retail value of the item. Also, the rules are slightly different than the real world game in that if all bidders are over, the closest bidder is the winner. So player 1 can form any guess between 0 and 100 with equal probability. Let's use $$\mathbb{R}_{0 < p < 100} = \{p \in \mathbb{R}| 0 < p < 100\}$$ to mean the price is any positive real number between 0 and 100 and then $$\mathbb{R}_{0 < g_i < 100} = \{g_i \in \mathbb{R}| 0 < g_i < 100\}$$ to mean that the guess for contestant $$i = \{1,2,3\}$$ is also a real in the same domain as the price. The twitter back and forth on this game clarifies that guesses can be any real number and that player 2 can predict what player 3 will do and factor that into their gaming. Since we are considering some general properties of this game we know the first player could only choose randomly in the absence of any information, but the other players will not use random guesses if they use an optimal strategy. So, in frequentist expectation, we can take the first guess to be: $$E(g_1) = .5 \times (a+b) = .5 \times (0+100) = 50$$ if player 1 in fact guesses randomly. If we apply the LPA as suggested by Blatt then player 2 will guess 51. However, since the last bidder intends to maximize their approach, they would combine both the cutoff strategy and also the LPA to make a final bid. Let $$\epsilon$$ be some infinitesimally small value such that $$51 + \epsilon > 51$$. In this way, player 3 has effectively prevented player 2 from ever winning the game unless that player chooses the exact right price. This essentially makes it a game only between two players, player 1 and player 3. Let's explore what happens if this strategy is applied using simulation. R Code below (the function tpir is provided below) implements this approach and sets $$\epsilon = .00001$$. In this code, player 1 guesses 50, player 2 guesses 51, and then player 3 guesses 51 + $$\epsilon$$. The result yields a 51% chance for player 1 and a 49% chance for player 3 and player 2 has been elimated, as expected.  e <-.00001 tpir(50,51,51+e, K=1000000) winner 1 3 50.965 49.035   Let's assume now that in contrast, player 2 knows that player 3 will use a very deterministic way of playing and always use the LPA. A smart player 2 would then drive the second price up to 99.99 such that player 3 must always bet 100. This now yields a benefit for player 2 and eliminates player 3, but highly favors player 1. This strategy would yield a 99.99% win probability for player 1 and a .01% win probability for player 2. Player 3 would be entirely eliminated as expected.  tpir(50,99.99,100, K=1000000) winner 1 2 99.9909 0.0091   Of course, Player 3 won't be bullied!! So, if player 2 makes this move, then player 3 would bid the other extreme,$1.00. Simulation code below shows how this scenario plays out. In this case, player 1 has a 50% chance, player 3 has a 49.95% chance and then player 2 has about a .009% chance.  tpir(50,99.99,1, K=1000000) winner 1 2 3 50.0342 0.0087 49.9571   Of course, player 2 knows that if they bid such a ridiculously high bid player 3 would respond similarly. Perhaps instead, the second player uses the LPA and then player 3 dives under player 1 by 1 dollar, thus ignoring the advice of Blatt. In this scenario, we would observe a 49% chance of winning by player 2 a 50% chance for player 3 and then only a 1% chance of winning by player 1.  tpir(50,51,49, K=1000000) winner 1 2 3 0.9986 48.9946 50.0068   So far player 1 has been treated rather unfairly and bullied around. In fact, player 1 knows something about expected values and properties of uniform distributions. So, player 1 surmises that the expected value of the price will be $50.00 and strategically chooses $$50 - \epsilon$$. The other players follow the LPA sequentially. This would yield a 50% chance for player 1, a 1% chance for player 2 and a 49% chance for player 3.  e <-.00001 tpir(50-e,50+e,51+e, K=1000000) winner 1 2 3 49.9514 1.0120 49.0366   However, in the end, the players want to maximize their own profit--they are not interested in sharing the gain. So, both players 2 and 3 can completely eliminate player 1 by choosing values directly under or above player 1 and split the win probability between the two of the (almost) entirely. It no longer matters what player 1 guesses, players 2 and 3 can eliminate player 1. So, let's assume player 1 chooses$50. Then, player 2 in turn dives just under this number, $$50 - \epsilon$$ and player 3 goes just above, $$50 + \epsilon$$. In other words, their strategy is to form boundaries around player 1 such that the only chance of winning is if player 1 chooses the exact right number. Formally, the probability that player 1 chooses the exact right number when the other players use the cut-off strategy is: $$P(g_1) = \frac{[(g_1 + \epsilon) - (g_1 - \epsilon)]}{100}$$ Again, simulating to observe an outcome if this strategy was used eliminates player 1 as expected and yields the largest possible gain for players 2 and 3:  e=.000001 tpir(50,50-e,50+e, K=1000000) winner 2 3 49.9095 50.0905   Generally, players 2 and 3 know that they can always eliminate player 1. But, if player 1 chooses a low value, say \$1, then player 2 would live with $$1-\epsilon$$ because if they choose $$1+\epsilon$$ then player 3 would choose $$1+2\times\epsilon$$, thus eliminating player 2.


### R Code function
tpir <- function(player1,player2, player3, K){
winner <- numeric(K)
for(i in 1:K){
price <- runif(1,0,100)
guesses <- c(player1, player2 , player3)
### Who is lower and closest
if(any(guesses < price)){
less <- which(guesses < price)
winner[i] <- which(guesses==guesses[less][which.min(price-guesses[less])])
} else {
winner[i] <- which.min(guesses - price)
}
}
table(winner)/K * 100
}



# Eating All The Chocolates

## Problem Statement

### The eating chocolate problem stated here asks: I have 10 chocolates in a bag: Two are milk chocolate, while the other eight are dark chocolate. One at a time, I randomly pull chocolates from the bag and eat them — that is, until I pick a chocolate of the other kind. When I get to the other type of chocolate, I put it back in the bag and start drawing again with the remaining chocolates. I keep going until I have eaten all 10 chocolates. For example, if I first pull out a dark chocolate, I will eat it. (I’ll always eat the first chocolate I pull out.) If I pull out a second dark chocolate, I will eat that as well. If the third one is milk chocolate, I will not eat it (yet), and instead place it back in the bag. Then I will start again, eating the first chocolate I pull out. What are the chances that the last chocolate I eat is milk chocolate? The answer is 50%. The game is based on the concept of a Markov Chain where the probability of eating the next chocolate depends only on the prior chocolate eaten. Hats off to those who worked the probabilities by laying out all of the possible state transitions. It's simple to know the probability of eating the first chocolate--that's always 80% for dark chocolate and 20% for milk chocolate. Then, our bag of chocolates is reduced to nine. At this point, we need to consider the likelihood that we miss the mark and draw a milk chocolate (2/9) which creates a little chaos. We would put that back into the bag and walk through the new state space again eating the new first draw and then successfully drawing the same as our first (new) draw and continuing or unsuccessfully doing so and having to start over yet again. This solution walks through the state space using a simulation. Below is R code that counts the proportion of times that milk chocolate (type 2) is drawn last.


K <- 1000000
final <- numeric(K)
for(j in 1:K){
### Original bag
bag <- c(1,1,1,1,1,1,1,1,2,2)
draw <- numeric(10)
### Take first chocolate from bag
draw[1] <- sample(bag,1)
### "eat" the chocolate and remove from bag
bag <- bag[-which(bag == draw[1])[1]]
i <- 1
### Now take next draw
while(length(bag) > 1){
i <- i + 1
x <- sample(bag,1)
if(x == draw[(i-1)]){ ### If same chocolate eat and remove
draw[i] <- x
bag <- bag[-which(bag == draw[i])[1]] # eat it
} else { ### If not, put it back and start over
x <- sample(bag,1)
bag <- bag[-which(bag == x)[1]] # eat it
draw[i] <- x
}
}
final[j] <- bag
}
table(final)/K
final
1        2
0.499596 0.500404



# Shooting Par

### 09/26/2020

Errata (9/28/2020). The solution below fails to convert either $$L_0$$ to inches or $$L_4$$ to yards. So, either set $$L_0$$ = 14,400 or set $$L_4$$ = 0.059027778. Then, the proposed solution stands.

# Basketball Problem

## Towards a Solution

### The motivating example shows a total of $$\frac{(N-1)^2 + (N-1)}{2}$$ unique combinations for equal teams where town $$x_1$$ is pitted against towns $$x_2$$ and $$x_3$$. But, since this can be arranged such that any town is the third town, we actually have $$\frac{(N-1)^2 + (N-1)}{2} \times 3$$ possible equal team combinations. Since we also assume each outcome is equally as likely (i.e., any number from 1 to 5 might show up), we have a probability of $$p = \left(\frac{1}{N}\right)^3$$ to observe this outcome for each of the possible combinations to make equal teams. So in words, it's the probability of the outcome times the number of times an "equal teams" outcome can occur with $$N$$ players from 3 towns. We can "check" the analytic expression with a simulation. Some R code to run a simulation over $$K$$ replications of the problem where $$N$$ is the upper limit on the number of players that might arrive from any given town.

 ### MC Answer K <- 1000000 N <- 5 # Change this to be any number of max players team1 <- sample(N,K, replace = TRUE) team2 <- sample(N,K, replace = TRUE) team3 <- sample(N,K, replace = TRUE) full <- as.data.frame(cbind(team1, team2, team3)) indx <- apply(full, 1, function(x) which.max(x)) result <- sapply(1:K, function(i) sum(full[i, -indx[i]]) == full[i,indx[i]]) table(result)[2]/K ### Analytic (1/N)^3 * ((N-1)^2 + (N-1))/2 * 3