سیستم‌های پیچیده: چه طور سه نفر جمع درآمدشان را پیدا کنند، بدون اعلام خود درآمد

فرض کنید سه نفر داریم (تعداد بیش‌تر هم ممکن است و فرقی در مساله ایجاد نمی‌شود) که می‌خواهند جمع درآمدشان را پیدا کنند و در ضمن هیچ‌کدام نمی‌خواهند دیگران به میزان درآمدشان پی ببرند. آیا راهی هست که بتوانند؟

این ایده از «سندی پنتلند» است: نفر اول درآمدش (A) را به همراه یک عدد دل‌خواه (a) به نفر دوم می‌گوید. نفر دوم عددی را که از نفر اول گرفته (A+a)، با درآمدش (B) و یک عدد دل‌خواه خودش (b) جمع می‌کند و به نفر سوم می‌دهد. نفر سوم عددی را که از نفر دوم گرفته (A+a+B+b) با درآمدش (C) و یک عدد دل‌خواه خودش (c) جمع می‌کند و به نفر اول می‌دهد. نفر اول از عددی که از نفر سوم گرفته است (A+a+B+b+C+c)، عدد دل‌خواهی که اضافه کرده بوده (a) را کم می‌کند و نتیجه (A+B+b+C+c) را به نفر دوم می‌دهد. نفر دوم هم کار مشابه می‌کند و نتیجه (A+B+C+c) را به نفر سوم می‌دهد. نفر سوم هم عددی را که اضافه کرده بوده (c) کم می‌کند و نتیجه (A+B+C) را به همه اعلام می‌کند. به این ترتیب همه از جمع درآمد همگی خبر دارند، بدون این که درآمد هیچ‌یک از افراد علنی شده باشد.

یکی از فرض‌های این روش این است که همه‌ی شرکت کنندگان صداقت دارند و بعدتر دقیقن همان عددی زا کم می‌کنند که از اول اضافه کرده‌اند. البته ممکن است اگر صداقت نداشته باشند، در شرایطی، معلوم شود که بعضی صادق نبوده‌اند (برای مثال وقتی که جمع درآمدها منفی شود).

سوال: چه طور می‌شود از این روش برای رای‌گیری مخفیانه بین چند گزینه استفاده کرد؟

کمی فکر کنید…

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

روشی که به ذهن من می‌رسد مشابه همین روش است: به جای این که از یک عدد (اسکالر) برای عدد دست به دست شونده استفاده کنیم، از یک آرایه استفاده کنیم. هر عضو آرایه نشان‌دهنده‌ی تعداد رای‌های هریک از گزینه‌هاست (مثلن عنصر اول برای نامزد اول، عنصر دوم برای نامزد دوم و به همین ترتیب). هرکس رای خود را به گزینه‌ی مورد نظر اضافه می‌کند و به همه‌ی گزینه‌های آرایه عددهای دل‌خواهی اضافه می‌کند (که این عددها لازم نیست مثبت باشند). آرایه را دست به دست می‌کنند تا دوباره به هرکس برسد. در دور دوم هرکس عددهای دل‌خواهی را که اضافه کرده کم می‌کند (و به رای‌اش دست نمی‌زند) تا این که در پایان یک آرایه داشته باشیم که هر عنصرش نشان‌دهنده‌ی تعداد رای‌های هر گزینه باشد.

سوال: آیا در این روش امکان تقلب وجود دارد؟