Диссертация (1150529), страница 13
Текст из файла (страница 13)
. . , Wn .Îïðåäåëèì õàðàêòåðèñòè÷åñêóþ ôóíêöèþ ñëåäóþùèì îáðàçîì. Ðàññìîòðèìêîàëèöèþ K è åå äîïîëíåíèå A \ K . Ïðåäïîëîæèì, ÷òî êîàëèöèÿ K ìîæåò âûñòàâèòü íà âûáîðû åäèíîãî êàíäèäàòà i ∈ K , â òî âðåìÿ êàê êîàëèöèÿ A \ Kâûñòàâëÿåò ñâîåãî êàíäèäàòà j ∈ A \ K . Êàíäèäàò, íàáðàâøèé áîëüøå ïîëîâèíû ãîëîñîâ, îáúÿâëÿåòñÿ ïîáåäèòåëåì, â ïðîòèâíîì ñëó÷àå îáúÿâëÿåòñÿ íè÷üÿ.Âûèãðûø â ýòîé èãðå ðàâåí(n),H(i, j) = I h(i, j) −2ãäå èíäèêàòîðíàÿ ôóíêöèÿ I(z) = 1 åñëè z > 0, I(z) = 1/2 åñëè z = 0, è 0èíà÷å.Ðàâíîâåñèå â òàêîé èãðå â ñìåøàííûõ ñòðàòåãèÿõ ãàðàíòèðóåòñÿ òåîðåìîéÍýøà è çíà÷åíèå òàêîé èãðû è áóäåò çíà÷åíèåì õàðàêòåðèñòè÷åñêîé ôóíêöèèv(K) â êîîïåðàòèâíîé èãðå.Òàêèì îáðàçîì, â êà÷åñòâå âûèãðûøà v(K) êîàëèöèè K ðàññìàòðèâàåòñÿâûèãðûø â ðàâíîâåñèè â èãðå ñ ïîñòîÿííîé ñóììîé êîàëèöèè K ïðîòèâ êîíòðêîàëèöèè A \ K .
Ñìåøàííîé ñòðàòåãèåé êîàëèöèè K ÿâëÿåòñÿ âåêòîð p = (pi )i∈K .Ñ âåðîÿòíîñòüþ pi ≥ 0 êîàëèöèÿ K âûäâèãàåò åäèíîãî êàíäèäàòà i ∈ K , ñóììà∑âåðîÿòíîñòåépi = 1. Ñòðàòåãèåé êîàëèöèè A \ K áóäåò âåêòîð q = (qj )j∈A\K ,i∈K∑òàêîé ÷òî qj ≥ 0 äëÿ âñåõ j ∈ A \ K , ñóììà âåðîÿòíîñòåéqj = 1. Òîãäàõàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ v îïðåäåëÿåòñÿ ïî ôîðìóëåv(K) = max minpq∑ ∑j∈A\KH(i, j)pi qj .i∈K j∈A\KÇàìåòèì, ÷òîv(K) + v(A \ K) = 1.Íàïðèìåð, âû÷èñëèì âûèãðûø v äëÿ êîàëèöèé ac, bde ïðèìåðà 3.1.
Ìàòðèöàâûèãðûøåé êîàëèöèè ac ïðîòèâ êîàëèöèè bde åñòü87b d e()a 0 1 0c 1 0 1 ñìåøàííûõ ñòðàòåãèÿõ êîàëèöèÿ ac ïîëó÷àåò âûèãðûø 0.5, çíà÷èò,v(ac) = v(bde) = 0.5.Äëÿ ïîáåäû êîàëèöèè íåîáõîäèìî íàáðàòü íå ìåíåå 23 ãîëîñîâ. Êîàëèöèèce, abe è acd ÿâëÿþòñÿ ìèíèìàëüíûìè âûèãðûâàþùèìè êîàëèöèÿìè.
Êàíäèäàòû c è e ÿâëÿþòñÿ ñèëüíåéøèìè ïðè òàêîé ïðîöåäóðå ãîëîñîâàíèÿ. Ëþáàÿâûèãðûâàþùàÿ êîàëèöèÿ äîëæíà âêëþ÷àòü â ñåáÿ êàíäèäàòà c èëè e.Õàðàêòåðèñòè÷åñêóþ ôóíêöèþ ìîæíî âû÷èñëèòü äëÿ âñåõ 2m êîàëèöèé êàíäèäàòîâ. Ïîñëå òîãî, êàê õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ ïîñòðîåíà, ìîæíî âû÷èñëèòü ñèëó êàíäèäàòà, èñïîëüçóÿ âåêòîð Øåïëè∑ k!(m − k − 1)!(v(K ∪ x) − v(K)) ,m!φx (v) =x ∈ A.K:x̸∈K ðàçäåëå 3.4 íàõîäèòñÿ òàáëèöà ñî âñåìè çíà÷åíèÿìè äëÿ õàðàêòåðèñòè÷åñêîé ôóíêöèè v ïðèìåðà 3.1.Âåêòîð Øåïëè äëÿ õàðàêòåðèñòè÷åñêîé ôóíêöèè ïðèìåðà 3.1.vabcdeðàíæèðîâàíèå0,1670,0830,3330,0830,333e=c>a>b=dÄàëåå íàì ïîíàäîáÿòñÿ äâå âñïîìîãàòåëüíûå ëåììû.Ëåììà 3.2.
Ïóñòü (hij ) åñòü n×m-ìàòðèöà âûèãðûøåé â èãðå ñ ïîñòîÿííîéñóììîé è çíà÷åíèåì èãðû v ∗ . Òîãäà â èãðå ñ ìàòðèöåé bh, òàêîé ÷òî bhij ≥ hijäëÿ âñåõ i, j , çíà÷åíèå èãðû áóäåò íå ìåíüøå ÷åì v ∗ .Äîêàçàòåëüñòâî.Ïóñòü p∗ , q ∗ ëþáûå îïòèìàëüíûå ñòðàòåãèè ïåðâîãî è âòîðîãî èãðîêîâ â èãðåñ ìàòðèöåé h. Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íî çàìåòèòü, ÷òî â èãðå ñ ìàòðèöåébh ñòðàòåãèÿ p∗ ãàðàíòèðóåò ïåðâîìó èãðîêó âûèãðûø íå ìåíüøå, ÷åì v ∗ . Äîïóñòèì, ÷òî íàøëàñü ñòðàòåãèÿ âòîðîãî èãðîêà q , òàê ÷òî âûèãðûø ïåðâîãî88èãðîêà ìåíüøå, ÷åì v ∗ . Òîãäàn ∑m∑p∗i qj bhij∗<v ≤i=1 j=1mn ∑∑p∗i qj hij ,i=1 j=1÷òî áûëî áû íåâîçìîæíî ïðè bhij ≥ hij .Ëåììà 3.3. Ïóñòü õàðàêòåðèñòè÷åñêèå ôóíêöèè v è vb äëÿ íåêîòîðîé ïàðûêàíäèäàòîâ x è y è ëþáîé êîàëèöèè S ⊆ A \ {x, y} óäîâëåòâîðÿþò ñëåäóþùèìóñëîâèÿìv(S) = vb(S),v(S ∪ y) ≥ vb(S ∪ y),v(S ∪ x) ≤ vb(S ∪ x),v(S ∪ y ∪ x) = vb(S ∪ y ∪ x).Òîãäà ïðè ïåðåõîäå îò v ê vb äëÿ êàíäèäàòà x çíà÷åíèå φx â âåêòîðå Øåïëè íå óìåíüøèòñÿ, à äëÿ y çíà÷åíèå φy íå óâåëè÷èòñÿ.
Äëÿ ëþáîãî äðóãîãîêàíäèäàòà z ∈ A \ {x, y} ïðèðàùåíèå çíà÷åíèÿ â âåêòîðå Øåïëè φz (bv ) − φz (v)íå áîëüøå ïðèðàùåíèÿ φx (bv ) − φx (v) äëÿ x è íå ìåíüøå ïðèðàùåíèÿ çíà÷åíèÿφy (bv )−φy (v) äëÿ y . Ñëåäîâàòåëüíî, êàíäèäàò x íå óìåíüøèò ñâîé ðàíã, à êàíäèäàò y íå óâåëè÷èò ñâîé ðàíã â êîëëåêòèâíîì ïðåäïî÷òåíèè ïðè èçìåíåíèèõàðàêòåðèñòè÷åñêîé ôóíêöèè ñ v íà vb.Äîêàçàòåëüñòâî.Èç âûïîëíåíèÿ óñëîâèé ëåììû î÷åâèäíî ñëåäóåò, ÷òî äëÿ êàíäèäàòà x çíà÷åíèå â âåêòîðå Øåïëè íå óìåíüøèòñÿ, à äëÿ y íå óâåëè÷èòñÿ.
Ïîêàæåì, ÷òîäëÿ ëþáîãî äðóãîãî êàíäèäàòà z ∈ A \ {x, y} ïðèðàùåíèå çíà÷åíèÿ â âåêòîðåØåïëè íå ïðåâîñõîäèò ïðèðàùåíèÿ äëÿ x.Îöåíèì∑ k!(m−k−1)!(bv (K ∪ x)−bv (K))−(v(K ∪ x)−v(K))φx (bv )−φx (v)=m!K:x̸∈K(3.1)89è∑ k!(m−k−1)!(bv (K ∪ z)−bv (K))−(v(K ∪ z)−v(K))). (3.2)φz (bv )−φz (v)=m!K:z̸∈KÎáîçíà÷èì∆K (x) = (bv (K ∪ x) − vb(K)) − (v(K ∪ x) − v(K)).Çàìåòèì, ÷òî åñëè x, z ̸∈ K , òî ïðè y ̸∈ Kvb(x ∪ K) − vb(K) − (v(x ∪ K) − v(K)) = vb(x ∪ K) − v(x ∪ K) ≥ 0,â òî âðåìÿ, êàêvb(z ∪ K) − vb(K) − (v(z ∪ K) − v(K)) = 0.Îòñþäà ñëåäóåò, ÷òî ∆K (x) ≥ ∆K (z). Åñëè æå y ∈ K òî èç íåðàâåíñòâvb(x ∪ K) − vb(K) − (v(x ∪ K) − v(K)) = v(K) − vb(K) ≥ 0,vb(z ∪ K) − vb(K) − (v(z ∪ K) − v(K)) == vb(z ∪ y ∪ (K \ y)) − v(z ∪ y ∪ (K \ y)) − (bv (K) − v(K)) ≤ v(K) − vb(K),îïÿòü ïîëó÷àåì ∆K (x) ≥ ∆K (z).Ðàññìîòðèì òåïåðü êîàëèöèè K â ñóììå (1), êîòîðûå ñîäåðæàò èãðîêà z .Ïîñòàâèì èì â ñîîòâåòñòâèå êîàëèöèè âèäà K ′ = x ∪ (K \ z) â ñóììå (2).
Âçàâèñèìîñòè îò òîãî, ïðèíàäëåæèò ëè ýòîé êîàëèöèè èãðîê y èëè íåò, ñïðàâåäëèâû ñëåäóþùèå íåðàâåíñòâà.Åñëè y ̸∈ K , òî∆x (K) = vb(x ∪ K) − vb(K) − (v(x ∪ K) − v(K)) == vb(x ∪ K) − v(x ∪ K)) ≥ 0,90â òî âðåìÿ êàê∆z (K ′ ) = vb(z ∪ K ′ ) − vb(K ′ ) − (v(z ∪ K ′ ) − v(K ′ )) == vb(z ∪ x ∪ (K \ z)) − vb(x ∪ (K \ z)) − (v(z ∪ x ∪ (K \ z)) − v(x ∪ (K \ z))) ≤≤ vb(x ∪ K) − v(x ∪ K) = ∆x (K).Åñëè æå y ∈ K , òî∆x (K) = vb(x ∪ y ∪ (K \ y))−bv (y ∪ (K \ y))−(v(x ∪ y ∪ (K \ y))−v(y ∪ (K \ y)) == v(y ∪ (K \ y))−bv (y ∪ (K \ y))≥0,â òî âðåìÿ êàê∆z (K ′ ) = vb(z ∪ K ′ ) − vb(K ′ ) − (v(z ∪ K ′ ) − v(K ′ )) == vb(x ∪ K) − vb(x ∪ (K \ z)) − (v(x ∪ K)) − v(x ∪ (K \ z))) = 0.Îòñþäà ñëåäóåò ∆x (K) ≥ ∆z (K ′ ).
Òàêèì îáðàçîì, ïîêàçàíîφx (bv ) − φx (v) ≥ φz (bv ) − φz (v).Àíàëîãè÷íî ìîæíî ïîêàçàòü, ÷òî ïðèðàùåíèå çíà÷åíèÿ äëÿ y â âåêòîðå Øåïëè íå ïðåâîñõîäèò ïðèðàùåíèÿ äëÿ z . Òàêèì îáðàçîì, äîêàçàíî, ÷òî êàíäèäàòx íå óìåíüøèò ñâîé ðàíã, à êàíäèäàò y íå óâåëè÷èò ñâîé ðàíã â êîëëåêòèâíîìïðåäïî÷òåíèè ïðè èçìåíåíèè õàðàêòåðèñòè÷åñêîé ôóíêöèè ñ v íà vb.Òåîðåìà 3.1. Õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ v ÿâëÿåòñÿ íåîòðèöàòåëüíîéè ìîíîòîííîé.
Ðàíæèðîâàíèå ñîãëàñíî âåêòîðó Øåïëè äëÿ ôóíêöèè v îáëàäàåò ñâîéñòâàìè ãîìîãåííîñòè, åäèíîãëàñèÿ, ìîíîòîííîñòè, ïðàâèëà áîëüøèíñòâà, Êîíäîðñå è ñèëüíîãî ñâîéñòâà Êîíäîðñå.Äîêàçàòåëüñòâî.Íåîòðèöàòåëüíîñòü è ìîíîòîííîñòü ôóíêöèè v î÷åâèäíîñëåäóåò èç èõ îïðåäåëåíèÿ. Çàìåòèì, ÷òî ïðè íå÷åòíîì ÷èñëå èçáèðàòåëåé váóäåò òàêæå è ñóïåðàääèòèâíîé.Äîêàæåì, ÷òî âûïîëíÿåòñÿ ñâîéñòâî åäèíîãëàñèÿ.
Ïóñòü êàíäèäàò x ïðåäïî÷òèòåëüíåå, ÷åì êàíäèäàò y , äëÿ âñåõ ãîëîñóþùèõ. Äîñòàòî÷íî ïðîâåðèòü âûïîëíåíèå íåðàâåíñòâà v(y ∪ S) ≤ v(x ∪ S) äëÿ ëþáîé êîàëèöèè S ⊆ A \ {x, y}.91Îáîçíà÷èì K = A \ {x, y} \ S . Çàìåòèì, ÷òî h(i, x) ≤ h(i, y), h(y, j) ≤ h(x, j)äëÿ ëþáûõ i, j . Ñëåäîâàòåëüíî, H(i, x) ≤ H(i, y), H(y, j) ≤ H(x, j) äëÿ ëþáûõi, j . Ñðàâíèì ìàòðèöó âûèãðûøåé êîàëèöèè y ∪ S ïðîòèâ x ∪ Kxk1y0H(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 )(3.3)è ìàòðèöó âûèãðûøåé êîàëèöèè x ∪ S ïðîòèâ y ∪ Kyk1x1H(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.4)Ýëåìåíòû íèæíåé ìàòðèöû íå ìåíüøå ñîîòâåòñòâóþùèõ ýëåìåíòîâ âåðõíåéìàòðèöû. Ñîãëàñíî ëåììå 3.2, âûïîëíÿåòñÿ v(y ∪ S) ≤ v(x ∪ S). Ñëåäîâàòåëüíî,äëÿ êàíäèäàòà x çíà÷åíèå â âåêòîðå Øåïëè íå ìåíüøå, ÷åì äëÿ êàíäèäàòà y .Äîêàæåì âûïîëíåíèå ñâîéñòâà ìîíîòîííîñòè ðàíæèðîâàíèÿ. Ïóñòü â îäíîìèç áþëëåòåíåé êàíäèäàò x ïîäíèìåòñÿ íà îäíó ïîçèöèþ ââåðõ, à êàíäèäàò yîïóñòèòñÿ íà îäíó ïîçèöèþ âíèç.
Îáîçíà÷èì vb õàðàêòåðèñòè÷åñêóþ ôóíêöèþïîñëå ýòîãî èçìåíåíèÿ. Íåòðóäíî âèäåòü, ÷òî äëÿ ëþáîé êîàëèöèè S ⊆ A\{x, y}âûïîëíÿþòñÿ óñëîâèÿ ëåììû 3.3. Ïî ëåììå 3.3 êàíäèäàò x íå óìåíüøèò ñâîéðàíã, à êàíäèäàò y íå óâåëè÷èò ñâîé ðàíã â êîëëåêòèâíîì ïðåäïî÷òåíèè.Ïðîâåðèì âûïîëíåíèå ñâîéñòâà Êîíäîðñå. Ïóñòü êàíäèäàò x åñòü ïîáåäèòåëü Êîíäîðñå. Ñðàâíèì åãî ñ ëþáûì äðóãèì êàíäèäàòîì y . Äëÿ ëþáîãî ìíîæåñòâà S ⊆ A \ {x, y} êîàëèöèÿ x ∪ S âûñòàâëÿåò åäèíîãî êàíäèäàòà x è âûèãðûâàåò. Ïîýòîìó âûïîëíÿåòñÿ1 = v(x ∪ S) > v(y ∪ S) = 0,îòêóäà âûòåêàåò, ÷òî äëÿ êàíäèäàòà x çíà÷åíèå â âåêòîðå Øåïëè áîëüøå, ÷åìäëÿ êàíäèäàòà y .92Äîêàæåì âûïîëíåíèå ñèëüíîãî ñâîéñòâà Êîíäîðñå. Ïóñòü 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 .
Ïðîâåðèì âûïîëíåíèå íåðàâåíñòâà v(y ∪ S) ≤v(x ∪ S) äëÿ ëþáîãî ìíîæåñòâà S ⊆ A \ {x, y}. Îáîçíà÷èì ìíîæåñòâî K =A \ {x, y} \ S . Ìàòðèöû âûèãðûøåé êîàëèöèè y ∪ S ïðîòèâ x ∪ K â òî÷íîñòèòàêèå æå, êàê è ìàòðèöû (3) è (4) ïðè ïðîâåðêå ñâîéñòâà åäèíîãëàñèÿ. Òîãäàñîãëàñíî ëåììå 3.2 âûïîëíÿåòñÿ óñëîâèå v(y ∪ S) ≤ v(x ∪ S). Ñëåäîâàòåëüíî,äëÿ êàíäèäàòà x çíà÷åíèå â âåêòîðå Øåïëè íå ìåíüøå, ÷åì äëÿ êàíäèäàòà y .Äëÿ ôóíêöèè v âûïîëíÿåòñÿ ñèëüíîå ñâîéñòâî Êîíäîðñå, à ïî ëåììå 3.1,ñëåäîâàòåëüíî, è ïðàâèëî áîëüøèíñòâà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
