لایب سان

One of the most actively growing subareas in multi-agent systems is computational social choice theory, which provides a theoretical foundation for preference aggregation and collective decision-making in multi-agent domains. It is concerned with the application of techniques developed in computer science, including complexity analysis and algorithm design, in the study of social choice mechanisms, such as voting. It seeks to import concepts from social choice theory into Artificial Intelligence and computing. People often have to reach a joint decision despite conflicting preferences over the alternatives. This joint decision can be reached by an informal negotiating process or by a carefully specified protocol. Over the course of the past decade or so, computer scientists have also become deeply involved in this study. Within computer science, there is a number of settings where a decision must be made based on the conflicting preferences of multiple parties. The paradigms of computer science give a different and useful perspective on some of the classic problems in economics and related disciplines. A natural and very general approach for deciding among multiple alternatives is to vote on them. Voting is one of the most popular ways of reaching common decisions. As such, the study of elections is an area where fields such as computer science, economics, business, operations research, and political science can be brought together. Social choice theory deals with voting scenarios, in which a set of individuals must select an outcome from a set of alternatives. This book focuses on convergence to pure strategy Nash equilibria in plurality voting games and a number of other positional and non-positional scoring rules. In such games, the voters strategically choose a candidate to vote for, and the winner is determined by the plurality (or other) voting rules. Voters take turns modifying their votes; these manipulations are classified according to the way in which they affect the outcome of the election. The focus is on achieving a stable outcome, taking strategic behaviour into account. A voting profile is in equilibrium, when no voter can change his vote so that his more preferable candidate gets elected. The book investigates restrictions on the number of iterations that can be made for different voting rules, considering both weighted and equi-weighted voting settings.

چکیده فارسی

یکی از زیرحوزه‌های فعال در حال رشد در سیستم‌های چند عاملی، نظریه انتخاب اجتماعی محاسباتی است، که پایه‌ای نظری برای تجمیع ترجیحات و تصمیم‌گیری جمعی در حوزه‌های چند عاملی فراهم می‌کند. به کاربرد تکنیک‌های توسعه‌یافته در علوم رایانه، از جمله تحلیل پیچیدگی و طراحی الگوریتم، در مطالعه مکانیسم‌های انتخاب اجتماعی، مانند رأی‌گیری، مربوط می‌شود. این به دنبال وارد کردن مفاهیم از نظریه انتخاب اجتماعی به هوش مصنوعی و محاسبات است. مردم اغلب مجبورند با وجود ترجیحات متناقض نسبت به گزینه ها، به یک تصمیم مشترک برسند. این تصمیم مشترک می تواند از طریق یک فرآیند مذاکره غیررسمی یا با یک پروتکل به دقت مشخص شده حاصل شود. در طول یک دهه گذشته یا بیشتر، دانشمندان کامپیوتر نیز عمیقاً درگیر این مطالعه شده اند. در علم کامپیوتر، تعدادی تنظیمات وجود دارد که در آنها باید تصمیمی بر اساس ترجیحات متضاد چندین طرف گرفته شود. پارادایم های علوم کامپیوتر دیدگاه متفاوت و مفیدی را در مورد برخی از مسائل کلاسیک در اقتصاد و رشته های مرتبط ارائه می دهند. یک رویکرد طبیعی و بسیار کلی برای تصمیم گیری در میان گزینه های متعدد، رأی دادن به آنها است. رای دادن یکی از محبوب ترین راه ها برای رسیدن به تصمیمات مشترک است. به این ترتیب، مطالعه انتخابات حوزه ای است که در آن زمینه هایی مانند علوم کامپیوتر، اقتصاد، بازرگانی، تحقیقات عملیاتی و علوم سیاسی را می توان گرد هم آورد. نظریه انتخاب اجتماعی با سناریوهای رای گیری سروکار دارد که در آن مجموعه ای از افراد باید یک نتیجه را از مجموعه ای از گزینه ها انتخاب کنند. این کتاب بر روی همگرایی به تعادل‌های نش استراتژی خالص در بازی‌های رای‌گیری چندگانه و تعدادی دیگر از قوانین امتیازدهی موقعیتی و غیر موقعیتی تمرکز دارد. در چنین بازی‌هایی، رای‌دهندگان به صورت استراتژیک، نامزدی را برای رای دادن انتخاب می‌کنند و برنده توسط قوانین رای‌گیری کثرت (یا دیگر) تعیین می‌شود. رای دهندگان به نوبت آرای خود را تغییر می دهند. این دستکاری ها بر اساس روشی که بر نتیجه انتخابات تأثیر می گذارد طبقه بندی می شوند. تمرکز بر دستیابی به یک نتیجه پایدار با در نظر گرفتن رفتار استراتژیک است. زمانی که هیچ رأی دهنده ای نمی تواند رأی خود را تغییر دهد تا نامزد ارجح تر او انتخاب شود، یک نمایه رأی گیری در حالت تعادل است. این کتاب محدودیت‌هایی را در مورد تعداد تکرارهایی که می‌توان برای قوانین رأی‌گیری مختلف ایجاد کرد، با در نظر گرفتن تنظیمات رأی‌گیری وزنی و هم وزن بررسی می‌کند.