Pith. sign in

REVIEW 2 major objections 5 minor 55 references

Learning in Matching Games with Bandit Feedback

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A centralized platform can learn a matching equilibrium — stable matching with each pair playing an unknown zero-sum game at its Nash value — from bandit feedback alone, at expected cumulative instability ~sqrt(T m k p a).

desk verdict New setting and a clean regret metric, but the main theorem's final Cauchy-Schwarz step drops a sqrt(min(p,a)) factor, so the claimed bound and unification with prior work do not follow as stated. read the letter →

arxiv 2506.03802 v2 pith:SKM35DSZ submitted 2025-06-04 cs.LG

Andreas Athanasopoulos , Christos Dimitrakakis This is my paper
classification cs.LG MSC 91A2691B68
keywords two-sidedmatchingmarketsbanditfeedbackzero-sumgamesequilibriuminstabilityUCBalgorithmregretbounddeferredacceptance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether a centralized platform can learn an equilibrium of a two-sided matching market when the payoff of a match is not a fixed random reward but the outcome of an unknown zero-sum game that the two matched agents play against each other. The central claim is that it can: agents form preferences from optimistic upper-confidence-bound estimates of the game values, each matched pair plays the min-max strategies of those optimistic payoff matrices, and the platform computes the matching with deferred acceptance, yielding expected cumulative matching instability of $\tilde{O}(\sqrt{T\, m\, k\, p\, a})$ over a horizon $T$. Matching instability, the paper's new yardstick, is the minimum subsidy needed to make the current matching and strategies stable, so it measures economic distance from the equilibrium rather than raw payoff loss. A correct bound of this form would mean that a platform with no knowledge of the interaction payoffs can still push the market toward a stable matching in which agents receive the Nash values of their games, at a rate that degrades gracefully with market size and action counts. The same bound unifies two previously separate results, the pure matching-market bound ($m = k = 1$) and the single-pair matrix-game bound ($p = a = 1$).

What carries the argument

The load-bearing object is the matching instability $\mathrm{MI}(m, X)$ of Definition 4: the minimum total subsidy $\sum_a s_a$ that stabilizes a candidate solution, subject to no blocking pair (C1), individual rationality for every matched agent (C2), and every matched agent receiving at least the Nash value $V^\star_{a,m(a)}$ of their game (C3). Because the subsidies must pay for every violation of the equilibrium conditions, cumulative matching instability serves as the regret measure for the whole learning problem. The argument is carried by three interacting mechanisms: entry-wise upper confidence bounds $\bar{A}_{p,a}(i,j) = \hat{A}_{p,a}(i,j) + \sqrt{2\log(1/\delta)/(1 \vee n^t_{p,a}(i,j))}$; preferences formed by sorting the optimistic game values $\bar{V}^\star_{p,a}$, which the platform feeds into the Gale-Shapley deferred acceptance algorithm; and matched pairs playing the min-max strategies of the optimistic matrix. The key per-step lemma constructs feasible subsidies $s_a = \bar{U}_{a,m(a)}(x_a, x_{m(a)}) - U_{a,m(a)}(x_a, x_{m(a)})$ under the confidence event, so the instability at round $t$ is charged to the widths of the confidence intervals, and summing those widths over the horizon produces the $\sqrt{T\, m\, k\, p\, a}$ rate.

What would settle it

Inspect the step between equations (34) and (35) of Appendix C.2: the inequality $\sum_{p,a,i,j} \sqrt{n^T_{p,a}(i,j)} \le \sqrt{T\, m\, k\, p\, a}$ is valid only if $\sum_{p,a,i,j} n^T_{p,a}(i,j) \le T$, that is, only if at most one match observation occurs per round. Recomputing the trailing regret term with the true observation budget $T\,\min(p,a)$ yields a different dependence on $p$ and $a$, and a simulation with $p = a$ large, $m = k = 1$, and single-action games would separate the two predictions: if cumulative instability tracks $\sqrt{T\,p\,a\,\min(p,a)}$ instead of $\sqrt{T\,p\,a}$, the displayed bound's dependence on market size would need correction.

