Групповое определение в тестировании программного обеспечения
Групповое определение в тестировании программного обеспечения
Др. Джеймс Мак-Кэффри (Dr. James McCaffrey)
Подумайте об общей проблеме определения лучшего варианта из списка, когда процесс принятия решений выполняется группой людей, а не одним человеком, или посредством чисто количественного приема. В число примеров действий такого рода входят голосование на выборах губернатора города из списка кандидатов и определение советом директоров крупной компании, приобретение какой из нескольких мелких компаний следует поставить целью. По сути, группа должна обговорить свои варианты таким образом, чтобы можно было определить лучший из них.
Групповое определение лучшей из альтернатив случается также в разработке и тестировании программного обеспечения. Для примера, рассмотрим группу пользователей бета-версии, выбирающих лучший интерфейс пользователя из набора прототипов. Или представьте себе членов проекта с открытым исходным кодом, голосующих за политику.
Мне приходилось отмечать, что практические приемы выполнения группового определения лучшей из альтернатив и потенциальные ловушки этого процесса не слишком известны в сообществе тестировщиков программного обеспечения. Существуют десятки приемов группового анализа. В статье за этот месяц я опишу пять наиболее распространенных методов, используемых для группового определения лучшей альтернативы в среде тестирования программного обеспечения: методика простого большинства, методика нескольких туров голосований, система счета Борда, метод Кондорсе и метод Шульце.
Все эти приемы анализа хорошо известны за пределами разработки программного обеспечения и были всесторонне исследованы. Я опишу каждый из приемов с упором на его применение к тестированию программного обеспечения. Я думаю, что читатели найдет знание о приемах группового анализа ценным добавлением к своему инструментарию.
Ситуации, где группа людей должна выбрать только один вариант из набора, случаются в широком спектре областей задач. В различных областях обычно используется различная терминология. Например, в социологии изучение проблем такого типа обычно именуется теорией социального выбора; в ней, как правило, используются такие термины, как «варианты» и «оценивающие». В политологии анализ этих проблем часто называется теорией голосования; в ней используются термины «кандидаты» и «избиратели». В математике групповое определение лучшего из вариантов часто считается подветвью теории решений. В моем рассказе я буду использовать смесь терминологий по причине отсутствия определенного набора терминологий, используемого при применении приемов к разработке программного обеспечения и среде тестирования.
Приемы, которые я описываю в этой статье, применимы к довольно узкому диапазону проблем и не применяются в чистом виде к ситуациям, когда лучший выбор можно четко определить в числовой форме. Как можно будет увидеть, когда группа людей выбирает «лучший» вариант, значение характеристики «лучший» определяется используемым приемом. Кроме того, описываемые мною здесь приемы неприменимы к ситуациям сотрудничества, когда группа использует дискуссию и согласование, чтобы достичь консенсуса.
Простое большинство и голосование в несколько туров
Начнем рассказ о групповом определении лучшего варианта со взгляда на простейший и наиболее распространенный прием - но позвольте мне предупредить, что во многих ситуациях тестирования он не является лучшим. Предположим, что мы разрабатываем корпоративное программное приложение для внутреннего использования в компании и создали четыре довольно различных прототипа интерфейса пользователя. Хотя попросить оценить различные прототипы можно и одного человека, во многих случаях лучше предложить сравнить четыре различных проекта группе людей.
Как оказывается, процесс выполнения групповой оценки и интерпретации результатов несколько хитрее, чем может показаться. Простейший из возможных приемов групповой оценки - предоставить оценивающим варианты и позволить им выбрать, или проголосовать за, лишь один из них. Вариант, получивший большинство голосов, объявляется победителем. Этот прием часто именуется правилом простого большинства.
Итак, предположим, что четыре различных прототипа (назовем их А, В, С и D) отправлены 10 оценивающим, и каждому из них предложено выбрать лучший прототип. И предположим, что результаты таковы: прототип А считают лучшим 4 человека, В - 3 человека, С - 2 человека и D - один человек. В силу этого для дальнейшей разработки выбирается прототип А.
Здесь есть несколько проблем. Предположим, что когда оценивающие рассматривают четыре прототипа, они явно или неявно расставляют их по ранжиру, как показано на рис. 1. В этой схеме каждый столбец представляет ранжирование прототипов одним из оценивающих.
Рис. 1. Ранжирование прототипов для 10 оценивающих
Отметьте, что хотя прототип А выбран простым большинством, 60% группы оценивающих оценили его как худший. Вдобавок, предположим, что прототип А из данной ситуации был бы сравнен по очереди с каждым из других прототипов. Прототип А проиграл бы в каждом из лобовых сравнений с соотношением 60% к 40%. Вторая, тесно связанная с этим проблема приема простого большинства заключается в том, что мнения, не получившие большинства, ничего не вносят в итоговый результат.
Проблемы с чистым большинством ведут к другому приему группового выбора, именуемому системой голосования в несколько туров. Существуют несколько вариантов этой методики, но для победы в ней всегда необходимо получить более 50% всех поданных голосов.
Этого можно добиться за счет нескольких туров голосования или выполнения лишь одного тура, в котором оценивающие должны ранжировать все возможные варианты. Например, если бы оценивающие проголосовали за лучший проект прототипа, как показано на рис. 1, ни один из прототипов не получил бы большинства после первого раунда голосования. Так что список кандидатов мог бы быть сокращен, обычно до двух наиболее популярных вариантов; в данном случае прототипа А с четырьмя голосами и прототипа В с тремя голосами.
После этого произошел бы второй тур голосования. Если в нем оценивающие проголосовали бы соответственно своим предпочтениям с рис. 1, то после второго тура прототип А все еще получил бы четыре голоса, но прототип В получил бы шесть голосов, поскольку оценивающие, ранее выбиравшие прототипы С и D, выбрали бы теперь прототип В.
По моему опыту, использование нескольких туров голосования в разработке программного обеспечения и средах тестирования имеет существенные недостатки по сравнению с одним туром. Во-первых, в некоторых ситуациях разработки программного обеспечения несколько туров голосования просто не применимы практически. Вдобавок, поскольку речь идет о работе с людьми, несколько туров голосования могут всем надоесть. Что еще хуже, может возникнуть ситуация, в которой группа людей голосует за проигрывающие варианты раз за разом (неизменно получая негативный ответ), пока им не придется выбрать не нравящийся им вариант. Если голосующие являются заинтересованными лицами, в том смысле, что результат голосования скажется на них, то в итоге схемы с несколькими физическими турами можно получить голосующих, лишившихся своего права повлиять на ситуацию.
Вместо выполнения нескольких реальных туров голосования, где каждый оценивающий голосует лишь за одну альтернативу, можно просто выполнить один раунд голосования, но потребовать от оценивающих ранжировать все варианты от лучшего к худшему. Это позволяет определить предпочтения голосующих в виртуальных турах голосования.
Требование ранжирования всех вариантов тоже имеет определенные недостатки. Этот прием часто непрактичен, когда число вариантов велико (обычно больше восьми), просто потому, что людям сложно сравнивать большое число альтернатив. Кроме того, исследования показали, что оценивающие часто становятся беспечны при оценке вариантов, стоящих низко в их списке предпочтений. И при выполнении нескольких физических туров голосования оценивающие могут ранжировать поднабор вариантов в том же порядке, в котором они ранжировали полный набор.
Метод Шульце: за и против
У метода Шульце есть свои сильные и слабые стороны. Одной из слабостей в некоторых случаях является то, что метод Шульце далеко не интуитивен. В случаях, когда оценивающие являются заинтересованными лицами, метод Шульце может легко представиться загадочным черным ящиком, магически производящим результаты.
Основным преимуществом метода Шульце является то, что он был всесторонне проанализирован и показал свое соответствие многим важным критериям. (Вспомним, что на систему счета Борда может повлиять удаление варианта, не имеющего отношения к делу.)
Существует много критериев оценки систем голосования. Например, критерий монотонности можно грубо сформулировать как принцип, согласно которому выигрывающий вариант не может стать невыигрышным из-за одного или нескольких оценивающих, оценивших его выше. Критерий независимости от вариантов-клонов заявляет, грубо говоря, что добавление нового варианта, идентичного существующему, не должно влиять на исход анализа. Существует также много предлагаемых критериев оценки систем голосования; метод Шульце продемонстрировал свое соответствие и большинству из них.
Интересным исключением является то, что метод Шульце нарушает так называемый критерий участия. В неформальных терминах, к существующей системе можно добавить новых голосующих, которые предпочитают текущего победителя другим вариантам, в результате чего менее предпочитаемый вариант становится победителем по методу Шульце.
Несмотря на эти недостатки, метод Шульце часто очень эффективен, особенно в ситуациях с большой, образованной (то есть имеющей представление о методе Шульце) группой оценивающих, определяющих альтернативную политику (а не принимающих решение о продукте) и являющихся заинтересованной стороной в конечном результате. Например, метод Шульце используется несколькими группами, работающими над проектами с открытым кодом, для определения общей политики и для выбора лиц на должности. В случаях тестирования программного обеспечения метод Шульце обычно является первым приемом, который я предпочитаю применить, а затем я использую эти результаты в качестве основы, с которой сравниваются результаты остальных приемов.
Система счета Борда
Проблемы с методиками простого большинства и голосования в несколько туров привели к разработке двух очень распространенных приемов группового анализа. Это система счета Борда и метод попарного сравнения Кондорсе, названные в честь двух математиков, предложивших эти подходы во второй половине XVIII века.
Система счета Борда очень проста, и читатели почти наверняка знакомы с ней. Предположим, что существует n вариантов. Каждый из оценивающих ранжирует варианты от лучшего к худшему. Получившему наибольший ранг варианту выдается n-1 очков, второму n-2 очков и так далее вплоть до последнего из вариантов, получающего 0 очков. Счет Борда - это просто сумма очков для каждого из вариантов.
Краткий пример для пояснения этих мыслей. Предположим, что имеется четыре варианта A, B, C и D. В этом случае вариант, получивший первое место, стоит 3 очка, второе - 2, третье - 1 и последнее место стоит 0 очков. На рис. 2 показаны результаты, а под ними счет Борда для семи оценивающих, где как лучший из предлагаемых выбран вариант А.
Рис. 2. Результаты и значения счета Борда для семи оценивающих (щелкните изображение, чтобы увеличить его)
Прием счета Борда широко используется во многих областях задач, особенно в спортивных состязаниях. Преимущества приема счета Борда при использовании в разработке программного обеспечения и средах тестирования заключаются в интуитивной понятности приема и принятии во внимание мнений всех оценивающих.
Но у приема счета Борда есть несколько технических проблем. Предположим, мы решили удалить вариант D, который явно проигрывает остальным. Здравый смысл говорит, что удаление не имеющего значения варианта не должно повлиять на конечный результат. Но на рис. 3 показано, что случается после удаления варианта D. Теперь вариант В становится лучшим вместо А. Другими словами, с этим набором данных устранение не имеющего значения варианта меняет результат. Можно даже сконструировать примеры счета Борда, в которых лучший из вариантов реально становится худшим. Этот эффект порой именуется парадоксом превращения победителя в проигравшего при счете Борда.
Рис. 3. Результаты и счета Борда после удаления варианта D (щелкните изображение, чтобы увеличить его)
У приема счета Борда есть две другие, тесно связанные технические проблемы. Первая - это проблема попарного сравнения. При использовании счета Борда возможно столкнуться с ситуацией, когда победитель по этому приему проиграет любому другому варианту при прямом сравнении с ним.
Предположим для примера, что имеется четыре варианта и 12 оценивающих (см. рис. 4). При использовании метода счета Борда вариант А выбирается лучшим, набрав 25 очков. Однако если сравнить варианты друг с другом, то можно заметить, что вариант В предпочитается всем прочим: B предпочитают A 7 человек против 5, B предпочитают C также 7 против 5 и B предпочитают D, опять же, 7 против 5.
Рис. 4. Вариант В выигрывает в прямом сравнении (щелкните изображение, чтобы увеличить его)
Другой проблемой с приемом счета Борда является его уязвимость к манипуляциям оценивающими. На результат оценки счетом Борда теоретически возможно повлиять добавлением мнимой альтернативы, которая (с точки зрения предпочтений оценивающих) очень близка к существующей. Это может привести к «разбавлению» близких альтернатив и изменению победителя анализа. Ссылки в конце данной статьи содержат примеры данного эффекта.
Несмотря на технические недостатки приема счета Борда, эта система весьма практичная и часто эффективно работает при определении политики в среде тестирования программного обеспечения небольшими группами. Согласно моему опыту, счет Борда часто субъективно считается честным голосующими и, следовательно, если голосующие являются заинтересованными сторонами, те, кто проголосовал за проигравшие варианты, обычно принимают результаты голосования и не вырабатывают предубеждения против выигравшего варианта.
Мораль этой истории в том, что в случае использования счета Борда следует знать об эффекте удаления несущественных вариантов, результатах попарного сравнения победителя по счету Борда с проигравшими вариантами, а также добавлении новой альтернативы в середине процесса и проверять свои данные на предмет всего этого.
Прием Кондорсе и метод Шульце
Прием Кондорсе для совместного определения лучшего варианта из набора был разработан в первую очередь как реакция на проблему попарного сравнения в методе счета Бодпа. Метод Кондорсе очень прост. Он требует от оценивающих ранжировать все варианты, после чего формируется сравнение результатов между каждой возможной парой вариантов.
Если один из вариантов побивает все остальные варианты в прямом сравнении, то этот вариант объявляется победителем по методике Кондорсе. Если этот прием не дает победителя, то используется отдельный прием для разрешения ничейных вариантов. Этот прием разрешения ничьих может быть любым; смысл системы Кондорсе состоит в том, что единогласный победитель в прямых сравнениях должен автоматически выигрывать у любых вариантов, выбранных по любым другим критериям.
На практике, система Кондорсе редко используется как прием групповой оценки сама по себе. Вместо этого примы оценки наподобие простого большинства и счета Борда анализируются математически, чтобы увидеть, удовлетворяют ли они принципу Кондорсе во всех случаях. Так что вместо: «Мы решили использовать систему Кондорсе для оценки имеющихся альтернатив», чаще можно прочесть нечто вроде: «Мы решили использовать систему оценки Х, отвечающую принципу Кондорсе».
Одна из наиболее интересных систем, отвечающих принципу Кондорсе, имеет ряд названий, включая «метод Шульце», «защищенная от клонов методика последовательного отброса Шварца» и «метод прокладки пути». Я буду называть этот прием «методом Шульце».
Метод Шульце несколько более сложен, чем ранее описанные мною методики. Он подобен системе Кондорсе в том смысле, что смотрит, не выигрывает ли один вариант у всех других. Но вместо прямого использования данных ранжировки, как это делается в системе Кондорсе, в методе Шульце выполняется попарное сравнение при помощи непрямого измерения сравнительной силы альтернатив. Это непрямое измерение называется силой пути.
Давайте разберем это на примере. Взгляните на рис. 5. На нем показано простую демонстрацию метода Шульце в действии. На первой части показан пример ввода. Имеются четыре варианта (A, B, C и D) и 11 оценивающих. Первая строка означает, что трое оценивающих помещают вариант А над В, который, в свою очередь, лучше С, который лучше D. Метод Шульце позволяет оценивающим давать вариантам разные оценки, а также не давать оценок вовсе.
Рис. 5. Демонстрация метода Шульце (щелкните изображение, чтобы увеличить его)
В следующей части результатов показана матрица поражений в попарных сравнениях. Эта матрица вычисляется напрямую из данных первоначальной ранжировки.
Первая строка матрицы означает, что вариант А предпочитается варианту В шестью голосующими, предпочитается С тремя, а D - четырьмя. Вторая строка означает, что 5 голосующих предпочитают вариант В варианту А, 7 - варианту С и 8-варианту D. Третья и четвертая строки для вариантов C и D интерпретируются аналогичным образом. Значения матрицы поражений в попарных сравнениях на основой диагонали равны 0, поскольку эти значения являются сравнением варианта с самим собой.
На этом этапе в системе Кондорсе была бы выполнена проверка этих данные прямого сравнения в парах, чтобы увидеть, не выявился ли единогласный победитель, но в методе Шульце вычисляется непрямое значение силы вариантов. Следующая часть результатов - это сила путей между каждым вариантом. Это ключевая и весьма остроумная идея метода Шульце. Третья строка этой матрицы означает, что сила пути от варианта С к варианту А равна 8, от С к В равна 4, а от С к D равна 10.
Объяснить идею силы пути лучше всего визуально, как сделано на рис. 6. Сперва мы выражаем данные ранжировок в матрице поражений в попарных сравнениях. Далее мы представляем поражения в попарных сравнениях в виде ориентированного графа.
Рис. 6. Поражения в попарных сравнениях в форме матрицы и графа (щелкните изображение, чтобы увеличить его)
Стрелка от узла А к узлу В означает, что 6 оценивающих предпочитают вариант А варианту В. Я не поместил стрелки от узла В к узлу А, поскольку только 5 оценивающих предпочитают вариант В варианту, так что А господствует над В. В этом примере все стрелки односторонни, но если два узла предпочитаются равным числом оценивающих, то я могу нарисовать двустороннюю стрелку.
Теперь рассмотрим путь от узла А к узлу D. А побивает В на шесть, а В в свою очередь побивает D на 8. Мы выбираем 6, меньшее из этих значений, чтобы представить общую силу пути между А и D. Смысл в том, что общую силу пути между двумя узлами, где есть промежуточные узлы, лучше всего предоставлять наименьшей из сил прямого пути от узла к узлу. Обратите внимание, что мы также можем пройти от А к D другим путем и сказать, что А побивает В на 6, В побивает С на 7 и С побивает D на 10, после чего выбрать наименьшее число, 6, что даст нам тот же результат.
Выходит, что вычисление силы каждой пары узлов можно выполнить с помощью варианта элегантного алгоритма Флойда-Уоршолла, как я сейчас объясню. Стандартный алгоритм Флойда-Уоршолла находит самый короткий путь во взвешенном ориентированном графе. После того, как силы пути были определены, мы можем определить победителей по методу Шульце, проверив, существует ли вариант, в котором сила пути больше или равна соответствующим силам пути всех других вариантов.
На Рис. 7 показана матрица сил пути, соответствующая данным на рис. 6; видно, что победителем по методу Шульце является вариант В. Визуально вариант является победителем по методу Шульце, если значение силы каждого пути в строке этого варианта выше или равно соответствующему значению вдоль основной диагонали матрицы.
Рис. 7. Данные силы пути используются для определения победителя по методу Шульце
Вариант В является победителем, поскольку сила пути варианта В к варианту А равна 7 (а варианта А к варианту В - только 6), сила его пути к варианту С - 7 (но сила пути С к В - только 6) и сила его пути к варианту D - 8 (но сила пути от D к В - только 6). С другой стороны, вариант D не является победителем по методу Шульце, поскольку сила пути варианта D лучше, чем варианта А (7 к 6), но сила варианта D хуже, чем варианта С (6 к 10).
Метод Шульце в коде
В этом примере имеется лишь один победитель по методу Шульце, но их может быть несколько. В подобных ситуациях необходимо использовать какую-либо форму разрешения ничьих. Давайте разберем часть кода в программе, создающей результаты с рис. 5, чтобы лучше разобраться в методе Шульце.
Программа начинает с установки типа перечисления для представления альтернатив и глобального значения N для хранения реального числа альтернатив:
enum options { A, B, C, D, E, F, G, H, I, J };
static int N; // actual number of options
Затем демонстрационная программа устанавливает ввод задачи в форме массива строк:
string[] rawData = new string[] {
"A>B>C>D 3",
"B>C>D>A 4",
"C>D>A>B 2",
"D>C>B>A 1",
"C>A>B>D 1"
};
Для простоты в моей демонстрационной программе подразумевается, что ничьи не дозволены и что все варианты ранжированы. Это позволяет мне очень просто анализировать строки необработанных данных. Законченная демонстрационная программа доступна в материалах для загрузки, прилагаемых к статье. Изменение кода, чтобы он позволял ничьи и отсутствующие варианты, не должно представлять больших проблем.
Далее, моя демонстрационная программа проверяет массив строк rawData, после чего определяет и распечатывает число вариантов и число оценивающих. Далее программа заново проверяет массив ввода и создает матрицу поражений в попарных сравнениях, используя статический метод помощи, именуемый MakeDefeats:
int[,] defeats = MakeDefeats(rawData);
Console.WriteLine("\n== Pairwise defeats data is: \n");
Print(defeats);
Матрица поражений затем передается в качестве ввода другому вспомогательному методу, именуемому MakePathStrengths, который создает матрицу сил путей:
int[,] strengths = MakePathStrengths(defeats);
Console.WriteLine("\n== Path strength data is: \n");
Print(strengths);
Внутри метода MakePathStrengths я начинаю с устранения записей, над которыми господствуют другие:
int[,] result = new int[N, N];
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (d[i, j] > d[j, i])
result[i, j] = d[i, j];
else
result[i, j] = 0;
}
}
Обратите внимание, что оператор result[i, j] = 0; не является технически необходимым, поскольку C# автоматически инициализирует все элементы массивов типа int нулями.
Далее я использую вариант алгоритма Флойда-Уоршолла, чтобы вычислить силу каждого из возможных путей:
for (int k = 0; k < N; ++k) {
for (int i = 0; i < N; ++i) {
if (k == i) continue;
for (int j = 0; j < N; ++j) {
if (k == j || i == j) continue;
result[i, j] =
Math.Max(result[i, j], Math.Min(result[i, k], result[k, j]));
} //j
} //i
} //k
Если проследить за кодом вручную, то можно заметить, что он реализует определение силы пути, существующее между узлом [i] и узлом [j], как я описал ранее. Метод Max в коде работает над обеспечением того, чтобы при каждом проходе через внешний цикл я обновлял бы матрицу результатов, только если найден более сильный путь. Метод Min в коде соответствует идее использования наименьшей силы между узлами для представления общей силы пути, существующей между любыми двумя узлами.
После того, как у меня имеются силы всех путей, я могу использовать эту информацию для вычисления массива, представляющего победителей по методу Шульце, и затем перебрать этот массив и отобразить значение перечисления, соответствующее каждому победителю:
bool[] winners = MakeWinners(strengths);
Console.WriteLine("\n== Best option(s) is: \n");
for (int i = 0; i < winners.Length; ++i) {
if (winners[i] == true)
Console.Write(Enum.GetName(typeof(options), i) + " ");
}
Метод MakeWinners устанавливает одномерный логический массив, где значение true указывает победителя, а значение false - все остальных. Я предполагаю, что каждый из вариантов является победителем, затем перебираю матрицу силы путей, сравнивая значение силы в индексе [i,j] с тем же в индексе [j,i], чтобы увидеть, является ли этот вариант победителем на самом деле:
static int[] MakeWinners(int[,] ps) {
bool[] result = new bool[N];
for (int i = 0; i < N; ++i)
result[i] = true;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j)
if (ps[i, j] < ps[j, i])
result[i] = false;
}
return result;
}
Что еще оценивать
В число некоторых из ключевых факторов, которые следует принимать во внимание при использовании приемов групповой оценки, входит число вариантов, число оценивающих, являются ли альтернативы решениями по политикам или решениями по продуктам, и степень, в которой оценивающих затрагивают итоговые результаты анализа. В целом, следует по возможности использовать более чем один прием группового анализа, чтобы использовать несколько результатов для перекрестной проверки анализа (если несколько приемов приводят к одному результату, то это придает уверенности в нем).
Ситуации, в которых используются приемы, описанные мною в этой статье, почти всегда довольно субъективны. Опыт и интуиция должны играть большую роль в анализе результатов группового определения.
Как общее эмпирическое правило, прием простого большинства эффективен только в случаях, когда оценивающие не являются заинтересованными сторонами или когда ранжирование всех вариантов непрактично. Прием голосования в несколько туров в принципе может привести к отчуждению до 49% оценивающих и, по моему опыту, его обычно стоит использовать лишь для поддержки других приемов.
Система счета Борда, несмотря на свои технические недостатки, работает довольно неплохо, особенно когда оценивающие являются заинтересованными сторонами. Принцип Кондорсе очень прост и, в силу этого, часто может быть использован для проверки результатов других приемов. Метод Шульце - отличная многоцелевая методика во многих ситуациях тестирования программного обеспечения, за исключением случаев, когда речь идет об относительно малой группе оценивающих, на которых скажутся результаты и которые не разбираются в алгоритме Шульце.
В этой статье излагаются лишь основы интересного и полезного предмета. Существует большое число исследований по приемам группового определения лучшего варианта из набора. Среди прочих стоит воспользоваться книгой «A Primer in Social Choice Theory» («Знакомство с теорией социального выбора»), написанной Вульфом Гэртнером (Wulf Gaertner) (изд-во Oxford University Press, 2006 г.). Я также рекомендую «Comparing Voting Systems» («Сравнение систем голосования»), за авторством Ханну Нурми (Hannu Nurmi) (изд-во Springer-Verlag, 1987 г.).
Др. Джеймс Мак-Кэффри (Dr. James McCaffrey)
Подумайте об общей проблеме определения лучшего варианта из списка, когда процесс принятия решений выполняется группой людей, а не одним человеком, или посредством чисто количественного приема. В число примеров действий такого рода входят голосование на выборах губернатора города из списка кандидатов и определение советом директоров крупной компании, приобретение какой из нескольких мелких компаний следует поставить целью. По сути, группа должна обговорить свои варианты таким образом, чтобы можно было определить лучший из них.
Групповое определение лучшей из альтернатив случается также в разработке и тестировании программного обеспечения. Для примера, рассмотрим группу пользователей бета-версии, выбирающих лучший интерфейс пользователя из набора прототипов. Или представьте себе членов проекта с открытым исходным кодом, голосующих за политику.
Мне приходилось отмечать, что практические приемы выполнения группового определения лучшей из альтернатив и потенциальные ловушки этого процесса не слишком известны в сообществе тестировщиков программного обеспечения. Существуют десятки приемов группового анализа. В статье за этот месяц я опишу пять наиболее распространенных методов, используемых для группового определения лучшей альтернативы в среде тестирования программного обеспечения: методика простого большинства, методика нескольких туров голосований, система счета Борда, метод Кондорсе и метод Шульце.
Все эти приемы анализа хорошо известны за пределами разработки программного обеспечения и были всесторонне исследованы. Я опишу каждый из приемов с упором на его применение к тестированию программного обеспечения. Я думаю, что читатели найдет знание о приемах группового анализа ценным добавлением к своему инструментарию.
Ситуации, где группа людей должна выбрать только один вариант из набора, случаются в широком спектре областей задач. В различных областях обычно используется различная терминология. Например, в социологии изучение проблем такого типа обычно именуется теорией социального выбора; в ней, как правило, используются такие термины, как «варианты» и «оценивающие». В политологии анализ этих проблем часто называется теорией голосования; в ней используются термины «кандидаты» и «избиратели». В математике групповое определение лучшего из вариантов часто считается подветвью теории решений. В моем рассказе я буду использовать смесь терминологий по причине отсутствия определенного набора терминологий, используемого при применении приемов к разработке программного обеспечения и среде тестирования.
Приемы, которые я описываю в этой статье, применимы к довольно узкому диапазону проблем и не применяются в чистом виде к ситуациям, когда лучший выбор можно четко определить в числовой форме. Как можно будет увидеть, когда группа людей выбирает «лучший» вариант, значение характеристики «лучший» определяется используемым приемом. Кроме того, описываемые мною здесь приемы неприменимы к ситуациям сотрудничества, когда группа использует дискуссию и согласование, чтобы достичь консенсуса.
Простое большинство и голосование в несколько туров
Начнем рассказ о групповом определении лучшего варианта со взгляда на простейший и наиболее распространенный прием - но позвольте мне предупредить, что во многих ситуациях тестирования он не является лучшим. Предположим, что мы разрабатываем корпоративное программное приложение для внутреннего использования в компании и создали четыре довольно различных прототипа интерфейса пользователя. Хотя попросить оценить различные прототипы можно и одного человека, во многих случаях лучше предложить сравнить четыре различных проекта группе людей.
Как оказывается, процесс выполнения групповой оценки и интерпретации результатов несколько хитрее, чем может показаться. Простейший из возможных приемов групповой оценки - предоставить оценивающим варианты и позволить им выбрать, или проголосовать за, лишь один из них. Вариант, получивший большинство голосов, объявляется победителем. Этот прием часто именуется правилом простого большинства.
Итак, предположим, что четыре различных прототипа (назовем их А, В, С и D) отправлены 10 оценивающим, и каждому из них предложено выбрать лучший прототип. И предположим, что результаты таковы: прототип А считают лучшим 4 человека, В - 3 человека, С - 2 человека и D - один человек. В силу этого для дальнейшей разработки выбирается прототип А.
Здесь есть несколько проблем. Предположим, что когда оценивающие рассматривают четыре прототипа, они явно или неявно расставляют их по ранжиру, как показано на рис. 1. В этой схеме каждый столбец представляет ранжирование прототипов одним из оценивающих.
Рис. 1. Ранжирование прототипов для 10 оценивающих
Отметьте, что хотя прототип А выбран простым большинством, 60% группы оценивающих оценили его как худший. Вдобавок, предположим, что прототип А из данной ситуации был бы сравнен по очереди с каждым из других прототипов. Прототип А проиграл бы в каждом из лобовых сравнений с соотношением 60% к 40%. Вторая, тесно связанная с этим проблема приема простого большинства заключается в том, что мнения, не получившие большинства, ничего не вносят в итоговый результат.
Проблемы с чистым большинством ведут к другому приему группового выбора, именуемому системой голосования в несколько туров. Существуют несколько вариантов этой методики, но для победы в ней всегда необходимо получить более 50% всех поданных голосов.
Этого можно добиться за счет нескольких туров голосования или выполнения лишь одного тура, в котором оценивающие должны ранжировать все возможные варианты. Например, если бы оценивающие проголосовали за лучший проект прототипа, как показано на рис. 1, ни один из прототипов не получил бы большинства после первого раунда голосования. Так что список кандидатов мог бы быть сокращен, обычно до двух наиболее популярных вариантов; в данном случае прототипа А с четырьмя голосами и прототипа В с тремя голосами.
После этого произошел бы второй тур голосования. Если в нем оценивающие проголосовали бы соответственно своим предпочтениям с рис. 1, то после второго тура прототип А все еще получил бы четыре голоса, но прототип В получил бы шесть голосов, поскольку оценивающие, ранее выбиравшие прототипы С и D, выбрали бы теперь прототип В.
По моему опыту, использование нескольких туров голосования в разработке программного обеспечения и средах тестирования имеет существенные недостатки по сравнению с одним туром. Во-первых, в некоторых ситуациях разработки программного обеспечения несколько туров голосования просто не применимы практически. Вдобавок, поскольку речь идет о работе с людьми, несколько туров голосования могут всем надоесть. Что еще хуже, может возникнуть ситуация, в которой группа людей голосует за проигрывающие варианты раз за разом (неизменно получая негативный ответ), пока им не придется выбрать не нравящийся им вариант. Если голосующие являются заинтересованными лицами, в том смысле, что результат голосования скажется на них, то в итоге схемы с несколькими физическими турами можно получить голосующих, лишившихся своего права повлиять на ситуацию.
Вместо выполнения нескольких реальных туров голосования, где каждый оценивающий голосует лишь за одну альтернативу, можно просто выполнить один раунд голосования, но потребовать от оценивающих ранжировать все варианты от лучшего к худшему. Это позволяет определить предпочтения голосующих в виртуальных турах голосования.
Требование ранжирования всех вариантов тоже имеет определенные недостатки. Этот прием часто непрактичен, когда число вариантов велико (обычно больше восьми), просто потому, что людям сложно сравнивать большое число альтернатив. Кроме того, исследования показали, что оценивающие часто становятся беспечны при оценке вариантов, стоящих низко в их списке предпочтений. И при выполнении нескольких физических туров голосования оценивающие могут ранжировать поднабор вариантов в том же порядке, в котором они ранжировали полный набор.
Метод Шульце: за и против
У метода Шульце есть свои сильные и слабые стороны. Одной из слабостей в некоторых случаях является то, что метод Шульце далеко не интуитивен. В случаях, когда оценивающие являются заинтересованными лицами, метод Шульце может легко представиться загадочным черным ящиком, магически производящим результаты.
Основным преимуществом метода Шульце является то, что он был всесторонне проанализирован и показал свое соответствие многим важным критериям. (Вспомним, что на систему счета Борда может повлиять удаление варианта, не имеющего отношения к делу.)
Существует много критериев оценки систем голосования. Например, критерий монотонности можно грубо сформулировать как принцип, согласно которому выигрывающий вариант не может стать невыигрышным из-за одного или нескольких оценивающих, оценивших его выше. Критерий независимости от вариантов-клонов заявляет, грубо говоря, что добавление нового варианта, идентичного существующему, не должно влиять на исход анализа. Существует также много предлагаемых критериев оценки систем голосования; метод Шульце продемонстрировал свое соответствие и большинству из них.
Интересным исключением является то, что метод Шульце нарушает так называемый критерий участия. В неформальных терминах, к существующей системе можно добавить новых голосующих, которые предпочитают текущего победителя другим вариантам, в результате чего менее предпочитаемый вариант становится победителем по методу Шульце.
Несмотря на эти недостатки, метод Шульце часто очень эффективен, особенно в ситуациях с большой, образованной (то есть имеющей представление о методе Шульце) группой оценивающих, определяющих альтернативную политику (а не принимающих решение о продукте) и являющихся заинтересованной стороной в конечном результате. Например, метод Шульце используется несколькими группами, работающими над проектами с открытым кодом, для определения общей политики и для выбора лиц на должности. В случаях тестирования программного обеспечения метод Шульце обычно является первым приемом, который я предпочитаю применить, а затем я использую эти результаты в качестве основы, с которой сравниваются результаты остальных приемов.
Система счета Борда
Проблемы с методиками простого большинства и голосования в несколько туров привели к разработке двух очень распространенных приемов группового анализа. Это система счета Борда и метод попарного сравнения Кондорсе, названные в честь двух математиков, предложивших эти подходы во второй половине XVIII века.
Система счета Борда очень проста, и читатели почти наверняка знакомы с ней. Предположим, что существует n вариантов. Каждый из оценивающих ранжирует варианты от лучшего к худшему. Получившему наибольший ранг варианту выдается n-1 очков, второму n-2 очков и так далее вплоть до последнего из вариантов, получающего 0 очков. Счет Борда - это просто сумма очков для каждого из вариантов.
Краткий пример для пояснения этих мыслей. Предположим, что имеется четыре варианта A, B, C и D. В этом случае вариант, получивший первое место, стоит 3 очка, второе - 2, третье - 1 и последнее место стоит 0 очков. На рис. 2 показаны результаты, а под ними счет Борда для семи оценивающих, где как лучший из предлагаемых выбран вариант А.
Рис. 2. Результаты и значения счета Борда для семи оценивающих (щелкните изображение, чтобы увеличить его)
Прием счета Борда широко используется во многих областях задач, особенно в спортивных состязаниях. Преимущества приема счета Борда при использовании в разработке программного обеспечения и средах тестирования заключаются в интуитивной понятности приема и принятии во внимание мнений всех оценивающих.
Но у приема счета Борда есть несколько технических проблем. Предположим, мы решили удалить вариант D, который явно проигрывает остальным. Здравый смысл говорит, что удаление не имеющего значения варианта не должно повлиять на конечный результат. Но на рис. 3 показано, что случается после удаления варианта D. Теперь вариант В становится лучшим вместо А. Другими словами, с этим набором данных устранение не имеющего значения варианта меняет результат. Можно даже сконструировать примеры счета Борда, в которых лучший из вариантов реально становится худшим. Этот эффект порой именуется парадоксом превращения победителя в проигравшего при счете Борда.
Рис. 3. Результаты и счета Борда после удаления варианта D (щелкните изображение, чтобы увеличить его)
У приема счета Борда есть две другие, тесно связанные технические проблемы. Первая - это проблема попарного сравнения. При использовании счета Борда возможно столкнуться с ситуацией, когда победитель по этому приему проиграет любому другому варианту при прямом сравнении с ним.
Предположим для примера, что имеется четыре варианта и 12 оценивающих (см. рис. 4). При использовании метода счета Борда вариант А выбирается лучшим, набрав 25 очков. Однако если сравнить варианты друг с другом, то можно заметить, что вариант В предпочитается всем прочим: B предпочитают A 7 человек против 5, B предпочитают C также 7 против 5 и B предпочитают D, опять же, 7 против 5.
Рис. 4. Вариант В выигрывает в прямом сравнении (щелкните изображение, чтобы увеличить его)
Другой проблемой с приемом счета Борда является его уязвимость к манипуляциям оценивающими. На результат оценки счетом Борда теоретически возможно повлиять добавлением мнимой альтернативы, которая (с точки зрения предпочтений оценивающих) очень близка к существующей. Это может привести к «разбавлению» близких альтернатив и изменению победителя анализа. Ссылки в конце данной статьи содержат примеры данного эффекта.
Несмотря на технические недостатки приема счета Борда, эта система весьма практичная и часто эффективно работает при определении политики в среде тестирования программного обеспечения небольшими группами. Согласно моему опыту, счет Борда часто субъективно считается честным голосующими и, следовательно, если голосующие являются заинтересованными сторонами, те, кто проголосовал за проигравшие варианты, обычно принимают результаты голосования и не вырабатывают предубеждения против выигравшего варианта.
Мораль этой истории в том, что в случае использования счета Борда следует знать об эффекте удаления несущественных вариантов, результатах попарного сравнения победителя по счету Борда с проигравшими вариантами, а также добавлении новой альтернативы в середине процесса и проверять свои данные на предмет всего этого.
Прием Кондорсе и метод Шульце
Прием Кондорсе для совместного определения лучшего варианта из набора был разработан в первую очередь как реакция на проблему попарного сравнения в методе счета Бодпа. Метод Кондорсе очень прост. Он требует от оценивающих ранжировать все варианты, после чего формируется сравнение результатов между каждой возможной парой вариантов.
Если один из вариантов побивает все остальные варианты в прямом сравнении, то этот вариант объявляется победителем по методике Кондорсе. Если этот прием не дает победителя, то используется отдельный прием для разрешения ничейных вариантов. Этот прием разрешения ничьих может быть любым; смысл системы Кондорсе состоит в том, что единогласный победитель в прямых сравнениях должен автоматически выигрывать у любых вариантов, выбранных по любым другим критериям.
На практике, система Кондорсе редко используется как прием групповой оценки сама по себе. Вместо этого примы оценки наподобие простого большинства и счета Борда анализируются математически, чтобы увидеть, удовлетворяют ли они принципу Кондорсе во всех случаях. Так что вместо: «Мы решили использовать систему Кондорсе для оценки имеющихся альтернатив», чаще можно прочесть нечто вроде: «Мы решили использовать систему оценки Х, отвечающую принципу Кондорсе».
Одна из наиболее интересных систем, отвечающих принципу Кондорсе, имеет ряд названий, включая «метод Шульце», «защищенная от клонов методика последовательного отброса Шварца» и «метод прокладки пути». Я буду называть этот прием «методом Шульце».
Метод Шульце несколько более сложен, чем ранее описанные мною методики. Он подобен системе Кондорсе в том смысле, что смотрит, не выигрывает ли один вариант у всех других. Но вместо прямого использования данных ранжировки, как это делается в системе Кондорсе, в методе Шульце выполняется попарное сравнение при помощи непрямого измерения сравнительной силы альтернатив. Это непрямое измерение называется силой пути.
Давайте разберем это на примере. Взгляните на рис. 5. На нем показано простую демонстрацию метода Шульце в действии. На первой части показан пример ввода. Имеются четыре варианта (A, B, C и D) и 11 оценивающих. Первая строка означает, что трое оценивающих помещают вариант А над В, который, в свою очередь, лучше С, который лучше D. Метод Шульце позволяет оценивающим давать вариантам разные оценки, а также не давать оценок вовсе.
Рис. 5. Демонстрация метода Шульце (щелкните изображение, чтобы увеличить его)
В следующей части результатов показана матрица поражений в попарных сравнениях. Эта матрица вычисляется напрямую из данных первоначальной ранжировки.
Первая строка матрицы означает, что вариант А предпочитается варианту В шестью голосующими, предпочитается С тремя, а D - четырьмя. Вторая строка означает, что 5 голосующих предпочитают вариант В варианту А, 7 - варианту С и 8-варианту D. Третья и четвертая строки для вариантов C и D интерпретируются аналогичным образом. Значения матрицы поражений в попарных сравнениях на основой диагонали равны 0, поскольку эти значения являются сравнением варианта с самим собой.
На этом этапе в системе Кондорсе была бы выполнена проверка этих данные прямого сравнения в парах, чтобы увидеть, не выявился ли единогласный победитель, но в методе Шульце вычисляется непрямое значение силы вариантов. Следующая часть результатов - это сила путей между каждым вариантом. Это ключевая и весьма остроумная идея метода Шульце. Третья строка этой матрицы означает, что сила пути от варианта С к варианту А равна 8, от С к В равна 4, а от С к D равна 10.
Объяснить идею силы пути лучше всего визуально, как сделано на рис. 6. Сперва мы выражаем данные ранжировок в матрице поражений в попарных сравнениях. Далее мы представляем поражения в попарных сравнениях в виде ориентированного графа.
Рис. 6. Поражения в попарных сравнениях в форме матрицы и графа (щелкните изображение, чтобы увеличить его)
Стрелка от узла А к узлу В означает, что 6 оценивающих предпочитают вариант А варианту В. Я не поместил стрелки от узла В к узлу А, поскольку только 5 оценивающих предпочитают вариант В варианту, так что А господствует над В. В этом примере все стрелки односторонни, но если два узла предпочитаются равным числом оценивающих, то я могу нарисовать двустороннюю стрелку.
Теперь рассмотрим путь от узла А к узлу D. А побивает В на шесть, а В в свою очередь побивает D на 8. Мы выбираем 6, меньшее из этих значений, чтобы представить общую силу пути между А и D. Смысл в том, что общую силу пути между двумя узлами, где есть промежуточные узлы, лучше всего предоставлять наименьшей из сил прямого пути от узла к узлу. Обратите внимание, что мы также можем пройти от А к D другим путем и сказать, что А побивает В на 6, В побивает С на 7 и С побивает D на 10, после чего выбрать наименьшее число, 6, что даст нам тот же результат.
Выходит, что вычисление силы каждой пары узлов можно выполнить с помощью варианта элегантного алгоритма Флойда-Уоршолла, как я сейчас объясню. Стандартный алгоритм Флойда-Уоршолла находит самый короткий путь во взвешенном ориентированном графе. После того, как силы пути были определены, мы можем определить победителей по методу Шульце, проверив, существует ли вариант, в котором сила пути больше или равна соответствующим силам пути всех других вариантов.
На Рис. 7 показана матрица сил пути, соответствующая данным на рис. 6; видно, что победителем по методу Шульце является вариант В. Визуально вариант является победителем по методу Шульце, если значение силы каждого пути в строке этого варианта выше или равно соответствующему значению вдоль основной диагонали матрицы.
Рис. 7. Данные силы пути используются для определения победителя по методу Шульце
Вариант В является победителем, поскольку сила пути варианта В к варианту А равна 7 (а варианта А к варианту В - только 6), сила его пути к варианту С - 7 (но сила пути С к В - только 6) и сила его пути к варианту D - 8 (но сила пути от D к В - только 6). С другой стороны, вариант D не является победителем по методу Шульце, поскольку сила пути варианта D лучше, чем варианта А (7 к 6), но сила варианта D хуже, чем варианта С (6 к 10).
Метод Шульце в коде
В этом примере имеется лишь один победитель по методу Шульце, но их может быть несколько. В подобных ситуациях необходимо использовать какую-либо форму разрешения ничьих. Давайте разберем часть кода в программе, создающей результаты с рис. 5, чтобы лучше разобраться в методе Шульце.
Программа начинает с установки типа перечисления для представления альтернатив и глобального значения N для хранения реального числа альтернатив:
enum options { A, B, C, D, E, F, G, H, I, J };
static int N; // actual number of options
Затем демонстрационная программа устанавливает ввод задачи в форме массива строк:
string[] rawData = new string[] {
"A>B>C>D 3",
"B>C>D>A 4",
"C>D>A>B 2",
"D>C>B>A 1",
"C>A>B>D 1"
};
Для простоты в моей демонстрационной программе подразумевается, что ничьи не дозволены и что все варианты ранжированы. Это позволяет мне очень просто анализировать строки необработанных данных. Законченная демонстрационная программа доступна в материалах для загрузки, прилагаемых к статье. Изменение кода, чтобы он позволял ничьи и отсутствующие варианты, не должно представлять больших проблем.
Далее, моя демонстрационная программа проверяет массив строк rawData, после чего определяет и распечатывает число вариантов и число оценивающих. Далее программа заново проверяет массив ввода и создает матрицу поражений в попарных сравнениях, используя статический метод помощи, именуемый MakeDefeats:
int[,] defeats = MakeDefeats(rawData);
Console.WriteLine("\n== Pairwise defeats data is: \n");
Print(defeats);
Матрица поражений затем передается в качестве ввода другому вспомогательному методу, именуемому MakePathStrengths, который создает матрицу сил путей:
int[,] strengths = MakePathStrengths(defeats);
Console.WriteLine("\n== Path strength data is: \n");
Print(strengths);
Внутри метода MakePathStrengths я начинаю с устранения записей, над которыми господствуют другие:
int[,] result = new int[N, N];
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (d[i, j] > d[j, i])
result[i, j] = d[i, j];
else
result[i, j] = 0;
}
}
Обратите внимание, что оператор result[i, j] = 0; не является технически необходимым, поскольку C# автоматически инициализирует все элементы массивов типа int нулями.
Далее я использую вариант алгоритма Флойда-Уоршолла, чтобы вычислить силу каждого из возможных путей:
for (int k = 0; k < N; ++k) {
for (int i = 0; i < N; ++i) {
if (k == i) continue;
for (int j = 0; j < N; ++j) {
if (k == j || i == j) continue;
result[i, j] =
Math.Max(result[i, j], Math.Min(result[i, k], result[k, j]));
} //j
} //i
} //k
Если проследить за кодом вручную, то можно заметить, что он реализует определение силы пути, существующее между узлом [i] и узлом [j], как я описал ранее. Метод Max в коде работает над обеспечением того, чтобы при каждом проходе через внешний цикл я обновлял бы матрицу результатов, только если найден более сильный путь. Метод Min в коде соответствует идее использования наименьшей силы между узлами для представления общей силы пути, существующей между любыми двумя узлами.
После того, как у меня имеются силы всех путей, я могу использовать эту информацию для вычисления массива, представляющего победителей по методу Шульце, и затем перебрать этот массив и отобразить значение перечисления, соответствующее каждому победителю:
bool[] winners = MakeWinners(strengths);
Console.WriteLine("\n== Best option(s) is: \n");
for (int i = 0; i < winners.Length; ++i) {
if (winners[i] == true)
Console.Write(Enum.GetName(typeof(options), i) + " ");
}
Метод MakeWinners устанавливает одномерный логический массив, где значение true указывает победителя, а значение false - все остальных. Я предполагаю, что каждый из вариантов является победителем, затем перебираю матрицу силы путей, сравнивая значение силы в индексе [i,j] с тем же в индексе [j,i], чтобы увидеть, является ли этот вариант победителем на самом деле:
static int[] MakeWinners(int[,] ps) {
bool[] result = new bool[N];
for (int i = 0; i < N; ++i)
result[i] = true;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j)
if (ps[i, j] < ps[j, i])
result[i] = false;
}
return result;
}
Что еще оценивать
В число некоторых из ключевых факторов, которые следует принимать во внимание при использовании приемов групповой оценки, входит число вариантов, число оценивающих, являются ли альтернативы решениями по политикам или решениями по продуктам, и степень, в которой оценивающих затрагивают итоговые результаты анализа. В целом, следует по возможности использовать более чем один прием группового анализа, чтобы использовать несколько результатов для перекрестной проверки анализа (если несколько приемов приводят к одному результату, то это придает уверенности в нем).
Ситуации, в которых используются приемы, описанные мною в этой статье, почти всегда довольно субъективны. Опыт и интуиция должны играть большую роль в анализе результатов группового определения.
Как общее эмпирическое правило, прием простого большинства эффективен только в случаях, когда оценивающие не являются заинтересованными сторонами или когда ранжирование всех вариантов непрактично. Прием голосования в несколько туров в принципе может привести к отчуждению до 49% оценивающих и, по моему опыту, его обычно стоит использовать лишь для поддержки других приемов.
Система счета Борда, несмотря на свои технические недостатки, работает довольно неплохо, особенно когда оценивающие являются заинтересованными сторонами. Принцип Кондорсе очень прост и, в силу этого, часто может быть использован для проверки результатов других приемов. Метод Шульце - отличная многоцелевая методика во многих ситуациях тестирования программного обеспечения, за исключением случаев, когда речь идет об относительно малой группе оценивающих, на которых скажутся результаты и которые не разбираются в алгоритме Шульце.
В этой статье излагаются лишь основы интересного и полезного предмета. Существует большое число исследований по приемам группового определения лучшего варианта из набора. Среди прочих стоит воспользоваться книгой «A Primer in Social Choice Theory» («Знакомство с теорией социального выбора»), написанной Вульфом Гэртнером (Wulf Gaertner) (изд-во Oxford University Press, 2006 г.). Я также рекомендую «Comparing Voting Systems» («Сравнение систем голосования»), за авторством Ханну Нурми (Hannu Nurmi) (изд-во Springer-Verlag, 1987 г.).