|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On random stable partitions | | Boris Pittel
; | | Date: |
23 May 2017 | | Abstract: | The stable roommates problem does not necessarily have a solution, i.e. a
stable matching. We had found that, for the uniformly random instance, the
expected number of solutions converges to $e^{1/2}$ as $n$, the number of
members, grows, and with Rob Irving we proved that the limiting probability of
solvability is $e^{1/2}/2$, at most. Stephan Mertens’s extensive numerics
compelled him to conjecture that this probability is of order $n^{-1/4}$. Jimmy
Tan introduced a notion of a stable cyclic partition, and proved existence of
such a partition for every system of members’ preferences, discovering that
presence of odd cycles in a stable partition is equivalent to absence of a
stable matching. In this paper we show that the expected number of stable
partitions with odd cycles grows as $n^{1/4}$. However the standard deviation
of that number is of order $n^{3/8}gg n^{1/4}$, too large to conclude that the
odd cycles exist with high probability (whp). Still, as a byproduct, we show
that whp the fraction of members with more than one stable "predecessor" is of
order $n^{-1/4}$. Furthermore, whp the average rank of a predecessor in every
stable partition is of order $n^{1/2}$. The likely size of the largest stable
matching is $n/2-O(n^{1/4+o(1)})$, and the likely number of pairs of unmatched
members blocking the optimal complete matching is $O(n^{3/4+o(1)})$. | | Source: | arXiv, 1705.8340 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER