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

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

7

Мельник Анна Владимировна

Равновесие в теоретико-игровых моделях массового обслуживания

01.01.09 - Дискретная математика и математическая кибернетика

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

005552580

1 & СЕН 2014

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

005552580

Работа выполнена в Санкт-Петербургском государственном университете.

доктор физико-математических наук, профессор,

Петросян Леон Аганесович Крепе Виктория Леонидовна, доктор физико-математических наук, Лаборатория теории игр и принятия решений СПбЭМИ РАН, ведущий научный сотрудник Ивашко Анна Антоновна, кандидат физико-математических наук, Лаборатория математической кибернетики Института прикладных математических исследований КарНЦ РАН, научный сотрудник

Ведущая организация: Институт проблем управления им. В. А. Тра-

пезникова РАН

Защита состоится "22"октября 2014 г. в 18 часов на заседании диссертационного совета Д 212.232.29 на базе Санкт-Петербургского государственного университета по адресу: 199178, Санкт-Петербург, 10 линия В.О., д.33/35, ауд. 74.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9 и на сайте

http : //spbu.ru/science/disser/dissertatsii — dopushchennye — к — zashchite — i — svedeniya — о — zashchite.

Автореферат разослан «_»_2014 г.

Научный руководитель:

Официальные оппоненты:

Ученый секретарь

диссертационного совета Нежинский В. М.

Общая характеристика работы

Актуальность темы исследования. Модели принятия решений занимают важное место в экономической науке. К ним относятся математические модели ценообразования, среди которых центральное место занимает дуополия Хотеллинга (Hotelling, 1929), которая учитывает местоположение фирм на рынке. В этой модели рассматривается линейный рынок, где конкурируют две фирмы, и плотность распределения покупателей на этом рынке равномерная. Каждая из фирм независимо задает цену на свой товар. После объявления цен на рынке происходит деление покупателей на два множества: тех, кто предпочитает воспользоваться услугами первой фирмы, и тех, кто предпочитает вторую фирму. Причем сам покупатель является «рациональным» и руководствуется в своем выборе затратами, которые состоят из цены на продукт и транспортных расходов. Выигрыши фирм в данной модели представляют собой доходы фирм, то есть цену на товар, умноженную на количество людей, купивших его.

В модели Хотеллинга основной проблемой является нахождение равновесных цен. Однако важной является и сама задача оптимального расположения фирм на рынке. Эта модель исследовалась затем во многих работах методами как некооперативной, так и кооперативной теории игр при исследовании пространственной конкуренции. Д'Аспремонт с соавторами в своей работе (С. D'Aspremont, J. J. Gabszewicz, J. F. Thisse, 1979) исследовал эту задачу в случае квадратичных транспортных расходов.

Хотеллинг рассмотрел модель дуополии только на линейном рынке, на плоскости и графе модель значительно усложнилась. Салоп (S. С. Salop, 1979) распространил модель "линейного"города Хотеллинга на плоскость, представив модель «кругового» города, в которой фирмы располагаются вдоль окружности на одинаковом расстоянии друг от друга. Фирмы могут входить в рынок последовательно, друг за другом. В статьях (Z. Drezner, 1982), (S. L. Hakimi, 1983) были исследованы проблемы оптимального расположения в условиях кон-

куренции на плоскости и на графе.

Эту же идею рационального поведения покупателей можно распространить на рынок пассажирских перевозок. В таких задачах поведение пассажиров влияет на интенсивности движения пассажирского транспорта. Хотя проблема математического моделирования транспортных потоков достаточно хорошо изучена (Е. А. Нурминский, Н. Б. Шамрай, 2010), (В. И. Швецов, 2003), конкурентным потокам посвящено небольшое количество работ. В работе (Е. АНтап, N. ЗЫткт, 1998) модель, связанная с функционированием системы массового обслуживания с двумя параллельными сервисами М/М/2, иллюстрирует формирование очередей у двух бензозаправочных станций, находящихся на одной трассе. Клиенты, прибывшие к обслуживающему сервису, сравнивали очереди в системе, и решали, следует ли им остановиться у одной из станций или проследовать к другой. В другой модели, исследованной в статье (Е. АЬтап, Ь. ^УупШег, 2004), рассматривалась игра N лиц на сетях с разной топологией, в которых каждый игрок обслуживал заданный поток, направляя заявки из начального пункта до места назначения. В этой модели использовались полиномиальные функции затрат и было доказано, что равновесие по Нэшу единственно. В статье (М. Е. Корягин, 2006) исследуется конкуренция на рынке пасеажиропере-возок, где распределение пассажиров по фирмам обслуживания определяется с помощью логит-анализа. Определен оптимальный график движения городского транспорта, который является равновесием по Нэшу в бескоалиционной игре на рынке пассажирских услуг.

Для моделирования дорожного трафика должны быть определены функции задержки на пути. Вид функции задержки может быть различным. Если рассматриваются транспортные системы с заторами, то задержка может иметь вид

где с - пропускная способность канала, А - размер трафика. Такой вид задерж-

ки используется в системах массового обслуживания М/М/1. Другой популярный вид задержки - это В PR-задержка, которая впервые была использована в департаменте транспорта США (U.S. Bureau of Public Roads. Traffic Assignment Manual, 1964). Эта задержка используется во многих практических задачах. Она имеет вид

Здесь 5е(Ле) - затраты на передвижение по ребру е и они зависят от потока на этом ребре Ае, удельных затрат на передвижение по пустому ребру пропускной способности ребра с1е. Эти параметры определяют время перемещения по данному пути е, которое зависит от числа и ширины полос движения, качества дорожного покрытия, числа светофоров и, конечно, интенсивности трафика. Основным инструментом для нахождения решения является равновесие по Вардропу (\Vardrop, 1952). Идея равновесия по Вардропу состоит в том, что на дорогах, которые используются для трафика, задержки всех участников движения одинаковые. В данной работе, идея равновесия по Вардропу распространяется на случай, когда в затраты включены не только задержка на дороге, но и цены на сервис. В транспортных моделях, как и в модели Хотеллинга, затраты пассажиров можно представить как цену на билет плюс ожидаемое время обслуживания. Тогда поток пассажиров, который предполагается пуассоновским, будет разбиваться на подпотоки пассажиров, которые будут использовать различные сервисы. Данную модель можно представить, как конкуренцию между транспортными компаниями, стратегиями которых является назначение определенной цены на билет на всех отрезках их маршрутов. В этом случае, нахождение равновесия может дать рекомендации управлению транспортными перевозками: каким образом вводить маршруты в городе, какой из транспортных компаний предоставить преимущество (например, муниципальный транспорт), а самим компаниям определить оптимальное количество транспортных средств на маршруте и цены на билет.

Цели и задачи диссертационной работы. Целью диссертационной работы является построение и исследование математических моделей массового обслуживания, относящихся к задачам ценообразования и размещения для двух и более лиц в условиях конкуренции и кооперации методами теории игр. Для достижения поставленных целей были решены следующие задачи:

1. Задача ценообразования и задача о размещении в дуополии Хотеллинга на плоскости, когда расстояние представлено в метрике Манхеттена, и сделано сравнение с оптимальным решением задачи в евклидовой метрике;

2. Задача ценообразования и определение оптимальной интенсивности в игре, связанной с транспортной системой М/М/тп на линейном сегменте;

3. Задача нахождения равновесия в транспортной системе, включающей в себя муниципальный транспорт (в условиях конкуренции и кооперации);

4. Задача нахождения равновесия в транспортной игре на графе, с различными типами задержек.

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

Методология и методы исследования. В диссертации применяются методы теории массового обслуживания, некооперативной и кооперативной теории игр, линейной алгебры.

Положения, выносимые на защиту:

1. Найдено равновесие в задаче ценообразования и оптимальное расположение игроков в дуополии Хотеллинга с расстоянием по Манхеттену.

2. Предложена теоретико-игровая модель ценообразования в транспортной игре, в которой потоки пассажиров образуют пуассоновский процесс.

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

4. Найдено равновесие в теоретико-игровой модели управления пассажиропотоками для различных видов транспортных сетей и различных типов задержки.

Степень достоверности и апробация результатов. Основные результаты диссертации докладывались на следующих конференциях:

1. Конференция "Процессы управления и устойчивость"(2009, 2010, 2011), Санкт-Петербург,

2. Международный семинар "Scientific Publishing" (2011), Хельсинки - Санкт-Петербург,

3. Международный семинар "Networking Games and Management"(2012), Петрозаводск,

4. Международный семинар "4th Nordic Triangular Seminar in Applied Stochas-tics"(2013), Хельсинки,

5. Международная конференция "SING9"(2013), Виго.

Публикации. Материалы диссертации опубликованы в 8 печатных работах, из них 3 статьи в рецензируемых журналах [1-3], 5 статей в сборниках трудов конференций [4-8].

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Все представленные в диссертации результаты получены лично автором.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и библиографии. Общий объем диссертации 112 страниц, из них 104 страницы текста, включая 12 рисунков. Библиография включает 52 наименования на 5 страницах.

