What we did

The research in our paper “Robust market equilibria with uncertain preferences,” published at AAAI 2020, is motivated by allocation problems in online markets. Real-world examples of online markets include the following:

• Online advertising: How should ads be allocated to impressions?
• Ride allocation: How should ride-sharing platforms allocate drivers to riders?
• Recommendation systems: How should online recommendation systems (for example, Facebook Jobs, which is a jobs recommendation system) allocate job recommendations to viewers?

In all of these examples, the market consists of buyers (i.e., advertisers) and items (i.e., ad impressions). The buyers have preferences, which are captured by their utility functions. When the platform makes an allocation of an item to a buyer, the buyer receives some utility. In exchange, the buyer often makes a payment of a real or fictitious currency. The allocation rule (who gets what) and the payment rules (pricing of the items) involved are important design choices because they influence whether participants in the market find satisfaction by participating.

A rich body of work, originally by Eisenberg and Gale (1959) in economics and computer science, investigates questions like these. The main insight is the introduction of the notion of a market equilibrium — wherein allocations and prices are determined so that each buyer is “satisfied” with the outcome.

An important challenge within this context is that markets are highly uncertain. At large scales (think billions of buyers and items), it is practically impossible to know the preferences of each buyer perfectly. (This theme has been extensively investigated in “Computing large market equilibria using abstractions,“ and is in a sense a starting point for this work.) In practice, platforms will have machine learning models to predict these preferences from extremely sparse data. These machine learning models are imperfect and make errors in prediction. The challenge we seek to investigate is how do we make allocation and pricing decisions in the face of this uncertainty?

Ideally, we would like our allocation and pricing decisions to be robust against the uncertainty. That is to say, we would like it so that buyers remain “satisfied” when the platform makes decisions with uncertain data. To that end, the work described in our recent paper extends the notion of a market equilibrium to the notion of a robust market equilibrium (RME). The focus of the paper is developing computational tools for RME, as well as applications of the same on some real-world data sets.

How we did it

We start with the decades-old result by Eisenberg and Gale, which answers the question of how to compute market equilibria. (As a caveat, we exclusively work in the so-called divisible goods setting.) They propose doing so by solving a convex optimization program that involves maximizing the geometric mean of all agents’ utilities (also known as Nash Welfare) subject to resource constraints. The key intuition here is that maximizing the geometric mean ensures that allocations cannot be too biased against any individual agent. For example, if we allocate no items to any individual agent, the Nash Welfare is zero.

An analysis of the optimality conditions of the Eisenberg-Gale convex program immediately reveals a host of attractive properties, including the proof that the resulting solution is a market equilibrium.

In order to model uncertain markets, we view the parameters (i.e., the utilities) of agents participating in the market as uncertain. There are many different ways of modeling this uncertainty, resulting in different uncertainty models. We propose and investigate a few natural models in our paper.

We then bring in the main idea of the paper, i.e., the application of a technique called robust optimization to the Eisenberg-Gale convex program. Robust optimization, which is a fairly mature subarea within optimization, deals with solving uncertain optimization problems. In a typical robust optimization problem, the parameters of the problem (the cost function and constraints) are uncertain — or they could be adversarially chosen from a known set.

The technique of robust optimization then seeks to find a solution that produces the best outcome possible against the (worst-case) adversarial choice of parameters from the uncertainty set. Interestingly, many classes of robust optimization problems (including the EG program, as we show in our paper) can be reformulated as (vanilla, certain) optimization problems via convex duality.

After applying the technique of robust optimization, we show a few interesting economic properties of the “robustified” Eisenberg-Gale convex program. One such result is that the solution of the robust variant can be thought of as another market equilibrium where each individual buyer seeks to maximize their uncertain utilities robustly — or, in other words, gain as much utility as possible in the face of adversarial uncertainty. Robust counterparts of a number of other classical properties also follow.

Next, we’ll discuss the application of these ideas to a real-world data set that provides preference information in a recommendation system, namely the MovieLens data set. We perform a thought experiment where we have users choosing movies, with the MovieLens data set indicating how much utility a user would get by watching a particular movie. However, there is a limited supply of movies, so then we would like to allocate movies judiciously, which is using a market equilibrium.

Figure 1
Figure 1 shows the behavior of the Nash Welfare (y-axis) as the size of the uncertainty set (x-axis) grows. The blue line shows the Nash Welfare if we had ignored the uncertainty and simply used the equilibrium based on the Eisenberg-Gale program. The green line shows the Nash Welfare when using the robust solution. There are two trends to note: First, the performance degrades as uncertainty increases, as expected. Second, by a widening margin, the robust solution outperforms the uncertainty-agnostic solution.

Other aspects of the solution can also be investigated. As an example, we consider how robust envy — which is a measure of how dissatisfied users are with their own allocation of movies, relative to others under preference uncertainty — can be compared in the uncertain market when using the robust against the vanilla solution.

Figure 2
In Figure 2, the green plot shows the distribution of users’ robust envy using the robust solution in comparison with the blue plot, which shows distribution of envy when using the uncertainty-agnostic solution. The robust envy is significantly lower.

In conclusion, the numerical results reaffirm that modeling uncertainty and accounting for the same when designing allocations result in better market allocations overall.

What’s next

One of our main follow-up questions is how to make such allocations in an online setting. Many practical applications of interest (such as recommender systems) make decisions online, where instead of seeing an entire view of the market and then making allocations, users and buyers arrive online and allocations must be made instantly. Further practical challenges include making allocation decisions within fractions of a second (very low latency), where solving convex optimization problems becomes infeasible.

In conclusion, our research shows that modeling and accounting for uncertainty in markets can dramatically impact the quality of allocations. We introduce the notion of an RME that is uncertainty-aware, show how to compute it numerically, and demonstrate that this uncertainty-aware allocation method is superior to more agnostic allocation methods.