HSE Researchers Prove the Existence of Nash Equilibrium for a New Class of Problems in Game Theory
Researchers at HSE University's St Petersburg School of Economics and Management have been exploring methods for the efficient allocation of resources in systems involving multiple players. The scientists have proven the existence of strategies for optimal decision-making in competition for limited, discrete resources in four different cases. The developed mathematical model can be applied in various fields, ranging from education and medicine to managing networks and computing power. The paper has been published in Games and Economic Behaviour.
There is ongoing competition for various resources in the world, and individuals must choose the optimal strategy to acquire them. Prospective students must choose which school to apply to, companies compete for the best projects, and gym-goers rush to claim an available machine.
Scientists strive to find methods that help systems with many participants operate efficiently, avoiding overloads and the irrational use of resources. These problems can be translated into a mathematical model where agents make decisions based on potential benefits, available resources, and their capabilities. In game theory, such models are analysed through the lens of Nash equilibrium—a state where no participant wishes to change their choice, as doing so would not lead to increased benefits.
Researchers at HSE University's St Petersburg School of Economics and Management have proven the existence of Nash equilibrium in certain types of games involving indivisible (ie discrete) resources, such as airplane seats, apartments, library books, or school placements. These resources are considered discrete because they cannot be divided—for instance, you cannot take half a window seat and half an aisle seat on a plane.
To demonstrate the existence of Nash equilibrium, the researchers developed a mathematical model in which each participant (agent) selects one of the available resources. Participants aim to gain the greatest benefit and maximise their share of the resource. This creates a system where an agent's choice is influenced not only by the resource itself, but also by the number of other participants selecting the same resource.
In the model, each participant is assigned a certain weight, which plays a significant role. For example, when prospective students select a school, they consider factors such as the quality of the educational programme, the school's accessibility, its reputation, and more. They assess the value of the resource and their ability to acquire it. Weight represents the agent's own capabilities in relation to a specific resource.
The researchers proved that a Nash equilibrium, beneficial for all agents, exists in four cases. The first case occurs when the agent's weight is independent of the resource, while the values of the resources vary. For example, when an applicant with the highest USE score chooses from several schools with varying rankings.
In the second case, the agent's weight depends on the resource, but the values of all resources are the same, eg an applicant wins an internal olympiad at a top school and gains priority for admission.
In the third case, an agent's weight depends on the resource, the values of the resources vary, but there are only two resources: eg an applicant can easily enrol in a lesser-known school by winning an internal olympiad, or they can compete for a spot at a prestigious school on equal terms with others.
The fourth case is special. If the number of participants in the system is large—more than 20 agents—the system tends to approach equilibrium but does not fully reach it. This is an asymptotic result that accurately reflects reality. In such cases, each participant acts nearly optimally. Even if the strategy is changed, the situation cannot be significantly improved.
Vasily Gusev
'We did not immediately find a proof for the fourth case; it was suggested by a student participating in an internship programme run by our laboratory. His name is Mikhail Reshetov, and he became our co-author,' says Vasily Gusev, Senior Research Fellow at the International Laboratory of Game Theory and Decision Making at HSE Campus in St Petersburg and co-author of the paper.
According to the researchers, the developed mathematical model opens up opportunities for improving resource allocation systems across various fields, from education and medicine to the distribution of computing power and management of large networks.
Alexander Nesterov
'We have shown that competition for resources does not lead to chaos, but instead stabilises without external interference. We have mathematically proven that if agents are given the freedom of choice, each will find a profitable outcome for themselves,' comments Alexander Nesterov, Head of the International Laboratory of Game Theory and Decision Making at HSE Campus in St Petersburg and co-author of the paper.
See also:
Researchers at HSE Centre for Language and Brain Reveal Key Factors Determining Language Recovery in Patients After Brain Tumour Resection
Alina Minnigulova and Maria Khudyakova at the HSE Centre for Language and Brain have presented the latest research findings on the linguistic and neural mechanisms of language impairments and their progression in patients following neurosurgery. The scientists shared insights gained from over five years of research on the dynamics of language impairment and recovery.
Neuroscientists Reveal Anna Karenina Principle in Brain's Response to Persuasion
A team of researchers at HSE University investigated the neural mechanisms involved in how the brain processes persuasive messages. Using functional MRI, the researchers recorded how the participants' brains reacted to expert arguments about the harmful health effects of sugar consumption. The findings revealed that all unpersuaded individuals' brains responded to the messages in a similar manner, whereas each persuaded individual produced a unique neural response. This suggests that successful persuasive messages influence opinions in a highly individual manner, appearing to find a unique key to each person's brain. The study findings have been published in PNAS.
Russian Scientists Improve Water Purification Membranes Using Metal Ions
Researchers have proposed using polymer membranes modified with copper, zinc, and chromium metal ions for water purification. These polymers were used for the first time in water purification via electrodialysis. Copper-based membranes demonstrated record selectivity for monovalent ions, opening new possibilities for sustainable water recycling. The study has been published in the Journal of Membrane Science.
Independent Experts More Effective Than Collective Expertise in Decision-Making Under Uncertainty
A collaborative study by Sergey Stepanov, Associate Professor at the HSE Faculty of Economic Sciences, and experts from INSEAD Business School and NYU Shanghai, indicates that in making decisions under high uncertainty, where it is unclear which choice is superior, advice from independent experts may be more beneficial than a collective opinion from a group of experts. The study has been published in Games and Economic Behavior.
HSE Researchers Uncover Causes of Gender Pay Gap among Recent University Graduates in Russia
A study conducted at HSE University shows that despite having the same education and similar starting conditions, the pay gap between male and female recent graduates can be as high as 22%. This is partly because female students often choose less lucrative fields and also because they tend to seek jobs in sectors that offer lower pay but are perceived to have more stable and safer working conditions.
Scientists at HSE University Devise More Accurate Method for Predicting the Electrical Conductivity of Electrolyte Solutions
Researchers at HSE MIEM have developed a model for calculating the electrical conductivity of aqueous electrolyte solutions; for the first time, it considers the spatial distribution of ion charges instead of assuming their localisation at a single point. The model remains effective even at high electrolyte concentrations and across a wide temperature range. This breakthrough will contribute to the development of more efficient batteries and enable the calculation of electrical conductivity without the need for experimental testing. The study has been published in the Journal of Chemical Physics.
Russian Scientists Integrate Microdisk Laser and Waveguide on a Single Substrate
A group of Russian scientists led by Professor Natalia Kryzhanovskaya at HSE Campus in St Petersburg has been researching microdisk lasers with an active region based on arsenide quantum dots. For the first time, researchers have successfully developed a microdisk laser coupled with an optical waveguide and a photodetector on a single substrate. This design enables the implementation of a basic photonic circuit on the same substrate as the radiation source (microlaser). In the future, this will help speed up data transfer and reduce equipment weight without compromising quality. The study results have been published in Semiconductors.
Scientists Disprove Bunkbed Conjecture
Mathematicians from Russia, including two HSE graduates, have disproven a well-known mathematical conjecture that, despite lacking solid proof, had been considered valid for 40 years. The ‘Bunkbed Conjecture’ belongs to percolation theory—a branch of mathematics that studies the formation of connected structures in independent environments.
Men Behind the Wheel: Three Times More Violations and Accidents than Women
Men are three times more likely than women to commit traffic violations while driving and to be involved in accidents. Moreover, they are more likely to create situations on the road that are highly dangerous to others. Men are also twice as likely to drive under the influence and nearly one-third more likely to receive a prison sentence for reckless driving. Perhaps it comes down to cultural norms and the different attitudes men and women have toward driving. These are the conclusions reached by Anton Kazun, Assistant Professor at the HSE Faculty of Economic Sciences, and Research Assistant Mikhail Belov.
HSE Scientists Discover How to Predict Charitable Behaviour Through Physiological Reactions
Researchers at the HSE Institute for Cognitive Neuroscience have investigated how the emotional impact of advertising affects the amount people willing to donate to support animal welfare. To accomplish this, the researchers measured physiological responses such as heart rate, electrodermal activity, and facial expressions in individuals viewing various photos of dogs. The findings indicate that willingness to donate is most accurately predicted by heart rate and facial muscle activation. The study has been published in Social Psychology.