CS Paper Radar

Strategic Tanking in Stable Matching Markets

James P. Bailey

cs.GT cs.MA ·submitted 2026-10-30 17:46 UTC · v1

Abstract

Motivated by a broad literature in psychology, organizational behavior, and matching markets, we introduce strategic tanking: an agent deliberately makes themselves less attractive to selected potential partners in order to improve their eventual assignment. Unlike traditional manipulation in stable matching, a tanker does not misreport whom they prefer; instead, they influence how others rank them. We show that tanking has a striking connection to classical preference manipulation. Cutoff tanking, in which an agent tanks with every potential partner below a chosen threshold, has exactly the same effect on the stable set as truncating one's own preference list at that threshold. Thus an agent can reproduce the power of a classical truncation while leaving their own preferences unchanged and every match acceptable. Arbitrary tanking, however, can go substantially further: under proposer-deferred acceptance, tanking equilibria can lie outside the sincere stable set. More broadly, whenever the sincere stable set contains multiple matchings, profitable strategic behavior remains available through either traditional preference manipulation or tanking, even when one side is restricted to honestly reporting their own preferences.

Closest papers

Nearest neighbours by meaning across the whole index.

Singleton-Attainability and Transparent Access in Matching

cs.GT econ.TH ·2026-09-23 ·Szilvia Pápai
similarity 0.68
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

From Preference to Reciprocity: Decentralized Matching with Empirically Grounded LLM-agent Based Modeling

cs.LG cs.AI ·2026-09-28 ·Wangxuan Fan, Xiaoyu Nie, Zhoutian Shi, Xiangcheng Meng, Shipei Zeng +3 more
similarity 0.63
Abstract

Bipartite matching is a fundamental problem in game theory and market design. Classical approaches such as Gale--Shapley assume complete preferences and centralized computation, whereas many real-world matching processes are decentralized, asynchronous, and shaped by sequential interaction under limited information. We propose a dynamic bipartite matching framework that combines large language model (LLM) agents with contextual bandits. In a simulated Chinese marriage market, economically grounded LLM agents evaluate locally encountered candidates, while agent-specific Logistic-UCB models learn reciprocal acceptance from realized proposal outcomes. The mechanism therefore separates two decisions---\emph{whom do I like?} and \emph{who is likely to like me back?}---without requiring ex ante market-wide preference rankings. We first validate LLM-induced mate preferences against the empirical conditional-logit reference across multiple LLM backbones. In the $50\times50$ matching experiment, Bandit-UCB achieves the highest mean mutual welfare (56.01 versus 54.87 for Gale--Shapley), a smaller gender rank gap than the classical baselines, and the fewest blocking pairs among the LLM-ABM policies. Learned acceptance models show economically interpretable gender-differentiated associations, while counterfactual setups reveal no systematic unilateral advantage from prior search knowledge. Overall, these results support the advantages of decentralized matching with LLM-based behavioral modeling and online learning under incomplete information for economic simulation and computational social science research.

0.26

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

cs.GT econ.TH ·2026-10-22 ·Yasushi Kawase, Ryosuke Sato
similarity 0.60
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.

0.07

Receiver Decides Agent-to-Agent Negotiations

cs.CL ·2026-10-13 ·Fardeen Sadab, Alif Hasnain, Afsana Shehrin, Md. Azam Hossain, Abu Raihan Mostofa Kamal
similarity 0.59
Abstract · 18 pages, 12 figures

When one language-model agent asks another for money, which of the two decides how much changes hands? We ran a round-robin tournament of 1,049 negotiations among fifteen agents. In each game a requester tries to raise money from a holder that has been told to keep a $100 endowment. Knowing which agent holds the money explains 47% of the variance in the amount transferred; knowing which agent asks explains 2%. Dropping the most extreme agents narrows the split to 22% against 4%. Changing the requester's appeal from one named person to a group changed what requesters wrote, but the amounts transferred under the two framings are statistically equivalent. The holders that lose least are the ones that turn down the opening request, and their turn-1 refusal rate ranks them by total losses (Spearman correlation = -0.73). Training moves this behaviour in both directions. Fine-tuning Qwen3-8B on a persuasion corpus with almost no refusals raised what it gave away as a holder from 12% to 84% of the endowment. Distilling two never-losing holders into a 4B student cut its losses from 95% to 1%. Evaluations of agents that hold resources should test them in the holder role, including after persuasion fine-tuning.

