CS Paper Radar

A Weakly Group Strategy-Proof and Pareto-Stable Matching Mechanism with Two-Sided Indifferences under Gross Substitutes

Yasushi Kawase, Ryosuke Sato

cs.GT econ.TH ·submitted 2026-10-22 06:32 UTC · v1

Abstract

We study finite many-to-one matching markets with indifferences on both sides and publicly known firm preferences over sets of workers. A standard approach breaks ties uniformly at random and runs deferred acceptance, which is strategy-proof for workers but may select a weakly stable matching that is Pareto dominated under the agents' original preferences. For the broad class of markets in which each firm's preferences admit a gross substitutes (GS) representation, we construct a deterministic generalized deferred acceptance mechanism that is weakly stable, Pareto efficient with respect to both sides, worker weakly group strategy-proof, and implementable in strongly polynomial time given value oracles for the GS representations. This domain includes nonresponsive firm preferences, such as additive scores under matroid constraints and assignment values. Our analysis bridges ordinal matching with indifferences and competitive equilibria under imperfectly transferable utility. Although the mechanism uses only ordinal comparisons, it returns a seller-optimal equilibrium matching of a tiered auxiliary market, and the equilibrium structure of this market yields the stability, efficiency, and incentive guarantees.

Closest papers

Nearest neighbours by meaning across the whole index.

Computing Stable Matchings under Complementarities and Preference Misalignment

cs.GT ·2026-10-05 ·Tatsuya Iwase, Baharak Rastegari, Sebastian Stein, Enrico H. Gerding
similarity 0.72
Abstract

We study many-to-one, two-sided stable matching problems in which preferences are complementary and firms and workers may rank the same allocation differently. Here a coalition is a group of workers that can be jointly matched with a firm. With complementary preferences, a stable matching need not exist. We show that a stable matching exists for every instance when two conditions hold. The first requires each firm to have an anchor worker who is included in every feasible coalition that can be matched with that firm. The second is Transitive Alignment, which means there must be an overall ranking across different coalitions that is consistent with the workers' preferences. We propose CDAR (Combinatorial Deferred Acceptance with Reproposals), a Deferred Acceptance-style algorithm that permits reproposals, and prove its finite-time convergence and its output of a stable matching by constructing an $N$-digit potential function. Moreover, we show that, under strict preferences, the output of CDAR is Pareto optimal among stable matchings. The proposed framework naturally captures applications such as vehicle-route assignment for traffic safety and the misaligned interests of labor and management in wage negotiation.

0.17

Singleton-Attainability and Transparent Access in Matching

cs.GT econ.TH ·2026-09-23 ·Szilvia Pápai
similarity 0.71
Abstract · 68 pages, 3 tables. JEL Classification: C78, D47

Matching mechanisms differ in how much of an agent's preference ranking must be determined and reported to obtain a particular object. A mechanism is singleton-attainable (SA) if every object that an agent can obtain through some report can also be obtained by reporting only that object as acceptable. With an SA mechanism, once an attainable object has been identified, the agent need not rank or report any other object. Singleton-attainability identifies a distinct dimension in matching theory and market design: transparent access to attainable outcomes, separate from incentives, stability, welfare or equity. We establish general conditions for SA and derive its strategic implications. Top-lift invariance and truncation invariance together imply SA, while strategyproofness and stability each imply SA. By contrast, no Pareto improvement over a strategyproof, individually rational, and non-wasteful mechanism is SA. In particular, every Pareto improvement over Deferred Acceptance violates SA. We introduce report width, which measures how many acceptable objects may have to be reported to obtain an object. SA mechanisms have report width one. Report width is unbounded for a large class of efficient mechanisms that Pareto-improve Deferred Acceptance. Stable selection with report-induced priorities has width one when priorities are monotone and maximal width under reverse priority dominance. Rank-welfare maximization has width one when the outside-option rank is fixed and maximal width when it is report-dependent. These results reveal a structural divide, which we call the width dichotomy: across all mechanisms and families in our classification and all structural classes we study, report width is either one or unbounded.

0.21

Top Trading Cycles with Indifferences under Matroid Constraints

cs.GT econ.TH ·2026-09-26 ·Yasushi Kawase
theory similarity 0.66
Abstract

We study the reallocation of indivisible objects among agents who may hold initial endowments and may be indifferent between objects. Each agent has her own set of admissible objects, and a matroid constraint specifies which combinations of assigned objects are feasible. The model contains the housing market, house allocation with newcomers who hold no endowment, and the assignment of students to schools under matroidal constraints at each school. For this model, we introduce the top-class trading cycles mechanism (TCTC), which extends the top trading cycles mechanism (TTC) to matroid constraints and weak preferences. When a trading cycle is selected, TCTC fixes each agent's top indifference class rather than a specific object and postpones the choice within the class to the end. TCTC is individually rational, Pareto efficient, and weakly group-strategy-proof on the full domain of weak preferences, and it runs in polynomial time. When preferences and reports are strict, TCTC is strongly group-strategy-proof. Together with a known impossibility result, our theorem establishes a maximal domain of school-by-school constraints for individual rationality, Pareto efficiency, and strategy-proofness.

