Strategic Voting in the Context of Stable-Matching of Teams

Leora Schmerler, Noam Hazon, Sarit Kraus

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

In the celebrated stable-matching problem, there are two sets of agents M and W, and the members of M only have preferences over the members of W and vice versa. It is usually assumed that each member of M and W is a single entity. However, there are many cases in which each member of M or W represents a team that consists of several individuals with common interests. For example, students may need to be matched to professors for their final projects, but each project is carried out by a team of students. Thus, the students first form teams, and the matching is between teams of students and professors. When a team is considered as an agent from M or W, it needs to have a preference order that represents it. A voting rule is a natural mechanism for aggregating the preferences of the team members into a single preference order. In this paper, we investigate the problem of strategic voting in the context of stable-matching of teams. Specifically, we assume that members of each team use the Borda rule for generating the preference order of the team. Then, the Gale-Shapley algorithm is used for finding a stable-matching, where the set M is the proposing side. We show that the single-voter manipulation problem can be solved in polynomial time, both when the team is from M and when it is from W. We show that the coalitional manipulation problem is computationally hard, but it can be solved approximately both when the team is from M and when it is from W.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings
المحررونPanagiotis Kanellopoulos, Maria Kyropoulou, Alexandros Voudouris
ناشرSpringer Science and Business Media Deutschland GmbH
الصفحات562-579
عدد الصفحات18
رقم المعيار الدولي للكتب (المطبوع)9783031157134
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2022
الحدث15th International Symposium on Algorithmic Game Theory, SAGT 2022 - Colchester, بريطانيا
المدة: ١٢ سبتمبر ٢٠٢٢١٥ سبتمبر ٢٠٢٢

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت13584 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference15th International Symposium on Algorithmic Game Theory, SAGT 2022
الدولة/الإقليمبريطانيا
المدينةColchester
المدة١٢/٠٩/٢٢١٥/٠٩/٢٢

بصمة

أدرس بدقة موضوعات البحث “Strategic Voting in the Context of Stable-Matching of Teams'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا