Теоретико-игровые решения для некоторых моделей рынка тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГ6 од

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

АДНАН ШАМОН ИОУСЙ'5

Теоретико-игровые решения для некоторых моделей рын:«.

Специальность 01.01.09. - Математическая кибернетика.

АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата физико-математических нзук

Санкт-Петербург 1993

Работа шгалнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского университета.

Научнкй руководитель - ■ кандидат физико-математических наук, доцент

КУЛАКОВСШ Т.Е.

Официальные оппоненты - доктор физико-математических наук ЕРМАКОВ М.С.

кандидат физико-математических наук ЧИРКОВ М.К.

Ведущая организация - Вычислительный центр

Российской Академии Наук

Защита состоится " /¿> " 1993 г_

в часов на заседании специализированного Совета К 063.57.49

по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском • государственном университете по адресу: 198904, Санкт-Петербург, Старый Петергоф, Библиотечная площадь, 2.

С диссертацией можно ознакомиться в библиотеке имени А.М.Горького Санкт-Петербургского государственного университета.

Автореферат разослан " " 1993 г.

УЧЕНЫЙ СЕКРЕТАРЬ специализированного Совета кандидат физико-математических

наук А.М.Шепелявый

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОШ

АКТУАЛЬНОСТЬ ТШ. Возростахщзй интерес к теоретико-игровым моделям определяется той ролью, которую играет теория игр в смежных областях математики и практических пр&лошшях. Принципы оптимальности, возникшие в кооперативных играх, получили широкое распространение в теории многокритериальной оптимизации, теории графов, математической статистике. Социально-экономические приложения весьма обширны - это задачи распределения прибыли, инвестиций, ценообразование в регулируемой экономике, процедуры голосования и переговоров, биржевые торги и аукционы, ,

Разнообразие экономических задач, порождающих теоретико- игровые модели кооперативного типа делают принципиально невозможным однозначное определение оптимального решения. Поэтому построение ноеых классов моделей, Еыработка для них принципов оптимальности, установление их реализуемости, создание ал.оритмов построения решений и их программного обеспечения является особенно актуальными для социально-экономических приложений, а исследования в этих направлениях дают новые возможности эффективного решения езеных практических задач изучения и управления социально- экономическими процессами.

ЦЕЛЬ РАБОТЫ. Состоит в изучении свойств ноеых классов теоретико-игроЕНХ моделей, возникающих в экономических задачах обмена, алгоритмов поиска решений, основанных на разработке различных принципов оптимальности и их реализации на ПЗВМ.

МЕТОДЫ ИССЛЕДОВАНИЯ. Разработка теоретико-игровых решений опирается на аппарат теории экстремальных задач, теории вероятностей и статистических решающих правил. Сложный характер возникающих экстремальных задач требует применения комбинированных методов, включая линейное, дискретное, выпуклое программирование и случайный поиск. Широко применяется аппарат теории кооперативных игр и теория рыночного равновесия.

НАУЧНАЯ НОВИЗНА. В диссертации:

- исследованы новые классы математико-экономических моделей обмена,

- для выделенных классов построены соответствующие кооперативные игры и исследованы свойства их решений, а также предложены новые принципы оптимальности,

- разработаны алгоритмы построения кооперативных игр и разных типов их решений для выделенных классов экономических моделей обмена,

- составлены программы реализации данных алгоритмов для ПЭВМ.

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ полученных результатов состоит в том, что

они открывают новые возможности для теоретико-игрового моделирования экономических процессов. Они могут быть полезны в экономической практике торгов для получения разумных предварительных . оценок возможностей отдельных участников и групп, приближений равновесных цен и других характеристик. Разработанные алгоритмы могут быть применены к оптимизационным задачам и другого физического содержания.

АПРОБАЦИЯ РАБОТЫ. Результаты работы докладывались: - на семинаре кафэдры статистического моделирования СПбГУ (19Э1, 19Э2)

- на Третьей международной конференции МОДА-З, С.-Петербург, 1992. ПУБЛИКАЦИИ. По теме диссертации опубликовано две работы. СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, грех глав и приложения. Библиография содержит 46 наименований. Общий объем 110 страниц.

С0ДЕР2АНЙЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Во_введении дается общая характеристика роли и места теории игр в задачах принятия решений с многими участниками в условиях конфликта или несовпадения интересов и приводится краткое изложение основных результатов диссертации.

Наиболее значительные приложения теории кооперативных игр относятся к экономическим моделям обмена. Возникающие здесь оптимизационные модели называются рынками.

Рынком с п участниками и о товарами называется совокупность м = {к, (Б1)^ , , (а1)^ } , где N = {1 ,...,п} -

участники, в1 £ - допустимые распределения товаров, и1 (х1) -

1 1 *п

функции полезности, заданные на в , • аА в - начальные распределения.

В дальнейшем и1- считается линейной. На рынке происходит обмен товарами в. соответствии с предпочтениями участников, заданными их функциями полезности. Механизм регулирования этого процесса осуществляется через вектор цен р « И™.

Изеэстно, что каздому рынку соответствует сбалансированная кооперативная игра. Решения таких игр могут быть использованы при

анализе соответствующих рынков.

Б главе_1 вводятся основные понятия и необходимые результаты

теории кооперативных игр. Кооперативной игрой п лиц называется

пара <и,?>, где ы={1.,,,п} - множество участников, Y -

характеристическая функция игры, ставящая в соответствие каждому

S s N число V(S), стандартно интерпретируемое как максимальный

выигрыш, который коалиция может себе обеспечить независимо от

остальных участников.

Исходами игры является элементы множества

A = (i«8n;ï, V(i), i=1....... E z* - V(N) )

l 1 ieN 1 i

называете дележами.

На множестве А. задано отношение доминирования. Пусть к,у е к.

Говорят, что х доминирует у (х dom у), если 1 ) > у^, i е s,

2) Е z, V(s) (условие достижимости). leS Х

с-ядром называется множество всех недоьынируемых элементов из

А.

Пусть S s N - характеристический вектор для S s N.

Пара (е,л), где в - множество подмножеств игроков, л = Og)^ -

множество неотрицательных чисел, называется сбалансированным набором, если е *8*s = *N.

Ssô

Игра называется сбалансированной, если e^çv(s) y(n) для

seö ь

любого сбалансированного набора.

Известно, что сбалансированность игры есть необходимое и достаточное условие неяустоты ее с-ядра.

Вектор Шепли. - это отображение, ставящее в соответствие каждой игре <IJ,V> вектор в пространстве Rn. Он однозначно определяется с помощью трех аксиом Шепли, и з большинстве случаев является дележом. Аксиомы Шэпли и их аналоги подробно рассмотрены в § 3.

Для вычисления компонент вектора Шепли используется формула, полученная из вероятностны;: соображений.

$ (у) = z АНр;.§_:Ш (7(S и i) - v(s))

1 S£N\i Г" Зта формула интерпретирует i-в компоненту вектора Шэпли как средний вклад игрока i во все коалиция, где коэффициент взвешивания равен вероятности того, что в случайной очередо (i^,...,^) перед игроком i стоят члены коалиции 3. Вектор » есть

h

вариант "справедливого" распределения, а индекс Шепли

Mi1

интерпретируется как индекс "силы", значимости игрока 1.

В 5 4 дается исторический обзор и последние достиеенкя в развитии идей Шепли, а также обсуждаются вычислительные аспекты, связанные с вектором Шепли.

В_главе II рассматривается теоретико-игровая модель торговой

сделки. В § 1 описывается класс моделей ринка, для которых проводится весь дальнейший анализ.

Имеются множества и={1,...,п} участников и к={1,...,ш}

к к

товаров. Для каздого к * К имеется разбиение N = и №> , где - множество продавцов, N2 - множество покупателей товара к. Допустимые распределения ?к по товару к образуют множество

D =

«?.....Г

Л ^

VI а I , i « llj

bï

•1 ui С

ieNo

i e No

E 4 = Z ?ï

4

Если = о , 1 « 5, к=1,...,п, то = ?к(з) называется допустимым Б-распределением.. Множество таких распределений обозначим 1)^(8).

Полезность единицы товара к для агента I обозначается (1=1,...,п).

Пара 1 * , з е называется к-допустимой, если Обмен товаром к может осуществляться только между к-допустимыми парами.

Доход коалиции s при распредалении есть

I - 1 qïçi

jellgTiS ■• ieliVnS