0.26

Non-obvious Manipulability with Groups in Shapley-Scarf Housing Markets

cs.GT econ.TH ·2026-08-16 ·Louise Demoor, Martí Jané-Ballarín, Pierre Nunn, Subhajit Pramanik, Antoine Prévotat +1 more
similarity 0.58
Abstract · 14 pages, no figures

In Shapley-Scarf housing markets, Ma (1994) shows that top trading cycles (TTC) is the unique mechanism satisfying individual rationality (IR), Pareto efficiency (PE), and strategy-proofness. We ask what other mechanisms become possible when strategy-proofness is replaced by a weaker condition called non-obvious manipulability (NOM), introduced by Troyan and Morrill (2020). We first show that this weaker condition does not help on its own: every IR and PE mechanism is already NOM. We therefore introduce a new condition: NOM with groups, under which each agent knows the preferences of the other members of her group, but not those of agents outside the group. This condition reduces to strategy-proofness when all agents belong to one group, and to standard NOM when every group is a singleton. Also, we introduce a participation condition called group rationality (GR), which requires that no group do worse than it would by trading only among its own members. We then define a class of mechanisms called TTC with super-groups, whose members satisfy GR, PE, and NOM with groups. The class includes mechanisms that differ from standard TTC, including mechanisms that are not strategy-proof. Furthermore, we show that every mechanism that satisfies GR, PE, and NOM with groups has the same best- and worst-case outcomes as every TTC with super-groups mechanism.

0.10

Fair Stable Matching: A Nash Social Welfare Approach

cs.GT cs.AI ·2026-09-02 ·Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar
similarity 0.58
Abstract

While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}. We develop \texttt{SNSW-Alg} that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in $\tilde{\mathcal{O}}(n^4)$ time, where $n$ is the number of men or women. We demonstrate that \texttt{SNSW-Alg} balances equity while preserving stability. We empirically evaluate our methods across diverse preference distributions, demonstrating significant gains in fairness without substantial losses in other key measures such as regret, egalitarian criterion, and sex equality. Our findings suggest that the stable matching produced by \texttt{SNSW-Alg} is statistically Pareto-undominated by stable matchings based on other fairness measures - regret, egalitarian, and sex equality. This study offers compelling insights for designing fair-stable matching.

0.23

On the Convergence of Iterated Round Robin

cs.GT ·2026-10-16 ·Maxime Lucet, Henri Surugue, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet +1 more
similarity 0.57
Abstract

Round Robin (RR) is a simple and widely used picking sequence mechanism for allocating indivisible goods, known to guarantee envy-freeness up to one item (EF1) when preferences are additive. Despite being manipulable (meaning that agents may have an incentive to strategically misreport their preferences), it is known to always admit at least one pure Nash equilibrium. In this paper, we study an iterated variant of RR, in which agents observe the outcome of the mechanism at each iteration and may revise their reported preferences through a best-response dynamics. We first consider a full-information setting, where agents observe both the outcome and the reported preferences of all the agents. In this setting, we show that cycles can occur even under strong restrictions on the manipulations carried out by the agents. We nonetheless identify a natural restriction (item-preserving swaps), under which convergence to a pure Nash equilibrium is guaranteed to exist for any number of agents and items. We also show that restricting to adjacent swaps guarantees convergence for two agents and a limited number of items, leaving the question open for unbounded number of items. We then turn to a partial-information setting, in which agents only observe the resulting allocation and must then infer the preference profiles of the others assuming consistency with the RR sequence. We study three behaviours guiding the agents when deciding how to manipulate under uncertainty on the other agents' preferences. We show that two of the studied behaviours, despite being quite natural, may cycle while a more cautious rule guarantees iterated RR to be strategyproof.

0.10

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.56
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.39