Papers for

marketplace designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Stable marriage matching algorithm runs in single-exponential time

A Single-Exponential Time Algorithm for the Maximum-Cardinality Weakly Stable Matching Problem with Ties and Incomplete Lists

Abstract: We study Stable Marriage with Ties and Incomplete lists (SMTI) under weak stability. For an instance with $n$ agents on each side, we give an exact algorithm that returns a maximum-cardinality weakly stable matching in $O^*(22.74^n)$ time. To the best of our knowledge, this is the first exact algorithm for this problem running in single-exponential time.

Thu 29 OctData Structures and Algorithms
The gist
This work addresses the problem of matching two groups of people, like men and women, where not everyone lists all possible partners and where ties in preferences may occur. The researchers developed an exact algorithm to find the largest set of matches that are stable under weak stability rules, meaning no pair wants to deviate given the ties. Importantly, their method runs in single-exponential time, which improves the efficiency over previous approaches for this problem.
Open → 2610.39764v1

Positive values do not guarantee efficient fair divisions of goods

Pareto Inefficiency of EFX

Abstract: We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX) and Pareto optimality. While some of the earliest work on EFX showed that Pareto optimal EFX allocations may not exist if agents can have zero value for some goods, it has remained open whether the same is true when all values are positive. We present a simple instance in which every good has positive value to every agent, but no Pareto optimal EFX allocation exists. We then generalize to a family of instances showing that Pareto optimal $α$-EFX allocations may not exist for any $α> 2/3$.

Wed 21 OctComputer Science and Game Theory
The gist
Dividing items fairly among people is tricky, especially when trying to be both fair and efficient. The authors show that even if everyone values every item positively, it’s still impossible to divide goods so that no one envies another’s share after removing any one item, while also making sure no one can be made better off without making someone else worse off. They also find that even relaxed versions of fairness may fail to coexist with maximum efficiency. This highlights limits in balancing fairness and efficiency in dividing goods.
Open → 2610.29201v1

Platforms optimize server growth and payment to balance demand

A Stochastic Growth Model for Online Platforms

Abstract: We investigate the growth trajectory of online platforms operating as market makers in two-sided matching markets. Their expansion, often referred to as the ``chicken-and-egg dilemma'' in the literature, poses an inherent challenge: service providers find value in joining the platform because of the presence of customers, while customers are drawn to the platform by the availability of service providers. Much of the existing literature addresses this expansion challenge through either a static market-clearing lens or aggregate dynamic models, emphasizing how network externalities shape a platform's growth trajectory and equilibrium size. These approaches do not fully capture how gradual growth must be implemented through server-level admission, assignment, and compensation decisions. Embedded in this growth process are intertemporal participation constraints that the platform must satisfy to attract and retain forward-looking servers. To explicitly account for the stochastic dynamics of a platform's gradual growth, we model the system as a Markov process. Potential servers and customers arrive according to Poisson processes, and customer demand is non-decreasing in the number of active servers. Under mild conditions, we characterize the platform's optimal admission, assignment, and compensation policies. The platform admits servers at the maximum feasible rate until it reaches an endogenous target size, which can be smaller than the static market-clearing optimum. In the baseline model, seniority-based compensation acts as an operational substitute for financially subsidized growth: instead of using upfront subsidies to induce early server participation, the platform uses future cash flows to reward early servers for joining when demand is limited and for helping the platform reach later, higher-demand states.

Mon 12 OctComputer Science and Game Theory
The gist
Online platforms that connect service providers with customers face a tricky problem: providers want customers to join first, while customers want many providers available. The authors look at how these platforms gradually grow over time, making decisions on who to let in and how to pay them. They show that platforms admit new providers steadily until a certain target size, which might be smaller than what a simple static model predicts. Instead of paying providers upfront, platforms reward early participants over time to keep them engaged as demand grows.
Open → 2610.17443v1