Optimal Search Segmentation Mechanisms for Online Platform Markets

Abstract

Online platforms, such as Airbnb, hotels.com, Amazon, Uber and Lyft, can control and optimize many aspects of product search to improve the efficiency of marketplaces. Here we focus on a common model, called the discriminatory control model, where the platform chooses to display a subset of sellers who sell products at prices determined by the market and a buyer is interested in buying a single product from one of the sellers. Under the commonly-used model for single product selection by a buyer, called the multinomial logit model, and the Bertrand game model for competition among sellers, we show the following result: to maximize social welfare, the optimal strategy for the platform is to display all products; however, to maximize revenue, the optimal strategy is to only display a subset of the products whose qualities are above a certain threshold. This threshold depends on the quality of all products, and can be computed in linear time in the number of products.

Research supported by NSF grants NeTS 1718203, CPS ECCS 1739189, CMMI 1562276, ECCS 16-09370, China Postdoctoral Science Foundation NO. 2018M642018.

1 Introduction

In recent years, we have witnessed the rise of many successful online platform markets, which have reshaped the economic landscape of modern world. The online platforms facilitate the exchange of goods and services between buyers and sellers. For example, buyers can purchase goods from sellers on Amazon, eBay and Etsy, arrange accommodation from hosts on Airbnb and Expedia, order transportation services from drivers on Uber and Lyft, and find qualified workers on online labor markets, such as Upwork and Taskrabbit. The total market value of online platforms has exceeded 4.3 trillion dollars worldwide, and is growing quickly [10].

Compared with traditional markets, the modern online marketplaces have greater controls over price determination, search and discovery, information revelation, recommendation, etc. For example, Uber and Lyft adopt the full control model, in which the ride-sharing platforms use online matching algorithms to determine matches between drivers and riders as well as the fee for the route. Amazon and Airbnb use the discriminatory control model, where the platforms only control the list of products to display for each buyer’s search, and the potential matches and transaction prices are determined by the preference of buyers and the competition among sellers. The platform can also use other types of control, such as commissions/subscriptions fees [7], to influence the outcomes of markets. The rich control options for online platforms have led to an increasing discussion about the design of online marketplaces with different optimization objectives [4, 5, 14].

In this paper, we investigate social welfare and revenue optimization under the discriminatory control model for online marketplaces. In the discriminatory control model, the platform has only control over search segmentation mechanisms - which products to display for each buyer’s search, and the transaction prices are endogenously determined by the competition among sellers. Unlike traditional firms, most online platforms do not manufacture goods or provide services, and thus they also do not dictate the specific transaction prices. Instead, buyers and sellers jointly determine the prices at which the goods or services will be traded. For example, sellers set prices for their goods on Amazon, hosts decide on the price for their properties on Airbnb, and freelancers negotiate employers with hourly fee on Upwork. These prices depend on the demand and supply for comparable goods and services in the market, and choosing different products to display for buyers impacts the transaction prices and then the social welfare and revenue. Motivated by this, we study the role of search segmentation mechanisms in social welfare and revenue optimization in the discriminatory control model with endogenous prices.

To calculate the social welfare and revenue, we first need to specify demand and supply in online marketplaces. Much of prior work simply represent the demand/supply curves with non-increasing/non-decreasing distributions [5, 7]. Instead, we consider a demand and supply function derived from a basic market setting in which each seller has one unit of product to offer, and each buyer demands at most one unit of product chosen from the products displayed to her¹. Given the quality and prices of products, the demand for each product is equivalent to the proportion of potential buyers that purchase such a product. Thus, the demand function is closely related to the purchase behaviors of buyers who face multiple substitutable products. We adopt the standard multinomial logit (MNL) model [16] to describe buyers’ choice behaviors, and then derive the demand as a softmax function. With such a specific demand function, we can model the competition among sellers via a Bertrand price competition game, which is a useful model for investigating oligopolistic competition in real markets [23]. For instance, the Bertrand game can model the situation where the hosts on Airbnb compete for potential guests by setting prices for their properties. The basic questions for the Bertrand competition game are existence, uniqueness, closed-form expression and learning algorithm of the equilibrium. The results in [2, 11] have shown that there exists a unique (pure) Nash equilibrium in the Bertrand game with a MNL model. Furthermore, the Nash equilibrium coincides with the solution of a system of first-order-condition equations. We can then characterize the Nash equilibrium in a “closed” form, and express the equilibrium social welfare/revenue by employing a variant of Lambert W function [8]. We also derive myopic learning strategies, i.e., best response dynamics, for sellers to reach the Nash equilibrium in practice.

