CS Paper Radar

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

Louise Demoor, Martí Jané-Ballarín, Pierre Nunn, Subhajit Pramanik, Antoine Prévotat, Makoto Yokoo

cs.GT econ.TH ·submitted 2026-08-16 08:53 UTC · v1

Abstract

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.

Comment
14 pages, no figures

Closest papers

Nearest neighbours by meaning across the whole index.

Top Trading Cycles with Indifferences under Matroid Constraints

cs.GT econ.TH ·2026-09-26 ·Yasushi Kawase
theory similarity 0.71
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

How Well Can Strategyproof Tournament Rules Resist Pairwise Manipulation?

cs.GT ·2026-09-07 ·Ke Ding, Bo Li, Fangxiao Wang
theory similarity 0.61
Abstract · 23 Pages

A tournament rule maps the outcomes of all pairwise matches among $n$ teams to a possibly randomized winner. Desirable rules should be Condorcet consistent and monotone, yet also resistant to manipulation among coalition. Prior work mostly measures such manipulation additively through $k$-strongly non-manipulable at $α$ ($k$-SNM-$α$), meaning that no coalition of size $k$ can fix the matches among themselves to increase their total winning probability by $α$. Very recently, two new notions of non-manipulability were introduced. Multiplicative non-manipulability ($k$-MNM-$δ$) is defined analogously, using the multiplicative factor instead. Non-manipulability for $λ$ ($k$-NM$_λ$) characterizes the selfishness of a team, which restricts a coalition's gain to be less than $λ$ times the winning probability sacrificed by its members. In this work, we begin with a strict hierarchy among these three notions: NM$_λ$ is stronger than MNM, which is then stronger than SNM. This motivates us to consider those two notions that are stronger but less studied: pairwise multiplicative non-manipulability and $2$-non-manipulability for $λ$. We show that Randomized Death Match is $2$-MNM-$3/2$ and optimally matches the lower bound. Then, we introduce the BlockBonusedWinStrengths rule, which is Condorcet consistent, monotone, and $2$-NM$_2$. This rule substantially improves the previous upper bound of $λ=11$ and comes within a factor of two of the lower bound $λ=1$.

0.23

RARE: Response-Aware Rational Equilibrium in Budget-Constrained Pricing Games

cs.GT ·2026-10-28 ·Bhaskar Ray Chaudhury, Jugal Garg, Xin Huang, Eklavya Sharma
theory similarity 0.60
Abstract · Changes in v2: improved title, exposition, and bibliography

We study a pricing game in markets with budget-constrained buyers, where each seller offers a single good and sets its price. We consider both non-rivalrous goods, such as datasets, and rivalrous goods, such as physical goods. For non-rivalrous goods, each buyer chooses a utility-maximizing bundle within her budget. For rivalrous goods, an allocation rule selects a Pareto-optimal allocation subject to the buyers' budgets and the goods' supply constraints. Pure Nash equilibria often fail to exist in this game. A key reason is that Nash equilibrium assumes that the other sellers keep their prices fixed when one seller deviates. In practice, however, sellers harmed by a price change may respond, for example, by matching the new price. We propose a new equilibrium notion called Response-Aware Rational Equilibrium (RARE). At a RARE, every deviation by a seller can be deterred by a response from the other sellers, in which no responder earns less than she did right after the deviation. Every Nash equilibrium is a RARE. Assuming that the allocation rule is continuous in prices, we show that a RARE always exists for rivalrous goods, and for non-rivalrous goods when buyers have equal budgets. Moreover, the RARE that we construct extracts the buyers' entire budget. For non-rivalrous goods with unequal budgets, we show that an approximate RARE exists, where a deviating seller can increase her revenue by a factor equal to the ratio of the average budget to the minimum budget. We also study a natural dynamic in which sellers repeatedly raise their prices to earn the revenue that they could guarantee themselves by deviating. We show that, in the settings where we prove exact existence, this dynamic reaches a RARE with additive error $δ$ within $\lfloor B/δ\rfloor$ rounds, where $B$ is the buyers' total budget. This paper's main results have been formally verified in Lean 4.

0.24

Fair Division Under Boolean Valuations: Beyond Normalization