Yk(?k(S) =

1

Общий доход коалиции s есть 2 Ув(?л(5)) = v(ç (s)).

к=1

Положим у (S) = max V(f(s)), где максимум берется по всем i(S) е D1(S)XD2(S)X...XDra(S).

Данная экстремальная задача есть задача линейного.

программирования транспортного типа, однако, возможное соотношение ее параметров £ а^ < £ ъ^ совершенно нетрадиционно для

транспортной задачи. Далее рассмотрим однопродуктовую модель.

В теореме 2.1. доказано, что решением экстремальной задачи нахождения v(s) является распределение, полученное методом северо-западного угла для специальной транспортной таблицы. Решение имеет следующую структуру. Существует пара i0(s) = n^ j"q(s) « Ng, называемая маргинальной, такая, что

fj: = а^ , если q^ (S) ' * е ^l03

fj = b3 ' есЛИ Ь > %(S) • ^NgPS q = О , если qlo(s) < qi < qJo(S) Если £ н < £ bj, TO F1q(S) = aiQ(S) , иначе = b^

Распределение f(s) назовем s-тривиалышм. Если s=N, то f(N)=f - тривиальное распределение.

Мз структуры решения видно, что агенты, для которых

q^ < q^ < q^, не участвуют в "оптимальной" сделке. Это дает

повод рассматривать и другие решения, в частности, вектор Шепли.

Кооперативной игрой, порожденной данным рынком, назовем кооперативную игру п лщ с характеристической функцией v(s), определенной выше.

В теореме 2.2 доказано, что такая игра имеет непустое ядро. Доказательство основано на проверке ее сбалансированности.

Вектор зс(?,р) е R? доходов от сделки при цене р>о и

а

распределении ? есть вектор с компонентами

^(f ,р) = ?А(p-q^) для i «

Zjii.p) = «¿(qj-p) ДЛЯ i « Ng

Пара (p°,f°) называется равнсзесной, если

x(p°,i°) x(p°,f) для всех допустимых распределений

Такое определение является аналогом конкурентного .равновесия в данной модели рынка.

В теореме 2.4. доказано, что существует цена р° > 0, при которой вектор доходов x(f,p°), где f - тривиальное распределение, содержится в ядре кооперативной игры <H,V>.

В § 5 полученные результаты обобщаются на многопродуктовый случай (m > 1).

В_главе_Ш предлагается в качестве решения (p*,i*) задачи о торговой сделке рассматривать такую пару, что вектор доходов х(р*,?*) является наилучшим приближением к некоторому "эталонному" вектору. Если эталонный Еектор - это вектор Шешш, то (р ,f ) может быть в ряде случаев более приемлемым для участников, чем (р°,Г), в силу интерпретации вектора Шешш как "справедливого" распределения.

Рассматривается экстремальная задача (А):

min Е (*« - х<(Р,?))2 i=1 1 1

при ограшг-эниях

? е D(N) Xjip,?) О i=1.....П.

Это нелинейная задача, однако при фиксированном р она сводится к задаче с квадратичной целевой функцией и линейными ограничениями меньшей размерности.

Для решения последней задачи предложена модификация выпуклого симплекс-метода Зангвилла-Вулфа.

Этот метод разработан для минимизации выпуклой функции при линейных ограничениях Ах = Ъ, х ©. Предложенная модификация пригодна для ограничений {Ах = Ъ, -© х с} и при этом нэ требузт увеличения числа переменных. Лемма 3.6 содержит необходимые и достаточные условия существования направления спуска в точке х, теорема 3.2 описывает точни Куна-Таккера. На основании этих результатов формулируется алгоритм.

В § 4 предлагается способ организации случайного поиска для решения задачи (А), которая добавлением штрафной функции перестраивается в задачу поиска на единичном кубе. Каждый раз через определенное число шагов закон, по которому выбирается точка из единичного куба меняется таким образом, чтобы вероятность попасть в ¿-окрестность глобального минимума увеличивалась, при этом учитывается накопленная информация.Кроме того, при решении задачи (А) производится "настройка" параметров поиска на функцию цели в диалоговом режиме.

При решении задачи (А) использовалась комбинация двух упомянутых методов, причем метод случайного поиска использовался для вычисления наиболее вероятного интервала поиска для р, а затем применялся выпуклый ' симплекс-метод. Затем случайный поиск

Г*

повторялся в уточненной области и т.д. Через несколько итераций удавалось получить решения с 5-6 верными знаками.

В_прилоаении представлены описания и листинги программ, составленных по рассмотренным в диссертации алгоритмам:

- алгоритм для построения коалиции S;

- алгоритм северо-западного угла вычисления v(S) й тривиального распределения;

- алгоритм вычисления вектора Швпли;

- алгоритм выпуклого симплекс-метода;

- алгоритм случайного поиска.

Все программы написаны на языке модифицированный gwbasic для IBM PC, работают в диалоговом режима, объединены в общую систему и могут по начальным данным экономической модели рассчитать распределения и цены, дающие наилучшее приближение к вектору Шепли. Результаты расчетов продемонстрированы на модельных примерах.

ОПУБЛИКОВАННЫЕ РА60ТЫ по теме диссертации:

1. Кулаковская Т.Е., Аднан Шамон. О применении выпуклого симплекс-метода ь одной задаче ценообразования. Вестник СПЯТ. Cep.I, 1993. Вып.2. C.I2I-I23.

2.' Kulakovskaja Т.Е., Adnan Shamon. The game theoretioal model of ад еоопошу. Model Oriented Data Analyses III, Contributions to statistics, 1993. XIV, p.279-284, Phisioa Varlag.