10
$\begingroup$

On the way home from work, I want to refuel my car. There are 5 petrol stations along the way that all have a different price for petrol. I know that the prices will be in the range [A, B], chosen uniformly at random. As I approach a petrol station I see the price of its fuel. At this point, I can either go in and refuel some percentage of my tank, or I can keep driving. Once I've passed a petrol station I cannot go back to it. What should be my strategy to refuel as cheaply as possible in expectation?

This is a real-life puzzle that has been bugging me for years and I would love to know the answer to it. I will accept solutions that refuel at multiple petrol stations as long as the total petrol added is 100%. For example, you could refuel 20% at the first station, 50% at the third station, and 30% at the fourth station. You could of course refuel all 100% at the first station. Note you can assume that the stations are close to each other and the amount of fuel needed to travel between them is insignificant.

$\endgroup$
12
  • 1
    $\begingroup$ Yes. Just updated the question with that information. $\endgroup$ – Dmitry Kamenetsky Nov 13 '20 at 13:27
  • 1
    $\begingroup$ Do you have an expected mean before the first station? Also, should we assume that the amount of fuel needed for the travel is insignificant? $\endgroup$ – Kepotx Nov 13 '20 at 13:46
  • 2
    $\begingroup$ Fixed Path Gas Station Problem: cs.umd.edu/projects/gas $\endgroup$ – RobPratt Nov 13 '20 at 14:59
  • 5
    $\begingroup$ I suppose some kind of price distribution is necessary if you want to do refill partially at several stations. Without distribution information, all you know is that every price ordering is equally probable, so each is equally likely to be the cheapest. For partial refills, the amount you pump would have to depend on the expected price differences (of later stations compared to the prices already seen), not just their ordering. $\endgroup$ – Jaap Scherphuis Nov 13 '20 at 16:00
  • 1
    $\begingroup$ @WeatherVane but in my city the prices can change from the morning, so when I drive back they can be quite different. $\endgroup$ – Dmitry Kamenetsky Nov 13 '20 at 22:13
7
+50
$\begingroup$

Scale [A,B] to [0,1], and buy 100% of your tank from the first station if its price is below 0.2583, then repeat for the remaining stations with limits 0.3047, 0.375, 0.5, and 1.

Solution explanation:

Here is a solution for strategies of a certain form: Before departing, declare a threshold price $T_i$ for each gas station $i \in \{1,2,3,4,5\}$. Upon arriving at station $i$, fill up 100% of the tank if the station's price is less than or equal to $T_i$. What are the optimal thresholds?

I conjecture that a strategy of this form is optimal, as the total cost we are optimizing is linear with respect to the price you end up paying. As such, I don't see any reason why you would ever do a partial fillup. If we were optimizing a nonlinear function, like the utility of your money, or the probability that you would spend less than some bound, then I could see reasons for a partial fill.

Assume each station's price $P_i$ is uniformly distributed on $[0,1]$ (for simplicity, this will be the price to fill up the entire tank, and can be scaled to $[A,B]$ at the end). We also must enforce $T_5 = 1$ to ensure that the tank is eventually full. Then, the expected cost of the fillup is

$E[Cost] = \sum_{i=1}^5E[P_i$ assuming $P_i \leq T_i]*Prob(P_i \leq T_i)*Prob(P_j > T_j$ for all $j < i)$.

Given that all prices are uniformly distributed (and assuming all thresholds are in $[0,1]$), we can write $Prob(P_i \leq T_i) = T_i$ and $E[P_i$ assuming $P_i \leq T_i]=\frac{T_i}{2}$. Then, the expected cost is

$E[Cost] = \left[T_1^2 + T_2^2(1-T_1)+T_3^2(1-T_1)(1-T_2)+T_4^2(1-T_1)(1-T_2)(1-T_3)+(1-T_1)(1-T_2)(1-T_3)(1-T_4)\right]*\frac{1}{2}.$

This is a function of four variables, and I used Wolfram Alpha to compute the local minimum. It returned

min{T_1^2 + T_2^2 (1 - T_1) + T_3^2 (1 - T_1) (1 - T_2) + T_4^2 (1 - T_1) (1 - T_2) (1 - T_3) + (1 - T_1) (1 - T_2) (1 - T_3) (1 - T_4)} = 483008799/1073741824 at (T_1, T_2, T_3, T_4) = (8463/32768, 39/128, 3/8, 1/2)

Therefore, you would expect to pay $\frac{483008799}{1073741824}*\frac{1}{2} \approx 0.2249$ on average using thresholds $(\frac{8463}{32768}, \frac{39}{128}, \frac{3}{8}, \frac{1}{2}, 1) \approx (0.2583, 0.3047, 0.375, 0.5, 1).$

To scale prices to $[A,B]$, multiply each value by $(B-A)$ and add $A$.

