Reading Difficulty: 1.5/5

Here's a light read for once.



The Premise

Genshin Impact includes minigames in which you negotiate on a price with someone. You get some number of attempts to offer a price until they get very upset. The goal is to purchase what you want by offering the lowest price you can.

Let's formulate this into mathspeak. Let be a positive integer. The price of a prize is selected uniformly at random from the interval , but is not revealed to you. You are to offer a price between and .

• If , then the prize is sold and you pay .
• If , you're told that the offer is too low, and you must offer another price.

You may get a total of attempts to offer a price. You must succeed in buying the prize within the attempts.

What strategy should I follow to minimize the expected value of the price I end up paying?

Example game 1

Let .

1. I offer . It's not enough. (I now know that )
2. I offer . This happens to be enough, and so I end up paying with three attempts to spare.

Example game 2

Let .

1. I offer . It's not enough. (I now know that )
2. I offer . It's still not enough. (I now know that )
3. I offer . It's still not enough.
4. I'm out of extra attempts, so I must offer now to guarantee the purchase. This is indeed enough and I pay .

Solution

We claim that the minimum you need to pay in expectation is ....

The first observation is that we can fully decide which prices to offer beforehand. We shouldn't need to change our strategy in the middle of the game based on what happens. Also, each offer should be higher than the previous ofer. So, let's suppose that our first offer is , then the next offer is more than that, and then the next offer increases by another , and so on. So our list of offers is:

• 
• 
• 
• 
• 

If we ever actually have to use up all our offering attempts, then the last offer must be . That means that our variables must be subject to the condtion .

What's the expected value of the amount we end up paying?

• There's an chance that , and if this happens then we pay , so one of the terms for the expected value is .
• There's an chance that , and if this happens then we pay , so the next term is .
• There's an chance that , and if this happens then we pay , so the next term is .
• 
• There's an change that , and if this happens then we pay , so the last term is .

Altogether, the expected value is:
Using the distributive property, this can be expanded to become
That is, we have the sum of the squares, and then we add up every possible way to multiple an and an (with ).

This reminds me a lot of how you expand . This is great, because , so this could really help simplify things.

Hmm, it's not quite the same expression though, since
But that right side does kinda look like it! Let's do some algebra to "massage" this expression into what the expected value looks like. First, we add to both sides.
Then, we divide by .
And hey, that right side is now the expected value! So
Huh, what were we trying to do again? Right, we're trying to find the minimum possible expected value for some nice choices for , and so we're trying to find the minimum possible value of .

Inequality fans know what's coming! We use the powerful QM-AM inequality!
If we rearrange this, we get that
The helpful came to the rescue again! Now,
which is what I claimed.

But remember, whenever you're proving that something is the minimum, you always have to prove that it's obtainable. Right now, I've only shown that is a lower bound. If I wanted a lower bound, I could just pick like and be done with it, that's no fun.

The only part where an inequality came in was when we used QM-AM. That means that the only way to obtain the proposed minimum value is to achieve the equality case in the inequality . Fortunately some smart people already figured out that this happens exactly when all the variables are equal, i.e. . Combined with the condition that , we see that the minimum expected value is obtained when we choose , , , and .

This finishes the proof, and that "equality case" also tells us that the best strategy is to offer , then , then , etc. all the way up to .

---

It's always useful to do a quick sanity check to make sure that the answer you get makes sense.

When I plug in , the minimum expected value is . This makes sense because your first offer has to be .

Also, it makes sense that the minimum expected value keeps decreasing the more offers you're allowed to make.

What's interesting is that, no matter how many offers we're allowed to make, we can never do better than in expected value. This probably makes sense, because the expected of value of in the first place is , and we shouldn't anticipate being able to do better than the original expected value.

Hm, this makes me wonder what happens if was not chosen with a uniform distribution... Will it always be the case that we can't do better than ? Exciting!