The following question occurred to me during a recent search for a car parking place. Maybe it’s been done to death somewhere in the economics literature; let me know if you’ve seen it.
So I’m having trouble finding a parking space, and being a good liberal my reaction is to throw money at the problem. Since the car park’s full, the people who run it should jack up the price, right? With any luck, it would rise to a point where some of these cheapskates would get priced out, and I would still be in the game. Actually, there’s a smarter trick possible: you should have some cheap parking spaces and some expensive ones. The first people to arrive at the car park are able to take the cheap spaces, and later arrivals who are desperate for a space have to buy the expensive ones.
To see that this can increase the revenue, suppose that you own 100 spaces and there are 200 potential users, 190 of whom would pay £1 for a space, but the other 10 would be prepared to pay £5. Clearly we should charge either £1 or £5 for spaces, and if we charge £1 for all of them we raise £100, while if we charge £5 for all of them we raise £50 (selling 10 spaces and leaving the other 90 idle). Suppose instead that 99 spaces cost £1 and the other one costs £5. Suppose further that car park users arrive in a random order. In that case you are very likely to sell all spaces and raise £104; there is probability of only 2-10 that the 10 high-value users will be amongst the first 100 users to arrive, which would lead to the £5 space ending up idle and a revenue of only £99.
This suggests the following computational problem. You have n parking spaces and there are N>n users, where each user has a known value that he assigns to receiving a parking space. Assuming they arrive in a random order, how should you price the parking spaces so as to maximize the expected revenue? (Whenever a user arrives, they buy the cheapest available space, unless their value is less that the cheapest space, in which case they leave.) Indeed, for a given set of n prices for the spaces, I don’t see how to efficiently compute that expected value, although it would be easy enough to approximate by simulation (repeatedly generate random orderings of the users and see what happens).
It seems like the effectiveness of heterogeneous prices is greater when N is quite a lot larger than n. In the case that n>N, I don’t know of any examples where revenue-maximization requires prices to be non-uniform.
Sublinear Algorithms Day at MIT on April 10
2 hours ago