Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms

Overview

• Addresses the challenge of choice congestion in matching markets
• Introduces a two-sided assortment optimization framework to maximize the expected number of matches
• Identifies different classes of policies platforms can use in their design
• Measures the value of one policy class over another using the concept of "adaptivity gap"
• Approximates the optimization problem for different policy classes

Plain English Explanation

Matching markets, such as dating apps or job platforms, often face a challenge known as "choice congestion." This means that users can become overwhelmed by the sheer number of options presented to them, making it difficult to find the best match.

To address this, the researchers proposed a framework that allows platforms to optimize the assortment of options shown to users on both sides of the market. The goal is to maximize the expected number of successful matches by carefully curating the options and the order in which they are presented.

The researchers identified different strategies, or "policy classes," that platforms could use to display the assortments. They then explored the relative value of these policies by measuring the "adaptivity gap" - the worst-case ratio between the optimal values of two different policy classes.

Their findings suggest that policies that adaptively show assortments to one side of the market first perform significantly better than those that show assortments to all users at once. They also found that fully adaptive policies, which show assortments to users one by one, provide an additional boost in performance compared to the one-sided adaptive policies.

The researchers then developed approximate solutions to the optimization problem for different policy classes, allowing platforms to implement these strategies more effectively.

Technical Explanation

The paper presents a two-sided assortment optimization framework to address the choice congestion problem in matching markets. The goal is to maximize the expected number of matches by deciding which assortments to display to the agents and the order in which they are shown.

The researchers identify several classes of policies that platforms can use in their design:

1. Static one-sided policies: Assortments are shown to one side of the market first.
2. Adaptive one-sided policies: Assortments are adaptively shown to one side of the market first.
3. Fully adaptive policies: Assortments are shown to agents one by one.
4. Simultaneous policies: Assortments are shown to all agents at once.

To measure the value of one policy class over another, the authors define the "adaptivity gap" as the worst-case ratio between the optimal values of two different policy classes. They show that the gap between the static one-sided and adaptive one-sided policies is $1-1/e$, and the gap between the adaptive one-sided and fully adaptive policies is $1/2$. They also demonstrate that the simultaneous policies have an arbitrarily small adaptivity gap compared to the one-sided static policies.

For the optimization problem, the researchers first present a polynomial-time policy that achieves a $1/4$ approximation factor within the class of fully adaptive policies. They then show that, under the multinomial-logit choice model, a 0.066 approximation factor can be obtained within the class of simultaneous policies.

Critical Analysis

The paper provides a comprehensive framework for addressing the choice congestion problem in matching markets, and the insights on the adaptivity gap between different policy classes are particularly valuable. However, the research does have some limitations:

1. The analysis assumes that the platform has full knowledge of the agents' preferences, which may not be realistic in practice. Further research could explore how these policies perform under uncertainty or partial information about preferences.

2. The paper focuses on maximizing the expected number of matches, but other objectives, such as user satisfaction or platform revenue, could also be important considerations for platform design.

3. The approximation algorithms presented are theoretical in nature and may face challenges in real-world implementation. Additional research is needed to understand how these policies perform in practical settings.

4. The multinomial-logit choice model, while widely used, may not capture all the complexities of user decision-making in matching markets. Exploring alternative choice models could lead to additional insights.

Overall, the paper provides a solid foundation for understanding the trade-offs and optimizations in matching market design, but further research is needed to address the practical challenges and extend the framework to consider a broader range of objectives and constraints.

Conclusion

The paper introduces a novel two-sided assortment optimization framework to address the choice congestion problem in matching markets. By identifying different policy classes and analyzing their relative performance using the concept of adaptivity gap, the researchers offer valuable insights for platform design.

The approximation algorithms developed provide a starting point for platforms to implement more effective matching strategies, potentially leading to improved user experiences and higher matching rates. While the research has some limitations, it represents an important step forward in understanding and optimizing the complex dynamics of matching markets.