Диссертация (1150529), страница 12
Текст из файла (страница 12)
Åñëè æåIj−1 èñïîëüçóåò ñòðàòåãèþ xj−1 = 1 − δ + δxj = 1 − δ + δPi (δ) + δ i+1 x, òî′Pi+1 (δ) = 1 − δ + δPi (δ), Pi+1(δ) = −1 + Pi (δ) + δPi′ (δ), Pi+1 (1) = Pi (1),′Pi+1(1) = −1 + Pi (1) + Pi′ (1). Ñëåäîâàòåëüíî, äëÿ I1 íàèëó÷øèì îòâåòîì áóäåò x1 = w(x) = Pn (δ) + δ n x, ïðè÷åì Pn (1) = 0, Pn′ (1) = −k .Ðåøàÿ óðàâíåíèå w(x) = x, íàéäåì îïòèìàëüíîå ïðåäëîæåíèå ïåðâîãî èãðîêà (ïðè óñëîâèè x∗ ∈ (ck+1 , ck ))x∗ =Pn (δ).1 − δn80Ïðè δ → 1 èìååì íåîïðåäåëåííîñòü âèäà 00 , ðàñêðûâàÿ êîòîðóþ ïî ïðàâèëóËîïèòàëÿ, ïîëó÷èìPn′ (δ)Pn (δ)Pn′ (1)klim x = lim=lim==.δ→1 −nδ n−1δ→1δ→1 1 − δ n−nn∗≤ ck ≤ nk .Òàê êàê ðåøåíèå óðàâíåíèÿ w(x) = x íåïðåðûâíî çàâèñèò îò ïàðàìåòðîâ(δ, c1 , .
. . , cn ), òî äîñòàòî÷íî íàéòè ðåøåíèå â ñëó÷àå k−1< ck < nk , ck+1 <nck < ck−1 , è íåïðåðûâíî åãî ïðîäîëæèòü. Íå îãðàíè÷èâàÿ îáùíîñòè, ìîæíîïåðåíóìåðîâàòü èãðîêîâ, òàê ÷òî I1 èìååò ïèê ck .Ïðåäïîëîæèì, èãðîê I1 íà n + 1 øàãå ïðåäëàãàåò àëüòåðíàòèâó xn+1 = ck .Ðàññóæäàÿ êàê âûøå, ïîêàæåì, ÷òî ýòî è åñòü îïòèìàëüíàÿ ñòðàòåãèÿ. Äåéñòâèòåëüíî, ñóùåñòâóåò δ1 , òàêîå ÷òî äëÿ âñåõ δ ≥ δ1 íàèëó÷øèì îòâåòîì èãðîêîâíà ïðåäëîæåíèå xj+1 ñëåäóþùåãî èãðîêà äëÿ n − k èãðîêîâ Ij ñ ìàêñèìàëüíûìèïðåäïî÷òåíèÿìè cn , . . . , ck+1 áóäåò ñòðàòåãèÿ xj = δxj+1 , à äëÿ k − 1 èãðîêîâ ñìàêñèìàëüíûìè ïðåäïî÷òåíèÿìè ck−1 , . .
. , c1 îïòèìàëüíî èñïîëüçîâàòü ñòðàòåãèþ xj = 1−δ+δxj+1 . Íàèëó÷øèì îòâåòîì èãðîêà I2 áóäåò x2 = Pn−1 (δ)+δ n−1 ck ,′ïðè÷åì Pn−1 (1) = 0, Pn−1(1) = −k + 1. Äîïóñòèìûé èíòåðâàë ñòðàòåãèé x1 èãðîêà I1 åñòü I = [δPn−1 (δ) + δ n ck , 1 − δ + δPn−1 (δ) + δ n ck ]. Çíà÷èò, óñëîâèå ck ∈ Iðàâíîñèëüíî1 − δ + δPn−1 (δ)δPn−1 (δ)k≤c≤.1 − δn1 − δnÏðèìåíÿÿ ïðàâèëî Ëîïèòàëÿ, íàõîäèì, ÷òî2)k−1n′′(1) k − 1Pn−1 (δ) + δPn−1(δ) Pn−1 (1) + Pn−1δPn−1 (δ)lim=lim==,δ→1 1 − δ nδ→1−nδ n−1−nn′−1 + Pn−1 (δ) + δPn−1(δ)1 − δ + δPn−1 (δ)=lim=limδ→1δ→11 − δn−nδ n−1′−1 + Pn−1 (1) + Pn−1(1)k== .−nnÑëåäîâàòåëüíî, ñóùåñòâóåò δ2 , òàêîå ÷òî äëÿ âñåõ δ ≥ δ2 íàèëó÷øèì îòâåòîìáóäåò x1 = ck ∈ I , ò. å. x∗ = ck îïòèìàëüíàÿ ñòðàòåãèÿ ïåðâîãî èãðîêà.81Òàêèì îáðàçîì, ìû äîêàçàëè ñëåäóþùåå óòâåðæäåíèå.Òåîðåìà 2.6.
Îáîçíà÷èì â óáûâàþùåì ïîðÿäêå 0 = cn ≤ cn−1 ≤ . . . ≤ c2 ≤c1 = 1 ìàêñèìàëüíûå ïðåäïî÷òåíèÿ ó÷àñòíèêîâ ïîñëåäîâàòåëüíûõ ïåðåãîâîðîâ î ìîìåíòå âñòðå÷è. Íåçàâèñèìî îò ïîñëåäîâàòåëüíîñòè âíåñåíèÿ ïðåäëîæåíèé ó÷àñòíèêàìè ñóùåñòâóåò ïðåäåë îïòèìàëüíûõ ñòðàòåãèé ïðè ñòðåìÿùåìñÿ ê åäèíèöå êîýôôèöèåíòå äèñêîíòèðîâàíèÿ.1åñëè c2 < n1 ,n,... ck , åñëè k−1 ≤ ck ≤ k ,∗nnlim xj =kkk+1δ→1åñëè c< n < ck ,n,... n−1 , åñëè n−1 < cn−1 ,nnè ïåðåãîâîðû çàâåðøàþòñÿ íà ïåðâîì øàãå ïðèíÿòèåì àëüòåðíàòèâû x∗1 .82Ãëàâà 3Ïåðåãîâîðû ñ êîíå÷íûì ìíîæåñòâîìàëüòåðíàòèâ3.1Çàäà÷à êîëëåêòèâíîãî ðàíæèðîâàíèÿàëüòåðíàòèâÐàññìîòðèì çàäà÷ó êîëëåêòèâíîãî ðàíæèðîâàíèÿ êàíäèäàòîâ (àëüòåðíàòèâ,âàðèàíòîâ ðåøåíèé) ñîãëàñíî ëè÷íûì ïðåäïî÷òåíèÿì ó÷àñòíèêîâ ïåðåãîâîðîâ(èçáèðàòåëåé, ãîëîñóþùèõ, ýêñïåðòîâ).
Ëè÷íûå ïðåäïî÷òåíèÿ ó÷àñòíèêîâ çàäàþòñÿ ëèíåéíûì ïîðÿäêîì íà êîíå÷íîì ìíîæåñòâå àëüòåðíàòèâ, âîçìîæíî èíåñòðîãèì. Ïðîôèëåì ïðåäïî÷òåíèé íàçûâàþòñÿ ñãðóïïèðîâàííûå ñ ó÷åòîì âåñà ó÷àñòíèêà ëè÷íûå ïðåäïî÷òåíèÿ âñåõ ó÷àñòíèêîâ. Ïðîöåäóðà ðàíæèðîâàíèÿêàæäîìó ïðîôèëþ ïðåäïî÷òåíèé ñîïîñòàâëÿåò ëèíåéíûé ïîðÿäîê íà ìíîæåñòâå àëüòåðíàòèâ, âîçìîæíî è íåñòðîãèé.
Òàêàÿ ïðîöåäóðà ïîçâîëÿåò îïðåäåëèòü êîëëåêòèâíîå ðåøåíèå: âûáîð îäíîé àëüòåðíàòèâû, âûáîð íåñêîëüêèõ àëüòåðíàòèâ, ðàíæèðîâàíèå àëüòåðíàòèâ ïî ìåñòàì.Òàêàÿ çàäà÷à âîçíèêàåò ïðè âûáîðàõ ïðåçèäåíòà ñòðàíû, äèðåêòîðà êîìïàíèè, ïðîôåññîðà êàôåäðû è ìíîãèõ äðóãèõ ïîçèöèé. Ïðè ýòîì, ïðåäïîëàãàåòñÿ, ÷òî âûáîðû ÿâëÿþòñÿ ñâîáîäíûìè, ÷åñòíûìè è îòêðûòûìè. Ïðè ãîëîñîâàíèè èçáèðàòåëè çàïîëíÿþò áþëëåòåíè, â êîòîðûõ îíè óêàçûâàþò ñâîè ëè÷íûå ïðåäïî÷òåíèÿ ïðåäñòàâëåííûì êàíäèäàòàì. Íà îñíîâàíèè âñåõ çàïîëíåííûõ áþëëåòåíåé äîëæåí áûòü îïðåäåëåí ïîáåäèòåëü (íåñêîëüêî ïîáåäèòåëåé,ëèáî ðàíæèðîâàíèå ïî ìåñòàì).
Âàæíîå çíà÷åíèå èìååò ñïîñîá îïðåäåëåíèÿïîáåäèòåëÿ. Ýòîò ñïîñîá îáðàáîòêè áþëëåòåíåé äîëæåí îáëàäàòü ðÿäîì ïîëîæèòåëüíûõ ñâîéñòâ. Îò ãîëîñóþùèõ òðåáóåòñÿ çàïîëíèòü áþëëåòåíü, óêàçàâîòíîñèòåëüíûå ïðåäïî÷òåíèÿ äëÿ êàíäèäàòîâ. Ñóùåñòâóþò ðàçíûå ñïîñîáû çà-83ïîëíåíèÿ áþëëåòåíåé. Áþëëåòåíü áóäåò ëó÷øå âñåãî îòðàæàòü âîëþ ó÷àñòíèêà,åñëè â íåì ìîæíî óêàçàòü òî÷íûé ëèíåéíûé ïîðÿäîê (ñòðîãèé èëè íåñòðîãèé)ëè÷íûõ ïðåäïî÷òåíèé.Îáîçíà÷èì êîíå÷íîå ìíîæåñòâî m ≥ 2 àëüòåðíàòèâ (êàíäèäàòîâ, âàðèàíòîâðåøåíèé) êàê A = {a, b, c, .
. .}, ìíîæåñòâî n ≥ 2 ó÷àñòíèêîâ ïåðåãîâîðîâ (èçáèðàòåëåé, ýêñïåðòîâ) êàê P = {I1 , I2 , . . . , In }. Âåñ ó÷àñòíèêîâ W1 , W2 , . . . , Wn > 0õàðàêòåðèçóåò èõ îòíîñèòåëüíóþ ñèëó (êîëè÷åñòâî ãîëîñîâ). Îáîçíà÷èì ñóììàðíûé âåñ âñåõ ó÷àñòíèêîâ W . Ëè÷íûå ïðåäïî÷òåíèÿ ó÷àñòíèêîâ çàäàþòñÿíåñòðîãèì ëèíåéíûì ïîðÿäêîì íà ìíîæåñòâå àëüòåðíàòèâ. Ïðîôèëåì ïðåäïî÷òåíèé íàçûâàþòñÿ ñãðóïïèðîâàííûå ëè÷íûå ïðåäïî÷òåíèÿ âñåõ ó÷àñòíè-êîâ (ñóììèðóþòñÿ âåñà ó÷àñòíèêîâ, èìåþùèõ îäèíàêîâûå ïðåäïî÷òåíèÿ).Íèæå ïðèâåäåí ïðèìåð, êàê âûãëÿäèò ïðîôèëü ïðåäïî÷òåíèé 45 ó÷àñòíèêîâ(ñ ðàâíûì âåñîì 1) íà ìíîæåñòâå 5 êàíäèäàòîâ.Ïðèìåð 3.1.
Èìååòñÿ n = 45 ãîëîñóþùèõ è m = 5 êàíäèäàòîâ. Ïðåäïî÷òåíèÿèçáèðàòåëåé çàäàþòñÿ òàáëèöåé íèæå.Ïðîôèëü ïðåäïî÷òåíèé55837278aabcccdecdeaabcbbedbeaeaecaebdbddbcddeacÏî ïðîôèëþ ëè÷íûõ ïðåäïî÷òåíèé âû÷èñëÿþòñÿ çíà÷åíèÿ ôóíêöèè h(x, y)êàê ñóììà âåñîâ ó÷àñòíèêîâ, äëÿ êîòîðûõ àëüòåðíàòèâà x ïðåäïî÷òèòåëüíåå,÷åì àëüòåðíàòèâà y , è ïîëîâèíû âåñîâ ó÷àñòíèêîâ, äëÿ êîòîðûõ àëüòåðíàòèâû x è y ðàâíîöåííû. Ìàòðèöà ñî çíà÷åíèÿìè h(x, y) íàçûâàåòñÿ òóðíèðíîéìàòðèöåé.Áóäåì ãîâîðèòü, ÷òî x ïîáåæäàåò y ïðè ïîïàðíîì ñðàâíåíèè, åñëèh(x, y) > W/2.
Àëüòåðíàòèâà íàçûâàåòñÿ ïîáåäèòåëåì Êîíäîðñå, åñëè îíàïîáåæäàåò ëþáóþ äðóãóþ àëüòåðíàòèâó ïðè ïîïàðíîì ñðàâíåíèè. Îáîçíà÷èìw(x) - ìíîæåñòâî êàíäèäàòîâ, ó êîòîðûõ x âûèãðûâàåò ïðè ïîïàðíîì ñðàâíåíèè, à l(x) - òåõ, êîìó ïðîèãðûâàåò. Çàìåòèì, ÷òî êàíäèäàò x ÿâëÿåòñÿ ïîáåäèòåëåì Êîíäîðñå, òîãäà è òîëüêî òîãäà, êîãäà w(x) = A \ {x} è l(x) = ∅.Òóðíèðíàÿ ìàòðèöà äëÿ ïðèìåðà 3.1 èìååò ñëåäóþùèé âèä84Òóðíèðíàÿ ìàòðèöàaabcde202630221633181724b25c1929d151228e2327211431Òóðíèðíàÿ ìàòðèöà ÷àñòî áåðåòñÿ çà îñíîâó îêîí÷àòåëüíîãî îïðåäåëåíèÿïîáåäèòåëÿ.
Äàëåå ìû áóäåì ñòðîèòü õàðàêòåðèñòè÷åñêóþ ôóíêöèþ ñ ïîìîùüþ òóðíèðíîé ìàòðèöû. Äëÿ ñóùåñòâóþùèõ ïðîöåäóð îáðàáîòêè áþëëåòåíåéè îïðåäåëåíèÿ ïîáåäèòåëÿ æåëàòåëüíî âûïîëíåíèå ñëåäóþùèõ ñâîéñòâ.Ãîìîãåííîñòü. Êîëëåêòèâíîå ðàíæèðîâàíèå íå ìåíÿåòñÿ ïðè ïðîïîðöèî-íàëüíîì èçìåíåíèè âåñîâ â ïðîôèëå ëè÷íûõ ïðåäïî÷òåíèé.Åäèíîãëàñèå. Åñëè êàæäûé èçáèðàòåëü ñòàâèò êàíäèäàòà x íå íèæå êàí-äèäàòà y , òîãäà â êîëëåêòèâíîì ïðåäïî÷òåíèè x íå íèæå, ÷åì y .Ìîíîòîííîñòü. Åñëè îäèí èç èçáèðàòåëåé â ëè÷íîì ïðåäïî÷òåíèè ïîäíè-ìåò êàíäèäàòà x íà îäíó ïîçèöèþ, íå èçìåíÿÿ ðàíæèðîâàíèÿ äðóãèõ êàíäèäàòîâ, òîãäà â êîëëåêòèâíîì ïðåäïî÷òåíèè x íå ïîíèçèò ñâîé ðàíã.
Åñëè æåîäèí èç èçáèðàòåëåé, íàîáîðîò, â ëè÷íîì ïðåäïî÷òåíèè îïóñòèò x íà îäíó ïîçèöèþ, íå èçìåíÿÿ ðàíæèðîâàíèÿ äðóãèõ êàíäèäàòîâ, òîãäà â êîëëåêòèâíîìïðåäïî÷òåíèè x íå ïîâûñèò ñâîé ðàíã.Ñâîéñòâî Êîíäîðñå. Åñëè êàíäèäàò ÿâëÿåòñÿ ïîáåäèòåëåì Êîíäîðñå, òî-ãäà ýòîò êàíäèäàò â êîëëåêòèâíîì ïðåäïî÷òåíèè çàíèìàåò ïåðâîå ìåñòî.Ê ýòèì ñâîéñòâàì äîáàâèì åùå äâà ñâîéñòâà, âûïîëíåíèå êîòîðûõ ìû áóäåìïðîâåðÿòü äëÿ ïðåäëîæåííûõ íàìè ñïîñîáîâ ðàíæèðîâàíèÿ.Ñèëüíîå ñâîéñòâî Êîíäîðñå.
Åñëè w(x) ⊇ w(y), l(x) ⊆ l(y) è h(x, y) ≥W/2, òî â êîëëåêòèâíîì ïðåäïî÷òåíèè êàíäèäàò x áóäåò íå íèæå, ÷åì êàíä. y .Ïðàâèëî áîëüøèíñòâà. Äëÿ ëþáîãî íà÷àëüíîãî ïðîôèëÿ ïðåäïî÷òåíèéè ëþáîãî ïîðÿäêà êàíäèäàòîâ a1 > a2 > ... > am ñóùåñòâóåò ÷èñëî V , òàêîå÷òî ïðè äîáàâëåíèè ó÷àñòíèêà ñ äàííûì ïîðÿäêîì êàíäèäàòîâ è ñ âåñîì íåìåíüøå, ÷åì V , òî äëÿ íîâîãî ïðîôèëÿ ïîëó÷èòñÿ êîëëåêòèâíîå ðàíæèðîâàíèå,â êîòîðîì a1 > a2 ≥ . . . ≥ am .Ëåììà 3.1. Åñëè äëÿ ïðîöåäóðû ðàíæèðîâàíèÿ âûïîëíÿåòñÿ ñèëüíîå ñâîéñòâî Êîíäîðñå, òî ïðàâèëî áîëüøèíñòâà òàêæå âûïîëíÿåòñÿ.85Äëÿ äîêàçàòåëüñòâà ëåììû äîñòàòî÷íî çàìåòèòü, ÷òî äîáàâëåíèå ó÷àñòíèêàñ ïîðÿäêîì ïðåäïî÷òåíèé a1 > a2 > ...
> am è âåñîì áîëüøèì, ÷åì ñóììàðíûéâåñ îñòàëüíûõ ãîëîñóþùèõ, ïðèâîäèò ê êîëëåêòèâíîìó ðàíæèðîâàíèþ a1 >a2 > ... > am .Äàëåå ìû ïðîâåðèì âûïîëíåíèå äàííûõ ñâîéñòâ äëÿ ïðåäëàãàåìûõ íèæåïðîöåäóð ðàíæèðîâàíèÿ êàíäèäàòîâ. Ýòè ïðîöåäóðû îñíîâàíû íà ôîðìèðîâàíèè íåêîòîðîé êîîïåðàòèâíîé èãðû, ñâÿçàííîé ñ ïðîôèëåì çàïîëíåííûõ áþëëåòåíåé. Áóäåì îáîçíà÷àòü K ⊆ A êàê êîàëèöèþ êàíäèäàòîâ. Ïðåäïîëîæèì,÷òî äëÿ êàæäîé êîàëèöèè K îïðåäåëåíà íåîòðèöàòåëüíàÿ ìîíîòîííàÿ ôóíêöèÿv(K).  êîîïåðàòèâíîé òåîðèè èãð îíà íàçûâàåòñÿ õàðàêòåðèñòè÷åñêîé. Áóäåìîïðåäåëÿòü õàðàêòåðèñòè÷åñêóþ ôóíêöèè v(K) äëÿ çàäàííîãî ïðîôèëÿ ïðåäïî÷òåíèé ãîëîñóþùèõ. Òîãäà äëÿ ðàíæèðîâàíèÿ êàíäèäàòîâ ìîæíî èñïîëüçîâàòüêðèòåðèè êîîïåðàòèâíîé òåîðèè èãð äëÿ èññëåäîâàíèÿ çàäà÷è ãîëîñîâàíèÿ.
Äàëåå â êà÷åñòâå òàêîãî êðèòåðèÿ áóäåì èñïîëüçîâàòü ñèëó âëèÿíèÿ êàíäèäàòà ââèäå âåêòîðà Øåïëè. Òîãäà ðàíæèðîâàíèå êàíäèäàòîâ áóäåò ñäåëàíî ñîãëàñíîçíà÷åíèÿì âåêòîðà Øåïëè äëÿ ñïåöèàëüíûì îáðàçîì ïîñòðîåííîé õàðàêòåðèñòè÷åñêîé ôóíêöèè.3.2Õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ êàê çíà÷åíèåèãðû ñ ïîñòîÿííîé ñóììîéÌû áóäåì îïðåäåëÿòü õàðàêòåðèñòè÷åñêóþ ôóíêöèþ íà îñíîâå òóðíèðíîéìàòðèöû. Íå îãðàíè÷èâàÿ îáùíîñòè, ìîæíî ñ÷èòàòü, ÷òî ïðåäïî÷òåíèÿ ó÷àñòíèêîâ îïèñûâàþòñÿ ñòðîãèì ëèíåéíûì ïîðÿäêîì.  ñàìîì äåëå, åñëè ïîðÿäîêíåñòðîãèé, òî ïîäåëèì êîëè÷åñòâî ãîëîñîâ â ïðîôèëå ïðåäïî÷òåíèé íà ðàâíûå÷àñòè ìåæäó ïåðåñòàíîâêàìè ñðåäè ðàâíîöåííûõ êàíäèäàòîâ.
Íàïðèìåð, ïóñòüèçáèðàòåëü èìååò W1 ãîëîñîâ è íåñòðîãèå ïðåäïî÷òåíèÿ a = b = c > d = e.Òîãäà â ïðîôèëå ïðåäïî÷òåíèé ó÷òåì åãî ãîëîñà, êàê ïî W1 /12 ãîëîñîâçà ñòðîãèå ïîðÿäêè a>b>c>d>e, a>c>b>d>e, b>a>c>d>e, b>c>a>d>e,c>a>b>d>e,c>b>a>d>e,a>b>c>e>d,a>c>b>e>d,b>a>c>e>d,b>c>a>e>d, c>a>b>e>d, c>b>a>e>d. Íåòðóäíî ïîíÿòü, ÷òî òàêèå ïðåîáðàçîâàíèÿ íå ìåíÿþò òóðíèðíóþ ìàòðèöó.Çàìåòèì, ÷òî ïðè ïðîïîðöèîíàëüíîì èçìåíåíèè âåñîâ ó÷àñòíèêîâ ýëåìåíòûòóðíèðíîé ìàòðèöû èçìåíÿþòñÿ ñ òåì æå êîýôôèöèåíòîì ïðîïîðöèîíàëüíî-86ñòè, ïîýòîìó íåóäèâèòåëüíî, ÷òî ñâîéñòâî ãîìîãåííîñòè áóäåò âûïîëíÿòüñÿ äëÿâñåõ ïîñòðîåííûõ íàìè ïðîöåäóð ðàíæèðîâàíèÿ íà îñíîâå òóðíèðíîé ìàòðèöû.Äëÿ óäîáñòâà áóäåì ñ÷èòàòü, ÷òî âåñ êàæäîãî ó÷àñòíèêà ðàâåí åäèíèöå. Îäíàêî, âñå ïîëó÷åííûå ðåçóëüòàòû áóäóò ñïðàâåäëèâû è äëÿ îáùåãî ñëó÷àÿ âåñîâW1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
