Голосование
Четверо друзей Аня, Боря, Вася и Даша решили вместе найти подработку на лето. У них есть три варианта: работать в книжном магазине, в детском лагере или в IT компании. Дело в том, что работать ребята хотят только вместе, поэтому они решили голосовать. Однако, есть одна проблема: у каждого из друзей есть свои способности, таланты и предпочтения, из-за чего в одном месте им могут предложить разные должности и разные зарплаты. Например, в летний лагерь кого-то готовы нанять преподавателем, когото – вожатым, кого-то – организатором. Зарплаты у преподавателя, вожатого и организатора отличаются, и никто из ребят не может быть принятым на другую позицию. Например, если Дашу готовы взять преподавателям в лагере, её ни в коем случае не возьмут вожатым или организатором. Предположим, что ребята получают выигрыш от работы на определенной вакансии равный зарплате. Само собой, есть и четвертый вариант – остаться вовсе без работы. Чистый доход за весь период работы представлен в таблице:
Предполагается, что друзья считают победившей ту альтернативу, что набрала больше всего голосов. Голос отдается за тот вариант, что принесет человеку наибольший доход. В случае, если голосование обернется ничьей, ребята выбирают ту работу, при устройстве на которую их суммарный доход наибольший.
(а) [5 баллов] Если ребята голосуют честно, куда они устроятся на работу?
(б) [6 баллов] Предположим, ребята могут обманывать, то есть голосовать не за ту альтернативу, что приносит наибольший доход. Какая альтернатива победит в таком случае?
(в) [7 баллов] Ребята поняли, что голосование имеет слабое место, которое было описано в предыдущем пункте. Предположим, что друзья могут запретить одному из участников голосовать до начала голосования. Кому нужно запретить голосовать, чтобы никто не хотел не обманывать? Увеличится ли суммарный доход ребят в результате принятия этой меры?
(г) [8 баллов] Ребята посчитали несправедливым исключать кого-то из голосования, вместо этого, теперь каждый голос будет проверяться, каждый должен голосовать за альтернативу, которая приносит ему строго больший выигрыш. Но теперь ребята могут делиться зарплатой. Например, Даша может поделиться одной денежной единицей с Аней, если она проголосует за работу в IT компании и этот вариант выиграет. Куда в таком случае устроятся на работу друзья?
(д) [4 баллов] Сравните все предыдущие пункты. В каком случае общий доход друзей был максимальным? Найдите какие доходы получат Аня, Боря, Вася и Даша в каждой ситуации. Если бы они могли проголосовать за то, в какой из ситуаций лучше оказаться (честное голосование, голосование с обманом, введение запрета на голосование для одного участника, голосование с возможностью делиться зарплатой), то какая ситуация получила бы меньше всего голосов?
(а) Если ребята голосуют честно, то каждый проголосует за вариант, который принесет им наибольший выигрыш. Так, Аня и Боря проголосуют за работу в книжном магазине, Вася за работу в детском лагере, а Даша за IT компанию. Это значит, что победившей альтернативой является книжный магазин, и все четверо устроятся на работу туда.
(б) Предположим, все четверо проголосовали честно. Осталось понять, кому из ребят выгодно изменить свой выбор (проголосовать за другую альтернативу). Это точно не Аня и Боря – они проголосовали за наилучший для себя вариан т, который одержал победу. В случае, если Вася решит изменить своё решение, то исход голосования не изменится. Однако если Даша решит проголосовать за детский лагерь (второй по привлекательности вариант), ситуация будет выглядеть иначе. Книжный магазин приносит друзьям суммарный выигрыш в размере 8 + 4 + 5 + 2 = 19, тогда как детский лагерь приносит друзьям суммарный выигрыш в размере 6 + 3 + 6 + 7 = 22 > 19. Это значит, что если Даша решит обмануть своих друзей и проголосовать за работу в детском лагере, эта альтернатива победит, поскольку приносит бОльший суммарный выигрыш друзьям. Значит, Даша обманет (она получит 7 > 2 при работе в книжном магазине), и победит альтернатива «детский лагерь».
(в) Важное примечание. При проверке стоит учитывать двойственность интерпретации вопроса. Подразумевалось, что ни у кого не должно возникнуть стимулов обманывать, но школьникам разрешается предполагать, что у всех должны быть стимулы обманывать. В этом случае решение тривиально и ответом будет отсутствие такого человека, удаление из голосование которого создаст всем стимулы обманывать. Рассмотрим по отдельности удаление из голосования каждого из друзей.
- Аня. Если Аня не будет принимать участие в голосовании, победит детский лагерь, поскольку за каждую из альтернатив будет отдано по одному голосу при честном голосовании, а детский лагерь приносит друзьям наибольший суммарный выигрыш. Никто из друзей не сможет обмануть так, что ему станет лучше, чем при честном голосовании. Значит, удаление Ани создаст стимулы не обманывать для всех.
- Боря. В случае удаления Бори ситуация аналогична удалению Ани – вновь победит детский лагерь и никто не сможет обмануть и выиграть от этого.
- Вася. В случае, если Вася будет исключён из голосования, победит книжный магазин, поскольку больше всего голосов будет отдано за него. Даша не сможет обмануть и изменить исход голосования. Вновь никто не захочет обманывать (Аня и Боря голосуют за наилучший вариант для себя и он побеждает).
- Даша. Случае удаления Даши ситуация аналогичная удалению Васи – вновь победит книжный магазин и никто не захочет обманывать. Это наталкивает нас на простой вывод: кого бы ни отстранили от голосования, удаление одного из участников всегда закончится ситуацией, в которой каждый голосует честно.
(г) Как мы выяснили в пункте (б), Аня и Боря довольны положением, которое складывается в результате честного голосования. Значит, нам стоит проверить, есть ли возможность у Васи и/или Даши «поделиться» с кем-то из друзей, чтобы повлиять на исход выборов.
Рассмотрим Васю. Вася может передать одному из друзей максимум 1 денежную единицу, поскольку отдав больше 1 денежной единицы, он сделает для себя альтернативу «детский лагерь» менее привлекательной, чем книжный магазин, который побеждает при честном голосовании. Если он подарит 1 денежную единицу Ане или Боре, он не сможет переубедить их голосовать за альтернативу, которая не является для них наилучшей (Аня и Боря при голосовании за детский лагерь получат 7 или 4 соответственно), равно как и Дашу (которая в детском лагере заработает 8, что меньше 11). Значит, Вася не может поделиться деньгами так, что кто-то из друзей изменит своё решение. Рассмотрим Дашу. Даша готова «подарить» друзьям не более 11 − 2 = 9 денежных единиц. В противном случае, книжный магазин, который побеждает при честном голосовании, станет наиболее привлекательным. Аня согласится проголосовать за IT компанию, если Даша подарит ей строго больше 3 денежных единиц; Боря – если Даша подарит ему строго больше 3 денежных единиц; Вася – если Даша подарит ему строго больше 2 денежных единиц. Наиболее выгодным вариантом выглядит поделиться с Васей. Осталось лишь проверить, что IT компания приносит бОльший суммарный выигрыш, чем книжный магазин (поскольку голоса поделятся поровну, надо определить, какая альтернатива одержит победу в этом случае). При победе IT компании друзья получат в сумме 5 + 1 + 4 + 11 = 21 > 19. Значит, друзья выберут работу в IT компании, а Даша подарит Васе немного больше 2 д.е. Почему «немного больше»? 2 д.е. не убедят Васю – нужно, чтобы вариант приносил строго бОльший выигрыш. Но и сильно много отдавать Васе невыгодно для Даши – она может увеличить свой выигрыш, сократив подарок Васи, при условии, что он строго больше 2.
(д) Общий доход друзей был максимальным в пункте (б). Выигрыши друзей в каждом из пунктов можно показать в таблице:
где a – очень маленькая положительная величина. Аня и Боря проголосуют за варианты I и III, Вася и Даша проголосуют за V. Меньше всего голосов (ноль) получили бы варианты II и IV.