The online platform can further optimize the equilibrium social welfare/revenue by employing search segmentation mechanisms. Different sets of sellers involved in the Bertrand competition game lead to different equilibrium solutions. The goal of the search segmentation mechanisms is to efficiently choose a set of products to display for buyers (or in other words, choose a set of sellers to compete in the Bertrand game) that maximizes the equilibrium social welfare or revenue. This display control optimization problem is combinatorial in nature and the number of possible product sets can be very large, particularly when there are many potential products to offer. One of our main contributions is to identify the efficient and optimal search segmentation mechanism, which turns out to have a simple structure. We show that the online platform will display all products to maximize equilibrium social welfare, but just display the top $k^*$ highest quality products to maximize equilibrium revenue. We also refer the optimal mechanism for revenue maximization as quality-order mechanism. The optimal threshold $k^*$ depends on the quality of all products, and can be calculated in linear time in terms of the number of products. The optimality of such simple search segmentation mechanisms has crucial theoretical and practical implications. On the theoretical side, this result allows the platform to find the optimal set of displayed products in linear time, significantly reducing the computational complexity. On the practical side, optimality of quality-order mechanism is quite appealing as it guarantees that a lower quality product will not be chosen for display over a higher quality product. Moreover, in order to increase the opportunity of being selected, sellers would improve the quality of their products as product quality is the selection criteria of the optimal mechanism, which will benefit all the market participants in the long term.

The optimality of the quality-order mechanism for revenue maximization is established by making a novel connection between the quasi-convexity of equilibrium revenue function and the optimal control decision on selecting displayed products. We show that in the Bertrand game with a given subset of sellers, the equilibrium revenue can be expressed as a quasi-convex function with respective to an independent variable, which is a one-to-one transformation of the quality of a candidate product. The property of quasi-convexity guarantees that the maximum revenue can be obtained at one of the two endpoints, which corresponds to the options of displaying the current set of products or involving a new product with the highest quality among the remaining products. With this critical observation, if the platform decides to add a new product, it will always select the available product with the highest quality. Thus, we can efficiently construct the optimal set of displayed products from any product set. Specifically, if the current product set does not contain all the top $k^*$ products, we can further improve the equilibrium revenue by repeatedly replacing one currently selected product with an unselected product with a higher quality.

Our work in this paper is related to work on the design of markets for networked platforms [1, 5, 6, 15, 19]. We present a detailed discussion of related work towards the end of the paper. Here, we briefly discuss the similarities and differences between our work and prior work on networked market platforms. In networked markets, there are buyers and sellers connected by a bipartite graph, where each link indicates that a specific buyer is allowed to buy from a specific seller. The goal is to remove links from the complete bipartite graph to maximize either social welfare or revenue. However, much of the prior work focuses on a linear price-demand curve which does not explicitly model situations where each buyer is interested in buying only one product (such as one copy of a book) and each buyer takes into account the quality of each product (available typically in the form of reviews) while making a buying decision. For such situations, economists use the MNL model, which we have adopted in this paper. On the other hand, compared to prior work on networked markets, we only consider a much simpler bipartite graph where there is only one representative buyer. Such a model is appropriate when there are no capacity constraints for products at a seller, for example, each seller may have many copies of a book and there is no danger of immediately selling out a particular book title. The model is also appropriate for hotels.com-type settings in situations when most hotels have multiple available rooms. In situations where multiple buyers are performing searches simultaneously and hotels are about to sell out of rooms, capacity constraints do matter. Such capacity-constrained situations have not been studied either in this paper or in prior work, and is a topic for future research.

We now summarize the main contributions of this paper.

• We introduce a stylized model to capture the main features of online platform markets. We explicitly model the market, where each buyer is interested in purchasing one product, and takes into account the quality of products when making choice. Specifically, the demand function for products is derived from the multinomial logit (MNL) choice model, and the supply response of sellers is described by the outcome of Bertrand competition game. We show that the Bertrand game exists a unique (pure) Nash equilibrium, and the best response dynamics converge to the equilibrium. We also explicitly express the social welfare and revenue under the equilibrium.

• We design efficient search segmentation mechanisms to optimize equilibrium social welfare and revenue under the Bertrand model of competition. We first prove that it is optimal to display all products to maximize social welfare. For revenue maximization, we then show that the optimal mechanism, referred to as quality-order mechanism, only needs to display the top $k^*$ highest quality products, where the optimal number of products $k^*$ can be found in linear time.

• We prove the result for social welfare maximization by showing the equilibrium social welfare function is decreasing with respective to an independent variable, which also decreases for involving a new product. We establish the optimality of the quality-order mechanism for revenue maximization by making a novel connection between the quasi-convexity of equilibrium revenue function and the optimal decision on selecting displayed products.

2 Preliminaries