Watch

Extended reading notes

Core claim

The paper's central discovery is that learning a matching equilibrium can be reduced to running a UCB scheme at two levels: each agent's preference report is an optimistic index, and each matched pair's play is a min-max response to an optimistic payoff matrix. Theorem 1 states that when Algorithm 1 is run with $\delta = 1/(4T^2 p^2 a^2 m k)$, the expected regret $\mathbb{E}[R_T] = \mathbb{E}[\sum_{t=1}^T \mathrm{MI}(m_t, X_t)]$ is at most $\tilde{O}(\sqrt{T\, m\, k\, p\, a})$. The proof shows that on the good event, under which every true payoff lies inside its confidence interval, the per-step matching instability is no larger than the sum of the UCB exploration bonuses over the matched pairs, and the failure probability is chosen so that the off-event contribution is only a constant. The paper also establishes that matching instability is non-negative, is zero exactly when the matching is stable and every agent attains the Nash value of their game, and reduces to subset instability when $m = k = 1$ and to $|V^\star - U|$ when $p = a = 1$. The significance claimed is that the bound interpolates between, and generalizes, the subset-instability bound for learning stable matchings and the UCB bound for learning zero-sum games from bandit feedback.

Load-bearing premise

The sublinear bound leans on a counting step that assumes only one matched pair is observed per round, whereas with $p$ agents on one side and $a$ on the other, up to $\min(p,a)$ disjoint pairs can be matched and observed each round, so the total number of observations over the horizon can be $T\,\min(p,a)$ rather than $T$.

Editorial extensions

If this is right

  • A platform running Algorithm 1 can push total accumulated instability below any fixed tolerance $\varepsilon$ within roughly $mkpa/\varepsilon^2$ rounds, up to logarithmic factors, so hidden interaction payoffs do not obstruct convergence to a stable market outcome.
  • The bound $\tilde{O}(\sqrt{T\,m\,k\,p\,a})$ specializes to $\tilde{O}(\sqrt{T\,p\,a})$ when $m = k = 1$, recovering the subset-instability result for learning stable matchings, and to $\tilde{O}(\sqrt{T\,m\,k})$ for a single agent on each side, matching the matrix-game bandit bound.
  • Because matching instability vanishes exactly when the matching is stable and each agent attains the Nash value of their game, sublinear cumulative instability means that, on average over time, blocking pairs disappear and agents' realized payoffs approach equilibrium values.
  • The result extends bandit learning in matching markets to matches whose value is determined by strategic interaction, so the platform never needs to estimate match-level rewards directly; the agents' own play generates the learning signal.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the per-step lemma only requires each matched agent's optimistic value to dominate the true one, the guarantee plausibly survives when the two sides of the market hold different information — for instance, one side knowing its payoff matrices — which is consistent with the paper's Nash-response simulation, although the paper proves no such bound.
  • The instability yardstick is defined against the game's value rather than against the equilibrium strategy, so any playing rule that merely attains the value, such as no-regret dynamics that converge to it, could in principle replace exact min-max computation inside the algorithm; the analysis does not exploit this slack.
  • The protocol needs no central planner with special information, only an entity that aggregates announced preference orderings, so the same UCB-plus-deferred-acceptance machinery could transplant to a market where agents broadcast preferences themselves, a decentralized setting the paper leaves for future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper introduces a repeated two-sided matching market in which matched agents play an unknown zero-sum game, and asks whether a central platform can learn a matching equilibrium from bandit feedback. It defines a new metric, matching instability, as a subsidy-based distance from equilibrium, proposes a UCB-style algorithm (UCB-MG) that forms preferences and selects min-max strategies from optimistic payoff estimates, and claims in Theorem 1 an expected cumulative regret of O~(sqrt(T mkpa)), where m,k are action counts and p,a are agent counts. The paper further claims that this rate unifies the known O~(sqrt(T pa)) bound for matching markets with one action per agent and the O~(sqrt(T mk)) bound for two-player zero-sum games. The main proof is in Appendix C, with the key concentration and counting argument in C.2.