Содержание работы

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

В первой главе рассматривается задача ценообразования и размещения в модели дуополии Хотеллинга на плоскости, когда в затратах покупателей расстояние представлено в метрике Манхеттена.

Представим город, где располагаются две фирмы. Каждая из них задает свою цену на производимый товар, который один и тот же для обеих фирм. Пусть цены будут с\ и с2 соответственно. Город разбит на улицы, которые проходят параллельно осям х и у и формируют равномерную сетку. Покупатели в городе располагаются равномерно вдоль улиц и двигаются по ним, причем расстояние р(х,у), пройденное покупателем из точки х = (¿1, Ji) в точку у = («2,^2), определяется как расстояние Манхеттена, т.е. р(х,у) = |ij — ¿2) + \j\ — j21.

Каждый покупатель сравнивает затраты от посещения каждой из фирм, причем затраты складываются из цены на товар плюс транспортные расходы, т. е. Li = Ci + р(х,у), г = 1, 2, и выбирает фирму, посещение которой ему обойдется дешевле. Под функцией выигрыша игрока будем понимать произведение

цены товара на долю покупателей, выбравших данную фирму, т. е.

Н^а) = с1в1, Н2(сис2) = с252,

где в1, й2 - это доли покупателей, которые предпочитают фирму / и фирму II соответственно.

Очевидно, что цены зависят от расположения фирм на рынке. Поэтому сначала находится равновесие по Нэшу в игре ценообразования, а после находится равновесие по Нэшу в игре размещения. Таким образом, необходимо найти такие точки (х^Ух) и (х'2, у'2), используя найденные равновесные цены, что

