Выборы, выборы, кандидаты ...

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Выборы, выборы, кандидаты ...

Сообщение Dendr »

Инна писал(а):Так что имхо при таких принципах далеко до честности и демократии :-(
Угу... точно тоже придумал, пока обедал.
Допустим, выбирают 100 человек одного из трех: Джона, Мэри и, например, Седрика. Выбирают директора банка на собрании правления.
Согласно условиям задачи, каждый избиратель ставит каждому кандидату в соответствие некую функцию.
Пусть секретарь правления придумал схему честных выборов. В этой схеме нашлось и место принципу единогласия, и место принципу отсутствия диктатора.
А как насчет принципа независимости?
Допустим, что вышло так:
50 голосующих (мужчины) дали такие числа (в порядке Джон-Мэри-Седрик): 0.90-0.09-0.01
50 голосующих (женщины): 0.49-0.50-0.01
Секретарь закладывает эти данные в схему и получает, к примеру, результат: Д-М-С.

Но! Схема недолжна зависеть от альтернатив!
Что, если женщины проголосовали 0.09-0.90-0.01,
а мужчины 0.50-0.49-0.01.
Мы видим строгую симметрию с предыдущим примером, и, по идее, должны на выходе получить М-Д-С. Т.е. Мэри и Джон поменялись местами.
Но мы видим-то, что относительные предпочтения каждого не изменились!

Противоречие.

Вывод. Нет, это не значит, что подобной схемы не существует. Это значит, что приведенное выше определение демократических выборов - некорректно.

Upd. Поправил кое-что, писал в спешке, и принцип единогласия попортил слегка.
Последний раз редактировалось Dendr 19 фев 2008, 14:51, всего редактировалось 1 раз.

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Выборы, выборы, кандидаты ...

Сообщение Dendr »

Точнее, так.
Если под демократическими выборами предполагать выборы, правила которых придуманы Эрроу, то они никогда не бывают честными.

Как говорится - извините, но я отказываюсь решать задачу, которая внутренне противоречива.

Давайте еще предположим, что морского ежа причесать можно, и решать задачки в такой топологии. Мы получим, разумеется, черт-те что. В результате докажем, что причесать ежа все-таки невозможно, но проку от этого не будет никакого.

Аватара пользователя
molch64
Литератор-любитель
Литератор-любитель
Сообщения: 266
Зарегистрирован: 08 июн 2006, 11:05
Пол: Мужской

Re: Выборы, выборы, кандидаты ...

Сообщение molch64 »

Dendr, см. моё сообщение от 13.00:

ЦИК не знает функцию предпочтения каждого избирателя!

Когда ЦИК знает её, это другая задача! И там тоже есть своя теорема.
Каждый кандидат шлет в ЦИК только упорядоченный набор кандидатов! Т.е. предпочтения вида a>b>c.
Голоса он не шлет. Вот такая система голосования.

А цифры я придумал для удобства, но по ходу ими запутал :)
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Выборы, выборы, кандидаты ...

Сообщение Инна »

molch64 писал(а): ЦИК не знает функцию предпочтения каждого избирателя!

Когда ЦИК знает её, это другая задача! И там тоже есть своя теорема.
Каждый кандидат шлет в ЦИК только упорядоченный набор кандидатов! Т.е. предпочтения вида a>b>c.
Голоса он не шлет. Вот такая система голосования.
Так принцип независимости (та формула) как раз и сводит любую функцию предпочтения к упорядоченному набору.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Выборы, выборы, кандидаты ...

Сообщение Инна »

Я думала над чуть другой задачей.
В общем виде: Есть соревнования из нескольких туров, в каждом по нескольку заданий (битовых, решил-не решил) разной сложности.
Как расставить участников по результатам и в частности, определить победителя соревнований?
Самое простое - это оценить заранее каждое задание в баллах, и решивший задание получает баллы по нему. Баллы участника суммируются по всем турам и в зависимости от набранных сумм участники ранжируются (1).
В частности, например, можно считать, что каждое задание стоит ровно 1 и победит тот, кто больше заданий решит.
Можно действовать более хитро: считать сумму мест по турам, каждую задачу оценивать количеством не решивших ее (т.е. чем меньше решило, тем сложнее и дороже задача) и т.д...

Метод оценки, на мой взгляд, должен обладать простым свойством:

Если во втором случае все кроме участника Х решили всё точно так же, как и в первом, а участник Х решил в дополнение к решенному в первом случае еще что-то, то место участника Х во втором случае должно быть не меньше, чем в первом, а места всех остальных - не больше чем в первом (***)

И я кажется доказала, что это свойство соблюдается только при методе (1).
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Выборы, выборы, кандидаты ...

Сообщение Dendr »

