• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
November 17, 2026
Physicists Show How a Solvent Shapes the Response of Drug Molecules
Many drug molecules can switch between different three-dimensional shapes. Using a mathematical model of ibuprofen dissolved in supercritical CO₂, researchers from HSE University and the Institute of Solution Chemistry of the Russian Academy of Sciences have shown that the solvent can make these molecules appear to respond unusually slowly. The molecules themselves continue to change shape rapidly, but their surroundings rearrange much more slowly, and this lag shows up in the measurements. The study has been published in The Journal of Chemical Physics. 
November 10, 2026
Physicists Train AI to Optimise Particle Beams in Accelerators
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science and the Budker Institute of Nuclear Physics at the Siberian Branch of the Russian Academy of Sciences have developed RLABC (Reinforcement Learning for Accelerator Beamline Control), a framework that uses reinforcement learning to identify optimal settings for a particle accelerator. In a computer simulation, RLABC optimised the accelerator's parameters to achieve a particle transmission rate of 70%. The study has been published in Computer Physics Communications.
November 9, 2026
'Organ-on-a-Chip Technology Could Eliminate the Need for Animal Testing'
The Laboratory of Molecular Physiology at the HSE Faculty of Biology and Biotechnology investigates how molecular regulators known as microRNAs control gene expression and contribute to the development of diseases, including cancer, viral and inflammatory conditions, and pregnancy complications. At HSE University, researchers develop organ-on-a-chip models: miniature devices containing living cells that mimic the functions of human organs, such as the placenta and intestines. These models help researchers understand how diseases develop and how drugs affect them. HSE News Service spoke with Evgeny Knyazev, Head of the Laboratory.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies

International Journal of Game Theory. 2024. Vol. 53. P. 449–473.
Boros E., Franciosa P. G., Gurvich V., Vyalyi M.

We prove that a deterministic n-person shortest path game has a Nash equlibrium in
pure and stationary strategies if it is edge-symmetric (that is (u, v) is a move when-
ever (v, u) is, apart from moves entering terminal vertices) and the length of every
move is positive for each player. Both conditions are essential, though it remains an
open problem whether there exists a NE-free 2-person non-edge-symmetric game
with positive lengths. We provide examples for NE-free 2-person edge-symmetric
games that are not positive. We also consider the special case of terminal games
(shortest path games in which only terminal moves have nonzero length, possibly
negative) and prove that edge-symmetric n-person terminal games always have Nash
equilibria in pure and stationary strategies. Furthermore, we prove that an edge-
symmetric 2-person terminal game has a uniform (subgame perfect) Nash equilib-
rium, provided any infinite play is worse than any of the terminals for both players.

