قضیه گیبورد-سَترثویت
در حوزه نظریه انتخاب اجتماعی، قضیه گیبورد-سَترثویت (Gibbard–Satterthwaite theorem) نتیجهای است که در سالهای 1973 و 1975 به طور مستقل توسط آلن گیبورد (Allan Gibbard) و مارک سَترثویت (Mark Satterthwaite) منتشر شد. این قضیه به سیستمهای انتخاباتی ترتیبی قطعی (deterministic ordinal electoral systems) میپردازد که یک برنده واحد را انتخاب میکنند. قضیه بیان میکند که برای هر قانون رأیگیری، یکی از سه شرط زیر باید برقرار باشد:
- قانون دیکتاتورانه است، یعنی رأیدهنده خاصی وجود دارد که میتواند برنده را انتخاب کند.
- قانون، نتایج ممکن را به دو گزینه محدود میکند.
- قانون مستعد رأیگیری تاکتیکی است: در شرایط خاص، رأی صادقانه یک رأیدهنده ممکن است بهترین دفاع از نظر او نباشد.
در حالی که دامنه این قضیه به رأیگیری ترتیبی محدود میشود، قضیه گیبورد کلیتر است، زیرا به فرایندهای تصمیمگیری جمعی میپردازد که ممکن است ترتیبی نباشند؛ برای مثال، سیستمهای رأیگیری که در آنها رأیدهندگان به نامزدها امتیاز میدهند. قضیه گیبورد در سال 1978 و قضیه هیولند (Hylland's theorem) حتی کلیتر هستند و این نتایج را به فرایندهای غیرقطعی، یعنی جایی که نتیجه ممکن است نه تنها به اقدامات رأیدهندگان بستگی داشته باشد، بلکه شامل عنصری از شانس نیز باشد، گسترش میدهند.
توصیف غیررسمی
سه رأیدهنده به نامهای آلیس، باب و کارول را در نظر بگیرید که میخواهند از میان چهار نامزد به نامهای A، B، C و D یک برنده انتخاب کنند. فرض کنید آنها از روش رأیگیری بوردا (Borda count) استفاده میکنند: هر رأیدهنده ترتیب ترجیحات خود را نسبت به نامزدها اعلام میکند. برای هر رأی، 3 امتیاز به نامزد اول، 2 امتیاز به نامزد دوم، 1 امتیاز به نامزد سوم و 0 امتیاز به نامزد آخر اختصاص مییابد. پس از شمارش تمام آرا، نامزدی که بیشترین امتیاز را کسب کند، برنده اعلام میشود.
فرض کنید ترجیحات آنها به شرح زیر باشد:
- آلیس: A > B > C > D
- باب: B > C > D > A
- کارول: C > D > A > B
اگر رأیدهندگان آرای صادقانه خود را بیان کنند، امتیازات به شرح زیر خواهد بود:
- A: 3 + 0 + 1 = 4
- B: 2 + 3 + 0 = 5
- C: 1 + 2 + 3 = 6
- D: 0 + 1 + 2 = 3
در نتیجه، نامزد C با 6 امتیاز انتخاب خواهد شد.
اما آلیس میتواند به صورت استراتژیک رأی دهد و نتیجه را تغییر دهد. فرض کنید او رأی خود را تغییر میدهد تا وضعیت زیر ایجاد شود:
- آلیس (استراتژیک): A > C > B > D
- باب: B > C > D > A
- کارول: C > D > A > B
آلیس به طور استراتژیک نامزد A را ارتقا داده و نامزد B را تنزل داده است. اکنون امتیازات به شرح زیر است:
- A: 3 + 0 + 1 = 4
- B: 0 + 3 + 0 = 3
- C: 2 + 2 + 3 = 7
- D: 1 + 1 + 2 = 4
در نتیجه، C انتخاب میشود. آلیس از تغییر رأی خود راضی است، زیرا نتیجه C را به نتیجه B ترجیح میدهد، که نتیجهای بود که اگر صادقانه رأی میداد، به دست میآورد.
به این ترتیب میگوییم که روش بوردا قابل دستکاری است: موقعیتهایی وجود دارد که رأی صادقانه بهترین دفاع از ترجیحات یک رأیدهنده نیست.
قضیه گیبورد-سَترثویت بیان میکند که هر قانون رأیگیری قابل دستکاری است، مگر در دو مورد احتمالی: اگر یک رأیدهنده دیکتاتور وجود داشته باشد که قدرت دیکتاتوری دارد، یا اگر قانون نتایج ممکن را به دو گزینه محدود کند.
بیان رسمی
مجموعه آلترناتیوها (که متناهی فرض میشود) را با $\(A\)$ نشان میدهیم. این آلترناتیوها میتوانند نامزد، یا تصمیمات مختلف در مورد یک مسئله باشند. مجموعه رأیدهندگان را با $\(N\)$ نشان میدهیم. مجموعه ترتیبهای ضعیف اکید بر روی $\(A\)$ را با $\(mathcal{P}\)$ نشان میدهیم؛ هر عضو این مجموعه میتواند نمایانگر ترجیحات یک رأیدهنده باشد، که در آن یک رأیدهنده ممکن است نسبت به ترتیب برخی آلترناتیوها بیتفاوت باشد. یک قانون رأیگیری تابعی است مانند $\(f: \mathcal{P}^N \to A\)$. ورودی این تابع، نمایه ترجیحات $\(P = (P_i)_{i \in N}\)$ است و نتیجه آن، هویت نامزد برنده است.
میگوییم $\(f\)$ قابل دستکاری است اگر و تنها اگر نمایه ترجیحاتی $\(P \in \mathcal{P}^N\)$ وجود داشته باشد که در آن یک رأیدهنده $\(i \in N\)$، با جایگزین کردن رأی خود $\(P_i\)$ با رأی دیگر $\(P'_i\)$، بتواند به نتیجهای دست یابد که آن را ترجیح میدهد (به معنای $\(P_i\)$).
تصویر $\(f\)$، یعنی مجموعه نتایج ممکن برای انتخابات را با $\(Im(f)\)$ نشان میدهیم. به عنوان مثال، میگوییم $\(f\)$ حداقل سه نتیجه ممکن دارد اگر و تنها اگر کاردینالیتی $\(Im(f)\)$ برابر یا بیشتر از 3 باشد.
میگوییم $\(f\)$ دیکتاتورانه است اگر و تنها اگر رأیدهنده $\(i \in N\)$ به عنوان دیکتاتور وجود داشته باشد، به این معنا که آلترناتیو برنده همیشه مورد علاقه اول او در میان نتایج ممکن، صرف نظر از ترجیحات سایر رأیدهندگان باشد. اگر دیکتاتور چندین آلترناتیو با اولویت یکسان در میان نتایج ممکن داشته باشد، آنگاه آلترناتیو برنده صرفاً یکی از آنهاست.
مثالها
حکمیت سریال (Serial dictatorship)
حکمیت سریال به شرح زیر تعریف میشود: اگر رأیدهنده اول یک نامزد منحصر به فرد را ترجیح دهد، آن نامزد برنده میشود. در غیر این صورت، نتایج ممکن به نامزدهای اولویتدار محدود میشوند، در حالی که سایر نامزدها حذف میشوند. سپس رأی رأیدهنده دوم بررسی میشود: اگر در میان نامزدهای حذف نشده، یک نامزد منحصر به فرد با بالاترین اولویت وجود داشته باشد، آن نامزد برنده میشود. در غیر این صورت، لیست نتایج ممکن دوباره محدود میشود و غیره. اگر پس از بررسی تمام آرا هنوز چندین نامزد حذف نشده باقی بمانند، از یک قانون شکستن تساوی دلخواه استفاده میشود.
این قانون رأیگیری قابل دستکاری نیست: یک رأیدهنده همیشه در موقعیت بهتری است که ترجیحات صادقانه خود را بیان کند. همچنین دیکتاتورانه است و دیکتاتور آن رأیدهنده اول است: آلترناتیو برنده همیشه مورد علاقه اول آن رأیدهنده خاص است یا در صورت وجود چندین آلترناتیو با اولویت یکسان، از میان آنها انتخاب میشود.
رأی اکثریت ساده
اگر فقط 2 نتیجه ممکن وجود داشته باشد، یک قانون رأیگیری ممکن است بدون دیکتاتورانه بودن، قابل دستکاری نباشد. به عنوان مثال، این مورد در رأی اکثریت ساده صدق میکند: هر رأیدهنده به آلترناتیو مورد علاقه خود 1 امتیاز و به دیگری 0 امتیاز میدهد و آلترناتیوی که بیشترین امتیاز را کسب کند، برنده است. (اگر هر دو آلترناتیو امتیازات یکسانی کسب کنند، تساوی به روشی دلخواه اما قطعی شکسته میشود، مثلاً نتیجه A برنده میشود.) این قانون رأیگیری قابل دستکاری نیست زیرا یک رأیدهنده همیشه در موقعیت بهتری است که ترجیحات صادقانه خود را بیان کند؛ و به وضوح دیکتاتورانه نیست. بسیاری از قوانین دیگر نه قابل دستکاری هستند و نه دیکتاتورانه: به عنوان مثال، فرض کنید آلترناتیو A برنده میشود اگر دو سوم آرا را کسب کند، و در غیر این صورت B برنده میشود.
یک فرم بازی که نشان میدهد عکس قضیه برقرار نیست
قانون زیر را در نظر بگیرید. تمام نامزدها حذف میشوند، مگر نامزد یا نامزدهایی که در جایگاه اول رأی رأیدهنده اول قرار دارند. سپس، در میان نامزدهای حذف نشده، یکی با استفاده از روش بوردا انتخاب میشود. کل این فرایند به تعریف، دیکتاتورانه است. با این حال، به دلایل مشابه روش بوردا، قابل دستکاری است. بنابراین، قضیه گیبورد-سَترثویت یک استلزام است و نه یک همارزی.
متمم قضیه
اکنون مورد خاصی را در نظر میگیریم که در آن فرض میشود یک رأیدهنده نمیتواند بین دو نامزد بیتفاوت باشد. مجموعه ترتیبهای اکید کلی بر روی $\(A\)$ را با $\(mathcal{O}\)$ نشان میدهیم و یک قانون رأیگیری اکید را به صورت تابعی $\(g: \mathcal{O}^N \to A\)$ تعریف میکنیم. تعاریف نتایج ممکن، قابل دستکاری و دیکتاتورانه، انطباق طبیعی با این چارچوب دارند.
برای یک قانون رأیگیری اکید، عکس قضیه گیبورد-سَترثویت برقرار است. در واقع، یک قانون رأیگیری اکید دیکتاتورانه است اگر و تنها اگر همیشه نامزد مورد علاقه دیکتاتور را در میان نتایج ممکن انتخاب کند؛ به ویژه، این انتخاب به آرای سایر رأیدهندگان بستگی ندارد. در نتیجه، قابل دستکاری نیست: دیکتاتور توسط رأی صادقانه خود به طور کامل دفاع میشود و سایر رأیدهندگان هیچ تأثیری بر نتیجه ندارند، بنابراین انگیزهای برای انحراف از رأی صادقانه ندارند. بنابراین، همارزی زیر را به دست میآوریم:
یک قانون رأیگیری اکید با حداقل سه نتیجه ممکن، قابل دستکاری نیست اگر و تنها اگر دیکتاتورانه باشد.
در قضیه، و همچنین در متمم آن، نیازی به فرض اینکه هر آلترناتیو میتواند انتخاب شود، نیست. فقط فرض میشود که حداقل سه مورد از آنها میتوانند برنده شوند، یعنی نتایج ممکن قانون رأیگیری هستند. ممکن است برخی دیگر از آلترناتیوها تحت هیچ شرایطی انتخاب نشوند؛ قضیه و متمم آن همچنان اعمال میشوند. با این حال، متمم گاهی اوقات تحت شکلی کلیتر ارائه میشود: به جای فرض اینکه قانون حداقل سه نتیجه ممکن دارد، گاهی فرض میشود که $\(A\)$ حداقل سه عنصر دارد و قانون رأیگیری پوشا (onto) است، یعنی هر آلترناتیو یک نتیجه ممکن است. فرض پوشا بودن گاهی با فرض اجماع (unanimous) جایگزین میشود، به این معنا که اگر همه رأیدهندگان یک نامزد خاص را ترجیح دهند، آن نامزد باید انتخاب شود.
طرح اثبات
قضیه گیبورد-سَترثویت را میتوان بر اساس قضیه عدم امکان اَرو (Arrow's impossibility theorem) اثبات کرد، که به توابع رتبهبندی اجتماعی، یعنی سیستمهای رأیگیری که برای ارائه یک ترتیب کامل ترجیحات نامزدها طراحی شدهاند، به جای صرف انتخاب یک برنده، میپردازد. ما طرح اثباتی را در حالت سادهشدهای که قانون رأیگیری $\(f\)$ فرض میشود اجماعی باشد، ارائه میدهیم. امکان ساخت یک تابع رتبهبندی اجتماعی $\(R\)$ به شرح زیر وجود دارد: برای تصمیمگیری در مورد اینکه آیا $\(x \succ y\)$ (یعنی x بر y ترجیح داده میشود)، تابع $\(R\)$ ترجیحات جدیدی ایجاد میکند که در آن $\(x\)$ و $\(y\)$ در بالای ترجیحات همه رأیدهندگان قرار میگیرند. سپس $\(R\)$ بررسی میکند که آیا $\(x\)$ یا $\(y\)$ را انتخاب میکند. میتوان ثابت کرد که اگر $\(f\)$ غیرقابل دستکاری و غیردیکتاتورانه باشد، آنگاه $\(R\)$ خواص زیر را برآورده میکند: اجماع، استقلال از آلترناتیوهای نامرتبط، و دیکتاتوری نیست. قضیه عدم امکان اَرو میگوید که وقتی سه یا بیشتر آلترناتیو وجود داشته باشد، چنین تابع $\(R\)$ نمیتواند وجود داشته باشد. بنابراین، چنین قانون رأیگیری $\(f\)$ نیز نمیتواند وجود داشته باشد.
تاریخچه
جنبه استراتژیک رأیگیری از سال 1876 توسط چارلز لاتویج داجسون (Charles Dodgson)، که با نام لوئیس کارول (Lewis Carroll) نیز شناخته میشود، پیشگام نظریه انتخاب اجتماعی، مورد توجه قرار گرفت. نقل قول او (درباره یک سیستم رأیگیری خاص) توسط دانکن بلک (Duncan Black) مشهور شد:
این اصل رأیگیری، انتخابات را بیشتر به یک بازی مهارت تبدیل میکند تا آزمونی واقعی از خواستههای رأیدهندگان.
در دهه 1950، رابین فارکوهارسون (Robin Farquharson) مقالات تأثیرگذاری در نظریه رأیگیری منتشر کرد. در مقالهای با مایکل دامت (Michael Dummett)، او حدس زد که قوانین رأیگیری قطعی با حداقل سه مسئله، با رأیگیری تاکتیکی فراگیر روبرو هستند. این حدس فارکوهارسون-دامت (Farquharson-Dummett conjecture) به طور مستقل توسط آلن گیبورد و مارک سَترثویت اثبات شد. گیبورد در مقالهای در سال 1973 از قضیه عدم امکان اَرو در سال 1951 برای اثبات نتیجهای که اکنون به عنوان قضیه گیبورد میشناسیم، استفاده کرد و سپس نتیجه فعلی را استنتاج کرد که پیامد فوری آن است. به طور مستقل، سَترثویت همین نتیجه را در پایاننامه دکتری خود در سال 1973 اثبات کرد و سپس آن را در مقالهای در سال 1975 منتشر کرد. اثبات او نیز بر اساس قضیه عدم امکان اَرو است، اما او نسخه کلیتر ارائه شده توسط قضیه گیبورد را توضیح نمیدهد. بعدها، نویسندگان مختلفی، نسخههای کوتاهتر اثبات را، چه برای خود قضیه و چه برای متمم و نسخههای ضعیف شدهای که ذکر کردیم، توسعه دادند.
نتایج مرتبط
قضیه گیبورد به فرایندهای انتخاب جمعی میپردازد که ممکن است ترتیبی نباشند، یعنی جایی که اقدام یک رأیدهنده ممکن است شامل اعلام یک ترتیب ترجیحات بر روی نامزدها نباشد. قضیه گیبورد در سال 1978 و قضیه هیولند این نتایج را به مکانیزمهای غیرقطعی، یعنی جایی که نتیجه ممکن است نه تنها به آرا، بلکه شامل عنصری از شانس نیز باشد، گسترش میدهند.
قضیه دگان-شوارتز (Duggan–Schwartz theorem) این نتیجه را در جهت دیگری گسترش میدهد و به قوانین رأیگیری قطعی میپردازد که به جای یک برنده واحد، زیرمجموعهای غیرتهی از نامزدها را انتخاب میکنند.
میراث
قضیه گیبورد-سَترثویت به طور کلی به عنوان نتیجهای متعلق به حوزه نظریه انتخاب اجتماعی و کاربردی در سیستمهای رأیگیری ارائه میشود، اما میتوان آن را به عنوان نتیجه بنیادی طراحی مکانیزم (mechanism design) نیز در نظر گرفت، که به طراحی قوانینی برای اتخاذ تصمیمات جمعی، احتمالاً در فرایندهایی که شامل انتقال پولی است، میپردازد. نوآم نیسان (Noam Nisan) این رابطه را توصیف میکند:
قضیه GS به نظر میرسد هر امیدی را برای طراحی توابع انتخاب اجتماعی سازگار با انگیزه از بین میبرد. کل حوزه طراحی مکانیزم تلاش میکند تا با اصلاحات مختلف در مدل، از این نتیجه عدم امکان فرار کند.ایده اصلی این «مسیرهای فرار» این است که آنها فقط با کلاسهای محدودی از ترجیحات سروکار دارند، در مقابل قضیه گیبورد-سَترثویت که با ترجیحات دلخواه سروکار دارد. به عنوان مثال، در این رشته، اغلب فرض میشود که عاملان دارای ترجیحات شبهخطی (quasi-linear preferences) هستند، به این معنی که تابع مطلوبیت آنها به طور خطی به پول بستگی دارد. در این صورت، انتقالات پولی میتواند آنها را وادار به اقدام صادقانه کند. این ایده پشت مزایده ویکری-کلارک-گراوز (Vickrey–Clarke–Groves auction) موفق است.
جستارهای وابسته
- قضیه گیبورد
- قضیه عدم امکان اَرو
- قضیه دگان-شوارتز