Нх{с{{х1, у и х2, у2), с%(х1, у и х2, у2), хи уи х*2, у*2) < Н\(с*!(х!, у{, Х2, У2), С2(х{, у?, х'2, у2), , у\, Х2, у2), Н2{с\{х1,у1,х2,у2),с^{х\,у{,х2,у2),х*иу1,х2,у2) < Н2{С\{Х\,У1,Х1,у'2),С1{Х\,У\^У1),Х1У\,Х1,У*2), где с\{хъуъх2,у2) и с%(хиуих2,у2) - это равновесие по Нэшу в задаче ценообразования, когда игроки располагаются в фиксированных точках (хх, ух) и (х2,У2).

В пункте 1.3 рассматривается общий случай, когда город разбит равномерной сеткой улиц на п2 частей. Фирмы располагаются в точках (хх,ух) = (ч/п,31/п) и {х2,у2) = (г2/п,^2/п) соответственно, где 0 < %к,3к <п,к = 1,2 (¿1 < Ч и il < з2).

Теорема 1. В игре Гх =< II, с\, с2, Нъ Н2 > существует ситуация равновесия по Нэшу {с\,с*2), которая принимает следующие значения:

1. если у2 — У\ > х2 — х\, то равновесие имеет вид

с{ = ^(2 + ух + у2 + X! - х2 + х\ - х\), = ^ (4 - (У! + у2 + Хх - х2 + х\ - х\)) ,

2. если у2 < Х2 — Х\, то цены в равновесии составят величину

с{ = + XI + х2 4- ух - у2 + у\ - у\),

<4 = £ (4 - (^1 + + 2/1 - У2 + у1 ~ у\)) ,

3. если г/2 — 2/1 = — XI, то цены в равновесии равны

с{ = |(2 + 2/1 + (XI + 2/г)2), 3 = |(4 - у\ ~ (XI + 2/г)2),

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

Н1{х1,у1;х2,у2) = Н1(х1,у1;х2,у2) - +2/1)2, (1)

А /V

Я2(х1,2/1;х2,2/2) = Я2(х1,2/1;х2,2/2) - — атг - г/2)2, (2)

т. е. для фирмы 7 невыгодно отклоняться от точки (0,0), а для фирмы II - от точки (1,1), 7 - некоторый параметр.

Теорема 2. В игре размещения Г2 =< I, II, (^1,У1)ЛХ2,У2), Н1(хиуих2,у2),

#2(х1,2/1,Х2,2/2) >' е когпоР°й х2 = у2 = к > 1/2, = уг = 6 < 1/2 и

функции выигрыша имеют вид (1)-(2) существует ситуация равновесия по

Нэшу ((*!, у{), Уг)) = ((1 - к, 1 - к), (к, к)), где

/;г_27 + 3 27 + 6'

Для сравнения полученных результатов было найдено равновесие в задаче ценообразования и размещения на плоскости для случая, когда затраты потребителей представлены в евклидовой метрике. Сравнивая значения для одинаковых параметров, показано, что в модели размещения с расстоянием по Ман-хеттену фирмам выгодно располагаться примерно в два раза ближе к предпочтительным точкам, чем в модели с евклидовой метрикой.

Результаты второй главы опубликованы в работе [1]

Во второй главе модель дуополии Хотеллинга распространяется на рынок пассажирских перевозок. Вначале, находится равновесие в задаче ценообразования, связанной с функционированием транспортной системы с участием двух компаний. Транспортная система представляет собой систему массового обслуживания М/М/2, в которой участвуют два конкурирующих сервера. Пусть игроки I и II обслуживают входящий поток, который представлен пуас-соновским процессом с параметром Л, и при этом их время обслуживания имеет экспоненциальный вид с интенсивностями щ и /х2. Игроки назначают соответственно цены на свои услуги сг и с2. Тогда пассажиры будут выбирать сервис с меньшими затратами, и входящий поток разобьется на два пуассоновских под-потока с интенсивностями А1 и Л2, где Ах+Аг = А. При этом затраты посетителя, воспользовавшегося г-м сервисом, будут равны

здесь 1 /{рц - А^ - ожидаемое время пребывания пользователя в системе обслуживания. Тогда выигрыши игроков можно записать как доход от обслуживания данного потока в единицу времени, который будет пропорционален назначенной цене на обслуживание.

Нх(с1,с2) = \\Си Я2(сьс2) = А2с2.

В случае, когда два сервиса одинаковы, т. е. ¡Х\ = = А4, доказано следующее утверждение

Теорема 3. В игре Г =< II, сь с2, Я^сь с2), Я2(сь с2) > существует ситуация равновесия по Нэшу (с^), которая имеет вид

_ с. - Л

С1

Для несимметричного случая ^ ф доказано утверждение

Теорема 4. В игре Г =< /, II, сь с2, #1(сь с2), Я2(сь с2) > существует ситуация равновесия по Нэшу (с1,с2), которая находится из системы

» . _ 1 _1

С^ С2 — ---— 1. —.

Далее в модель введен дополнительный игрок - муниципальный транспорт, который отличается от остальных тем, что у него фиксирована плата за проезд, и фиксированное количество транспортных единиц, которые он использует. Найдено равновесие в задаче ценообразования в случае п игроков в условии конкуренции и кооперации. В кооперативной постановке задачи характеристическая функция определяется специальным образом. В случае образования коалиции, игроки из коалиции 5 играют как один игрок, а игроки, не входящие в эту коалицию находятся в равновесии с ней, т. е. в качестве стратегий используются равновесные цены. Эти цены являются равновесием по Нэшу в игре п — в + 1 лиц и значение характеристической функции есть выигрыш рассматриваемого игрока или коалиции в ситуации равновесия по Нэшу. Решение кооперативной игры представлено вектором Шепли.

Результаты второй главы опубликованы в работе [2].

В третьей главе предложена общая постановки транспортной игры, когда поток пассажиров образует пуассоновский процесс. Каждый игрок - транспортная компания имеет ряд маршрутов, которые она обслуживает. На каждом маршруте компания задает цену на проезд, и пассажиры выбирают услугу игрока с наименьшими затратами, которые складываются из цены на билет плюс ожидаемое время пребывания пользователя в системе обслуживания. Рассмотрена модель пассажироперевозок, в которой исследуется конкуренция т игроков на графе. Пусть Г =< И, С?, > - транспортная игра, в которой N = {1,...,т}-множество игроков (транспортные компании), обслуживающие пассажиров на графе С =< V, Е >, где V - множество вершин и Е - множе-

ство ребер. Будем считать, что все вершины пронумерованы, V = {иь..., г/п}. Для каждого игрока i существует набор маршрутов Zi из вершины ув 6 V в ц, £ У, которые обслуживает игрок г. Таким образом, Z^ = (Л'цЩ,..., Д^.), г = 1,.., т. Каждый маршрут представляет собой путь, т. е. последовательность вершин, соединенных ребрами Я = (г)5,г)3+ь ...,и(), в которой конец одного ребра является началом другого ребра, т.е. (у3, € Е. Маршруты будем обозначать большими буквами И, а подпути обозначим малыми буквами г. Чтобы подчеркнуть, что начало пути есть у„, а конец есть г>(, будем обозначать такой путь или г8(. Будем говорить, что путь гу(< является подпутем пути т\,4 и писать г3>г С г^, если путь ту^ является подпоследовательностью вершин, содержащихся в г.5(.

Обслуживание пассажиров игроком i имеет экспоненциальное распределение времени обслуживания с параметром на каждом маршруте Д £ Введем в рассмотрение матрицу интенсивностей {Л5(} потоков из точки г;., в точку Уь для различных в, £ = 1,..., п

Л :

О Л12 Л21 О

Ап1 А„2

А^

Аг п

7

Игрок г назначает цены на свои услуги с?, с\ на каждом маршруте Де^и

всех его подпутях г С Д. Формируется профиль стратегий {с^} = {с-}, г сДе

= 1,..., 771. Предположим, что пассажиры минимизируют свои затраты,

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

время обслуживания, и выбирают сервис, который дешевле остальных.

Тогда входящий поток Л5( разбивается на пуассоновские подпотоки с инт

тенсивностями А*4, где А'( = Хзи причем, если ни в одном из маршрутов 1=1

множества игрока г нет подпути то А'5(=0.

Затраты пассажира, воспользовавшегося г-м сервисом по подпути г какого-

то маршрута Я 6 будут равны .

< + Е „Д _ V л< . 1 = 1,2,...,п.

гц'.еегцСг

Таким образом, в равновесии затраты всех пассажиров на конкурентных направлениях будут совпадать для всех сервисов. Отсюда можно найти интенсивности А*( для всех сервисов г = 1, ...,т и подпутей г,г. А именно,

V л-.

1

- »Я _ у^ д> ^^ ¿^ Л' _ у >

г^ебг^сгся Г.,:Г„СГСЛ'

для всех 1,3 таких, что г С Д € ^ и г С К' € Выигрыш игрока г можно записать как доход в единицу времени от обслуживания всех потоков на всех маршрутах игрока, т.е.

Я4({с?*},-6*) = £ АХ.

r,l:г,tCгcЯeZi

Предложенная транспортная игра рассматривается на графах различной топологии. Найдено равновесие в такой игре для линейных маршрутов. Результаты третьей главы опубликованы в работе [3]. В четвертой главе исследуются теоретико-игровые модели транспортных перевозок с ДРЯ-функциями затрат для пассажиров. Рассмотрена конкуренция 771 транспортных компаний на тп параллельных маршрутах. Каждая компания обслуживает пассажиров на своем маршруте, назначая цену на обслуживание с*, г = 1, ...,771 соответственно. Поток пассажиров А разбивается на

т

тп потоков А;, ^ А,- = А, в соответствии с балансовыми уравнениями

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

Н{ = с*А;, г = 1, 2,..., 771.

Данная схема моделируется при различных параметрах модели, в том числе степени /3. В линейном случае, когда 0 = 1 сформулировано условие, при котором транспортные компании будут конкурентоспособны. Теорема 5. Если выполнено условие

тп-1

¿т

^=1

то равновесные цены имеют вид

I

-х и I 1

С\ — А; , -г т

«I а

\ ^ /

т . » Л- Е ^

(т

Е ¿г

i = 1, ...,т,

г = 1,..., т,

где

л + ь> = ~У~ +

Яг

1

Е £

-, г = 1,...,77г.

Применение предложенных методов продемонстрировано на графе Эйлера, который соответствует знаменитой задаче Эйлера о кёнигсбергских мостах.

В Заключении представлены выводы, полученные в ходе исследования всех рассмотренных моделей.

Список публикаций

1. Мазалова А. В. Дуополия в системе обслуживания с очередями // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2013. Т. 4. С. 32-41.

2. Мазалова А. В. Дуополия Хотеллинга на плоскости в метрике Манхеттена // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2012. Т. 2. С. 33-43.

3. Мельник А. В. Равновесие в транспортной игре // Математическая теория игр и ее приложения. 2014. Т. 6, JY* 1. С. 41-55.

4. Мазалова А. В. Дуополия Хотеллинга на окружности // Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. 2009. С. 643-646.

5. Мазалова А. В. Равновесие в модели Хотеллинга с расстоянием по Манхег-тену // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. 2010. С. 666-670.

6. Мазалова А. В. Парадокс Браесса // Процессы управления и устойчивость: Труды 42 -й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова. 2011. С. 519-521.

7. Mazalova А. V. Pricing and Transportation Costs in Queucing System // Contributions to Game Theory and Management. 2013. V. 6. P. 301-306

8. Melnik A. V. Pricing in Queueing Systems M/M/m with delays // Contributions to Game Theory and Management. 2014. V. 7. P. 214-220.

Подписано к печати 30.06.14. Формат60 x 84 'Л б. Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. _Тираж 100 экз. Заказ 6046.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919