Significance. If the claimed rate were correct, the paper would make a useful step by adding strategic interaction to the bandit learning of matching markets and by unifying two previously separate settings. The formal development is self-contained: matching instability is defined explicitly, Proposition 2 captures the optimism properties, and the proof is not circular. The simulation section is a useful sanity check, though the code is only promised, not provided. However, the central theorem contains a counting error in the Cauchy-Schwarz step, and the advertised pa dependence is not established. A corrected analysis gives a rate with an additional factor sqrt(min(p,a)), which breaks the claimed unification with prior work. The paper is best viewed as a promising framework with a theorem that needs to be corrected or substantially reframed.

major comments (2)
  1. [Appendix C.2, Eqs. (34)-(35)] The transition from Eq. (34) to Eq. (35) bounds sum_{p,a,i,j} sqrt(n^T_{p,a}(i,j)) by sqrt(T mkpa). This is valid only if the total number of matched-pair observations over T rounds is at most T. In this model a matching can contain up to min(p,a) disjoint pairs per round, and with the standard choice U_{a,⊥}=-1 the platform can match min(p,a) pairs in every round. Hence N_T = sum_{t=1}^T |m_t| is at most T min(p,a), and Cauchy-Schwarz gives sqrt(mkpa * N_T) = sqrt(T mkpa min(p,a)), not sqrt(T mkpa). For p=a=n the corrected bound is sqrt(T mk n^3), a factor sqrt(n) larger than the claimed sqrt(T mk n^2). This invalidates the stated rate in Theorem 1 and the claimed recovery of the O~(sqrt(T pa)) bound from [26] for m=k=1. The proof needs to be repaired, for example by proving a bound of O~(sqrt(T mkpa min(p,a))) or by modifying the algorithm so that at most one pair is matched per round.
  2. [Definition 4 and Appendix A, Remark 1] The matching-instability metric does not actually certify a matching equilibrium as defined in Definition 3. Constraint C3 only forces the realized utility of each matched agent to be at least the value V* of the matched game; combined with the zero-sum structure, this gives equality of utilities with V*, but it does not enforce best response. The authors' own example in Appendix A shows a non-Nash strategy profile with the value of the game, so MI(m,X)=0 can hold for a pair that is not playing a Nash equilibrium. Thus the abstract's claim of 'learning an equilibrium' is stronger than what the regret measure proves. The authors should either weaken the solution concept to a value-based notion and state the results in those terms, or add a constraint to the LP in Definition 4 that directly penalizes profitable unilateral deviations.
minor comments (5)
  1. [Section 2, Notation] The notation line '[n] := {1, 2, ..., k}' should read '[k] := {1, 2, ..., k}'.
  2. [Section 2.2] The sentence before Definition 1 contains the typo 'Bellow' instead of 'Below'.
  3. [Algorithm 1, line 9] The expression hat{pi}_a = arg sort_i bar{V}_{a,i} is ambiguous because i is used for actions elsewhere; the sorting should be over agents on the opposite side, not over action indices.
  4. [Section 3.1, step 5] The phrase 'The agents a in A observes' should be 'The agents a in A observe'.
  5. [Appendix D.1] Appendix D.1 refers to 'Figure 2' for the experiments, but the experiments are presented in Figure 1; the two figure captions are nearly identical and should be consolidated.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the regret bound is derived from UCB concentration arguments, and the only self-citation is in related work and not load-bearing.

full rationale

