Suppose you want to sell a car and there are 10 agents willing to buy it. You are not sure how much they could pay but for each of them you know a probability distribution of how high the offer will be. For example, a car salon would always pay 10K  but some person might offer 5K or 15K with equal probability. The best you could do is to first negotiate with all of them and then pick the highest bid. Unfortunately, you cannot do so - after seeing each offer you must irrevocably choose either to sell the car or to refuse the offer. What is the best strategy to maximize your revenue in this case?

In turns out that this is a well-studied optimization problem with a simple strategy that guarantees you can (on expectation) earn at least half as much as a hypothetical prophet, who knows all the bids in advance. This result is known as the prophet inequality. What is more surprising, this strategy would work even if you are a car retailer and want to sell five cars. Moreover, you might want to have some constraints, for example you do not want to sell two cars to buyers from the same city, or have multiple kinds of cars with different evaluations, and you can always guarantee an expected revenue comparable to the one of the prophets.

This problem not only exploits beautiful math but also has important applications in internet ad display. Actually, whenever you type a query into a web search engine, the ad system performs this kind of car-selling game with the ad suppliers, who offer different bids for their ad to be displayed to you.

Here is a link to our recent work with new developments in this theory: http://ieee-focs.org/FOCS-2018-Papers/pdfs/59f790.pdf

Michał Włodarczyk