From Routing to Pricing and Learning: Why Are They Hard to Compute?

Parinya Chalermsook

From Routing to Pricing and Learning: Why Are They Hard to Compute?

Pricing problems usually involve a setting where a store owner is interested in selling items to customers in a way that maximizes the profit. This class of problems includes many applications: a dealer who sells cars of various types, a transportation company who owns the toll roads and charges a toll to drivers, a social network owner (e.g. Facebook) who sells commercial products for their advertisers, etc. The challenges of this problem lie in striking the right prices – too low a price is not profitable; too high a price scares off customers). In an apparently unrelated setting, network routing problems ask for algorithms that send data (i.e. packets) over the network and guarantee certain quality criteria, e.g., route as many packets as possible in a given time. The challenges of routing lie not only in choosing the right set of requests to route but also in planning their routes along the network. These are some of the most fundamental issues in networking and optimization, so it is no surprise that these problems have shown strong connections to major development in algorithm design, complexity theory, graph theory, and optimization. As computer scientists, we are interested in efficient computational solutions for these problems, or seek an explanation for why such solutions cannot exist.

In this project, it is shown that computational aspects of routing and pricing problems share more similarities than one would imagine. Network routing problems have been popular since the 1980s. On the other hand, pricing problems only started receiving attention since 2000 – in the 90s, hardly anyone ever thought about selling their products over the internet. Computer scientists knew how to route packets much better than how to price items. We had some idea why a certain routing problem is very hard to compute, and it is better NOT to compute them than to let a computer run the task until the end of the universe. When we see a practical setting, we model the problem in a way that it is possible to efficiently compute the solution. We had much less understanding of pricing problems. 

Together with my collaborators, I connect these two areas by transferring the knowledge from routing problems. Our results show that algorithm designers face a common difficulty when dealing with routing and pricing. With this discovery, now we understand that certain settings of pricing problems are computationally very hard: For instance, (even approximately) maximizing profits from the toll roads is very hard when there are many more drivers than toll segments. Theoreticians will benefit from rich technical tools developed in our work, and practitioners will learn to reformulate their problems in order to avoid these difficult settings.

We pushed this technique even further, and we ultimately succeeded in “transferring” the techniques from both pricing and routing to help understand the computational complexity of almost 20 other problems. These problems arise routinely in practical settings and we now know they all share a common source of computational diffi culty. After 25 years, we now completely understand that a computer is, very likely, incapable of learning even a very simple language (i.e. it cannot learn deterministic fi nite automation). Computer scientists have already suspected this limitation: A ground-breaking result of Kearns and Valiant showed that any algorithm capable of such learning task would be able to break the famous cryptographic system (RSA), thus convincing a number of researchers that such an algorithm should not exist. Our result provides an even more convincing evidence: such an algorithm would not only break the cryptographic system but also solve tens of thousands of other hard computational problems (i.e., all NP-hard problems).