?
Generalized matchings for preferences represented by simplest semiorder: Stability and pareto optimality
Automation and Remote Control. 2014. Vol. 75. No. 6. P. 1069–1077.
Sofya Kisel'gof
We consider an extension of the classical model of generalized Gale-Shapley matchings. The model describes a two-sided market: on one side, universities each of which has a restriction on the number of enrolled students; on the other side, applicants each of which can get a single place in the university. Both applicants and universities have preferences with respect to the desired distribution. We assume that each applicant constructs a linear order on the set of desired universities, and each university has preferences that are simplest semiorders For this modification, we show that a stable matching always exists. Moreover, we formulate necessary and sufficient conditions for Pareto optimality of the stable matching.
Language:
English
Publication based on the results of:
Kanunnikov A., Promyslov V., Vassilieva E., Electronic Journal of Combinatorics 2024 Vol. 31 No. 3 Article P3.6
Introduced by Goulden and Jackson in their 1996 paper, the matchings-Jack conjecture and the hypermap-Jack conjecture (also known as the b-conjecture) are two major open questions relating Jack symmetric functions, the representation theory of the symmetric groups and combinatorial maps. They show that the coefficients in the power sum expansion of some Cauchy sum for ...
Added: August 7, 2026
Ponomarenko A., / Series Computer Science "arxiv.org". 2025.
This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection ...
Added: July 30, 2026
Zhuravleva T., Afanasev K., Engelmann J. et al., / Series "SSRN Working Paper Series". 2026.
Extortionary ("harassment") bribery can persist even when widely condemned, consistent with a coordination problem sustained by beliefs about what others do and what others consider acceptable. We study whether a minimal institutional featurethe presence of a third-party monitor empowered to punish-shifts (i) normative expectations about extortion and compliance and (ii) empirical expectations about their prevalence. ...
Added: July 22, 2026
Loubenets E. R., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.
In many quantum applications it is important to know whether or not a Bell nonlocal two-qudit state exhibits its nonlocality under correlation scenarios with some given numbers S1,S2≥1 of generalized quantum measurements at two sites. In the present article, we find analytically a new general locality condition sufficient for a nonseparable Werner state with a ...
Added: July 21, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Chow polylogarithms are some special functions arising in explicit description of the Beilinson regulator map. The most interesting functional equation for this function reflects its vanishing on the boundary in the Bloch's cycle complex. We show that this functional equation formally follows from more simple ones, namely skew-symmetry, functoriality and multiplicativity.
To prove this, we study ...
Added: July 16, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Let K be a field of characteristic zero. We prove that its motivic cohomology in degree m−1 and weight m is rationally isomorphic to the cohomology of the polylogarithmic complex. This gives a partial extension of A. Suslin theorem describing the indecomposable K3 of a field. ...
Added: July 16, 2026
Panov V., Ryabchenko A., / Series arXiv "stat.ME". 2026. No. 2607.05048.
This paper investigates the problem of statistical inference for a mixture distribution consisting of a discrete and a continuous component, with a particular focus on the class of rational-infinitely divisible distributions. We consider non-parametric estimation of both components of the mixture as well as the quasi-L{é}vy measure, assuming that the mixture belongs to the class ...
Added: July 9, 2026
Mishin A., Guerrieri L., Kim J., / Series 2026-042 "Finance and Economics Discussion Series (FEDS)". 2026.
Within narrowly defined industries, the most productive firms produce far more than the least productive from the same inputs, and this dispersion widens in downturns. We build a tractable representative-agent model in which financial frictions—adverse selection and moral hazard—make firms sort endogenously into lenders, strategic defaulters, and producers. As credit conditions vary, the resulting misallocation ...
Added: June 28, 2026
Власов С. А., Nevalennyi M., Сафиулин Р. Р. et al., / Банк России. Серия Аналитическая записка "Материалы Банка России". 2026.
В аналитической записке обсуждается долгосрочно устойчивый уровень цены на российскую нефть. Это тот уровень, к которому цена нефти, вероятнее всего, будет тяготеть в долгосрочной перспективе. Потребность в его определении возникает по нескольким причинам. Во-первых, цена на нефть остается одним из ключевых экономических показателей российской экономики, определяющих экспорт, обменный курс рубля, прибыль, доходы и расходы бюджета, ...
Added: June 27, 2026
Глазова А. М., Nevalennyi M., Синяков А. А., / Банк России. Серия Препринты Банка России "Серия докладов об экономических исследованиях". 2025. № 154.
The paper proposes a graphical model of a small open economy. The dynamics of the graphical model is then illustrated using impulse responses from the corresponding formal semi-structural model (QPM model). The authors have several goals in preparing this description of the graphical macroeconomic model. The first goal of the paper is to present an adapted ...
Added: June 27, 2026
Mishin A., Guerrieri L., Canzoneri M. et al., / Series 2026-042 "Finance and Economics Discussion Series (FEDS)". 2026.
Added: June 27, 2026
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Piontkovski D., / Series arXiv "math". 2025.
If a symmetric multilinear algebra is weakly nil, then it is Engel. This result may be regarded as an infinite-dimensional analogue of the well-known Jacobian theorem, which states that if a polynomial mapping has a polynomial inverse, then its Jacobian matrix is invertible. This refines a theorem of Gerstenhaber and partially answers a question posed ...
Added: June 23, 2026
Konakov V., Kucher D., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.
In this paper, we construct strong approximations for discrete-time Markov chains weakly converging to continuous diffusion processes, as well as for their perturbed counterparts. Under the assumption of bounded coefficients, we construct closely coupled versions of these processes on a shared probability space. In particular, for both non-degenerate and degenerate cases, we maximize the probability ...
Added: June 11, 2026
Bogatyrev R., Sandomirskaia M., / NRU Higher School of Economics. Series EC "Economics". 2026. No. 19(1).
This work develops a tractable model of price competition in fragmented markets where consumers consider both local and distant varieties, with cross-regional purchases subject to stochastic costs. Global competition and full localization emerge as polar cases; hybrid competition is not merely intermediate and exhibits distinctive features such as an endogenous price ceiling and non-monotonic entry ...
Added: June 11, 2026
Kravtsova M., Musaev A. U., Welzel C., / Series "SSRN Working Paper Series". 2026.
Elaborating on Welzel et al.'s "Cool Water Theory," our study zooms into the more limited (albeit still varied) framework conditions of Russia's huge territory. Within Russia's confines, we examine how the combination of moderately cool seasons with steady rain (i.e., Cool Water) affects sub-national areas' contemporary societal progress in two modernization indicators: material prosperity in ...
Added: June 3, 2026
Синяков А. А., Зверева В., Шелованова Т. И., / Центральный банк Российской Федерации. Серия 132 / 2024 "Серия докладов об экономических исследованиях". 2024. № 132.
At the end of 2023, Russia updated its Strategy for Improving Financial Literacy and Developing Financial Culture Until 2030. Unlike the previous strategy, the current strategic goals include not only financial literacy but also financial culture. ‘Culture’ is normative and socially preferred behaviour. The updated strategy brings into focus the relationship between financial literacy and responsible financial behaviour. To explore this relationship, the authors rely on data from the All-Russian Survey of Consumer Finance (2020 and 2022). Socially ...
Added: June 1, 2026
Vorchik A., / SSRN. Серия Social Science Research Network "Social Science Research Network". 2026.
This work is devoted to a theoretical explanation of the Easterlin paradox, according to which long-term economic growth does not make average level of people's happiness increasing. By happiness, we mean the intensity of emotions people experience while comparing their new income with its expected value, or the target income with its original value. In the first case, ...
Added: May 31, 2026
Дистель Р., М.: МЦНМО, 2024.
С момента выхода первого издания на английском языке в 1997 году книга известного математика, профессора Гамбургского университета Рейнгарда Дистеля стала основным учебником по теории графов во многих университетах, выдержав к настоящему времени пять изданий, перевод последнего из которых предлагается читателю. Уникальность учебника в его глубине при относительно небольшом объёме: в книге найдутся задачи как доступные ...
Added: January 25, 2026
Beaudou L., Echeverría H., Foucaud F. et al., Procedia Computer Science 2025 Vol. 273 P. 86–93
We prove that the recognition of exact cubes of trees can be done in polynomial time. More precisely, the exact distance power of a graph is a refinement of the more usual notion of graph power. Given a graph G and a positive integer p, the exact distance pth power of G is the graph G#p on the same vertex set where two vertices ...
Added: December 3, 2025
Karpov A., Automation and Remote Control 2022 Vol. 83 P. 1329–1354
A survey of papers on practically significant restrictions on the preference profile of a collective is carried out, including single-peaked preferences, group-separable preferences, preferences with the single-crossing property, and Euclidean preferences and their extensions. Both ordinal and dichotomous preferences are considered. For structured preferences, we present characterization in terms of forbidden subprofiles and the probability ...
Added: October 31, 2022
А. В. Карпов, Автоматика и телемеханика 2022 № 9 С. 3–35
Проведен обзор работ по практически значимым ограничениям на профиль предпочтений коллектива: однопиковые предпочтения, сепарабельные предпочтения, предпочтения со свойством единственного пересечения, евклидовы предпочтения и их расширения. Рассмотрены как ординальные, так и дихотомические предпочтения. Для структурированных предпочтений представлена характеризация через запрещенные подпрофили и вероятность появления профиля с заданным свойством. Для сепарабельных предпочтений описан алгоритм построения иерархического дерева. ...
Added: September 15, 2022
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2019.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Babenko M. A., Artamonov S., , in: 28th International Symposium on Algorithms and Computation, ISAAC 2017Vol. 92.: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1–12.
Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m ...
Added: March 1, 2018