cs.GT ·2026-08-30 ·Nisarg Shah, Paritosh Verma
similarity 0.59
Abstract

We study fair division of indivisible items when agents have arbitrary two-level preferences: the value of each agent for any set of items is Boolean, which need not be monotone or additive. Notably, we do not impose the standard assumption of normalization, i.e., different agents may value the empty set at different Boolean levels. Since the preferences are nonmonotone, envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) each admit several variants, depending on which items are tested for removal and whether they are removed from the envious agent's bundle or the envied agent's bundle. This paper investigates the existence of these variants of EF1 and EFX, on their own and together with economic efficiency, incentive compatibility, feasibility constraints, and lottery-based randomization. Our results highlight that the existence landscape depends crucially on the number of normalized agents, who value the empty bundle at the lower Boolean level. The authors used significant assistance from GPT-5.6-Sol for deriving theoretical results, verified any AI-generated proofs for correctness, and expanded on the exposition and simplified arguments, with the aid of GPT-5.6-Sol and Claude Opus 5.

0.17

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.58
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

Price of Anarchy of First-Price Auctions in Agentic Markets

cs.GT cs.AIcs.LG ·2026-10-14 ·Shubhendu Trivedi, Jacob Eisenstein, Alekh Agarwal, Ian Gemp, Michael Kaisers +1 more
position similarity 0.58
Abstract · 40 pages

An agentic market is a decentralized serving-time market where AI agents bid to claim each user prompt. An agent's bid is based on its expected value for the prompt, which is the expectation of the reward for its response minus its inference costs. First-price auctions (FPAs), in which the highest bidder pays its bid and receives the prompt, are a natural way to allocate prompts in such a market, since they are simple and transparent to run, and do not require central knowledge of private capabilities and costs. However, FPAs are not truthful: participants may bid less than their true value in the hope of a larger profit, and the prompt may then be allocated to someone other than the bidder who values it the most. This welfare loss is quantified by the $\textit{price-of-anarchy}$ (PoA). In this paper, we argue that agentic markets are likely to possess features that reduce the price-of-anarchy. The first is a $\textit{competitive floor}$, which occurs when multiple bidders usually value the prompt above some baseline share of the optimal welfare (e.g., because the best models are often distilled into cheaper alternatives, which perform similarly). We show that competition among them then limits the welfare loss, which can be driven to zero as the floor rises. The second feature is $\textit{near-independence}$ of values after conditioning on the prompt, which occurs when most of the predictable variation in the expected value is determined by the difficulty of the prompt. As the value distribution approaches conditional independence, we can derive an efficiency guarantee that approaches a factor of $1 - 1/e^2$ of the optimal welfare. Thus, both features give rise to welfare lower bounds that are significantly better than the well-known general case of $1 - 1/e$. We validate these results empirically using auctions with strategic bidders simulated on the EmbedLLM prompt routing dataset.

0.34

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.58
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

Persistence of Bounded Rationality in Financial Markets: An Evolutionary Game-Theoretic Model

cs.GT econ.THq-fin.GN ·2026-10-29 ·Cheng Zhang
similarity 0.58
Abstract · 4 pages, 1 figure. JEL: C73, G14, G41

Classical theory predicts that irrational traders lose money to rational traders and are eventually driven out of the market. Yet noise trading, herding, and heuristic trading persist even in highly developed markets. We model a financial market as an ecology of two trading-behavior types, relatively rational (R) and boundedly rational (N), whose composition evolves under replicator dynamics according to relative performance. Each type's fitness depends on the share of the other type and on frictions. When the interaction is complementary, that is, rational traders profit from the mispricing created by boundedly rational traders while the latter benefit from the liquidity and price correction supplied by the former, and when the difference in frictions is moderate, a unique interior composition exists and is globally asymptotically stable: bounded rationality persists endogenously. When the interaction is antagonistic, the same point becomes a tipping threshold between two one-type regimes. Comparative statics show that lowering the costs of disciplined trading, as algorithmic and AI-based trading does, shifts the composition toward rational trading continuously but does not eliminate bounded rationality unless the cost advantage exceeds an explicit threshold.

0.33