molch64 писал(а):Каждый кандидат шлет в ЦИК только упорядоченный набор кандидатов! Т.е. предпочтения вида a>b>c.
Упустил, пардон.
Но тогда система может быть такая (ср. у Кондорсе): устраиваем "однокруговой турнир" между парами кандидатов. Для трех - только три сравнения (из 6 вариантов распределения) А-Б, А-В и Б-В. Без ограничения общности можно считать, что если среди троих есть кандидат, который "победил" остальных, то это А. И опять же, без ограничения общности, считаем, что Б "победил" В. Тогда решение ЦИК будет следующее: А>Б>В.

Однако, и тут есть подводный камень. Что, если в "турнире" получится следующая ситуация: A>Б, Б>В, В>А? Причем все поровну:
33 1/3 % сказали A>Б>В, и по столько же Б>В>А и В>А>Б. Правда, это - крайний прецедент, и придется переголосовать. В противном случае - можно предложить систему, зависящую от разницы превосходств.
Т.е., пусть А>Б на (а), Б>В на (б), В>А на (в). Тогда ставим соответствие А=а-в, Б=б-а, В=в-б, и распределять АБВ в порядке убывания, и все ОК.

Хм.

Странно. Наверное, где-то тут не удовлетворяется один из принципов...

Аватара пользователя
basil0
Популярный автор
Популярный автор
Сообщения: 2007
Зарегистрирован: 10 ноя 2006, 01:17
Пол: Мужской
Откуда: Москва
Контактная информация:

Re: Выборы, выборы, кандидаты ...

Сообщение basil0 »

При таких минитурнирах нарушается принцип независимости - при добавлении еще одного кандидата изменяется соотношение старых было А>B становится А=В
С уважением, Василий.
А кто сказал, что я прав?

Аватара пользователя
molch64
Литератор-любитель
Литератор-любитель
Сообщения: 266
Зарегистрирован: 08 июн 2006, 11:05
Пол: Мужской

Re: Выборы, выборы, кандидаты ...

Сообщение molch64 »

Инна писал(а):Если во втором случае все кроме участника Х решили всё точно так же, как и в первом, а участник Х решил в дополнение к решенному в первом случае еще что-то, то место участника Х во втором случае должно быть не меньше, чем в первом, а места всех остальных - не больше чем в первом (***)
И я кажется доказала, что это свойство соблюдается только при методе (1).
А чем вариант считать по количеству нерешивших плох?
Dendr писал(а):Странно. Наверное, где-то тут не удовлетворяется один из принципов...
Да, обламывается принцип независимости.

Рассмотрим 100 избирателей.
30 голосуют A>Б>B
30 голосуют так же: A>Б>B
40 голосуют: Б>A>В. Ясно, что В - лузер, а в остальном ЦИК скажет A>Б, итого A>Б>В.

Теперь:

30 голосуют А>Б>В
30 голосуют В>A>Б
40 голосуют Б>В>A.

Получам: А>Б - 60; Б>В - 70; В>A - 70. Придется считать точнее.
Итого по той системе Dendr'a за A - 60-70=-10. Б - 70-60=10 В - 60-60=0 ==> Б>В>A.
Но, по принципу независимости от посторонних альтернатив, A>Б. Фигово :(
Последний раз редактировалось molch64 19 фев 2008, 22:47, всего редактировалось 1 раз.
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Выборы, выборы, кандидаты ...

Сообщение Инна »

molch64 писал(а): А чем вариант считать по количеству нерешивших плох?
Сейчас, будем сходу придумывать. Пусть есть участники Х У Z. У X например 20 очков, у У 10 очков, а у Z - 9.
Пусть участник Х во втором случае решил дополнительно две задачи, причем те, которые решил Y но не решил Z, а результаты Y и Z остались те же.
Тогда сумма у Y уменьшится на 2 (за счет понижения по баллу на этих двух задачах) и станет 8, а у Z не изменится. Z обгонит Y, его место улучшится, что исключается (***)
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
molch64
Литератор-любитель
Литератор-любитель
Сообщения: 266
Зарегистрирован: 08 июн 2006, 11:05
Пол: Мужской

Re: Выборы, выборы, кандидаты ...

Сообщение molch64 »

Инна писал(а):Сейчас, будем сходу придумывать. Пусть есть участники Х У Z. У X например 20 очков, у У 10 очков, а у Z - 9.
Пусть участник Х во втором случае решил дополнительно две задачи, причем те, которые решил Y но не решил Z, а результаты Y и Z остались те же.
Тогда сумма у Y уменьшится на 2 (за счет понижения по баллу на этих двух задачах) и станет 8, а у Z не изменится. Z обгонит Y, его место улучшится, что исключается (***)
А... Понял, нужно сохранить относительный порядок между собой всех участников без того кто решил больше задач. Согласен. :)
Зато есть дополнительный стимул у тех, кто решил сложную задачу никому её не рассказывать (в т.ч. аутсайдерам, которые уж точно не догонят)
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

Ответить

Вернуться в «Задачки»