$\endgroup$
6
  • 1
    $\begingroup$ Regarding a partial fillup, it seems that there is no reason to ever consider it in a deterministic strategy by the following logic. Assume that your strategy leads you to fill up some fraction of the tank that is less than 1. Having done that, you are now in exactly the same position you were in upon arrival at that station - just with a smaller tank. Unless your strategy is probabilistic, it will again lead you to fill up the same fraction of the remaining tank, etc etc. $\endgroup$ – hdsdv Nov 14 '20 at 1:02
  • $\begingroup$ This is brilliant! I would love to see the confirmation of the expected value with a simulation. I'll try to write a program for this when I have time. $\endgroup$ – Dmitry Kamenetsky Nov 14 '20 at 1:19
  • 1
    $\begingroup$ I think you could also come to the same strategy by working backwards. The expected value at the last stop is 0.5. So you should buy at the second to last stop if the price is less than 0.5. This strategy averages 0.375, so at the third to last stop you buy if less than 0.375, etc. $\endgroup$ – Brady Gilg Nov 14 '20 at 2:57
  • $\begingroup$ I wrote a program and I can confirm that your quoted expected cost of 0.2249 is correct. $\endgroup$ – Dmitry Kamenetsky Nov 27 '20 at 0:16
  • $\begingroup$ I can now confirm that this is also the optimal strategy of this type: ie. if fuelCost(i) < limit(i) then refuel 100% at fuelCost(i). $\endgroup$ – Dmitry Kamenetsky Nov 27 '20 at 1:06
4
$\begingroup$

I think this is more of a Mathematical problem than a puzzle, and one possible solution (for a single refuel) is:

viewing it as an instance of the Secretary Problem, which suggests that the best strategy would be: always reject the first 2 stations, and then refuel in the next one that is the cheapest so far, resulting in a 43,3% chance of getting the cheapest gas in your route.

More about the solution:

The original problem is about an administrator who needs to hire the best secretary of n applicants, but they need to decide right after the interview if they will or will not hire the person, without the possibility to call an earlier applicant. There is a nice video from Numberphile about that problem, if you want a better and more visual explanation.

$\endgroup$
4
  • 2
    $\begingroup$ I think this problem differs from the secretary problem in two ways: 1) the secretary problem only cared about getting the best secretary, and anything else is considered a complete failure (2nd best and worst are equally bad), 2) the secretary problem only used relative comparisons rather than absolute ones. If you consider point #1, your solution might change to: ignore 2 stations, if 3rd is best pick it, if 4th is top N (2?) pick it, otherwise settle for 5th station. Not sure how to involve point #2 without knowing the random distribution beforehand. $\endgroup$ – JS1 Nov 13 '20 at 21:00
  • $\begingroup$ @JS1, I have read the question as desire to find the cheapest fuel station, to which the secretary problem seemed a good analogy to me, but now I see that there may be a better solution in optimizing the money spent. Knowing the distribution would lead to more interesting solutions. Good point $\endgroup$ – Jose HLS Nov 13 '20 at 21:50
  • $\begingroup$ I have added information about the distribution of prices. $\endgroup$ – Dmitry Kamenetsky Nov 13 '20 at 21:56
  • 1
    $\begingroup$ I think this is a good and valid answer. I feel that this is different from the secretary problem, because we are not looking for the lowest price, but least money spent in expectation. Plus we can refuel at multiple stations. $\endgroup$ – Dmitry Kamenetsky Nov 13 '20 at 22:20
2
$\begingroup$

For simplicity, assume that [A,B] = [0,1] and that the price of a full tank is 1. It is easy to rescale at the end.

  1. Assume there is only one station. The expected price is $\int_0^1 x dx = {^1/_2}$.

  2. Assume there are 2 stations. The price in the first is $x$ and you fill $p$. The expected price is $px + (1-p){^1/_2} = {^1/_2} + p(x-{^1/_2})$. If $x \le {^1/_2}$ this is minimized by $p = 1$, and if $x > {^1/_2}$ by $p = 0$. Therefore the expected price is ${^1/_2} {^1/_4} + {^1/_2} {^1/_2} = {^3/_8}$ (the first halves are the probabilities of x being below/above half, the other term is the expected price on this event.)

  3. Similarly, if the expected price for n stations is $Z_n$ then the expected price for $n+1$ stations is $Z_{n+1} = Z_n \times {^{Z_n}/_2} + (1-Z_n) \times Z_n = \frac{Z_n (2-Z_n)}{2}$

This simple formula gives $\frac{39}{128}, \frac{8463}{32768}, \frac{483008799}{2147483648}$ for 3, 4 and 5 stations, and one can easily extend to any number of stations.

$\endgroup$
1
  • $\begingroup$ Thanks. That looks correct. Your final ratio is the same as Brady's. $\endgroup$ – Dmitry Kamenetsky Dec 12 '20 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.