Research target: Computer Science Mathematics
Language: English
DOI
Text on another site
Keywords: Nash equilibriumn-Person deterministic graphical gamesShortest path gamesTerminal games
Publication based on the results of:
Mathematical methods and algorithms in information theory, computational complexity, formal languages, and combinatorial matrix theory (2024)
Similar publications
Genus zero Whitham hierarchy via Hurwitz–Frobenius manifolds
Basalaev A., Journal of Geometry and Physics 2027 Vol. 232 Article 106032
B. Dubrovin introduced the structure of a Dubrovin–Frobenius manifold on a space of ramified coverings of a sphere by a genus g Riemann surface with the prescribed ramification profile. This is now known as a genus g Hurwitz–Frobenius manifold. We investigate the genus zero Hurwitz–Frobenius manifolds and their connection to the integrable hierarchies. In particular, ...
Added: November 19, 2026
FLowRA: Flow-Guided Rank Allocation for Parameter-Efficient Fine-Tuning of Deep Neural Networks
Aleksei Samarin, Nazarenko A., Kotenko E. et al., Machine Learning and Knowledge Extraction 2026 Vol. 8 No. 11 Article 389
Low-rank adaptation (LoRA) is widely used for parameter-efficient fine-tuning, yet uniform rank assignment ignores the varying contribution of layers to a downstream task. Adaptive methods such as AdaLoRA allocate ranks via gradient and singular-value importance, but they do not exploit the representation change induced by the task. We introduce FLowRA, a calibration-based rank-allocation framework that ...
Added: November 19, 2026
Uniqueness of addition in Schrödinger algebras
Sosnov G., / Series arXiv "math". 2026.
We obtain a criterion for the uniqueness of addition in Schrödinger Lie algebras, applicable to both bijections and injections. This allows us to construct the first example of a Lie algebra with unique addition and a non-trivial center over a field of characteristic zero. Furthermore, a necessary and sufficient condition is established for the Schrödinger ...
Added: November 19, 2026
Uniqueness of addition in Lie rings gl_n(K) and sl_n(K)
Sosnov G., / Series math "arxiv.org". 2026.
We prove that for any Lie ring R and any commutator-preserving bijection α:gln(K)→R, the map α is additive on sln(K), where n≥2 and K is an arbitrary field. Using this result we find criteria for Lie rings gln(K) and sln(K) to be unique addition. We also show that any commutator-preserving injection of Lie rings β:sl2(K)→S ...
Added: November 19, 2026
Machine Learning for Astrophysics 2024
Springer, 2026.
This proceedings book reviews the state of the art in the exploitation of machine learning techniques for the astrophysics community and gives the reader a complete overview of the field. The contributed chapters allow the reader to easily digest the material through balanced theoretical and numerical methods and tools with applications in different fields of ...
Added: November 19, 2026
Approximation of Multivariate Time Series in Astronomy Using Vector Gaussian Processes
Semenikhin T. A., Kornilov M., Pruzhinskaya M. V., Moscow University Physics Bulletin 2025 Vol. 80 No. S1 P. S204–S207
In astronomy, it is often necessary to approximate sparse vector functions, such as multiband light curves of transient objects. Traditional methods typically treat each photometric band independently, ignoring interband correlations and thus failing to fully exploit the available multiband information in sparsely sampled datasets. We propose a vector Gaussian process (GP) framework that models multi-band ...
Added: November 19, 2026
Anomaly detection in Fink: I. Discovery, follow-up, and classification of unusual sources
Pruzhinskaya M. V., Kornilov M., Dodin A. V. et al., Astronomy and Astrophysics 2026 Vol. 715 P. 1–18
Context. Modern wide-field time-domain surveys produce alert streams whose scientific potential is often concentrated in rare and unusual events. Efficient discovery therefore requires automated pipelines to be combined with rapid expert validation and follow-up. Aims. We present the first-year performance of the anomaly detection (AD) pipeline operating within the Fink broker on the Zwicky Transient ...
Added: November 19, 2026
Supernova scores for active anomaly detection
Semenikhin T. A., Kornilov M.V., Pruzhinskaya M. V. et al., Astronomy and Computing 2026 Vol. 56 Article 101126
Large time-domain sky surveys generate extensive multi-year catalogs of light curves in which scientifically valuable transients, such as supernovae (SNe), are vastly outnumbered by artifacts and routine star variability. While supervised machine learning models can efficiently filter known classes, they struggle with extreme class imbalance and may overlook rare or novel events. Conversely, unsupervised anomaly ...
Added: November 19, 2026
Soliton turbulence within the modified Benjamin–Bona–Mahony equation
Flamarion M. V., Pelinovsky E., Physica D: Nonlinear Phenomena 2027 Vol. 500 Article 135452
In this work, we investigate soliton turbulence in the modified Benjamin–Bona–Mahony (mBBM) equation. A key advantage of this model is that it admits solitary wave solutions of both polarities while also being interpretable as a perturbation of the integrable modified Korteweg–de Vries (mKdV) equation. This framework enables a direct comparison of the main properties of soliton turbulence in ...
Added: November 18, 2026
Топология 3-многообразий, допускающих НМС-потоки с единственной седловой орбитой
Yagilev A., Pochinka O., Shubin D., Математический сборник 2026 Т. 217 № 11 С. 130–144
Рассматриваются неособые потоки Морса-Смейла (НМС-потоки) на замкнутых ориентируемых 3-многообразиях $M^3$, в предположении, что среди периодических орбит ровно одна седловая. Устанавливается, что  многообразие $M^3$ допускает такой поток  тогда и только тогда, когда оно гомеоморфно  линзовому пространству, связной сумме линзовых пространств или многообразию Зейферта вида $M(\mathbb S^2, (p_1,q_1), (p_2,q_2), (p_3,q_3))$. ...
Added: November 17, 2026
Active learning of collinear magnetic Moment Tensor Potentials using the spin-MLIP package from soft-constrained spin-polarized DFT calculations: a case study of Fe-Pd
Burov A., Котыхов А. С., Aksyonov D. et al., Computer Physics Communications 2027 Vol. 330 Article 110458
Explicit incorporation of magnetic degrees of freedom in machine-learning interatomic potentials (magnetic MLIPs) plays a crucial role in the correct description of magnetic materials and their properties. An important ingredient for fitting of magnetic MLIPs is spin-polarized density functional theory (DFT) calculations with non-equilibrium magnetic moments, i.e. DFT calculations with constraints on magnetic moments. In this study, we ...
Added: November 17, 2026
Toward reliable false discovery rate control in classification problems under distribution shift
Kertesz-Farkas A., Andrey B., Plos One 2026 Vol. 21 No. 11 P. 1–20
Background Domain shifts or batch effects can significantly degrade the performance of machine learning-based classifiers in software production without any warning. This can particularly be problematic in medical applications which involve human lives. The shift changes the shape of the prediction score distribution of the test samples compared to that of the training samples; hence, decision ...
Added: November 17, 2026
The Implementability of Liberalism
Hermida Rivera H., Public Choice 2025 Vol. 203 P. 493–501
This note shows that under the unrestricted domain, there exists a choice liberal and Nash implementable social choice rule if and only if there are at least three players and the outcome set is at least twice as large as the player set. A social choice rule is choice liberal if and only if for ...
Added: September 22, 2026
The punctuality stability of the Nash equilibrium: the advantage of a late player in potential and aggregative games
Gusev V., Operational Research 2027 Vol. 27 Article 8
In a Nash equilibrium, no player can gain by unilaterally deviating. In many practical settings, however, players can also choose when to act, and delaying may be profitable because it allows a player to move last and respond to others (for example, waiting for competitors to announce prices before setting one’s own). We ask whether ...
Added: August 11, 2026
Two-Person Positive Shortest Path Games Have Nash Equilibria in Pure Stationary Strategies
Boros E., Elbassioni K., Gurvich V. et al., Dynamic Games and Applications 2026 Vol. 16 P. 1097–1115
We prove that every finite two-person shortest path game, where the local cost of every move is positive for each player, has a Nash equilibrium (NE) in pure stationary strategies, which can be computed in polynomial time. We also extend the existence result to infinite graphs with finite outdegrees. Moreover, our proof gives that a ...
Added: February 22, 2026
More on discrete convexity
Gurvich V., Naumova M., / Series "Working papers by Cornell University". 2024.
In several recent papers some concepts of convex analysis were extended to discrete sets. This paper is one more step in this direction. It is well known that a local minimum of a convex function is always its global minimum. We study some discrete objects that share this property and provide several examples of convex ...
Added: August 19, 2024
On Nash-solvability of n-person graphical games under Markov and a-priori realizations
Gurvich V., Naumova M., Annals of Operations Research 2023 No. 336 P. 1905–1927
Added: August 7, 2024
Price oligopoly with differentiated product and dependence of total demand on the bottom price
Филатов А. Ю., / Series 02:43:16 "CEST". 2023.
The paper proposes a game theory model of price oligopoly with a heterogeneous product, where total demand depends linearly on the minimum market price. This model develops the Bertrand oligopoly for the case of imperfect price elasticity of demand. The most interesting result is an asymmetric Nash equilibrium with different prices and sales in the ...
Added: January 10, 2024
Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles
Gurvich V., Naumova M., Discrete Applied Mathematics 2023 Vol. 340 P. 53–68
In 1975 the first author proved that every finite tight two-person game form g is Nashsolvable, that is, for every payoffs u and w of two players the obtained normal form game (g; u,w) has a Nash equilibrium (NE) in pure strategies. Several proofs of this theorem were obtained later. Here we strengthen the result and give a ...
Added: September 8, 2023
Модель двухуровневой межгрупповой конкуренции
Samoylenko I., Кулешов И. В., Райгородский А. М., Компьютерные исследования и моделирование 2023 Т. 15 № 2 С. 355–368
At the middle of the 2000-th, scientists studying the functioning of insect communities identified four basic patterns of the organizational structure of such communities. (i) Cooperation is more developed in groups with strong kinship. (ii) Cooperation in species with large colony sizes is often more developed than in species with small colony sizes. And small-sized ...
Added: July 28, 2023
Cooperative Game-Theoretic Models of the Cournot Oligopoly
Korolev A. V., Ougolnitsky G. A., International Game Theory Review 2023 Vol. 25 No. 2 Article 2350004
In this paper, we build and investigate cooperative games with different characteristic functions (von Neumann–Morgenstern, Petrosyan–Zaccour, Gromova–Petrosyan) on the  base of symmetrical Cournot oligopoly game-theoretic models in normal form. We find Nash and Stackelberg equilibria and cooperative solutions for nonsymmetrical Cournot oligopoly game-theoretic models in normal form. Also, we build and investigate coop27 erative three-player games with the same characteristic ...
Added: January 26, 2023
Lexicographically maximal edges of dual hypergraphs and Nash-solvability of tight game forms
Gurvich V., Naumova M., Annals of Mathematics and Artificial Intelligence 2022
We prove a new property of dual hypergraphs and derive from it Nash-solvability of the corresponding (tight) game forms. This result is known since 1975, but its new proof is much simpler. ...
Added: December 10, 2022
On Nash Equilibrium in Repeated Hierarchical Games
Pankratova Y., Petrosyan L., , in: Stability and Control Processes: Proceedings of the 4th International Conference Dedicated to the Memory of Professor Vladimir Zubov.: Cham: Springer, 2022. Ch. 65 P. 447–455.
Added: June 5, 2022
Transition Dynamics in a Network Game with Heterogeneous Agents: the Stochastic Case
Korolev A. V., Automation and Remote Control 2022 Vol. 13 No. 1 P. 483–501
Stochastic parameters are introduced into a model of network games with production and knowledge externalities. The model was formulated by V. Matveenko and A. Korolev and generalizes Romer’s two-period model. The agents’ productivities have both deterministic and Wiener components. The research represents the dynamics of a single agent and the dynamics in a triangle that ...
Added: April 22, 2022
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit