Papers for

marketplace platform developers

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.

One sided matching achieves sublinear metric distortion with new method

Sublinear Metric Distortion for Matching

Abstract: We study metric distortion in one-sided matching. Given $n$ agents and $n$ items in an unknown metric space, our goal is to match agents to items so that the total distance between matched pairs is small. However, instead of direct access to the distances in the metric, we are only given each agent's ranking of the items by distance. What is the smallest worst-case approximation factor (called the distortion) that a mechanism can guarantee in expectation? Despite significant interest over the last decade, the best-known guarantee has been the $O(n)$ distortion of Random Serial Dictatorship since the beginning. We give a matching mechanism with distortion $O(n^{\log_4 3})$, the first sublinear upper bound. The key idea is to use a partial matching derived from a truncated version of either Random Serial Dictatorship or the Probabilistic Serial rule. We then complete this matching using a new, general-purpose cluster completion algorithm that ensures unmatched agents receive nearby items. Along the way, we pin down the optimal distortion of Random Serial Dictatorship and Probabilistic Serial up to logarithmic and constant factors, respectively, and give improved lower bounds for truthful mechanisms.

Wed 4 NovComputer Science and Game TheoryDiscrete MathematicsData Structures and Algorithms
The gist
Matching people to items based on how close they are is hard when only orderings of preferences are known, not exact distances. Previous methods guaranteed a total distance within a factor proportional to the number of people, which can be very large. The authors introduce a new matching method that improves this to grow slower than the number of agents, the first time this has been done. Their approach cleverly combines partial pickings with a clustering technique to ensure unmatched people get nearby items. They also clarify how well commonly used methods perform and give limits on truthful methods.
Open → 2611.05777v1

Algorithms improve fairness in dividing items with complex preferences

Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations

Abstract: We study two fairness objectives for allocating $m$ indivisible items among $n$ agents with subadditive valuations: the max-min objective, also known as the Santa Claus problem, which maximizes the smallest value of an agent, and the weighted Nash social welfare, which maximizes the weighted geometric mean of the agents' values. For the max-min allocation problem, we give a randomized polynomial-time $O(\sqrt n)$-approximation algorithm for subadditive valuations with demand queries, improving the $2n-1$ bound of Khot and Ponnuswami. For additive valuations and for submodular valuations with value queries, we give simpler $O(\sqrt n)$-approximation algorithms. For additive valuations, this improves the $O(\sqrt{n\log n})$ bound of Saha and Srinivasan. For these two classes, $O(m^\varepsilon)$-approximation algorithms are also known for every constant $\varepsilon>0$. Our ratios depend only on $n$ and match, up to constants, the $Ω(\sqrt n)$ integrality gap of the configuration LP. For the weighted Nash social welfare problem with subadditive valuations and demand queries, we give an $O(Γ(w))$-approximation algorithm, where $Γ(w)=\exp\bigl((\ln n-H(w))/2\bigr)$ and $H(w)$ is the entropy of the weight vector $w$. The factor $Γ(w)$ equals $1$ for equal weights and is at most $\sqrt n$ for all weights. We show that this ratio is tight for algorithms analyzed against the configuration LP: for every weight vector, the configuration LP has an integrality gap of $Θ(Γ(w))$, even for XOS valuations, and this gap is $Ω(\sqrt n)$ when one agent has almost all the weight. For submodular valuations, the configuration LP has a constant integrality gap for all weights.

Tue 3 NovData Structures and Algorithms
The gist
The paper studies how to fairly divide a set of items among people who value combinations differently. It focuses on two fairness goals: making the least happy person as happy as possible and balancing happiness across people with different weights. The authors develop new algorithms that give better guarantees on how fair the division can be, especially when people's preferences are complex but satisfy certain mathematical properties. They also show limits on how well any algorithm can do based on known mathematical models.
Open → 2611.05229v1

Reinforcement learning trains language model sellers in multi-product markets

Learning to Sell: Reinforcement Learning for Strategic Large Language Model Agents in Multi-Product Markets

Abstract: Autonomous large language model (LLM) agents operating in multi-product markets must make sequential decisions under information asymmetry and resource constraints. We develop a machine learning approach for training such agents to act effectively as sellers in a multi-item bargaining environment, where a seller concurrently negotiates a catalog of substitutable assets across a pool of independent buyers. Buyers hold private, heterogeneous valuations across products, and each can purchase at most one item. Facing limits on total communication turns, the seller must dynamically match buyers with the most profitable products considering their private valuations, while strategically allocating its limited interaction budget toward combinations of greater potential value. We formalize this problem as a Partially Observable Markov Decision Process using a structured, four-part message protocol that maps natural language into a parsable and regulated decision space. Using this formalization, we design a post-training method using Reinforcement Learning from Verifiable Rewards (RLVR). To evaluate this framework, we construct a multidimensional metric suite that quantifies constraint adherence, seller surplus extraction, and allocation quality. Our trained seller agent learns to match limited inventory to buyers more effectively, matching or outperforming trillion-parameter frontier models in both seller surplus extraction and buyer-product allocation quality. Finally, these learned strategies generalize robustly to unseen market structures, correlated valuation distributions, and price ranges not encountered during training.

Sun 27 SeptArtificial Intelligence
The gist
Selling many items to different buyers can be tricky because buyers value items differently, and sellers have limited time to talk. This paper shows how to train large language model agents to be better sellers by teaching them to match buyers with the most profitable items and wisely use their limited negotiation turns. The method turns the selling process into a decision problem and uses reinforcement learning based on clear rewards. Their trained agents perform as well as or better than huge models at making money and allocating products. These strategies also work well in new, different market situations not seen before.
Open → 2609.33289v1

Private algorithms improve fair division of indivisible goods

Differentially Private Multicolor Discrepancy and Fair Division of Indivisible Goods

Abstract: We study the fair division of indivisible goods under pure differential privacy, continuing the line of work initiated by Manurangsi and Suksompong. For $n$ agents with nonnegative additive utilities over $m$ goods and a fixed privacy parameter, we give an entry-private algorithm that, with high probability, achieves consensus envy-freeness up to $O(\sqrt n+\log^3 m)$ goods. This substantially improves the dependence on $n$ over the previous $O(n\log m)$ guarantee for ordinary envy-freeness, while providing the stronger consensus guarantee. A key ingredient is a private algorithm for multicolor discrepancy, which may be of independent interest. Our algorithm may require exponential time. We also obtain substantially stronger guarantees under additional structure: when all item values belong to a public alphabet of size $D$, we give a polynomial-time entry-private algorithm achieving ordinary envy-freeness up to $O(\operatorname{polylog}(mD))$ goods with high probability. Finally, we prove an $Ω(\log n)$ lower bound on the number of goods that must be removed to achieve ordinary envy-freeness under entry privacy, for sufficiently many goods, even with binary utilities.

Mon 14 SeptComputer Science and Game Theory
The gist
Fairly dividing items among people is hard when the items can’t be split and privacy about preferences is important. The authors study how to do this division so that people mostly feel things are fair, while protecting their private preferences. They improve previous methods by reducing how many items need to be ignored for fairness when keeping privacy. They also show faster methods if item values come from a small set, and prove some limits on how fair you can get while being private.
Open → 2609.15372v1