0.07

Sharp Second-Best Welfare in Bilateral and Matching Markets

cs.GT ·2026-09-29 ·Zhengyang Liu, Ying Qin, Zihe Wang
similarity 0.65
Abstract

How much social welfare must a market lose because values are private? We determine the sharp ratio of second-best to first-best welfare under independent nonnegative types, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. The ratio is approximately $0.8882516903$ for arbitrary priors and $0.9113893681$ when buyers have monotone hazard rates and sellers are unrestricted. The arbitrary-prior guarantee holds for every downward-closed family of feasible matchings; the MHR guarantee holds when every matching of a compatibility graph is feasible. Both constants are \revise{attained}{sharp} already in bilateral trade. The proof keeps the sellers' initial endowment inside the budget Lagrangian. For arbitrary priors, a common threshold decomposition reduces the problem to three-parameter power-law distributions. For monotone hazards, common transformations of buyer and seller scores reduce it to shifted capped exponential buyers; a typewise allocation certificate and an explicit worst-case seller satisfy the same boundary equation. The bilateral-to-matching framework, with a welfare endowment charge and an MHR-preserving packing argument, transfers these affine inequalities without loss. We give exact variational characterizations of both constants and reproducible interval certificates for their numerical evaluation. Unrestricted signed transfers also permit pointwise strong budget balance.

0.14

Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies

cs.DS cs.CCcs.GTecon.TH+1 ·2026-10-09 ·Nick Arnosti, Rad Niazadeh, Pranav Nuti, Felipe Simon
benchmarktheory similarity 0.63
Abstract

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

0.37

Second-Best Gains from Trade in Matching Markets

cs.GT ·2026-09-16 ·Xiaohui Bei, Bo Li, Wenhao Wu, Shengwei Zhou
benchmarktheoryhighly cited similarity 0.63
Abstract · 44 pages, 2 figures; Updated with the section on Subsidized Markets

We study gains from trade (GFT) in two-sided matching markets with independent private types and arbitrary downward-closed feasibility constraints. The second-best benchmark is the maximum expected GFT achievable by a Bayesian incentive-compatible, interim individually rational mechanism that is strongly budget balanced at every report profile. These constraints generally preclude attaining the first-best GFT and raise the question of how much efficiency must be lost. We prove that the second-best GFT is at least one half of the first-best GFT in every such matching market. This recovers and generalizes the recent $1/2$ guarantee for bilateral trade by Liu, Qin, Ren, and Wang to markets with multiple buyers and sellers and arbitrary downward-closed feasibility constraints. Together with their matching upper bound for bilateral trade, our result establishes a tight worst-case ratio of $1/2$ for this general class of matching markets. Our proof builds on the virtual-GFT framework of Brüstle, Cai, Wu, and Zhao to reduce the problem to a one-parameter Lagrangian. The main step is a geometric, edge-by-edge analysis based on first-best edge-selection regions, combined with a randomized contraction in rank space. The same analysis also determines the exact worst-case efficiency for every level of outside subsidy. In particular, even a small outside subsidy can significantly improve the worst-case guarantee.

0.33

Envy-Free Allocation of Indivisible Goods under Leontief Preferences

cs.GT cs.CC ·2026-09-23 ·Tanmay Inamdar, Pallavi Jain, Pranjal Pandey
theory similarity 0.63
Abstract

Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.

0.03

Approximately Efficient Multidimensional Bilateral Trade

cs.GT ·2026-09-02 ·Aviad Rubinstein, Xizhi Tan, Zixin Zhou
top venuehighly cited similarity 0.63
Abstract · To appear in the 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)

A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets. Because achieving the full GFT is generally impossible, the literature has focused on constant-factor approximations---a notoriously difficult problem even in simple settings. It was only recently that a breakthrough result by [DMSW22] achieved a constant-factor approximation for single-item bilateral trade. The same guarantee was later extended to single-dimensional matching markets with general downward-closed constraints [BRTW26]. Most existing results, however, are limited to single-dimensional agents. A notable multi-dimensional exception is [CGMZ21]. They considered a market with one constrained-additive buyer and $n$ single-dimensional sellers and provided a mechanism that achieves a $\log^2(n)$ approximation to the second-best GFT, i.e., the maximum expected GFT theoretically achievable by any mechanism satisfying Bayesian Incentive Compatibility (BIC), Interim Individual Rationality (IIR), and ex-ante Weak Budget Balance (WBB). In this paper, we study multi-dimensional bilateral trade problem where both sides of the market are multi-dimensional. We start with one buyer with XOS valuation and one seller with an additive cost function. We then generalize to a market with $n$ XOS buyers and one additive seller. Assuming independent items' values and costs, in both settings we propose simple mechanisms that are BIC, IIR, and ex-ante WBB, while achieving a constant fraction of the optimal (first-best) expected GFT.

0.47