Tootfinder

Correlation of Rankings in Matching Markets
R\'emi Castera, Patrick Loiseau, Bary S. R. Pradelski
https://arxiv.org/abs/2512.05304 https://arxiv.org/pdf/2512.05304 https://arxiv.org/html/2512.05304
arXiv:2512.05304v1 Announce Type: new
Abstract: We study the role of correlation in matching markets, where multiple decision-makers simultaneously face selection problems from the same pool of candidates. We propose a model in which a candidate's priority scores across different decision-makers exhibit varying levels of correlation dependent on the candidate's sociodemographic group. Such differential correlation can arise in school choice due to the varying prevalence of selection criteria, in college admissions due to test-optional policies, or due to algorithmic monoculture, that is, when decision-makers rely on the same algorithms and data sets to evaluate candidates. We show that higher correlation for one of the groups generally improves the outcome for all groups, leading to higher efficiency. However, students from a given group are more likely to remain unmatched as their own correlation level increases. This implies that it is advantageous to belong to a low-correlation group. Finally, we extend the tie-breaking literature to multiple priority classes and intermediate levels of correlation. Overall, our results point to differential correlation as a previously overlooked systemic source of group inequalities in school, university, and job admissions.
toXiv_bot_toot

Perfect Network Resilience in Polynomial Time
Matthias Bentert, Stefan Schmid
https://arxiv.org/abs/2602.03827 https://arxiv.org/pdf/2602.03827 https://arxiv.org/html/2602.03827
arXiv:2602.03827v1 Announce Type: new
Abstract: Modern communication networks support local fast rerouting mechanisms to quickly react to link failures: nodes store a set of conditional rerouting rules which define how to forward an incoming packet in case of incident link failures. The rerouting decisions at any node $v$ must rely solely on local information available at $v$: the link from which a packet arrived at $v$, the target of the packet, and the incident link failures at $v$. Ideally, such rerouting mechanisms provide perfect resilience: any packet is routed from its source to its target as long as the two are connected in the underlying graph after the link failures. Already in their seminal paper at ACM PODC '12, Feigenbaum, Godfrey, Panda, Schapira, Shenker, and Singla showed that perfect resilience cannot always be achieved. While the design of local rerouting algorithms has received much attention since then, we still lack a detailed understanding of when perfect resilience is achievable.
This paper closes this gap and presents a complete characterization of when perfect resilience can be achieved. This characterization also allows us to design an $O(n)$-time algorithm to decide whether a given instance is perfectly resilient and an $O(nm)$-time algorithm to compute perfectly resilient rerouting rules whenever it is. Our algorithm is also attractive for the simple structure of the rerouting rules it uses, known as skipping in the literature: alternative links are chosen according to an ordered priority list (per in-port), where failed links are simply skipped. Intriguingly, our result also implies that in the context of perfect resilience, skipping rerouting rules are as powerful as more general rerouting rules. This partially answers a long-standing open question by Chiesa, Nikolaevskiy, Mitrovic, Gurtov, Madry, Schapira, and Shenker [IEEE/ACM Transactions on Networking, 2017] in the affirmative.
toXiv_bot_toot

Replaced article(s) found for cs.GT. https://arxiv.org/list/cs.GT/new
[1/1]:
- Cumulative Games: Who is the current player?
Urban Larsson, Reshef Meir, Yair Zick
https://arxiv.org/abs/2005.06326
- Contest Design with Threshold Objectives
Edith Elkind, Abheek Ghosh, Paul W. Goldberg
https://arxiv.org/abs/2109.03179
- Deep Learning Meets Mechanism Design: Key Results and Some Novel Applications
V. Udaya Sankar, Vishisht Srihari Rao, Y. Narahari
https://arxiv.org/abs/2401.05683 https://mastoxiv.page/@arXiv_csGT_bot/111741115483021453
- Charting the Shapes of Stories with Game Theory
Daskalakis, Gemp, Jiang, Leme, Papadimitriou, Piliouras
https://arxiv.org/abs/2412.05747 https://mastoxiv.page/@arXiv_csGT_bot/113627246220336424
- Computing Evolutionarily Stable Strategies in Multiplayer Games
Sam Ganzfried
https://arxiv.org/abs/2511.20859 https://mastoxiv.page/@arXiv_csGT_bot/115620508246637361
- Autodeleveraging: Impossibilities and Optimization
Tarun Chitra
https://arxiv.org/abs/2512.01112 https://mastoxiv.page/@arXiv_csGT_bot/115649040881525135
- Static Pricing Guarantees for Queueing Systems
Jacob Bergquist, Adam N. Elmachtoub
https://arxiv.org/abs/2305.09168 https://mastoxiv.page/@arXiv_csDS_bot/110382625621173269
- Game of arrivals at a two queue network with heterogeneous customer routes
Agniv Bandyopadhyay, Sandeep Juneja
https://arxiv.org/abs/2310.18149 https://mastoxiv.page/@arXiv_csPF_bot/111322112226936579
- Characterization of Priority-Neutral Matching Lattices
Clayton Thomas
https://arxiv.org/abs/2404.02142 https://mastoxiv.page/@arXiv_econTH_bot/112205968984928881
- Seven kinds of equivalent models for generalized coalition logics
Zixuan Chen, Fengkui Ju
https://arxiv.org/abs/2501.05466 https://mastoxiv.page/@arXiv_csLO_bot/113819715349259373
- Matching Markets Meet LLMs: Algorithmic Reasoning with Ranked Preferences
Hadi Hosseini, Samarth Khanna, Ronak Singh
https://arxiv.org/abs/2506.04478 https://mastoxiv.page/@arXiv_csAI_bot/114635186215388479
toXiv_bot_toot