Диссертация (1150529), страница 14
Текст из файла (страница 14)
Òåîðåìà äîêàçàíà.Õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ v ó÷èòûâàþò òîëüêî ôàêò ïîáåäû îäíîãî êàíäèäàòà íàä äðóãèì ïðè ïîïàðíîì ñðàâíåíèè. Ïðåèìóùåñòâî â îäèí ãîëîñ èåäèíîãëàñíîå çäåñü ðàâíîçíà÷íû. Òàêîé ñïîñîá ðàíæèðîâàíèÿ ïîêàçûâàåò ñïîñîáíîñòü êàíäèäàòà ñîçäàâàòü êîàëèöèè, âûäâèãàþùèå ïîáåäèòåëÿ Êîíäîðñå.Åñëè ñðåäè âñåõ êàíäèäàòîâ óæå åñòü ïîáåäèòåëü Êîíäîðñå, òî âåêòîð Øåïëèáóäåò ðàâåí (1, 0, . . . , 0).Çàìå÷àíèå.
Âûøå çíà÷åíèå õàðàêòåðèñòè÷åñêîé ôóíêöèè áûëî îïðåäåëåíî êàê çíà÷åíèå èãðû ñ ïîñòîÿííîé ñóììîé â ñìåøàííûõ ñòðàòåãèÿõ. Ìîæíîòàêæå îïðåäåëèòü õàðàêòåðèñòè÷åñêóþ ôóíêöèþ îãðàíè÷èâàÿñü ðàññìîòðåíèåìëèøü ÷èñòûõ ñòðàòåãèé. Òîãäà åå çíà÷åíèåì â èãðå êîàëèöèè K ïðîòèâ êîíòðêîàëèöèè A \ K áóäåòv0 (K) = max min H(i, j).i∈K j∈A\KÇàìåòèì, ÷òî óòâåðæäåíèå òåîðåìû 3.1 áóäåò òàêæå ñïðàâåäëèâî è äëÿ òàêîéõàðàêòåðèñòè÷åñêîé ôóíêöèè.3.3Ðàíæèðîâàíèå íà îñíîâå òóðíèðíîéìàòðèöûÄëÿ âû÷èñëåíèÿ ôóíêöèè v èñïîëüçîâàëàñü ìàòðèöà âûèãðûøåé, ñîñòîÿùàÿèç íóëåé è åäèíèö.
Äàëåå áóäåì áîëåå òî÷íî îöåíèâàòü ïðåèìóùåñòâî îäíîãîêàíäèäàòà íàä äðóãèì. Ðàññìîòðèì êàê è ðàíüøå èãðó ñ ïîñòîÿííîé ñóììîé êî-93àëèöèè K ïðîòèâ êîíòðêîàëèöèè A \ K . Êàæäàÿ êîàëèöèÿ âûñòàâëÿåò åäèíîãîêàíäèäàòà. Âûèãðûøåì êîàëèöèè áóäåì ñ÷èòàòü êîëè÷åñòâî ãîëîñîâ h(i, j), íàáðàííûõ åäèíûì êàíäèäàòîì i ∈ K ïðîòèâ åäèíîãî êàíäèäàòà j ∈ A \ K .Äëÿ êîàëèöèè K â êà÷åñòâå âûèãðûøà u(K) âîçüìåì âûèãðûø â ðàâíîâåñèèâ èãðå êîàëèöèè K ïðîòèâ êîíòð-êîàëèöèè A \ K . Îïòèìàëüíàÿ ñòðàòåãèÿ êîàëèöèè K (âûáîð åäèíîãî êàíäèäàòà i ∈ K ) â ýòîì ñëó÷àå ìîæåò îêàçàòüñÿ ñìåøàííîé.
Ñìåøàííàÿ ñòðàòåãèÿ êîàëèöèè K åñòü âåêòîð p = (pi )i∈K . Ñòðàòåãèåéêîàëèöèè A\K áóäåò âåêòîð q = (qj )j∈A\K . Òàêèì îáðàçîì, õàðàêòåðèñòè÷åñêàÿôóíêöèÿ îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì.u(K) = max minpq∑ ∑h(i, j)pi qj .i∈K j∈A\KÄëÿ ëþáîé êîàëèöèè K âûïîëíÿåòñÿ ðàâåíñòâîu(K) + u(A \ K) = n.Íàïðèìåð, íàéäåì çíà÷åíèÿ ôóíêöèè u äëÿ êîàëèöèé ac, bde èç ïðèìåðà 3.1.Ìàòðèöà âûèãðûøåé êîàëèöèè ac ïðîòèâ êîàëèöèè bde â ýòîì ñëó÷àå åñòüb d e()a 20 30 22c 29 17 24Äëÿ êîàëèöèè ac åäèíûé êàíäèäàò a ãàðàíòèðóåò 20 ãîëîñîâ ïðîòèâ b, à êàíäèäàò c ãàðàíòèðóåò 17 ãîëîñîâ ïðîòèâ d. Äëÿ êîàëèöèè bde åäèíûé êàíäèäàò bãàðàíòèðóåò 45-29=16 ãîëîñîâ ïðîòèâ c, d 45-30=15 ïðîòèâ a, e 45-24=21 ïðîòèâ c.
Ãàðàíòèðîâàííûå âûèãðûøè ïðè èñïîëüçîâàíèè ÷èñòûõ ñòðàòåãèé çäåñüðàâíû u(ac) = 20, u(bde) = 45 − 24 = 21.  ðàâíîâåñèè â ñìåøàííûõ ñòðàòåãèÿõ êîàëèöèÿ ac èñïîëüçóåò âåðîÿòíîñòè äëÿ ñòðàòåãèé (7/15, 8/15), à êîàëèöèÿbde (0, 2/15, 13/15). Ïðè ýòîì ïîëó÷àþòñÿ âûèãðûøè u(ac) = 346/15 ≈ 23.07,u(bde) = 329/15 ≈ 21.93.Äëÿ ñðàâíåíèÿ åùå íåñêîëüêî õàðàêòåðèñòè÷åñêèõ ôóíêöèé u0 , v1 , v2 , v3åñòåñòâåííûì îáðàçîì îïðåäåëèì ÿâíî ïî ôîðìóëàì:u0 (K) = max min h(i, j),i∈K j∈A\K94∑v1 (K) =min H(i, j),j∈A\Ki∈Kv2 (K) =∑i∈Kv3 (K) =min h(i, j)H(i, j),j∈A\K∑i∈Kmin h(i, j).j∈A\K ðàçäåëå 3.4 åñòü òàáëèöà ñî âñåìè çíà÷åíèÿìè äëÿ õàðàêòåðèñòè÷åñêèõôóíêöèé u, u0 , v1 − v3 äëÿ ïðèìåðà 3.1. ñëåäóþùåé òåîðåìå 3.2 èññëåäîâàíû ñâîéñòâà, êîòîðûì óäîâëåòâîðÿåò ðàíæèðîâàíèå ñîãëàñíî âåêòîðó Øåïëè äëÿ õàðàêòåðèñòè÷åñêèõ ôóíêöèéu, u0 , v1 − v3 .Òåîðåìà 3.2. Õàðàêòåðèñòè÷åñêèå ôóíêöèè u, u0 , v1 − v3 ÿâëÿþòñÿ íåîò-ðèöàòåëüíûìè è ìîíîòîííûìè, ïðè÷åì ôóíêöèè v1 − v3 ñóïåðàääèòèâíûìè.Ðàíæèðîâàíèå ñîãëàñíî âåêòîðó Øåïëè äëÿ ôóíêöèé u, u0 , v1 − v3 îáëàäàåòñâîéñòâàìè, ïðåäñòàâëåííûìè â òàáëèöå íèæå.Âûïîëíåíèå ñâîéñòâ äëÿ âåêòîðîâ Øåïëè õàð.
ôóíêöèéu, u0 , v1 − v3 .Ñâîéñòâîuu0v1v2v3ÁîðäàÊîóïëåíäìàêñèìèíÃîìîãåííîñòüäàäàäàäàäàäàäàäàÅäèíîãëàñèåäàäàäàäàäàäàäàäàÌîíîòîííîñòüäàäàäàäàäàäàäàäàÏðàâèëî áîëüøèíñòâàíåòíåòäàäàäàäàäàíåòÊîíäîðñåäàäàäàäàíåòíåòäàäàÑèëüíîå ÊîíäîðñåíåòíåòäàíåòíåòíåòäàíåòÄîêàçàòåëüñòâî.Óòâåðæäåíèÿ î íåîòðèöàòåëüíîñòè, ìîíîòîííîñòè è ñóïåðàääèòèâíîñòèôóíêöèé u, u0 , v1 - v3 î÷åâèäíî ñëåäóþò èç èõ îïðåäåëåíèÿ.
Ôóíêöèè u, u0ñóïåðàääèòèâíûìè íå ÿâëÿþòñÿ, ÷òî ïîêàçûâàåò ïðèìåð 3.1.Äîêàæåì, ÷òî âûïîëíÿåòñÿ ñâîéñòâî åäèíîãëàñèÿ. Ïóñòü êàíäèäàò x ïðåäïî÷òèòåëüíåå, ÷åì êàíäèäàò y , äëÿ âñåõ ãîëîñóþùèõ. Äîñòàòî÷íî ïðîâåðèòü âûïîëíåíèå íåðàâåíñòâà u(y ∪ S) ≤ u(x ∪ S) äëÿ ëþáîé êîàëèöèè S ⊆ A \ {x, y}.Îáîçíà÷èì K = A \ {x, y} \ S . Çàìåòèì, ÷òî h(i, x) ≤ h(i, y), h(y, j) ≤ h(x, j)äëÿ ëþáûõ i, j . Ñðàâíèì ìàòðèöó âûèãðûøåé êîàëèöèè y ∪ S ïðîòèâ x ∪ K95xk1y0h(y, k1 )s1 h(s1 , x) h(s1 , k1 ). .
.... ...sl h(sl , x) h(sl , k1 )...kr. . . h(y, kr ). . . h(s1 , kr ) ...... . . . h(sl , kr )è ìàòðèöó âûèãðûøåé êîàëèöèè x ∪ S ïðîòèâ y ∪ Kyk1xnh(x, k1 )s1 h(s1 , y) h(s1 , k1 ). . .... ...sl h(sl , y) h(sl , k1 )...kr. . . h(x, kr ). . . h(s1 , kr ) ...... . . . h(sl , kr )Ýëåìåíòû íèæíåé ìàòðèöû íå ìåíüøå ñîîòâåòñòâóþùèõ ýëåìåíòîâ âåðõíåéìàòðèöû. Ñîãëàñíî ëåììå 3.2, âûïîëíÿåòñÿ u(y ∪ S) ≤ u(x ∪ S).
Ñëåäîâàòåëüíî,äëÿ êàíäèäàòà x çíà÷åíèå â âåêòîðå Øåïëè íå ìåíüøå, ÷åì äëÿ êàíäèäàòà y .Äëÿ îñòàëüíûõ õàðàêòåðèñòè÷åñêèõ ôóíêöèé ýòî ñâîéñòâî äîêàçûâàåòñÿ àíàëîãè÷íî.Äîêàæåì âûïîëíåíèå ñâîéñòâà ìîíîòîííîñòè ðàíæèðîâàíèÿ. Ïóñòü â îäíîìèç áþëëåòåíåé êàíäèäàò x ïîäíèìåòñÿ íà îäíó ïîçèöèþ ââåðõ, à êàíäèäàò y îïóñòèòñÿ íà îäíó ïîçèöèþ âíèç. Îáîçíà÷èì ub è vbi õàðàêòåðèñòè÷åñêèå ôóíêöèèïîñëå ýòîãî èçìåíåíèÿ.
Íåòðóäíî âèäåòü, ÷òî äëÿ ëþáîé êîàëèöèè S ⊆ A\{x, y}âûïîëíÿþòñÿ óñëîâèÿ ëåììû 3.3. Ïî ëåììå 3.3 êàíäèäàò x íå óìåíüøèò ñâîéðàíã, à êàíäèäàò y íå óâåëè÷èò ñâîé ðàíã â êîëëåêòèâíîì ïðåäïî÷òåíèè.Ïðîâåðèì âûïîëíåíèå ñâîéñòâà Êîíäîðñå. Ïóñòü êàíäèäàò x åñòü ïîáåäèòåëü Êîíäîðñå. Ñðàâíèì åãî ñ ëþáûì äðóãèì êàíäèäàòîì y . Äëÿ ëþáîé êîàëèöèè S ⊆ A \ {x, y} ëåãêî ïîíÿòü, ÷òî âûïîëíÿþòñÿu(x ∪ S) >n> u(y ∪ S),2n> u0 (y ∪ S),2vi (x ∪ S) > vi (y ∪ S) = 0,i = 1, 2,u0 (x ∪ S) >96îòêóäà âûòåêàåò, ÷òî äëÿ êàíäèäàòà x çíà÷åíèå â âåêòîðå Øåïëè áîëüøå, ÷åìäëÿ êàíäèäàòà y .  ïðèìåðå 3.2 â âåêòîðå Øåïëè äëÿ v3 ïîáåäèòåëü Êîíäîðñåíå ïîëó÷àåò ìàêñèìàëüíîãî çíà÷åíèÿ.Äîêàæåì âûïîëíåíèå ñèëüíîãî ñâîéñòâà Êîíäîðñå äëÿ ôóíêöèè v1 .
Ïóñòüw(x) ⊇ w(y), l(x) ⊆ l(y) è h(x, y) > n/2. Òîãäà I(h(i, x) − n2 ) ≤ I(h(i, y) − n2 ),I(h(y, j)− n2 ) ≤ I(h(x, j)− n2 ) äëÿ ëþáûõ i, j . Ïðîâåðèì âûïîëíåíèå íåðàâåíñòâàv2 (y ∪ S) ≤ v2 (x ∪ S) äëÿ ëþáîé êîàëèöèè S ⊆ A \ {x, y}. Îáîçíà÷èì K =A \ {x, y} \ S . Êàê è â òåîðåìå 3.1, ñðàâíèì ìàòðèöó (3) âûèãðûøåé êîàëèöèèy ∪ S ïðîòèâ x ∪ K è ìàòðèöó (4) âûèãðûøåé êîàëèöèè x ∪ S ïðîòèâ y ∪ K .Ýëåìåíòû íèæíåé ìàòðèöû íå ìåíüøå ñîîòâåòñòâóþùèõ ýëåìåíòîâ âåðõíåéìàòðèöû. Çíà÷èò, âûïîëíÿåòñÿ v1 (y ∪ S) ≤ v1 (x ∪ S).
Ñëåäîâàòåëüíî, äëÿ êàíäèäàòà x çíà÷åíèå â âåêòîðå Øåïëè íå ìåíüøå, ÷åì äëÿ êàíäèäàòà y , è âûïîëíåíèå ñèëüíîãî ñâîéñòâà Êîíäîðñå äîêàçàíî. Çàìåòèì, ÷òî v1 (y ∪ A \ {x, y}) <v1 (x∪A\{x, y}). Ïîýòîìó ïî v1 êàíäèäàò x ïîëó÷èò ðàíã ñòðîãî áîëüøå, ÷åì êàíäèäàò y .  ïðèìåðå 3.4 ñèëüíîå ñâîéñòâî Êîíäîðñå íå âûïîëíÿåòñÿ äëÿ ôóíêöèéu, u0 , v2 , v3 .Äëÿ ôóíêöèè v1 âûïîëíÿåòñÿ ñèëüíîå ñâîéñòâî Êîíäîðñå, à ñëåäîâàòåëüíîè ïðàâèëî áîëüøèíñòâà. Ïðèìåð 3.3 ïîêàçûâàåò, ÷òî äëÿ u, u0 ýòî ñâîéñòâî íåâûïîëíÿåòñÿ. Îñòàëîñü äîêàçàòü, ÷òî ïðàâèëî áîëüøèíñòâà âûïîëíÿåòñÿ äëÿ v2è v3 .
Îáîçíà÷èì ôóíêöèþ g ≡ v1 äëÿ ïðîôèëÿ, ñîñòîÿùåãî èç îäíîãî áþëëåòåíÿñ ïîðÿäêîì a1 > a2 > ... > am . Åñëè ê ëþáîìó íà÷àëüíîìó ïðîôèëþ ðàçìåðà näîáàâèòü k > n áþëëåòåíåé ñ ïîðÿäêîì a1 > a2 > ... > am , òî ëåãêî ïîíÿòü, ÷òîg(S)k ≤ vi (S) ≤ g(S)k + nm,i = 2, 3,îòêóäà âûòåêàåò, ÷òî äëÿ ëþáîãî êàíäèäàòà x ïðè k → ∞ ñïðàâåäëèâîφx (vi )→ φx (g),kÒåîðåìà äîêàçàíà.i = 2, 3.973.4Ñðàâíåíèå ñ êëàññè÷åñêèìè ïðîöåäóðàìèðàíæèðîâàíèÿÑðàâíèì ïîëó÷åííûå íàìè ðåçóëüòàòû äëÿ ïðèìåðà 3.1 ñ äðóãèìè ñïîñîáàìèðàíæèðîâàíèÿ è îïðåäåëåíèÿ ïîáåäèòåëÿ, èñïîëüçóþùèìè òóðíèðíóþ ìàòðèöó [39]. Îäíèì èç òàêèõ ñïîñîáîâ ðàíæèðîâàíèÿ ñðåäè m êàíäèäàòîâ ÿâëÿåòñÿïðàâèëî Áîðäà, â êîòîðîì çà ïåðâîå ìåñòî â áþëëåòåíå êàíäèäàòó ïðèñâàèâàåòñÿ m − 1 áàëëîâ, çà âòîðîå m − 2, .
. . , çà ïîñëåäíåå ìåñòî 0 áàëëîâ. Ïîáåäèòåëåìîáúÿâëÿåòñÿ êàíäèäàò, íàáðàâøèé ìàêñèìàëüíîå êîëè÷åñòâî áàëëîâ. Ïîäñ÷åòáàëëîâ äëÿ êàíäèäàòà i ìîæíî ïðîâåñòè ïî ôîðìóëå∑h(i, j).j∈A\{i}Ïî ïðàâèëó Áîðäà ïîëó÷àåòñÿ ðàíæèðîâàíèå e > a > b > c > d c áàëëàìèñîîòâåòñòâåííî 102, 98, 92, 89 è 69.Ïî ìåòîäó Êîóïëåíäà, âû÷èñëÿÿ áàëëû ïî ôîðìóëå∑H(i, j),j∈A\{i}èìååì ðàíæèðîâàíèå e > a = b = c > d c áàëëàìè ñîîòâåòñòâåííî 3, 2, 2, 2 è 1.Ïî ïðàâèëó ìàêñèìèíà áàëëû äëÿ êàíäèäàòà i ðàññ÷èòûâàþòñÿ ñîãëàñíîmin h(i, j),j∈A\{i}è ïîëó÷àåòñÿ ðàíæèðîâàíèå e > a > c > b > d c áàëëàìè ñîîòâåòñòâåííî 21, 20,17, 16 è 12.Ïî ìåòîäó Øóëüöå [42] áóäåò e > a > c > b > d.Âåêòîðû Øåïëè õàðàêòåðèñòè÷åñêèõ ôóíêöèé ïðèìåðà 3.1.98abcdeðàíæèðîâàíèåuu0v1v2v310,9947,99,1615,30611,63910,957,8679,0335,36711,7830,9170,9171,1670,5831,41745,0542,849,21731,0556,88348,63345,0545,38335,350,633Áîðäà98928969102Êîóïëåíä22213ìàêñèìèí2016171221e>a>c>b>de>a>c>b>de>c>a=b>de>c>a>b>de>a>c>b>de>a>b>c>de>a=b=c>de>a>c>b>dÏðèìåð 3.2.
Ðàññìîòðèì ñèòóàöèþ ñ m = 3 êàíäèäàòàìè è n = 2k + 1 èçáèðà-òåëÿìè. Ïóñòü k + 1 ãîëîñóþùèõ ðàíæèðóþò â ïîðÿäêå a > b > c, à îñòàëüíûåk ≥ 1 èçáèðàòåëåé ïðåäïî÷èòàþò b > c > a.Ïðîôèëü ïðåäïî÷òåíèé ïðèìåðà 3.2.k+1kabbccaÊàíäèäàò a ÿâëÿåòñÿ ïîáåäèòåëåì Êîíäîðñå, îäíàêî, îí ïîáåæäàåò ó b è c ïðåèìóùåñòâîì âñåãî â îäèí ãîëîñ. Êàíäèäàò b ïðåäïî÷òèòåëüíåå, ÷åì c, äëÿ âñåõèçáèðàòåëåé. Ñîãëàñíî ïîïàðíûì ñðàâíåíèÿì êîëëåêòèâíûì ðåøåíèåì áóäåòïîðÿäîê a > b > c.Òóðíèðíàÿ ìàòðèöà ïðèìåðà 3.2.aabckkbck+1k+12k + 10 òàáëèöå ïðåäñòàâëåíû âåêòîðû Øåïëè äëÿ ôóíêöèé u, u0 v1 − v3 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