The paper's central claim, Theorem 1, is not equivalent to its inputs by construction. Matching instability (Definition 4) is defined as the value of an explicit linear program, and Proposition 1 derives its properties from that definition without assuming the theorem. Lemma 1 bounds the per-step instability by constructing a feasible subsidy vector from the UCB confidence widths, and the proof of Theorem 1 combines this with a union bound and sub-Gaussian concentration. No fitted parameter is renamed as a prediction, and no load-bearing result is imported from the authors' own prior work; the only self-citation ([3]) appears in a related-work paragraph on PAC sample complexity and is not used in the proof. The proof does contain a genuine gap at the Cauchy-Schwarz step between Equations (34) and (35), where sum sqrt(n^T_{p,a}(i,j)) is bounded as sqrt(T mkpa) although a matching can contain up to min(p,a) disjoint pairs, so the total number of pair observations can be T min(p,a). This is a correctness problem with the stated bound, not a circular reduction: the bound does not follow from the assumptions by construction, and correcting it would change the claimed p,a dependence rather than reveal that the theorem was assumed. Accordingly, no circular step under the defined taxonomy is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central result rests on standard game-theoretic existence results, the Gale-Shapley stability theorem, and sub-Gaussian concentration. The proof also implicitly assumes that at most one matching pair is formed per time step, which is not stated as an assumption and is false in general; this hidden assumption is what makes the claimed regret bound hold. The paper introduces a new metric, matching instability, but no new physical entities.

assumptions (4)
  • standard math Existence and computability of Nash equilibria in two-player zero-sum games via the minimax theorem
    Used in Section 2.1 to define game values and in Algorithm 1 to compute min-max strategies from upper-confidence matrices.
  • domain assumption Gale-Shapley deferred acceptance produces a stable matching, including individual rationality
    Used in Section 4 and in the proof of Lemma 1 (constraint C2) to assert the matching selected at each step is stable and individually rational under the estimated preferences. The paper does not specify how the outside option U_{a,⊥} is incorporated into the deferred acceptance procedure.
  • domain assumption Rewards are 1-sub-Gaussian (Assumption A3)
    Required for the confidence intervals and the union bound in the proof of Theorem 1.
  • ad hoc to paper Total number of matched pair interactions over T rounds is at most T
    This is the implicit assumption in the transition from inequality (34) to (35) in the proof of Theorem 1. It is false in general because a matching can contain up to min(p,a) disjoint pairs per round; the correct total is T times min(p,a).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning in Matching Games with Bandit Feedback." pith.science (2026). https://pith.science/paper/SKM35DSZ

@misc{pith2026250603802,
  author       = {Pith},
  title        = {Pith review of: Learning in Matching Games with Bandit Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SKM35DSZ}},
  note         = {Machine review of arXiv:2506.03802}
}
abstract

We introduce a learning problem in a generalized two-sided matching market, where agents select actions to interact with their match. Specifically, we consider a setting in which matched agents engage in zero-sum games with initially unknown payoff matrices, and we investigate whether a centralized procedure can learn an equilibrium from bandit feedback. We adopt the solution concept of a \emph{matching equilibrium}, where a matching \( \mathfrak{m} \) and a set of agent strategies \( X \) form an equilibrium if no agent has an incentive to deviate from \( (\mathfrak{m}, X) \). To quantify deviations of a candidate solution \( (\mathfrak{m}, X) \) from the equilibrium \( (\mathfrak{m}^\star, X^\star) \), we introduce the notion of \emph{matching instability}, which serves as a regret measure for the learning problem. We propose a UCB-based algorithm in which agents form preferences and select actions according to optimistic estimates of the payoffs. Our analysis establishes a sublinear, instance-independent regret upper bound, further supported by empirical evidence.

Figures

Figures reproduced from arXiv: 2506.03802 by the authors.

