DOI: https://doi.org/10.1016/j.econlet.2026.112936
تاريخ النشر: 2026-03-11
المؤلف: Josué Ortega وآخرون
الموضوع الرئيسي: نظرية الألعاب وأنظمة التصويت
نظرة عامة
في هذه الدراسة، نقوم بتحليل توزيع الحسد ضمن أسواق المطابقة العشوائية باستخدام خوارزمية القبول المؤجل (DA). من خلال استخدام تقنيات من الاحتمالات التطبيقية، نستنتج العدد المتوقع من الوكلاء المقترحين الذين لا يحسدهم أحد، وكذلك أولئك الذين لا يحسدون أحدًا. يتم إنشاء تعبير دقيق للسوق المحدود للأول من خلال علاقته بمشكلة جامع القسائم، بينما يتم تقديم حدود تقاربية للأخير.
علاوة على ذلك، نقارن هذه النتائج مع النتائج تحت نظام الدكتاتورية التسلسلية العشوائية (RSD). من الجدير بالذكر أنه بينما يقوم RSD بشكل مستمر بتعيين نسبة ثابتة من الوكلاء إلى اختيارهم الأعلى، فإن كل من DA و RSD ينتجان توقعًا بالضبط لعدد الوكلاء المقترحين الذين يبقون غير محسودين وهو $H_n$. تشير تحليلاتنا إلى أن هؤلاء الوكلاء المقترحين، الذين لا يمكن تحسينهم، يمثلون نسبة متناقصة من السوق الكلي مع زيادة حجمه.
مقدمة
في هذا القسم، يستكشف المؤلفون مفهوم المطابقات المستقرة في اختيار المدارس، مع التركيز بشكل خاص على آثار الحسد المبرر مقابل الحسد الكلي في سياق آلية القبول المؤجل (DA). يبرزون أهمية فهم فئتين محددتين من الطلاب: أولئك الذين لا يحسدون أحدًا وأولئك الذين لا يحسدهم أحد. يعتبر هذا التحليل حاسمًا لعدة أسباب: لا ينتج DA عادة مطابقة فعالة من حيث باريتو، وتكون الرؤى حول توزيع الحسد تحت DA محدودة مقارنة بالآليات الفعالة. بالإضافة إلى ذلك، ترتبط نسبة الطلاب الذين لا يحسدون أحدًا بأولئك المعينين لبدائلهم المفضلة، مما يوفر رؤى رفاهية قيمة لصانعي السياسات.
يهدف المؤلفون إلى قياس عدد الطلاب في هاتين الفئتين ضمن أسواق المطابقة العشوائية المستقلة والموزعة بشكل متطابق (i.i.d.). يقدمون تعبيرًا دقيقًا عن العدد المتوقع من الطلاب الذين لا يحسدهم أحد ويقدمون توصيفًا تقاربيًا لأولئك الذين لا يحسدون أحدًا. يستفيد تحليلهم من العلاقة بين التنفيذ المتسلسل لـ DA ومشكلة جامع القسائم، مما يقارن في النهاية نتائجهم بتلك المستمدة من آلية الدكتاتورية التسلسلية العشوائية (RSD). يساعد هذا المقارنة في وضع النتائج في سياقها وتعزيز فهم أداء آلية DA من حيث علاقات الحسد.
النتائج
في هذا القسم، يستكشف المؤلفون سوق مطابقة ثنائية الجانب تتكون من \( n \) وكيل على كل جانب، مع التركيز بشكل خاص على رفاهية الجانب المقترح، الذي يمثل في هذا السياق الطلاب المتقدمين للمدارس. يفترض النموذج أن كل من الطلاب والمدارس لديهم تفضيلات صارمة على المطابقات المحتملة، مع وجود حصة واحدة لكل مدرسة. من خلال استخدام إطار اختيار المدارس العشوائي حيث يتم سحب التفضيلات والأولويات بشكل مستقل وموحد، يهدف المؤلفون إلى استنتاج نتائج قابلة للتحليل تعكس الكفاءة المتوسطة لمختلف آليات المطابقة، كما هو موضح في الأدبيات السابقة.
يبدأ التحليل بتحديد نسبة الطلاب الذين لا يحسدون أي مطابقة لطالب آخر، تليها دراسة الطلاب الذين لا يحسدهم الآخرون. يبني هذا النهج على الدراسات السابقة التي استكشفت جوانب مثل العدد المتوقع من المطابقات المستقرة وآثار السلوك الاستراتيجي ضمن مشاكل المطابقة. من المتوقع أن تسهم النتائج في فهم أعمق لنتائج الرفاهية في سيناريوهات اختيار المدارس، بما يتماشى مع الأبحاث المعتمدة حول مشاكل المطابقة العشوائية.
المناقشة
في هذا القسم، تناقش الورقة العدد المتوقع من الطلاب الذين إما لا يحسدهم أحد أو لا يحسدون أحدًا تحت آلية القبول المؤجل (DA) في مشاكل اختيار المدارس. تؤكد الاقتراح 1 أن العدد المتوقع من الطلاب المعينين لمدارس ذات طلب منخفض، المشار إليه بـ $NE_n$، يساوي العدد الهارموني $H_n$. يستخدم المؤلفون تنفيذًا متسلسلًا لخوارزمية DA، مما يوضح أن عدد المدارس ذات الطلب المنخفض يتوافق مع عدد أنواع القسائم الفردية في مشكلة جامع القسائم الكلاسيكية، مما يؤدي إلى الاستنتاج بأن $NE_n = H_n$. وهذا يعني أنه مع زيادة حجم السوق $n$، تقترب نسبة الطلاب غير المحسودين من الصفر، مما يشير إلى أن عددًا قليلاً جدًا من الطلاب لا يحسدهم أحد حتى في الأسواق الكبيرة.
علاوة على ذلك، تقدم الورقة $EN_n$، العدد المتوقع من الطلاب الذين لا يحسدون أحدًا تحت DA، مقدرة إياه بـ $EN_n \approx n/H_n$. تشير هذه النتيجة، على الرغم من كونها تقاربية، إلى أن عدد الطلاب الذين لا يحسدون أحدًا صغير أيضًا ولكنه أكبر من عدد الطلاب غير المحسودين. يقارن المؤلفون DA مع الدكتاتورية التسلسلية العشوائية (RSD)، كاشفين أن كلا الآليتين تنتجان نفس العدد المتوقع من الطلاب غير المحسودين، $H_n$، على الرغم من اختلاف أدائهما فيما يتعلق بتعيينات الاختيار الأعلى. تختتم المناقشة بتسليط الضوء على ندرة الطلاب الذين لا يمكن تحسينهم وتطرح أسئلة للبحث المستقبلي، مثل قابلية تطبيق نتيجة $H_n$ على آليات أخرى وسلوك هذه الديناميات في الأسواق ذات العديد من الأطراف أو مع تفضيلات مرتبطة.
DOI: https://doi.org/10.1016/j.econlet.2026.112936
Publication Date: 2026-03-11
Author(s): Josué Ortega et al.
Primary Topic: Game Theory and Voting Systems
Overview
In this study, we analyze the distribution of envy within random matching markets utilizing the Deferred Acceptance (DA) algorithm. By employing techniques from applied probability, we derive the expected number of proposing agents who are not envied by anyone, as well as those who do not envy anyone. An exact finite-market expression for the former is established through its relationship with the coupon collector problem, while asymptotic bounds are provided for the latter.
Furthermore, we compare these findings with the outcomes under Random Serial Dictatorship (RSD). Notably, while RSD consistently assigns a fixed fraction of agents to their top choice, both DA and RSD result in an expectation of exactly $H_n$ proposing agents remaining unenvied. Our analysis indicates that these proposing agents, which cannot be improved upon, represent a diminishing fraction of the overall market as its size increases.
Introduction
In this section, the authors explore the concept of stable matchings in school choice, particularly focusing on the implications of justified envy versus total envy in the context of the Deferred Acceptance (DA) mechanism. They highlight the significance of understanding two specific categories of students: those who envy nobody and those who are envied by nobody. This analysis is crucial for several reasons: DA does not typically yield a Pareto-efficient matching, and insights into envy distribution under DA are limited compared to efficient mechanisms. Additionally, the proportion of students who envy nobody correlates with those assigned to their most preferred alternatives, providing valuable welfare insights for policymakers.
The authors aim to quantify the number of students in these two categories within independent and identically distributed (i.i.d.) random matching markets. They present an exact expression for the expected number of students who are not envied by anyone and offer an asymptotic characterization for those who envy nobody. Their analysis leverages the relationship between the sequential implementation of DA and the coupon collector problem, ultimately comparing their findings to those derived from the Random Serial Dictatorship (RSD) mechanism. This comparison serves to contextualize the results and enhance understanding of the DA mechanism’s performance in terms of envy relations.
Results
In this section, the authors investigate a two-sided matching market comprising \( n \) agents on each side, focusing specifically on the welfare of the proposing side, which in this context represents students applying to schools. The model assumes that both students and schools have strict preferences over potential matches, with each school having a quota of one. By employing a random school choice framework where preferences and priorities are drawn independently and uniformly, the authors aim to derive tractable results that reflect the average efficiency of various matching mechanisms, as established in prior literature.
The analysis begins by quantifying the fraction of students who are not envious of any other student’s match, followed by an examination of the students who themselves are not envied by others. This approach builds on previous studies that have explored aspects such as the expected number of stable matchings and the implications of strategic behavior within matching problems. The findings are anticipated to contribute to a deeper understanding of welfare outcomes in school choice scenarios, aligning with the established research on random matching problems.
Discussion
In this section, the paper discusses the expected number of students who are either unenvied or envy nobody under the Deferred Acceptance (DA) mechanism in school choice problems. Proposition 1 establishes that the expected number of students assigned to under-demanded schools, denoted as $NE_n$, equals the $n$-th Harmonic number $H_n$. The authors utilize a sequential implementation of the DA algorithm, demonstrating that the number of under-demanded schools corresponds to the number of singleton coupon types in the classical coupon collector problem, leading to the conclusion that $NE_n = H_n$. This implies that as the market size $n$ increases, the fraction of unenvied students approaches zero, indicating that very few students are unenvied even in large markets.
Furthermore, the paper introduces $EN_n$, the expected number of students who envy nobody under DA, approximating it as $EN_n \approx n/H_n$. This result, while asymptotic, suggests that the number of students who envy nobody is also small but greater than the number of unenvied students. The authors compare DA with Random Serial Dictatorship (RSD), revealing that both mechanisms yield the same expected number of unenvied students, $H_n$, despite differing in their performance regarding top-choice assignments. The discussion concludes by highlighting the rarity of unimprovable students and poses questions for future research, such as the applicability of the $H_n$ result to other mechanisms and the behavior of these dynamics in many-to-one markets or with correlated preferences.