Про одну статичну модель прогнозу голосування
A simplified model of finances distribution among regions by some competing pre-election unions in the fight for the maximal number of votes is formulated. The model is reduced to the search of the equilibrium point by Nash. To determine the point a numerical method solving for monotone variational...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/173800 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1866302511496822784 |
|---|---|
| author | Belyaeva, E. N. Panin, V. M. |
| author_facet | Belyaeva, E. N. Panin, V. M. |
| author_sort | Belyaeva, E. N. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-07-23T14:06:30Z |
| description | A simplified model of finances distribution among regions by some competing pre-election unions in the fight for the maximal number of votes is formulated. The model is reduced to the search of the equilibrium point by Nash. To determine the point a numerical method solving for monotone variational inequalities with a degenerate operator is used. |
| first_indexed | 2025-07-17T10:25:47Z |
| format | Article |
| fulltext |
© Е.Н. Беляева, В.М.Панин, 2003
Системні дослідження та інформаційні технології, 2003, № 3 81
УДК 518.9
ОБ ОДНОЙ СТАТИЧЕСКОЙ МОДЕЛИ ПРОГНОЗА
ГОЛОСОВАНИЯ
Е.Н. БЕЛЯЕВА, В.М. ПАНИН
Формулируется упрощенная модель распределения финансовых средств по ре-
гионам некоторыми конкурирующими предвыборными объединениями в
борьбе за получение как можно большего числа голосов избирателей. Модель
сведена к отысканию точки равновесия по Нэшу. Для её определения исполь-
зуется численный метод решения монотонных вариационных неравенств с вы-
рожденным оператором.
ПОСТАНОВКА ЗАДАЧИ
Пусть некоторый регион (страна) является объединением n более мелких
территориальных единиц, количество избирателей в каждой из которых
njT j ,,1, …= известно. Для определенности, 1T — число избирателей в
западном регионе (области), 2T — в северном, 3T — в центральном и т.д.
Предвыборную борьбу ведут m объединений, называемых далее партиями:
1=i — Народный фронт, 2=i — Партия зеленых и т.д. Каждая из партий
имеет ограниченное финансирование mihi ,,1, …= . Стратегия каждой i -й
партии — распределить свои средства jix по регионам nj ,,1 …= так, что-
бы набрать наибольшее число голосов.
Примем в качестве постулата, что функция выигрыша )( jiji xf i -й
партии в j -м регионе пропорциональна затраченным финансовым
средствам jix , например, ijijijiji hxkxf /)( = или iijij hxk
jiji exf /1)( −−= ,
и число проголосовавших за неё в j -м регионе определяется как
njxfT jijij ,,1,)( …= . Коэффициенты jik , называемые коэффициентами
приоритета партий, постоянны и рассматриваются далее. Ясно, что общее
число ),,( 1 niii xxf … голосов, поданных за i -ю партию, определяется как
их сумма по регионам:
mixfTxxf
n
j
jijijniii ,,1,)(),,(
1
1 …… ==∑
=
. (1)
Обозначим { } { }T
m
TT
nii
T
i xxxxxx )()1(1)( ,,;,, …… == , где T — символ
транспонирования; mnn
i RxRx ∈∈ ,)( — вектор-столбцы. Для иллюстрации
приведем следующую таблицу.
Е.Н. Беляева, В.М.Панин
ISSN 1681–6048 System Research & Information Technologies, 2003, № 3 82
Распределение финансовых средств и поданных голосов
Регионы ( )j
Количество избирателей ∑
=
n
j 1
1 j n
Партии ( )i
1T jT nT M
1 Финансовые
средства 11x jx1 nx1 1h
«За» )( 11111 xfT )( 11 jjj xfT )( 11 nnn xfT )( )1(1 xf
i Финансовые
средства 1ix jix nix ih
«За» )( 111 ii xfT )( jijij xfT )( ninin xfT )( )(ii xf
m Финансовые
средства 1mx jmx nmx mh
«За» )( 111 mm xfT )( jmjmj xfT )( nmnmn xfT )( )(mm xf
Здесь M — общее число избирателей, «За» — количество проголосо-
вавших «за».
Пояснения требуют лишь коэффициенты njmik ji ,,1,,,1, …… == .
Они учитывают известное предпочтение избирателей j -го региона в пользу
той или иной партии. Например, при 3,2 == nm запись { }=2111 ;kk
{ }5,0;1= , { } { }1;5,0; 2212 =kk , { } { }8,0;8,0; 2313 =kk означает, что в пер-
вом регионе предпочтение будет отдано первой партии, во втором — вто-
рой, в третьем — их шансы равны, но не так сильны как у первой или вто-
рой партии в соответствующих регионах.
Определение коэффициентов jik — сложная социологическая пробле-
ма. Для простоты можно предположить, что все jik принимают значения из
m фиксированных чисел mkk ,,1 … , где 01 1 ≥≥≥≥ mkk … ; 1k означает
наивысший приоритет, mk — самый низкий. При отсутствии информации о
приоритете партий значения jik можно полагать равными, например,
1=jik для всех ji, . Модель в этом случае называется моделью без приори-
тета (или с равным приоритетом) партий.
МАТЕМАТИЧЕСКАЯ ФОРМАЛИЗАЦИЯ
Стратегия поведения каждой партии заключается (при отсутствии ком-
промиcса) в максимизации поданных за нее голосов )( )(ii xf :
mixf ii
x i
,,1),(max )(
)(
…= (2)
на допустимом множестве. Допустимое множество определяется следую-
щими условиями.
Во-первых, необходимо соблюсти требование ограниченности финан-
совых средств:
Об одной статической модели прогноза голосования
Системні дослідження та інформаційні технології, 2003, № 3 83
.,0,,,1,
1
jixmihx ji
n
j
iji ∀≥=≤∑
=
… (3)
Во-вторых, количество проголосовавших «за» в каждом j -м регионе
не может превышать числа избирателей j -го региона:
njTCxfT
m
i
jjjijij ,,1,)(
1
…=≤∑
=
,
где jC — коэффициент участия в голосовании избирателей j -го региона.
Предполагая njC j ,,1,1 …== , вместо предыдущего условия запишем
njxf
m
i
jiji ,,1,1)(
1
…=≤∑
=
. (4)
Соотношения (3), (4) определяют допустимое множество Ω значений
аргумента nmRx∈ , на котором рассматриваются задачи (2).
Формулировка (2) – (4) представляет собой известную запись равнове-
сия по Нэшу с m «игроками» (партиями) и их функциями полезности )(xfi ,
когда )()( )(iii xfxf = — выпуклые функции, mi ,,1 …= . Решением по Нэ-
шу принято считать так называемую точку равновесия =Tx )( *
{ }T
m
T xx )(,,)( *
)(
*
)1( … , компоненты *
)(ix которой объявляются решениями
соответствующих задач (2). По определению равновесия при выборе други-
ми «игроками» (например, 1,,1 −= mi … ) неоптимальных значений
1,,1,*
)()( −=≠ mixy ii … последний m -й игрок может даже превысить
значение )( *
)(
*
mmm xff = , максимизируя функцию )( )(mm xf в (2) при огра-
ничениях (3), (4), в которых значения 1,,1,)( −== miyx ii … фиксирова-
ны. Гарантированный же выигрыш i -го «игрока» составляет величина
)( *
)(
*
iii xff = , для чего и необходимо найти *
)( ix .
Отыскание точки равновесия *x легко свести ( [1, 2] и др.) к решению
вариационного неравенства (ВН)
Ω∈∀≥− xxxxF 0,)( ** , (5)
где mnmn RRxF →:)( . Действительно, согласно необходимым условиям
экстремума первого порядка для задачи (2), имеет место
mixx
dx
xdf
ii
i
ii ,,1,0,
)( *
)()(
)(
*
)( …=≤− ,
где , — символ скалярного произведения векторов; )(ix — компонен-
ты произвольного допустимого вектора Ω∈x . Обозначая =)(xFi
Е.Н. Беляева, В.М.Панин
ISSN 1681–6048 System Research & Information Technologies, 2003, № 3 84
midxxdf iii ,,1,)( )()( …=−= , приходим к ВН (5), в котором ( ) =xF T
( ) ( ){ } mnT
m
T RxFxF ∈= ,,1 … .
Обозначим { }njmixRxX ji
mn ,,1;,,1,0 …… ==≥∈=+ ,
mihxxg
n
j
ijii ,,1,)(
1
…=−=∑
=
,
njxfxg
m
i
jijijm ,,1,1)()(
1
…=−= ∑
=
+ (6)
и сформулируем задачу окончательно.
Необходимо найти точку Ω∈*x , являющуюся решением следующего ВН:
Ω∈∀≥− xxxxF 0,)( ** ,
{ }.,,1,0)( nmrxgXx r +=≤∈=Ω + … (7)
Примем для исследования линейную форму функции выигрыша и
1=jik для всех ji, , т.е.
∑
=
−− ==
n
j
jijiiiijijiji xThxfhxxf
1
1
)(
1 )(,)( . (8)
Тогда функции ограничений )(xgr линейны по ,x а оператор
FxF =)( является постоянным с компонентами { }ni
T
i TThF ,,1
1 …−= ,
mi ,,1 …= . Представив ограничения (7) в виде ( ) 0≤−= bAxxg , легко убе-
диться, что матрица A и вектор b имеют следующую структуру:
{ }
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
+
+
==
+
+
−
−
−
−
1
1
,
11
11
1
1 1
1
1
1
1
1
1
1
1
m
nm
m
m
nm
n
m
m
n
rl
h
h
b
b
b
b
b
h
h
h
h
nm
m
m
aA .
Строки ( )xga T
rr ′= матрицы A при mr ,,1 …= имеют вид =ra
( ) ( ) ( ) ( ) ( ){ }T
m
T
r
T
r
T
r
T 0,,0,1,0,,0 111 …… +−= , где )(0 i и ( )i1 — n -мерные век-
тор-столбцы с координатами соответственно 0 и 1. Строки ( )xga T
jmr +′= ,
Об одной статической модели прогноза голосования
Системні дослідження та інформаційні технології, 2003, № 3 85
nj ,,1 …= матрицы A образуют (см. структуру A ) подматрицу )( nmn × с
ненулевыми диагональными отрезками { } n
ii Rhh ∈−− 11 ,,… , mi ,,1 …= .
АЛГОРИТМ ЧИСЛЕННОГО РЕШЕНИЯ
Перейдем к численному решению вариационного неравенства (7) с указан-
ными )(),( xgxF r . Необходимые условия первого порядка для него хорошо
известны:
0)(,0)()( **
1
*** ==′+ ∑
+
=
xgxgxF rr
nm
r
rr λλ ,
0,,,1,0 ** ≥+=≥ jir xnmr …λ . (9)
Вследствие линейности функций )(xgr условия (9) являются также и
достаточными, т.е. отыскание точки *x сводится к решению системы (9).
Отметим, что оператор )(xF для ВН (7) не является сильно монотонным,
( ) const=xF . Метод Пшеничного [3], как и другие методы проекционного
типа [2] для решения вырожденного ВН (7), является достаточно трудоем-
ким, так как требует решения вспомогательной задачи квадратичного про-
граммирования. Чтобы избежать этого, перейдем от ВН (7) к другому ВН.
Обозначим { }nmrR r
nm +=≥∈=Λ ++ ,,1,0 …λλ ,
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=
λ
x
z , ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−
=
)(
)(
)(
zL
zL
zL x
z
λ
, λT
x AFzL +=)( ,
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
==
+ )(
)(
)()(
1
xg
xg
xgzL
nm
…λ .
(10)
Отметим, что векторы z и )(zLz имеют размерность nmmn ++ ,
+Λ×Ω∈*z . Как показано в работе [2], оператор ( )zLz является монотон-
ным, т.е. 0,)~( ≥zzzLzz при любых +Λ×∈ mnRz~ , nmmnRz ++∈ , и на осно-
вании (7), (9) имеет место следующее ВН:
++ Λ×∈∀≥− XzzzzLz ,0,)( ** . (11)
Хотя его размерность гораздо выше, чем у ВН (7), решать ВН (11)
проще, чем (7), поскольку проектирование на множество +++ Λ×= XZ
осуществляется просто.
Применим для решения ВН (11) экстраградиентный метод Корпелевич
[4] ( ))(1 k
z
k
Z
k zLzz α−Π= +
+ , где ( ) LzLzz k
z
k
Z
k 1,)( ≤−Π= + αα ;
Е.Н. Беляева, В.М.Панин
ISSN 1681–6048 System Research & Information Technologies, 2003, № 3 86
L — константа Липшица для оператора ( )zLz ; +Π
Z
— оператор проекти-
рования на множество +Z .
Оценим L . Для произвольных 21, zz согласно обозначениям (10) име-
ем 2121 )()()( zzzLzLzL zzzz −≤− , где
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−
=
0
0)(
A
AzL
T
zz . Так как
z — евклидова норма вектора z , то )(zLzz — согласованная с ней спе-
ктральная норма (несимметричной) матрицы ( )zLzz , которую сложно вычи-
слять. Как известно из линейной алгебры, Ezzzz zLzL )()( ≤ , где
( ) Ezz zL — легко вычисляемая евклидова норма матрицы )(zLzz . Поэтому
в качестве L можно взять
21
1 1
22)( ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
== ∑ ∑
+
= =
nm
r
mn
l
lrEzz azLL .
Учитывая структуру матрицы A , окончательно находим
21
1
21)(2
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
+= ∑
=
−
m
i
ihnnmL . (12)
ФОРМУЛИРОВКА МЕТОДА
Обозначим kzρ компоненты вектора ,,,1, nmmnZz k ++=∈ + …ρ
( ) ( ) ( )
⎭
⎬
⎫
⎩
⎨
⎧= +
k
nm
kTk
m
TkTk xxz λλ ,,,,, 1)()1( …… . Пусть 0z — произвольное
начальное приближение из +Z , найдено L1=α с учетом (12) и задана точ-
ность окончания расчета ε . Опишем k -ю итерацию метода в точке
…,1,0, =∈ + kZzk .
Шаг 1. Вычислить согласно (10) компоненты ( )ρ)( k
z zL вектора
)( k
z zL , nmmn ++= ,,1 …ρ , учитывая, что r
k
r
k
r bxaxg −= ,)( и
.,,1, nmraA T
r
r
k
r
kT +==∑ …λλ
Шаг 2. Найти компоненты kzρ вектора kz .
( ){ } .,,1,)(;0max nmmnzLzz k
z
kk ++=−= …ρα ρρρ
Шаг 3. Аналогично шагу 1 вычислить )( k
z zL .
Шаг 4. Найти 1+kz .
( ){ } .,,1,)(;0max1 nmmnzLzz k
z
kk ++=−=+ …ρα ρρρ
Об одной статической модели прогноза голосования
Системні дослідження та інформаційні технології, 2003, № 3 87
Шаг 5. Если nmmnzz kk ++=∀≤−+ ,,1,1 …ρερρ , то принять
*zz k ≈ . Расчет окончен. В противном случае обозначить 1: += kk . Конец
итерации.
Алгоритм легко обобщается на случай, когда 1≤jik и 1≤jC ,
njmi ,,1,,,1 …… == . Если )( jiji xf — любые выпуклые функции, то не-
сложно распространить алгоритм и на этот случай. Однако если
ijiji hxk
jiji exf −−=1)( , то модель становится невыпуклой, ограничения (4)
могут определять несвязное допустимое множество, условия (9) перестают
быть достаточными, и задача отыскания *x усложняется.
ЛИТЕРАТУРА
1. Nagurney A. Network economics: a variational inequality approach. — Norwell: Klu-
wer academ. publ., 1993. — 326 p.
2. Панин В.М., Скопецкий В.В., Лаврина Т.В. Модели и методы конечномерных
вариационных неравенств // Кибернетика и системный анализ. — 2000. —
№ 6. — С. 47–64.
3. Пшеничный Б.Н., Калжанов М.У. Метод решения вариационных неравенств //
Кибернетика и системный анализ. — 1992. — № 6. — С. 48–55.
4. Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и
других задач // Экономика и математические методы. — 1976. — 12,
№ 4. — С. 747–756.
Поступила 21.04.2003
|
| id | journaliasakpiua-article-173800 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:25:47Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/90/1bf64d29dc743d040d5091ae19a2fa90.pdf |
| spelling | journaliasakpiua-article-1738002019-07-23T14:06:30Z On a static model of voting prognosis Об одной статической модели прогноза голосования Про одну статичну модель прогнозу голосування Belyaeva, E. N. Panin, V. M. A simplified model of finances distribution among regions by some competing pre-election unions in the fight for the maximal number of votes is formulated. The model is reduced to the search of the equilibrium point by Nash. To determine the point a numerical method solving for monotone variational inequalities with a degenerate operator is used. Формулируется упрощенная модель распределения финансовых средств по регионам некоторыми конкурирующими предвыборными объединениями в борьбе за получение как можно большего числа голосов избирателей. Модель сведена к отысканию точки равновесия по Нэшу. Для её определения используется численный метод решения монотонных вариационных неравенств с вырожденным оператором. Формулюється спрощена модель розподілу коштів по регіонам деякими конкуруючими передвиборними об’єднаннями у боротьбі за найбільшу кількість голосів виборців. Модель зведена до пошуку точки рівноваги по Нешу. Для її визначення використовується чисельний метод розв’язання монотонних варіаційних нерівностей з виродженим оператором. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-07-23 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/173800 System research and information technologies; No. 3 (2003); 81-87 Системные исследования и информационные технологии; № 3 (2003); 81-87 Системні дослідження та інформаційні технології; № 3 (2003); 81-87 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/173800/173678 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Belyaeva, E. N. Panin, V. M. Про одну статичну модель прогнозу голосування |
| title | Про одну статичну модель прогнозу голосування |
| title_alt | On a static model of voting prognosis Об одной статической модели прогноза голосования |
| title_full | Про одну статичну модель прогнозу голосування |
| title_fullStr | Про одну статичну модель прогнозу голосування |
| title_full_unstemmed | Про одну статичну модель прогнозу голосування |
| title_short | Про одну статичну модель прогнозу голосування |
| title_sort | про одну статичну модель прогнозу голосування |
| url | https://journal.iasa.kpi.ua/article/view/173800 |
| work_keys_str_mv | AT belyaevaen onastaticmodelofvotingprognosis AT paninvm onastaticmodelofvotingprognosis AT belyaevaen obodnojstatičeskojmodeliprognozagolosovaniâ AT paninvm obodnojstatičeskojmodeliprognozagolosovaniâ AT belyaevaen proodnustatičnumodelʹprognozugolosuvannâ AT paninvm proodnustatičnumodelʹprognozugolosuvannâ |