Let the Computer Pick the Prices

Let's say you run a toll road. You have some desired steady state behavior. Perhaps you'd like to ensure that the commute stays under 15 minutes, which you can do by limiting the number of cars on the road. Unfortunately, this goal isn't easy to achieve directly. Imagine hitting capacity and constantly opening the gate as one car gets off and then closing it as soon as the next gets on–-a horrible user experience!

Pricing as the solution

The real world has a nifty solution for this predicament: charge cars to use this road. NYC's congestion pricing uses this mechanism. The same idea shows up in any compute market (how much do your GPUs cost these days?). And I've talked a lot about this in the blockchain world.

Most pricing mechanisms today use a fixed price. This might be okay on average, but a fixed price will overcharge when demand is low and undercharge when demand is high. Perhaps a few decades ago, when prices were difficult to change, this strategy made sense. Today, however, we have computers. We can do much better by using dynamic prices.

How to set prices?

To set dynamic prices, we need some price update rule which tells us how to change the price to achieve our goals. Let's continue building our infrastructure empire. We want two basic properties: when commutes are too long, the price should go up; and when there's excess capacity on the toll road, prices should go down. But many rules satisfy these properties. How do we choose among them?

The system designer

To specify a price update rule, we first need to specify what we want.^[1] We'll do this via a loss function: a function that, for a certain amount of usage (of whatever we're pricing), outputs our unhappiness. As the designer, we want to ensure commute times stay reasonable by limiting the number of cars. If we'd like no more than 500 cars on the road, our loss function might look something like this:

In short, we don't care if there are too few cars on the road. We're not particularly concerned if there are a few too many, but as we get farther above our threshold, we become unhappy quickly.

The users

Let's say the current price of using the toll road is $10. User behavior is pretty straightforward. If someone needs to make an important meeting, they'll gladly pay the toll; in fact, maybe they would have paid more. On the other hand, someone not in a hurry may only be willing to pay $5 and will elect to take a different route. In aggregate, lots of users with lots of different preferences will make these decisions. We don't assume that we know anything about these preferences; we only observe the decisions.

The pricing rule

We want to trade off user welfare (maximizing the number of people who get to use the toll road) and system designer unhappiness (minimizing the amount of congestion). If we knew exactly how much everyone valued using the toll road, and could specify who got to use it, we could make this tradeoff optimally. Unfortunately, we are not omniscient and all powerful. Fortunately, we can construct a dynamic pricing rule that encourages this "optimal" behavior (i.e., prices that cause self-interested users to act in the way we want).

This pricing rule follows directly from our choice of loss function via convex duality.^[2] Importantly, we can mechanically go from a loss function to a pricing rule. We can also control the dynamics of these rules if we so desire (e.g., we might want the price to increase more quickly than it decreases). We show how to construct these rules in our paper on blockchain fee markets, and we show that these rules perform well, even in adversarial environments.^[3]

Adding dimensions

One toll road is all well and good, but it's hardly an infrastructure empire. Imagine we have many toll roads in a complex network, where different cars can take different but overlapping routes. These dynamic pricing rules can easily handle pricing each route separately but handling their interplay.^[4]

Wrapping up

Choosing prices to allocate resources is hard. Often, we can only estimate a "good price" for something based on trial and error. More importantly, this price might fluctuate a lot; a toll road is much more valuable during rush hour than in the middle of the night. For these reasons, dynamic price mechanisms are the best bet. These types of dynamic pricing algorithms are used for TCP congestion control, the data-link layer of wireless communications, and marketplace optimization. I believe they're useful in many more places. That said, fixed congestion prices are a great start.

Thank you to Alex Evans for helpful comments on a draft of this post.

Footnotes

^[1] Articulating exactly what we want can be quite a bit harder than it sounds! What's the best way to cut costs in an organization? Well, if nothing else is specified, just fire all employees and sell all the assets. Specifying the right objective is important!

^[2] There's a brief convex optimization primer in our paper.

^[3] The second paper also discusses the "online" case in far more depth than the original paper.

^[4] Consider pricing each non-overlapping segment. The price of a route is the sum of the prices of its segments, which we price individually.