We consider a two-sided market with n sellers $\mathbb {S}= \{1, 2, \cdots , n\}$ and one representative buyer, representing a set of homogeneous buyers. Each seller $i\in \mathbb {S}$ offers a product with quality $\theta _i$ and price $p_i$. We denote the quality and price vectors by $\varvec{\theta }=(\theta _1, \theta _2, \cdots , \theta _n)$ and $\varvec{p} = (p_1, p_2, \cdots , p_n)$, respectively. The quality vector $\varvec{\theta }$ is fixed, while the price vector $\varvec{p}$ is determined by the competition among sellers. Without loss of generality, we assume the products’ quality and prices are non-negative, i.e., $\theta _i\ge 0$ and $p_i \ge 0$, and the sellers are sorted according to the product quality in a non-decreasing order, i.e., $\theta _1 \ge \theta _2 \ge \cdots \ge \theta _n$. Given the quality $\varvec{\theta }$ and prices $\varvec{p}$ of all products, the buyer purchases one of the n products, or adopts an outside option, i.e., buys nothing from this market. We normalize the problem parameters so that outside option’s quality $\theta _0$ and price $p_0$ are zero, i.e., $\theta _0 = p_0 =0$.

In the random utility model [17], the buyer derives utility $u_i$ from purchasing the product $i\in \mathbb {S}$ or selecting the outside option $i=0$ as follows

$$\begin{aligned} u_i \triangleq \theta _i + \xi _i - p_i, \end{aligned}$$

where $\xi _i$ is a random variable representing buyer’s (private) preference about the ith alternative. Given the $n+1$ choices (n products and the outside option), the buyer selects the alternative with the maximum utility. Under the standard assumption that the random variables $\{ \xi _i \}$ are independent and identically distributed (i.i.d.) with Gumbel distribution [3, 12], it can be shown [3, 16] that the buyer selects the alternative $i\in \{0\}\cup \mathbb {S}$ with probability

$$\begin{aligned} q_i(\varvec{p}) \triangleq Pr(u_i = \max _{j\in \{0\}\cup \mathbb {S}} u_j) =\frac{a_i}{1+ \sum _{j\in \mathbb {S}} a_j}, \end{aligned}$$

(1)

where $a_i= \exp (\theta _i-p_i)$ for all $i \in \mathbb {S}$. We refer to $q_i$ as demand or market share of the alternative $i \in \{0\} \cup \mathbb {S}$. We can also interpret $q_i$ as the expected sales of quantity of product i normalized by the total number of potential buyers. This choice model is known as multinomial logit (MNL) model in economic literature [3, 12, 16]. We use $\varvec{q} = (q_0, q_1, \cdots , q_n)$ to denote the demands of products.

Under the above model, we can also obtain an explicit form for the utility $\bar{u}$ of the representative buyer

$$\begin{aligned} \bar{u} \triangleq \mathbb {E}[\max _{i\in \{0\} \cup \mathbb {S}} u_i] = \log (1+\sum _{i \in \mathbb {S}} a_i). \end{aligned}$$

From the demand $q_i(\varvec{p})$ in (1), we can express seller i’s expected revenue $r_i(\varvec{p})$ in terms of prices

$$\begin{aligned} r_i(\varvec{p}) \triangleq p_i \times q_i(\varvec{p}) = p_i \times \frac{a_i}{1+ \sum _{j\in \mathbb {S}} a_j}. \end{aligned}$$

(2)

The social welfare of the two-sided market is measured by the sum of buyer’s utility and the total revenue of sellers, i.e.,

$$\begin{aligned} sw(\varvec{p}) \triangleq \bar{u}+ \sum _{i\in \mathbb {S}} r_i(\varvec{p}) = \log (1+\sum _{j\in \mathbb {S}} a_j) + \sum _{i \in \mathbb {S}} p_i \times \frac{a_i}{1+ \sum _{j \in \mathbb {S}} a_j}. \end{aligned}$$

(3)

The revenue of the market is the total revenue of all sellers, i.e.,

$$\begin{aligned} {re}({\varvec{p}}) \triangleq \sum _{i \in \mathbb {S}} r_i({\varvec{p}}) = \sum _{i \in \mathbb {S}} p_i \times \frac{a_i}{1+ \sum _{j \in \mathbb {S}} a_j}. \end{aligned}$$

(4)

We now note the relation between price and demand in the MNL model, which would be quite useful for optimization and analysis later. Using the price-demand model in (1), we can express the price $p_i$ in terms of demands $\varvec{q}$:

$$\begin{aligned} p_i(\varvec{q}) = \theta _i + \log (1- \sum _{j \in {S}} q_j) - \log (q_i). \end{aligned}$$

(5)

The social welfare and revenue optimization would become convenient if we work with the demands $\mathbf q$ rather than the prices $\mathbf p$. For example, the social welfare and revenue functions are not concave in $\mathbf p$, but become jointly concave if we express the functions in terms of $\mathbf q$ [9, 13, 21]. We can leverage this property to derive the optimal prices for social welfare and revenue maximization in the full control model, where the platform can control both price and displayed products. We leave the detailed discussion in Appendix A of technical report [24].

