Реферат: Модель колективного вибору
Через очевидну простоту алгоритму для реалізації задачі найкраще вибрати процедурну парадигму програмування і мови Паскаль чи Сі. Звичайно, для написання гарного інтерфейсу можна взяти об’єктно-орієнтовані мови C Builder чи Delphi. Проте, як можна було побачити з розгляду алгоритму задачі, побудова інтерфейсу зводилася б до послідовного виведення вікон. Ще одним аргументом на користь мов Паскаль чи Сі є розміри програми, які б при використанні C Builder чи Delphi були набагото більшими.
Серед двох мов – Паскаль і Сі, – я оберу Паскаль як більш звичну для себе.
5.2 Структура програми
Структурно дану програму можна поділити на блоки. Кожен блок може бути віднесений до однієї з функціональних груп:
1. Побудова інтерфейсу;
2. Реалізація алгоритмів, представлених у розділі 4.
 |
Отже, програма має наступну структуру:
Рис. 5.1 Структура програми
Процедура victory – це реалізація алгоритму визначення переможця, описаного у попередньому розділі. Під час виклику даної процедури задається масив оцінок Борда чи Копленда, а також текст для виведення результатів (ним служать слова “Копленда” та “Борда”). У попередньому розділі вже було обгрунтовано, чому для визначення переможця за різними правилами використано єдиний алгоритм.
Процедура help виводить список імен кандидатів у нижньому рядку екрану. Вона введена для полегшення вводу інформації користувачем.
Процедура example містить дані контрольного прикладу. Вона введена для полегшення перевірки правильності роботи програми і носить демонстраційний характер.
Процедура right призначена для перевірки правильності вводу символу. Вона використовується при виборі внесення інформації (демонстрація контрольного прикладу чи самостійне внесення профілю) і виборі способу занесення даних (окремими виборцями чи працівниками виборчого комітету).
Перейдемо до розгляду основної програми.
Перш за все у ній проходить виклик і взаємозв’язок описаних вище процедур.
Процедури побудови інтерфейсу викликаються на початку роботи програми. Вони призначені для полегшення внесення даних.
Процедура victory визначає переможця і виводить результат голосування за певним правилом. Тому її виклик відбувається вкінці основної програми.
Опишемо змінні, які використовуються в основній програмі.
N: к-ть виборців;
M: к-ть кандидатів;
s: к-ть груп;
rang: профіль переваг;
a,b: для визначення оцінки Копленда (використовується у бінарних порівняннях);
kopl: масив оцінок Копленда;
vybor1, vybor2: змінні зовнішніх циклів при визначенні оцінки Копленда;
bord: масив оцінок Борда;
name: масив імен кандидатів;
k, i, j, l, r: допоміжні змінні;
many: масив груп виборців.
Опишемо структуру програми.
Спочатку програма просить внести усю потрібну інформацію. Користувач повинен вказати кількість виборців та кандидатів і спосіб занесення інформації (чи свої переваги буде вносити кожен виборець окремо, чи це буде проводити комісія, оперуючи згрупованими даними). Далі йде внесення профілю переваг і перевірка на його коректність. Профіль є некоректним, якщо у ньому зустрічається ім’я особи, яка не є вище вказаним кандидатом, або ж імена кандидатів повторюються.
У програмі використовуються алгоритми правил Борда та Копленда, вказані у попередньому розділі. Згідно отриманих оцінок визначається переможець за допомогою процедури victory, і проходить виведення результату.
Слід зауважити, що отримані переможці Копленда та Борда можуть не співпадати, що ще раз свідчить про недосконалість правил голосування більшістю голосів. Результати роботи алгоритму будуть показані у відповідному розділі.
Складність програми (у даному випадку розуміється час, затрачений на виконання), прямо пропорційно залежить від величини кількості виборців та кандидатів.
Так як дана програма носить більш демонстраційний характер, то я ввела межу для кількості виборців і кандидатів для того, щоб обмежити час виконання – 200 та 50 відповідно. В загальному воно не є суттєвим, так як завжди можна розбити виборчий округ на менший з умовою того, щоб виконувалось дане обмеження.
5.3 Інструкція користувачеві
Дана програма призначена для визначення переможця виборів за правилами Копленда і Борда і порівняння отриманих результатів.
На початку роботи програми користувач може вибрати, чи проглядати результати розв’язку контрольного прикладу, чи вносити власні дані. В обох випадках визначаються переможці за Коплендом і Борда.
Спочатку працівники виборчого органу вносять загальну інформацію: кількість виборців у даному окрузі та кількість кандидатів. Далі заносяться імена кандидатів і вказується спосіб занесення профілів переваг: кожним виборцем окремо чи працівниками виборчого округу. В останньому випадку інформація є згрупована (аналогічно до контрольного прикладу).
Внизу екрана виводяться імена усіх кандидатів. Кожен виборець (чи працівник виборчого округу) вносить профіль переваг, розташовуючи кандидатів у строго визначеному порядку.
Для кожного виборця не допускається випадків байдужості; крім того, кандидати повинні бути строго ранджовані (тобто кожен з них займає своє місце у перевазі виборця, і на одному рівні не можуть знаходитись два кандидати). Імена кандидатів, які заносяться виборцями, повинні співпадати з іменами, вказаними на початку заповнення інформації.
Після занесення усіх цих даних видається результат роботи програми.
Спочатку виводиться переможець Копленда і вказується, чи він визначений із збереженням нейтральності. Для переможця вказується його оцінка. У противному випадку виводиться множина переможців (кандидатів, сума очок яких дорівнює максимальній оцінці).
Аналогічно визначається переможець Борда.
Як буде показано у контрольному прикладі, оцінки кандидатів, отриманих за правилами Борда і Копленда, можуть ранджуватись у протилежному порядку.
6 Контрольний приклад
Нехай дано наступний профіль для 9 виборців і 5-ти кандидатів:
| 1 | 4 | 1 | 3 |
|
a b c d e |
c d b e a |
e a d b c |
e a b d c |
У кожному стовпці кандидати розташовані у порядку зменшення їх значущості для кожної групи виборців. Тобто, для першого стовпця можна визначити переваги наступним чином: група виборців, що складається з однієї особи, вважає кандидата a найкращим. На другому місці вони ставлять кандидата b, на третьому місці c і т.д.
Продемонструємо розв’язок контрольного прикладу за правилом Копленда. Визначаємо оцінку Копленда.
Кандидат a є кращим за b для 1+1+3 виборців, а для 4-х виборців кандидат b є кращим за a. Визначимо такі переваги для кожного кандидата, порівняємо його з усіма іншими.
|
ab – 5 ac – 5 ad – 5 ae – 1 |
ba – 4 ca – 4 da – 4 ea – 8 |
bc – 5 bd – 4 de – 5 |
cb – 4 db – 5 eb – 4 |
cd – 5 ce – 5 |
dc – 4 ec – 4 |
de – 5 | ed – 4 |
Визначимо оцінку Копленда для кожного кандидата. Кандидат a є кращим за b (додаємо +1); він також є кращим за c та d (додаємо два рази +1) і гіршим за e (додаємо –1). Отже, оцінка Копленда для a рівна 2.
Знайдемо оцінку для інших кандидатів.
a=+1+1+1-1=2
b=-1+1-1+1=0
c=-1-1+1+=0
d=-1+1-1+1=0
e=+1-1-1-1=-2
Серед отриманих оцінок визначаємо максимальну. Як бачимо, вона дорівнює 2 і належить кандидату a. Отже, a – переможець Копленда.
Якби у нас отрималось два кандидати з максимальною оцінкою, наприклад b та f, ми б обрали кандидата b, так як він розташований ближче за алфавітом.
Для цього ж профілю знайдемо переможця Борда.
Отже, отримуємо такі оцінки:
a=1*4+4*0+1*3+3*3=16
b=3*1+2*4+1*1+2*3=18
c=2*1+4*4+0+0=18
d=1*1+4*3+2*1+1*3=18
e=1*4+1*4+3*4+0=20
Переможцем за Борда є кандидат е.
Як бачимо, оцінки Борда ранджують кандидатів у порядку, протилежному до того, який отримується за оцінками Копленда.
Дана курсова робота була присвячена огляду методів голосування більшістю голосів. Було проведено порівняльну характеристику кожного з методів і з їх множини обрано найкращі. До них відносяться
1. заможні за Кондорсе правила Копленла і Сімпсона, дерево багатоетапного виключення;
2. один з методів підрахунку очок – правило Борда.
Всі ці правила задовольняють умовам оптимальності за Парето, монотонності та анонімності. Крім того, правило Борда задовольняє також аксіомі участі та поповнення.
Для програмної реалізації було обрано методи Копленда і Борда.
Результати роботи програми продемонстровано на контрольному прикладі.
1. Мулен Э. “Кооперативное принятие решений: Аксиомы и модели” – Москва, Мир, 1991.
2. Миркин Б. Проблема групового выбора. – Москва, Наука, 1974.
Програма
label y, z;
type mas = string[6];
type ball =array[1..10] of shortint;
var N: byte; {к-ть виборцiв}
M: byte; {к-ть кандидатiв}
s: byte; {к-ть груп}
rang: array[1..10,1..100] of mas; {профiль переваг}
k,i,j,l,r,contrl: byte;
a,b: byte; {для проведення парних порiвнянь}
kopl: ball; {масив оцiнок Копленда}
vybor1, vybor2: mas;
bord: ball; {масив оцiнок Борда}
name: array[1..10] of mas; {масив iмен кандидатiв}
many: array[1..100] of byte; {масив груп виборцiв}
n1: array[1..10] of mas;
c: char;
{дані контрольного прикладу}
{---------------------------}
procedure example;
var i, j: byte;
begin
clrscr; M:=5; n:=9; s:=4;
name[1]:='a'; name[2]:='b'; name[3]:='c'; name[4]:='d'; name[5]:='e';
many[1]:=1; many[2]:=4; many[3]:=1; many[4]:=3;
rang[1,1]:='a'; rang[1,2]:='c'; rang[1,3]:='e'; rang[1,4]:='e';
rang[2,1]:='b'; rang[2,2]:='d'; rang[2,3]:='a'; rang[2,4]:='a';
rang[3,1]:='c'; rang[3,2]:='b'; rang[3,3]:='d'; rang[3,4]:='b';
rang[4,1]:='d'; rang[4,2]:='e'; rang[4,3]:='b'; rang[4,4]:='d';
rang[5,1]:='e'; rang[5,2]:='a'; rang[5,3]:='c'; rang[5,4]:='c';
gotoXY(15,1);
writeln('Завдання контрольного прикладу');
writeln; writeln('Число виборців: ', N);
writeln('Число кандидатів: ', M);
writeln('Профіль переваг:');
for i:=1 to 40 do
write('-');
writeln; write('Число виборців ');
gotoXY(19,7);
for i:=1 to s do
write(many[i], ' ');
writeln; gotoXY(19,9);
for i:=1 to M do
begin
for j:=1 to s do
write(rang[i,j], ' ');
gotoXY(19, 9+i);
end;
gotoXY(1,15);
end;
{---------------------------}
{перевіряє правильність вводу варіанту вибору}
procedure right;
label l;
begin
l: readln(c);
if (c<>'0') and (c<>'1') then
begin
write('Повторіть спробу: ');
goto l;
end;
end;
{---------------------------}
{виводить список імен кандидатів}
procedure help;
var x,y,i: byte;
begin
x:=WhereX;
y:=WhereY;
gotoXY(1,24);
write('Імена кандидатів: ');
for i:=1 to M do
if i<>M then write(name[i], ', ')
else write(name[i]);
gotoXY(x,y);
end;
{---------------------------}
{визначення переможця виборів}
procedure victory(v: ball; s: string);
var max, t: shortint;
hl: array[1..10] of byte;
begin
{визначення максимальної оцiнки}
help;
max:=v[1];
for i:=1 to M do
if max<v[i] then
max:=v[i];
t:=1;
{визначення кандидатiв з максимальною оцiнкою}
for i:=1 to M do
if (v[i]-max)=0 then
begin
hl[t]:=i;
t:=t+1;
end;
if (t-1)=1 then
begin
write('Переможець за ', s, ' iз збереженням нейтральностi: ');
writeln(name[hl[1]]); writeln('Сума очок - ', max);
end
else
begin
vybor1:=name[hl[1]];
for i:=2 to t-1 do
if name[hl[i]]<vybor1 then
vybor1:=name[hl[i]];
write('Переможець за ', s, ' без збереження нейтральностi: ');
writeln(vybor1); writeln('Сума очок - ', max);
writeln('обраний з множини найкращих:');
for i:=1 to t-1 do
writeln(name[hl[i]]);
end;
end;
{---------------------------}
{основна програма}
begin
gotoXY(21,1); writeln('Визначення переможця виборів');
writeln; writeln('Запуск контрольного прикладу - 1; Самостійне внесення профілю - 0');
right;
if c='1' then
begin
example;
help;
goto z;
end
else clrscr;
write('Введiть кiлькiсть кандидатiв: ');
readln(M);
write('Введiть кiлькiсть виборцiв: ');
readln(N);
writeln('Введiть iмена кандидатiв');
for i:=1 to M do
begin
write('Кандидат ', i, ': ');
readln(name[i]);
end;
writeln('Як буде здiйснюватись занесення iнформацiї?');
write('1- окремими виборцями, 0- комiтетом: ');
right;
if c='1' then
for i:=1 to N do
many[i]:=1;
clrscr; writeln('Введiть профiль переваг');
s:=1; contrl:=0;
while contrl<>N do
begin
if c='1' then writeln('Виборець ', s)
else writeln('Група ', s);
for i:=1 to m do
n1[i]:='';
help;
for j:=1 to M do
begin
y:readln(vybor1);
{перевірка на коректність введеного профілю}
r:=0; a:=0; b:=0;
n1[j]:=vybor1;
for l:=1 to M do
begin
if vybor1=name[l] then
begin
b:=1;
for a:=1 to M do
{таке ім'я вже було введено у даному профілі}
if (vybor1=n1[a]) and ((a-j)<>0) then r:=1;
end;
{ім'я введеного кандидата не співпадає із жодним із списку}
if (vybor1<>name[l]) and (l=M) and (b<>1)then r:=1;
end;
if r=1 then
begin
n1[j]:='';
writeln('Уважно вводьте імена кандидатів');
goto y;
end
else rang[j,s]:=vybor1; {профіль коректний}
end;
if c='0' then
begin
writeln('Кiлькiсть виборцiв у групi ', s);
readln(many[s]);
contrl:=contrl+many[s];
end
else
contrl:=contrl+1;
s:=s+1;
clrscr;
end; {while}
{Визначення оцiнок Копленда}
z: contrl:=1;
while contrl<=M do
begin
k:=contrl+1;
vybor1:=name[contrl]; vybor2:=name[k];
while k<=M do
begin
i:=1; a:=0; b:=0;
while i<=s do
begin
for j:=1 to M do
if rang[j,i]=vybor1 then l:=j
else
if rang[j,i]=vybor2 then r:=j;
if l<r then a:=a+many[i]
else
if l>r then b:=b+many[i];
i:=i+1;
end;
if a>b then
begin
kopl[contrl]:=kopl[contrl]+1;
kopl[k]:=kopl[k]-1;
end
else
if a<b then
begin
kopl[k]:=kopl[k]+1;
kopl[contrl]:=kopl[contrl]-1;
end;
k:=k+1;
vybor2:=name[k];
end; {while по k}
contrl:=contrl+1;
end; {while по contrl}
{визначення оцiнок Борда}
for i:=1 to s do
for j:=1 to M do
begin
for k:=1 to M do
if rang[j,i]=name[k] then r:=k;
bord[r]:=many[i]*(M-j)+bord[r];
end;
victory(kopl, 'Коплендом');
writeln ('Натисніть будь-яку клавішу ');
readkey; writeln;
victory(bord, 'Борда');
end.
Результати роботи програми
Самостійне внесення профілю
Введіть кількість кандидатів: 5
Введіть кількість виборців: 9
Введіть імена кандидатів
Кандидат 1: а
Кандидат 2: b
Кандидат 3: c
Кандидат 4: d
Кандидат 5: е
Як буде здійснюватись занесення інформації?
1-окремими виборцями, 0 – комітетом: 0
Введіть профіль переваг
Група 1
a
b
c
d
e
Кількість виборців у групі 1: 1
Група 2
c
d
b
e
a
Кількість виборців у групі 2: 4
Група 3
e
a
d
b
c
Кількість виборців у групі 3: 1
Група 4
e
a
b
d
c
Кількість виборців у групі 4: 3
Переможець за Коплендом із збереженням нейтральності – а
Сума очок – 2
Переможець за Борда із збереженням нейтральності – е
Сума очок – 20
Демонстрація роботи контрольного прикладу