Figure 1
Figure 1. Regret of the different settings, including the theoretical bound. Lines represent the average [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Regret of the different settings, including the theoretical bound for varying numbers of [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

55 extracted references · 50 canonical work pages

  1. [26]

    Learning Equilibria in Matching Markets from Bandit Feedback

    Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael I. Jordan, and Jacob Steinhardt. Learning equilibria in matching markets from bandit feedback. CoRR, abs/2108.08843, 2021. URL https://arxiv.org/abs/2108.08843

    work page Pith review arXiv 2021

  2. [1]

    Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games

    Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 736–749, 2022

    work page 2022

  3. [2]

    Uncoupled learning dynamics with o(\log t) swap regret in multiplayer games

    Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o(\log t) swap regret in multiplayer games. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems , volume 35, pages 3292–3304. Curran Associate...

    work page 2022

  4. [3]

    Probably correct op- timal stable matching for two-sided markets under uncertainty.arXiv preprint arXiv:2501.03018, 2025

    Andreas Athanasopoulos, Anne-Marie George, and Christos Dimitrakakis. Probably correct op- timal stable matching for two-sided markets under uncertainty.arXiv preprint arXiv:2501.03018, 2025

    arXiv 2025

  5. [4]

    Gambling in a rigged casino: The adversarial multi-armed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages 322–331. IEEE, 1995

    work page 1995

  6. [5]

    The cost of stability in coalitional games

    Yoram Bachrach, Edith Elkind, Reshef Meir, Dmitrii Pasechnik, Michael Zuckerman, Jörg Rothe, and Jeffrey S Rosenschein. The cost of stability in coalitional games. In Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20,

    work page 2009

  7. [6]

    Beyond log2(t) regret for decentralized bandits in matching markets

    Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log2(t) regret for decentralized bandits in matching markets. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 705–715, Virtual, 18–24 Jul 2021. PMLR. URL htt...

    work page 2021

  8. [7]

    Zero-sum polymatrix games: A generalization of minmax

    Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41(2): 648–655, 2016

    work page 2016

Show all 55 references
  1. [8]

    Competing against Nash equilibria in adversarially changing zero-sum games

    Adrian Rivera Cardoso, Jacob Abernethy, He Wang, and Huan Xu. Competing against Nash equilibria in adversarially changing zero-sum games. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of...

  2. [9]

    Cen and Devavrat Shah

    Sarah H. Cen and Devavrat Shah. Regret, stability & fairness in matching markets with bandit learners. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , volume 1...

    2022

  3. [10]

    Prediction, Learning, and Games

    Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games . Cambridge University Press, 2006

    2006

  4. [11]

    Hedging in games: Faster convergence of external and swap regrets

    Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33:18990–18999, 2020

    2020

  5. [12]

    Two-sided bandits and the dating market

    Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI’05, page 947–952, San Francisco, CA, USA, 2005. Morgan Kaufmann Publishers Inc

    2005

  6. [13]

    Near-optimal no-regret algo- rithms for zero-sum games

    Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235–254. SIAM, 2011. 10

    2011

  7. [14]

    Near-optimal no-regret learning in general games

    Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604– 27616, 2021

    2021

  8. [15]

    Near-optimal no-regret learning dynamics for general convex games

    Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35:39076–39089, 2022

    2022

  9. [16]

    Asymptotic calibration.Biometrika, 85(2):379–390, 1998

    Dean P Foster and Rakesh V V ohra. Asymptotic calibration.Biometrika, 85(2):379–390, 1998

    1998

  10. [17]

    Gale and L

    D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962. ISSN 00029890, 19300972. URL http://www. jstor.org/stable/2312726

    1962

  11. [18]

    Decentralized job matching

    Guillaume Haeringer and Myrna Wooders. Decentralized job matching. International Journal of Game Theory, 40:1–28, 02 2011. doi: 10.1007/s00182-009-0218-x

    2011 doi

  12. [19]

    Approximation to bayes risk in repeated play

    James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3(2):97–139, 1957

    1957

  13. [20]

    A simple adaptive procedure leading to correlated equilib- rium

    Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilib- rium. Econometrica, 68(5):1127–1150, 2000

    2000

  14. [21]

    Putting gale & shapley to work: Guaranteeing stability through learning

    Hadi Hosseini, Sanjukta Roy, and Duohan Zhang. Putting gale & shapley to work: Guaranteeing stability through learning. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems , volu...

    2024

  15. [22]

    Instance-dependent regret bounds for learning two-player zero-sum games with bandit feedback

    Shinji Ito, Haipeng Luo, Taira Tsuchiya, and Yue Wu. Instance-dependent regret bounds for learning two-player zero-sum games with bandit feedback. arXiv preprint arXiv:2502.17625, 2025

    2025 arXiv

  16. [23]

    Equilibrium existence in bipartite social games: A generalization of stable matchings

    Matthew O Jackson and Alison Watts. Equilibrium existence in bipartite social games: A generalization of stable matchings. Economics Bulletin, 3(12):1–8, 2008

    2008

  17. [24]

    Social games: Matching and the play of finitely repeated games

    Matthew O Jackson and Alison Watts. Social games: Matching and the play of finitely repeated games. Games and Economic Behavior, 70(1):170–191, 2010

    2010

  18. [25]

    Learn- ing equilibria in matching markets from bandit feedback

    Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael Jordan, and Jacob Steinhardt. Learn- ing equilibria in matching markets from bandit feedback. Advances in Neural Information Processing Systems, 34:3323–3335, 2021

    2021

  19. [27]

    Thompson sampling for bandit learning in matching markets

    Fang Kong, Junming Yin, and Shuai Li. Thompson sampling for bandit learning in matching markets. In Lud De Raedt, editor,Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3164–3170, Vienna, Austria, 7 2022. International...

    2022 doi

  20. [28]

    Bandit algorithms

    Tor Lattimore and Csaba Szepesvari. Bandit algorithms. 2017. URL https:// tor-lattimore.com/downloads/book/book.pdf

    2017

  21. [29]

    The weighted majority algorithm

    Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212–261, 1994

    1994

  22. [30]

    Liu, Horia Mania, and Michael Jordan

    Lydia T. Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics , volume 108 of Proceedings of Machine Lear...

    2020

  23. [31]

    Bandit learning in decentralized matching markets

    Lydia T Liu, Feng Ruan, Horia Mania, and Michael I Jordan. Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1–34, 2021

    2021

  24. [32]

    Instance-dependent sample complexity bounds for zero-sum matrix games

    Arnab Maiti, Kevin Jamieson, and Lillian Ratliff. Instance-dependent sample complexity bounds for zero-sum matrix games. In International Conference on Artificial Intelligence and Statistics, pages 9429–9469. PMLR, 2023

    2023

  25. [33]

    Compet- ing bandits in time varying matching markets

    Deepan Muthirayan, Chinmay Maheshwari, Pramod Khargonekar, and Shankar Sastry. Compet- ing bandits in time varying matching markets. In Nikolai Matni, Manfred Morari, and George J. Pappas, editors, Proceedings of The 5th Annual Learning for Dynamics and Control Conference, vol...

    2023

  26. [34]

    Non-cooperative games

    John F Nash. Non-cooperative games. In The Foundations of Price Theory Vol 4, pages 329–340. Routledge, 2024

    2024

  27. [35]

    Vazirani.Algorithmic Game Theory

    Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V . Vazirani.Algorithmic Game Theory. Cambridge University Press, USA, 2007. ISBN 0521872820

    2007

  28. [36]

    Matrix games with bandit feedback

    Brendan O’Donoghue, Tor Lattimore, and Ian Osband. Matrix games with bandit feedback. In Uncertainty in Artificial Intelligence, pages 279–289. PMLR, 2021

    2021

  29. [37]

    Optimization, learning, and games with predictable sequences

    Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013

    2013

  30. [38]

    An iterative method of solving a game

    Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54(2):296–301,

  31. [39]

    The evolution of the labor market for medical interns and residents: a case study in game theory

    Alvin E Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of political Economy, 92(6):991–1016, 1984

    1984

  32. [40]

    Roth and Marilda A

    Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-Sided Matching: A Study in Game- Theoretic Modeling and Analysis. Econometric Society Monographs. Cambridge University Press, 1990

    1990

  33. [41]

    Dominate or delete: Decentralized competing bandits in serial dictatorship

    Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Stat...

    2021

  34. [42]

    Quasi-cores in a monetary economy with nonconvex preferences

    Lloyd S Shapley and Martin Shubik. Quasi-cores in a monetary economy with nonconvex preferences. Econometrica: Journal of the Econometric Society, pages 805–827, 1966

    1966

  35. [43]

    Fast convergence of regularized learning in games

    Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015

    2015

  36. [44]

    J v. Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295–320, 1928

    1928

  37. [45]

    Morgenstern, 0

    John V on Neumann. Morgenstern, 0. Theory of games and economic behavior, 3, 1944

    1944

  38. [46]

    More adaptive algorithms for adversarial bandits

    Chen-Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. InConference On Learning Theory, pages 1263–1291. PMLR, 2018. A Remark on constrain C3 of Definition 4 In this section, we provide a remark supporting constraint C3 in Definition 4 of matching insta...

    2018

  39. [50]

    It is always non-negative

  40. [51]

    B) The matching m is stable under the strategies X

    It is equal to zero if and only if both of the following hold: A) For strategiesX, each agent receives the same valuation as in the Nash equilibrium of their respective game, i.e., Ua,m(a)(xa, xm(a)) = V ⋆ a,m(a)∀a ∈ A. B) The matching m is stable under the strategies X

  41. [52]

    In the case where each agent has a single action, i.e., m = k = 1, the model reduces to the two-sided matching problem of Section 2.2, and the matching instability coincides with the subset instability of Definition 2

  42. [53]

    In the case of a single agent on each side, i.e., P = {p} and A = {a}, where they are always matched, i.e., m(p) = a, the model reduces to the ZSG setting. In this case, the matching instability MI(m, X) for strategies X = {xp, xa} becomes: MI(m, X) = V ⋆ a,m(a) − Ua,m(a)(xa, ...

  43. [54]

    We denote by (x⋆ p, y⋆ a) the Nash equilibrium of the game with payoff matrix ¯Ap,a, and by ¯V ⋆ p,a = x⋆T p ¯Ap,ay⋆ a the value of the game

    Agent p selects xp = x⋆ p = arg maxx miny xT ¯Ap,ay. We denote by (x⋆ p, y⋆ a) the Nash equilibrium of the game with payoff matrix ¯Ap,a, and by ¯V ⋆ p,a = x⋆T p ¯Ap,ay⋆ a the value of the game. 15

  44. [55]

    s 2 1 ∨ nt a,mt(a)(ita, it mt(a)) log 1 δ # (31) ≤ 2 TX t=1 X (p,a)∈mt E

    Accordingly, agent a selects xa = x⋆ a = arg maxx miny xT ¯Aa,py, with (x⋆ a, y⋆ p) being the Nash equilibrium of the game with payoff matrix ¯Aa,p. The value of the game for agent a is ¯V ⋆ a,p = x⋆T a ¯Aa,py⋆ p Note that the pair of strategies (xp = x⋆ p, xa = x⋆ a) selected...

  45. [1951]

    URL http://www.jstor.org/stable/1969530

    ISSN 0003486X, 19398980. URL http://www.jstor.org/stable/1969530

  46. [2009]

    Springer, 2009

    Proceedings 2, pages 122–134. Springer, 2009

    2009

  47. [2019]

    URL https://proceedings.mlr.press/v97/cardoso19a.html

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.