3 Bertrand Competition Game

In discriminatory control model, the online platform can only control the list of products to display for buyers, and the transaction prices are endogenously determined by the oligopolistic competition among sellers. In a Bertrand competition game, the seller of each product sets a price. Based on the prices of the products and the set of available products, the market produces a certain demand for each product. In our MNL model, the demand is simply the probability with which a product will be purchased by the buyer. This is the typical situation in a Airbnb-like model, where the owner of each rental unit sets a price, the platform controls the manner in which the rental units are displayed, and the renter selects a unit to rent.

In this section, we investigate the existence and uniqueness of equilibrium in the Bertrand competition game, explicitly express the equilibrium social welfare/revenue, and derive the best response dynamics to reach the Nash equilibrium. We assume that only a subset $S \subseteq \mathbb {S}$ of sellers are involved in the game. In other words, we assume that the platform has chosen to display the products of a subset S of the sellers. In the next section, we will show how the choice of S can be optimized by the platform to maximize either social welfare or revenue.

In the Bertrand competition game, seller $i\in {S}$ selects price $p_i$ to maximize her revenue $r_i(\varvec{p})= p_i \times q_i(\varvec{p})$, where the demand $q_i(\varvec{p})$ is determined by the prices $\varvec{p}$ of all products in (1). We can formally represent the Bertrand game as a triplet $G^b=\left( {S}, (\mathcal {P}_i)_{i\in {S}}, (r_i)_{i\in {S}}\right)$, where S is a set of players, $\mathcal {P}_i$ is the strategy space of player $i\in {S}$ (i.e., $\mathcal {P}_i \triangleq \{p_i | p_i \ge 0\}$), and $r_i(\varvec{p})$ is the payoff of player $i\in {S}$. We represent the set of strategy profiles by $\mathcal {P}=\mathcal {P}_1\times \mathcal {P}_2 \times \cdots \times \mathcal {P}_n$. We also denote the strategy profile $\varvec{p}\in \mathcal {P}$ as $\varvec{p}=(p_i, \varvec{p}_{-i})$, where $\varvec{p}_{-i}$ is the strategies (or prices) of all the players except i. For such Bertrand game, we have the following result from [11].

Theorem 1

There exists a unique (pure) Nash equilibrium in the Bertrand game $G^b=\left( {S}, (\mathcal {P}_i)_{i\in {S}}, (r_i)_{i\in {S}}\right)$. A vector of prices $\varvec{\bar{p}}=(\bar{p}_1,\bar{p}_2, \cdots , \bar{p}_n) \in \mathcal {P}$ satisfies $\partial r_i(\varvec{\bar{p}})/ \partial p_i =0$ for all $i\in {S}$ if and only if $\varvec{\bar{p}}$ is a Nash equilibrium in $\mathcal {P}$.

We next calculate a closed-form expression for the Nash equilibrium prices $\varvec{\bar{p}}$. For each seller $i\in {S}$, by the first-order condition $\partial r_i(\varvec{\bar{p}})/ \partial p_i =0$, we have the following relation for $\bar{p}_i$:

$$\begin{aligned} \bar{p}_i = \frac{1+ \sum _{j\in S} \bar{a}_j}{1+ \sum _{j\in S} \bar{a}_j -\bar{a}_i} =\frac{1}{1-\bar{q}_i}, \end{aligned}$$

(6)

where $\bar{a}_i \triangleq \exp (\theta _i-\bar{p}_i)$ and $\bar{q}_i$ is the demand of product i at the equilibrium, i.e., $\bar{q}_i \triangleq {\bar{a}_i}/(1+ \sum _{j \in {S}} \bar{a}_j)$. From the price function in (5) and with some calculations applied to (6), we have the following equations

$$\begin{aligned} \bar{q}_0 \times \exp (\theta _i-1) = \bar{q}_i \times \exp (\frac{\bar{q}_i}{1-\bar{q}_i}), \quad \forall i\in {S}, \end{aligned}$$

(7)

where $\bar{q}_0 \triangleq 1-\sum _{j \in {S}} \bar{q}_j$ is the probability of the buyer that purchases nothing. We introduce a function $V(x): (0, +\infty ) \rightarrow (0,1)$, such that for any $x\in (0, \infty )$, V(x) is the solution $v\in (0,1)$ satisfying

$$\begin{aligned} v\times \exp (\frac{v}{1-v}) = x. \end{aligned}$$

(8)

We can verify that V(x) is a strictly increasing and concave function over $[0,+\infty )$. This function is similar to the Lambert function W(x) [8], which is the solution w satisfying $w\times exp(w) = x$. With the function V(x) and (7), we can obtain a closed-form expression for the demand $\bar{q}_i = V(\bar{q}_0\times \exp (\theta _i-1)).$ Combing with the definition of $\bar{q}_0$, we can determine $\bar{q}_0$ by solving the following single-variable equation

