اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFriendly frogs, stable marriage, and the magic of invariance
237
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce a two-player game involving two tokens located at points of a fixed set. The players take turns to move a token to an unoccupied point in such a way that the distance between the two tokens is decreased. Optimal strategies for this game and its variants are intimately tied to Gale-Shapley stable marriage. We focus particularly on the case of random infinite sets, where we use invariance, ergodicity, mass transport, and deletion-tolerance to determine game outcomes.
قيم البحث
اقرأ أيضاً
Let $W^{(n)}$ be the $n$-letter word obtained by repeating a fixed word $W$, and let $R_n$ be a random $n$-letter word over the same alphabet. We show several results about the length of the longest common subsequence (LCS) between $W^{(n)}$ and $R_n
$; in particular, we show that its expectation is $gamma_W n-O(sqrt{n})$ for an efficiently-computable constant $gamma_W$. This is done by relating the problem to a new interacting particle system, which we dub frog dynamics. In this system, the particles (`frogs) hop over one another in the order given by their labels. Stripped of the labeling, the frog dynamics reduces to a variant of the PushTASEP. In the special case when all symbols of $W$ are distinct, we obtain an explicit formula for the constant $gamma_W$ and a closed-form expression for the stationary distribution of the associated frog dynamics. In addition, we propose new conjectures about the asymptotic of the LCS of a pair of random words. These conjectures are informed by computer experiments using a new heuristic algorithm to compute the LCS. Through our computations, we found periodic words that are more random-like than a random word, as measured by the LCS.
A two-type version of the frog model on $mathbb{Z}^d$ is formulated, where active type $i$ particles move according to lazy random walks with probability $p_i$ of jumping in each time step ($i=1,2$). Each site is independently assigned a random numbe
r of particles. At time 0, the particles at the origin are activated and assigned type 1 and the particles at one other site are activated and assigned type 2, while all other particles are sleeping. When an active type $i$ particle moves to a new site, any sleeping particles there are activated and assigned type $i$, with an arbitrary tie-breaker deciding the type if the site is hit by particles of both types in the same time step. We show that the event $G_i$ that type $i$ activates infinitely many particles has positive probability for all $p_1,p_2in(0,1]$ ($i=1,2$). Furthermore, if $p_1=p_2$, then the types can coexist in the sense that $mathbb{P}(G_1cap G_2)>0$. We also formulate several open problems. For instance, we conjecture that, when the initial number of particles per site has a heavy tail, the types can coexist also when $p_1 eq p_2$.
The Stable Marriage Problem is to find a one-to-one matching for two equally sized sets of agents. Due to its widespread applications in the real world, especially the unique importance to the centralized match maker, a very large number of questions
have been extensively studied in this field. This article considers a generalized form of stable marriage problem, where different numbers of men and women need to be matched pairwise and the emergence of single is inevitable. Theoretical analysis and numerical simulations confirm that even small deviations from equal number of two sides can have a large impact on matching solution of Gale-Shapley Algorithm. These results provide insights to many of the real-world applications when matching two sides with unequal number.
We study the variant of the stable marriage problem in which the preferences of the agents are allowed to include indifferences. We present a mechanism for producing Pareto-stable matchings in stable marriage markets with indifferences that is group
strategyproof for one side of the market. Our key technique involves modeling the stable marriage market as a generalized assignment game. We also show that our mechanism can be implemented efficiently. These results can be extended to the college admissions problem with indifferences.
Propellers are features in Saturns A ring associated with moonlets that open partial gaps. They exhibit non-Keplerian motion (Tiscareno 2010); the longitude residuals of the best-observed propeller, Bleriot, appear consistent with a sinusoid of perio
d ~4 years. Pan and Chiang (2010) proposed that propeller moonlets librate in frog resonances with co-orbiting ring material. By analogy with the restricted three-body problem, they treated the co-orbital material as stationary in the rotating frame and neglected non-co-orbital material. Here we use simple numerical experiments to extend the frog model, including feedback due to the gaps motion, and drag associated with the Lindblad disk torques that cause Type I migration. Because the moonlet creates the gap, we expect the gap centroid to track the moonlet, but only after a time delay t_diff, the time for a ring particle to travel from conjunction with the moonlet to the end of the gap. We find that frog librations can persist only if t_diff exceeds the frog libration period P_lib, and if damping from Lindblad torques balances driving from co-orbital torques. If t_diff << P_lib, then the libration amplitude damps to zero. In the case of Bleriot, the frog resonance model can reproduce the observed libration period P_lib ~ 4 yr. However, our simple feedback prescription suggests that Bleriots t_diff ~ 0.01P_lib, which is inconsistent with the observed libration amplitude of 260 km. We urge more accurate treatments of feedback to test the assumptions of our toy models.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