$$\begin{aligned} \sum _{i \in {S}} V(\bar{q}_0 \times \exp (\theta _i-1)) = 1- \bar{q}_0. \end{aligned}$$

(9)

This equation has a unique solution because V(x) is a strictly increasing function. We also refer this equation as the equilibrium constraint. The next theorem presents a closed-form expression for the Nash equilibrium solution in the Bertrand competition game.

Theorem 2

In the Bertrand game $G^b=\left( {S}, (\mathcal {P}_i)_{i\in {S}}, (r_i)_{i\in {S}}\right)$, the Nash equilibrium price $\bar{p}_i$ and the demand $\bar{q}_i$ for each product $i\in {S}$ are given by

$$ \bar{p}_i = \frac{1}{1-V(\bar{q}_0\times \exp (\theta _i-1))} \quad \text {and} \quad \bar{q}_i = V(\bar{q}_0\times \exp (\theta _i-1)), $$

where $\bar{q}_0$ is the unique solution to (9).

Substituting the equilibrium solutions into (3), we obtain the equilibrium social welfare in the Bertrand game with the sellers $S\subseteq \mathbb {S}$

$$\begin{aligned} \overline{sw}(S)= -\log \left( \bar{q}_0 \right) + \sum _{i \in {S}} \frac{\bar{q}_i }{1-\bar{q}_i}. \end{aligned}$$

(10)

By (4), we can similarly get the equilibrium revenue in the Bertrand game with the set of sellers $S\subseteq \mathbb {S}$

$$\begin{aligned} \overline{re}(S) = \sum _{i \in {S}} \frac{\bar{q}_i }{1-\bar{q}_i}. \end{aligned}$$

(11)

Instead of directly deriving the equilibrium strategies in one single step, in practice, the sellers may employ some simple, natural and myopic learning algorithms, such as best response, fictitious play or no-regret learning algorithm, to interact with each other and eventually reach the equilibrium. One straightforward procedure for sellers in online platform markets to reach the Nash equilibrium is best response dynamics. Specifically, suppose that the current vector of price $\mathbf p$ is not a Nash equilibrium, and a seller $i \in S$ deviates by setting a new $p^*_i$, which is the optimal price with respective to the other prices $\mathbf p _{-i}$, i.e.,

$$ p^*_i = B(\mathbf p _{-i}) \triangleq \mathop {\mathrm {arg}\,\mathrm {max}}\limits _{p\in [0,+\infty )} r_i(p, \mathbf p _{-i}). $$

We can verify that the revenue function $r_i(p, \mathbf p _{-i})$ is strictly quasi-concave in p, and thus it is not easy to explicitly solve the above optimization problem. One key observation is that the revenue function is strictly concave in the domain of the demand, which enables us to obtain closed-form expressions for the best response strategies, as shown in the following lemma.

Lemma 1

The best response price $p^*_i$ with respective to a fixed price vector $\mathbf p _{-i}$ can be calculated as

$$ p^*_i = \theta _i - log((1+\sum _{j\in S \backslash \{i\}} a_j) \times W(\frac{exp(\theta _i -1) }{1+\sum _{j\in S \backslash \{i\}} a_j}) ), $$

where W(x) is the Lambert function and $a_j = exp(\theta _j-p_j)$ for all $j\in S$.

The proof of Lemma 1 is in Appendix B of technical report [24]. We further have the following result for such best response dynamics in the Bertrand game.

Lemma 2

From an arbitrary price vector $\mathbf p$, the best response dynamics converge to the Nash equilibrium of the Bertrand game in a finite number of steps.

The basic idea to derive this result is to show the Bertrand game is an ordinal potential game [18] with a finite value; the detailed proof of Lemma 2 is in Appendix C of technical report [24].

4 Optimal Segmenting Mechanisms

In online marketplaces, the platform has control over search segmentation mechanisms - which set of products to display for a buyer. The platform can display any set of products, and the competition among selected sellers then takes place endogenously through the Bertrand game in Sect. 3. The goal of the platform is to decide the optimal products $S^* \subseteq \mathbb {S}$ to display, in order to maximize the equilibrium social welfare/revenue. For n potential products in the market, there are $2^n-1$ possible sets of products, thus an exhaustive search to determine the optimal set of displayed products is infeasible. We also note that the equilibrium constraint (9) imposed by the Bertrand competition game is highly nonlinear, which presents another challenge in deriving the optimal search segmentation mechanisms. In this section, we exploit the structure of social welfare/revenue functions to efficiently design the optimal search segmentation mechanisms.

4.1 Social Welfare Maximization

In the following theorem, we show the online platform would display all products to maximize social welfare.

Theorem 3

For social welfare maximization, the optimal search segmentation mechanism is to display all products $\mathbb {S}$ in the platform.

Proof

We prove this theorem by showing that adding a new product will always improve the equilibrium social welfare. Suppose the platform has already selected sellers $S \subset \mathbb {S}$, and consider introducing a new product $j \in \mathbb {S} \backslash S$. According to (10), we can express the equilibrium social welfare $\overline{sw}$ as

$$\begin{aligned} \overline{sw} = -\log {\bar{q}_0} +\sum _{i\in S} \frac{\bar{q}_i}{1-\bar{q}_i} + \frac{x_j\times \bar{q}_j}{1-x_j \times \bar{q}_j}. \end{aligned}$$

(12)

Here, $\bar{q}_i$ is a function of $q_0$, i.e., $\bar{q}_i = V(\bar{q}_0 \times \exp (\theta _i -1))$ and $x_j$ is an indicator for product $j\in \mathbb {S}\backslash S$, where $x_j=1$ denotes product j is selected for display; otherwise $x_j=0$. It is difficult to directly compare $\overline{sw}$ with $x_j=1$ and the one with $x_j=0$. From (9), the demands ${\varvec{q}}$ satisfy the equilibrium constraint:

$$\begin{aligned} 1-\bar{q}_0 =\sum _{i\in {S}} \bar{q}_i + x_j \times \bar{q}_j = \sum _{i\in {S}} V(\bar{q}_0 \exp (\theta _i -1)) +x_j \times V(\bar{q}_0 \exp (\theta _j -1)). \end{aligned}$$

(13)

Since V(x) is an increasing function, we can observe from the above equation that $\bar{q}_0$ decreases when $x_j$ changes from 0 to 1. Furthermore, with (12) and (13), we can express the equilibrium social welfare as a function of $\bar{q}_0$:

$$\begin{aligned} \overline{sw}(\bar{q}_0) = -\log {\bar{q}_0} +\sum _{i\in S} \frac{\bar{q}_i}{1-\bar{q}_i} + \frac{1-\bar{q}_0 - \sum _{i\in S} \bar{q}_i }{ \bar{q}_0+\sum _{i\in S} \bar{q}_i}. \end{aligned}$$

(14)

Thus, we only need to prove $\overline{sw}(\bar{q}_0)$ is a decreasing function. The basic idea is to explicitly calculate the first derivative of $\overline{sw}(\bar{q}_0)$, and show $\overline{sw}'(\bar{q}_0)<0$. We put the detailed proof of the following lemma in Appendix D of technical report [24].

Lemma 3

The social welfare $\overline{sw}(\bar{q}_0)$ is a decreasing function.

From this lemma and the above discussion, we can always improve the equilibrium social welfare by adding a new product, which completes the proof.    $\square$

4.2 Revenue Maximization

The optimal search segmentation mechanism with the objective of revenue maximization is different from the optimal mechanism when the platform attempts to maximize social welfare. To illustrate this difference, we consider two cases: a low quality case, e.g., $\theta _1 =\theta _2 = \cdots =\theta _n = 0.5$, and a high quality case, e.g., $\theta _1=\theta _2 = \cdots =\theta _n = 10$. From the result in Theorem 3, the optimal mechanisms for social welfare maximization in these two cases are to display all products. However, for revenue maximization, it can be verified that the platform still displays all products in the low quality case, but only selects the first product in the high quality case. The intuition behind this difference is that in some scenarios, the platform can further improve price and then revenue by reducing the competition among sellers. We next show the design rationale for the optimal search segmentation mechanisms for the revenue maximization.

One critical decision the platform has to make is the following: given a set of products $S\subset \mathbb {S}$, whether to just display the currently selected product set S, or add a new product j from $\mathbb {S} \backslash S$. We refer to such a decision problem as the “incremental” problem. Similar to the discussion on social welfare maximization, given a set of selected products $S\subset \mathbb {S}$, we can represent the equilibrium revenue under these two decision options with the following function:

$$\begin{aligned} \overline{re} = \sum _{i\in S}\frac{\bar{q}_i}{1-\bar{q}_i} + \frac{x_j \times \bar{q}_j}{1-x_j \times \bar{q}_j}. \end{aligned}$$

(15)

We recall that $x_j$ is an indicator for product $j\in \mathbb {S}\backslash S$, where $x_j=1$ indicates that product j is selected for display; otherwise $x_j=0$. The demands $\bar{q}_i$’s need to satisfy the following equilibrium constraint:

$$\begin{aligned} 1-\bar{q}_0 = \sum _{i\in S} \bar{q}_i+x_j \times \bar{q}_j = \sum _{i\in S} \bar{q}_i +x_j \times V(\bar{q}_0 \times \exp (\theta _j-1)) . \end{aligned}$$

(16)

Since V(x) is an increasing function, we have a critical observation from (16): given a selected product set S, the quality $\theta _j$ of the potential product $j \in \mathbb {S}\backslash S$ has a one-to-one and inverse relation with the demand $\bar{q}_0$, i.e., when $x_j=1$, involving the product with a higher quality $\theta _j$ leads to the lower value of $q_0$. With this observation, we can derive the feasible range of the independent value $\bar{q}_0$. On the one hand, when the platform selects the available product with the highest quality, i.e., the product $j\in \mathbb {S} \backslash S$ with $\theta _j \ge \theta _{j'}$ for all $j'\in \mathbb {S} \backslash S$, the demand $\bar{q}_0$ achieves its lower bound at $\bar{q}_0^{min}$. On the other hand, setting $x_j$ to 0 represent the case that the platform does not select any new product, and the corresponding demand $\bar{q}_0^{max}$ in this case is the upper bound of $\bar{q}_0$. Thus, we have $\bar{q}_0 \in \left[ \bar{q}_0^{min}, \bar{q}_0^{max} \right]$ for the decision on selecting different product $j \in \mathbb {S}\backslash S$.

Using Eq. (16), we can replace $x_j \times \bar{q}_j$ with $1-\bar{q}_0 -\sum _{i\in S} \bar{q}_i$ in (15) to express the equilibrium revenue as a function of $\bar{q}_0$:

$$\begin{aligned} \overline{re}(\bar{q}_0) =\sum _{i\in S}\frac{\bar{q}_i}{1-\bar{q}_i} + \frac{1}{\bar{q}_0+ \sum _{i\in S} \bar{q}_i } -1. \end{aligned}$$

(17)

Fig. 1.

$\overline{re}(\bar{q}_0)$ is a quasi-convex revenue function for the possible product set to display when the product 1 has been selected. $\overline{re}(\bar{q}^{min}_0)$ is the revenue obtained by displaying $S^*= \{1,2\}$, $\overline{re}(\bar{q}^{middle}_0)$ is the revenue from showing $S^*= \{1,n\}$, and $\overline{re}(\bar{q}^{max}_0)$ is the revenue of displaying $S^*= \{1\}$.

Such revenue function indeed captures the equilibrium revenue of making different decisions in the “incremental problem”. Specifically, adding a new product $j\in \mathbb {S} \backslash S$ (i.e., $x_j=1$) or do not add anything (i.e., $x_j=0$ for all $j\in \mathbb {S} \backslash S$) can obtain different values $\bar{q}_0$ calculated by (16), and then $\overline{re}(\bar{q}_0)$ from (17) is the corresponding equilibrium revenue. The property of the revenue function in (17), especially the quasi-convexity, is a key step to derive the optimal search segmentation mechanisms for revenue maximization.

Based on the above discussion, we show that the optimal search segmentation mechanism is to choose the $k^*$ products with the best quality, for an appropriate value of $k^*$, using the following steps:

• First, we show that one should always display the product with the best quality to maximize revenue (Lemma 4).

• Then, we consider the decision of adding one product to display. As discussed previously, we show that $re(q_0)$ is quasi-concave in $q_0$ which implies that the optimal decision is to add the next highest quality product or to not add a product at all, as illustrated in Fig. 1. The quasi-convexity of $re(q_0)$ is shown in Lemma 5 under a certain condition. Using the quasi-convexity of $re(q_0)$, in Lemma 6, we prove that if the optimal display set consists of $k^*$ products, then one should select the top $k^*$ products in terms of quality.

• The final step is to find the optimal $k^*$. This can be done by the following calculation. For each possible value of $k^* \in \{2, \cdots , n\}$, we select the top $k^*$ products and calculate the revenue. We choose $k^*$ to maximize this revenue. This is clearly a linear-time algorithm in n, since one has to add one term to the expression for the revenue when we increase $k^*$ by one. This result is summarized in Theorem 4.

We first show that revenue maximization implies that the highest quality product is always selected for display.

Lemma 4

For revenue maximization, it is optimal to always display the product with the highest quality.

The intuition behind the proof is to show that for any displayed product set, the revenue function in (17) increases with the quality of the product with the highest quality in this set. The proof is in Appendix E of technical report [24].

Lemma 4 implies that when the optimal search segmentation mechanism is to display one product, i.e., $k^*=1$, the platform will choose the first product. To obtain the result for the general case with $k^*\ge 2$, we need to establish the quasi-convexity of the revenue function in (17). It is non-trivial to directly verify this property because the first term in the revenue function, i.e., $\sum _{i\in S}\frac{\bar{q}_i}{1-\bar{q}_i}$, is increasing and concave with respective to $q_0$, while the remaining term $\frac{1}{\bar{q}_0+ \sum _{i\in S} \bar{q}_i } -1$ is decreasing and convex. We first prove the desired quasi-convexity by assuming all demands $\bar{q}_i$’s are less than 0.5, i.e., $q_1<0.5$, due to $q_i \le q_1$ for $i \in S$, meaning that no seller dominates the market. This assumption simplifies the analysis, but still preserves the major intuition. Our results also hold without this assumption, as shown in Appendix H of technical report [24].

Lemma 5

For any selected product set S, the revenue function $\overline{re}(\bar{q}_0)$ in (17) is quasi-convex in the range $\left[ \bar{q}^{min}_0, \bar{q}^{max}_0\right]$, under the assumption of $q_1<0.5$.

The basic idea to prove this result is to check the second-order conditions of a quasi-convex function, i.e., at any point with zero slope, the second derivative is non-negative, i.e., $\overline{re}'(\bar{q}_0) = 0 \Rightarrow \overline{re}''(\bar{q}_0) > 0$. The details are in Appendix F of technical report [24]. Equipped with Lemma 5, we can derive the optimal search mechanism for the case with $k^*\ge 2$.

Lemma 6

For revenue maximization, the optimal search segmentation mechanism is to display the top $k^*$ products if the cardinality of the optimal product set is $k^*\ge 2$, under the assumption of $q_1< 0.5$.

The optimality of the top $k^*$ mechanism in this lemma can be established by showing that replacing any product with a product of higher quality will increase the revenue (see Appendix G in technical report [24] for the proof).

While the specific value of $k^*$ depends on the quality of all products ${\varvec{\theta }}$, The platform can find the optimal $k^*$ in linear time by computing the revenue of each set with the top $k\in [1,n]$ products, and selecting the one with the maximum revenue. Thus, from Lemmas 4 and 6, we obtain the main result for the case of revenue maximization.

Theorem 4

For revenue maximization, the optimal search segmentation mechanism is to display the top $k^*$ products, where $k^*$ is determined by the quality of all products ${\varvec{\theta }}$, and can be calculated in linear time.

5 Related Work

Our work is related to the burgeoning literature that studies online platform marketplaces of using control levels other than pricing to influence the market outcomes [4, 5, 7, 14]. Kanoria and Saban designed a framework to facilitate the search for buyers and sellers on matching platforms, and found that simple restrictions on what buyers/sellers can access would boost social welfare [14]. Arnosti et al. investigated the welfare loss due to the uncertainty about seller availability in asynchronous dynamic matching markets, and also found that limiting the visibility of sellers can improve social welfare [4]. Our result, displaying only a subset of products to buyers can increase the equilibrium revenue, extends the findings in these two pieces of work to the context of revenue optimization. Banerjee et al. studied how the platform should control which sellers and buyers are visible to each other, and provided polynomial-time approximation algorithms to optimize social welfare and throughput [5]. In their model, supply and demand are associated with public distributions. By contrast, we adopt the MNL model to derive a specific demand system, and use the Bertrand game to capture supply response to this demand system, doing so leads to very different optimization problems.

Revenue management under general demand model has been extensively studied in economics, marketing and operation management [9, 20,21,22]. The model considered in this paper is closely related to that in assortment optimization, which is an active area in revenue management research. For assortment optimization, the demand of products are governed by the variants of attraction-based choice models [3], e.g., MNL model, mixed nested logit model and nested logit model, and each product is associated with a fixed price. The objective is to find a set of products, or an assortment to offer that maximizes the expected revenue. In [22], Talluri and van Ryzin studied the assortment optimization problem under the MNL model, and showed that the optimal assortment includes a certain number of products with the highest prices. We also derive a similar result, but use the criteria of quality rather than price to rank the potential products. In our setting a key difference from this line of work is that the product prices are determined endogenously by the outcome of oligopolistic competition games instead of being given beforehand. Pricing multiple differentiated products in the context of the MNL model is another fairly active direction [9, 13, 21]. In this setting, all products are displayed, and the objective is to choose pries of products to maximize revenue. In contrast, we focus on search segmentation mechanisms with endogenous prices, where the platform only controls the set of displayed products, to optimize the equilibrium social welfare/revenue.

6 Conclusion

In this paper, we have studied the problems of social welfare maximization and revenue maximization in designing search space for online platform markets. In the discriminatory control model, the platform can only control the search segmentation mechanisms, i.e., determine the list of products to display for buyers, and the products’ prices are determined endogenously by the competition among sellers. Under the standard buyer choice model, namely the multinomial logit mode, we have developed efficient and optimal search segmentation mechanisms to maximize the equilibrium social welfare and revenue under Bertrand competition game. For social welfare maximization, it is optimal to display all the products. For revenue maximization, the optimal search mechanism, referred as quality-order mechanism, is to display the top $k^*$ highest quality products, where $k^*$ can be computed in at most linear time in the number of products.