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

• Мельник, Анна Владимировна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Мельник, Анна Владимировна

Оглавление

Введение

Глава 1. Дуополия Хотеллинга в метрике Манхеттена

1.1. Введение

1.2. Равновесие в модели Хотеллинга с расстоянием по Манхеттену. Дискретный случай

1.3. Модель Хотеллинга с расстоянием по Манхеттену. Непрерывный случай

1.4. Оптимальное расположение фирм, асимптотическое поведение

1.5. Равновесные цепы в дуополии на квадрате с евклидовой метрикой

1.6. Задача о размещении на квадрате

1.7. Выводы к первой главе

Глава 2. Дуополия в системе обслуживания с очередями

2.1. Постановка задачи

2.2. Теоретико-игровая модель ценообразования

2.3. Конкурентные потоки и общественный транспорт

2.4. Кооперативное поведение

2.5. Конкуренция п игроков

2.6. Выводы ко второй главе

Глава 3. Равновесие в транспортной системе М/М/т

3.1. Теоретико-игровая модель ценообразования в транспортной игре

3.2. Конкуренция игроков на сегменте

3.3. Затраты, в которых учитывается время нахождения в очереди

3.4. Конкуренция т игроков на сегменте

3.5. Конкуренция т игроков на линейном маршруте

3.6. Конкуренция игроков на графе Сз

3.7. Выводы к третьей главе

Глава 4. Равновесие в транспортной игре с BPR-задержками

4.1. Введение

4.2. Постановка задачи

4.3. Транспортная игра с линейной функцией задержки

4.4. Транспортная игра с квадратической функцией задержки

4.5. Транспортная игра с нелинейной функцией задержки

4.6. Транспортная игра на графе Эйлера

4.7. Выводы к четвертой главе

Заключение

Список литературы

Список иллюстративного материала

Список таблиц

Введение диссертации (часть автореферата) на тему «Равновесие в теоретико-игровых моделях массового обслуживания»

Введение

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

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

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

Классической моделью ценообразования является дуополия Курно, описанная в научной работе «Исследование математических принципов теории богатства» (1838), где идея заключается в том, что покупатели объявляют цены, а продавцы приспосабливают свой объем выпуска к данным ценам. Формально, схему можно описать следующим образом: на рынке конкурируют две фирмы, которые производят определенное количество однотипного товара q\ и ^ соответственно. Цена на товар на рынке складывается из начальной цены р, объявленной покупателем, минус общее количество произведенной продукции (5 = 91 + 32- Равновесие в такой игре находится решением оптимизационной задачи, а именно, когда каждая из фирм максимизирует свою функцию выигрыша, которая представляет собой произведение цены товара на его количество минус себестоимость произведенной продукции.

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

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

Еще одной классической моделью ценообразования является дуополия Хо-теллинга [1], которая, в отличие от моделей Курно и Бертрана, учитывает местоположение фирм на рынке. Рассмотрим линейный рынок, где конкурируют две фирмы, и предположим, что покупатели распределены равномерно на этом рынке. Каждая из фирм независимо задает цену на свой товар. После объявления цен на рынке происходит деление покупателей на два множества, тех, кто предпочитает воспользоваться услугами первой фирмы, и тех, кто предпочитает вторую. Причем сам покупатель является «рациональным» и руководствуется в своем выборе затратами, которые равны сумме цены на продукт и транспортных расходов. Выигрыши фирм в данной модели представляют собой доходы фирм, то есть цена на товар умноженная на количество людей, купивших его. Эта модель исследовалась во многих работах методами как некооперативной, так и кооперативной теории игр [2-5] при исследовании пространственной конкуренции.

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

расположение вблизи друг друга, для того, чтобы привлечь покупателей. Существует большое количество работ, посвященных задачам о размещении [6-9]. В работе [10] рассматривались квадратичные транспортные расходы. Было показано, что в такой модели, при расположении фирм в одной точке, как и в модели Бертрана, существует только тривиальное решение. В работе также были сформулированы условия, когда равновесие существует. Для исследования тех моделей, когда не для каждого местоположения игрока существует равновесие Нэша в игре ценообразования, в работе [11] предлагается использовать безопасные стратегии для поиска равновесия, что позволяет полностью решить игровую задачу. Использование равновесия в безопасных стратегиях обусловлено стремлением игроков к увеличению своего выигрыша, но при условии своей безопасности относительно действий других игроков [12, 13]. Также, задача о размещении анализировалась на линейном рынке в работе [14]. В модели [15] транспортные расходы потребителей представлены в виде показательной функции.

Хотеллинг рассмотрел модель дуополии только на линейном рынке, на плоскости и графе модель значительно усложнилась. Салоп [16] распространил модель ,,линейного"города Хотеллинга на плоскость, представив модель «кругового» города, в которой фирмы располагаются вдоль окружности на одинаковом расстоянии друг от друга. Фирмы могут входить в рынок последовательно, друг за другом.

Обзор моделей и методов, используемых в задачах размещения, можно найти в [17]. В статьях [18, 19] были исследованы проблемы оптимального расположения в условиях конкуренции на плоскости и на графе соответственно, причем рассматривалось не равновесие по Нэшу, а равновесие по Штакельбергу, где существует иерархия игроков. В работе [20] рассматривались квадратичные транспортные расходы и было показано, что равновесие в задаче размещения двух фирм в городе, который был представлен в виде круга на плоскости, существует. Исследовался случай равномерного расположения покупателей и нерав-

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

Эту же идею рационального поведения покупателей можно распространить на рынок потребительских перевозок, причем не только в конкуренции, но и в кооперации. Оптимизационным задачам управления транспортными потоками было посвящено большое количество работ [23-28]. Значительно меньшее внимание было уделено теоретико-игровым моделям управления транспортными потоками. В статье [29] исследуется конкуренция на рынке пассажиропере-возок, когда обслуживание пассажиров описывается дискретным Марковским процессом. Определен оптимальный график движения городского транспорта, который является равновесием по Нэшу в бескоалиционной игре на рынке пассажирских услуг. Теоретико-игровым задачам, определенных на процессах с очередями посвящены работы [30-33]. В работе [34] рассматривается модель, связанная с функционированием системы массового обслуживания с двумя параллельными сервисами М/М/2. Клиенты, прибывшие к обслуживающему сервису, сравнивали очереди в системе, и решали, следует ли им войти в систему. В другой модели, исследованной в статье [35], рассматривалась игра N лиц на сетях с разной топологией, в которых каждый игрок обслуживал заданный поток, направляя заявки из начального пункта до места назначения. В этой модели использовались полиномиальные функции затрат и было доказано, что равновесие по Нэшу единственно. В работе [36] рассмотрена модель ценообразования для двух игроков. В этой модели к каждому игроку образовывается очередь из клиентов, причем у различных потребителей различные временные затраты. Каждый клиент должен выбрать, каким сервисом воспользоваться. Равновесием в такой модели является специализация фирм, у одной - обслуживание потребителей с высокими временными затратами, а у другой - обслуживание

остальных.

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

3(А) = -Ц-,

с — А

где с - пропускная способность канала, Л - размер трафика. Такой вид задержки используется в системах массового обслуживания М/М/т. Другой популярный вид задержки - это ВРЯ-задержка, которая впервые была использована в департаменте транспорта США [37]. В работах [25, 30, 38, 39] рассматривались модели транспортных потоков с ВРИ-функцией задержки на ребрах графа. Эта задержка используется во многих практических задачах. Она имеет вид

5е(Ле) = и (1 + лф^ .

Здесь 5е(Ле) затраты на передвижение по ребру е и они зависят от потока на этом ребре Ае, удельных затрат на передвижение по пустому ребру ¿е, пропускной способности ребра <1е. Эти параметры определяют время перемещения по данному пути е, которое зависит от числа и ширины полос движения, качества дорожного покрытия, числа светофоров и, конечно, интенсивности трафика. Параметры функции задержки можно вычислить статистически [40]. Основным инструментом для нахождения решения является равновесие по Вардро-пу [41]. Идея равновесия по Вардропу состоит в том, что на дорогах, которые используется для трафика, задержки всех участников движения одинаковые. Такие игры, при соблюдении ряда условий, могут быть потенциальными [4]. В этом случае равновесие достигается как минимум потенциальной функции. В последнее время появилось много работ, сравнивающих централизованное управление трафиком и некооперативное, при котором каждый участник движения минимизирует свои затраты. Такое отношение затрат в равновесии и централизованном управлении получило название цена анархии [42-48].

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

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

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

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

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

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

Научная новизна. Научная новизна работы заключается в разработке новых теоретико-игровых моделей ценообразования и размещения для двух и более игроков.

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

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

В транспортной модели на графе найден аналитический вид равновесия в задаче ценообразования.

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

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

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

1. Найдено равновесие в задаче ценообразования и оптимальное расположе-

ние игроков в дуополии Хотеллинга с расстоянием по Манхеттену.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

го обслуживания М/М/2, в которой участвуют два конкурирующих сервера. Игроки, или транспортные компании, обслуживают пассажиров с экспоненциальным распределением времени обслуживания с параметрами и ¿¿2- Поток пассажиров образует пуассоновский процесс с интенсивностью Л. Игра происходит следующим образом: игроки назначают цены на проезд, и пассажиры выбирают сервис, которым им воспользоваться, сравнивая свои затраты от посещения каждого из них. Затраты складываются из назначенной компанией цены на проезд плюс потери от пребывания пассажиры в системе обслуживания. Далее, модель усовершенствована путем введения дополнительного игрока - общественного транспорта, у которого фиксирована цена на обслуживание и интенсивность обслуживания. Рассматривается задача ценообразования в условиях конкуренции и кооперации в данной усовершенствованной модели. Введен способ построения характеристической функции.

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

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

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

15

Глава 1

Дуополия Хотеллинга в метрике Манхеттена 1.1. Введение

Рассмотрим модель Хотеллинга на плоскости. Представим город, где располагаются две фирмы. Каждая из них задает свою цену на производимый товар, который один и тот же для обеих фирм. Пусть цены будут С\ и С2 соответственно. Город разбит на улицы, которые проходят параллельно осям хиу и формируют равномерную сетку. Покупатели в городе располагаются равномерно вдоль улиц и двигаются по ним, причем расстояние, пройденное покупателем из точки х = (¿i,ji) в точку у = (¿2, J2), определяется как расстояние Манхеттена.

Определение 1.1. Расстояние Манхеттена между двумя точками х = (i\,ji) и У — (¿2,32) определяется как сумма модулей разностей их координат, т. е.

р{х,у) = \гг -i2\ + \j1-j2l

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

#i(ci, с2) = cisi, Я2(сь са) = c2s2,

где si, S2 - это доли покупателей, которые предпочитают фирму I и фирму II соответственно. Заметим, что в рассматриваемой модели каждый потребитель

покупает только одну единицу товара, причем эта величина не изменится при увеличении цены на товар.

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

Г1 =< /,7/,С1,С2,Я1(с1,С2),Я2(С1,С2) >, которая происходит следующим образом:

1. Игроки одновременно и независимо друг от друга задают цену на производимый товар С\ и с2 соответственно.

2. Посетители выбирают фирму, посещение которой обойдется дешевле, и фирмы получает выигрыши N1(01,02), #2(01,02) соответственно.

После нахождения равновесных цен, перейдем к нахождению равновесия по Нэшу в игре размещения,

Г2 =< 1,11,{Х1,У1),(Х2,У2),Н1{Х1,У1,Х2,У2),Н2{Х1,УЪХ2,У2) >, проходящей в два шага:

1. Игроки одновременно и независимо друг от друга выбирают свое местоположение (Х1,ух) и {х2,У2)-

2. Посетители выбирают фирму, посещение которой обойдется ему наименьшими затратами, и фирмы получают выигрыши

Н\(С1(Х1,У1, Х2, У2), с2(х 1, у1, х2, у2), xi, Уъ х2, у2),

н2(С1 (^1, Ух, Х2, У2), С2{хг, У1, Х2, У2), XI, Уи Х2, У2) соответственно.

В этой игре необходимо найти такие точки {х\,у\) и (х^у^), используя найденные равновесные цены, что

Н1{с1{х1,у1,х*2,у1),с1{х1,уъх1,у1),хиуъх11у*2) < Н2(с\(х 1, у1, х2, у2), 4(хъ уЬ х2, У2),х*1, у1, х2, у2) <

тт / * / * * * *\ */ * * * *\ * * *

п2\р1\хъ у\->х2-> у2)1 с2\хъ у\1х21 у2)1 хъ у\чх21 у2)1

где с\(х\, ?/1, х2, у2) и ¿2(2:1,2/1,2:2,2/2) - это равновесие по Нэшу в задаче ценообразования, когда игроки располагаются в фиксированных точках {х\,у\) и (х2,у2)-

1.2. Равновесие в модели Хотеллинга с расстоянием по Манхеттену. Дискретный случай

Начнем с конкретной ситуации. Рассмотрим город, представленный в виде единичного квадрата, разбитый улицами, вдоль которых равномерно располагаются покупатели. Для начала, разобьем каждую сторону квадрата на п = 3 части. Предположим, что фирмы размещаются в точках (0, 1) и (1, 0), а дороги, как на рисунке 1.1. Пусть фирма II определила цену на товар с2 < тогда в нее пойдет больше покупателей, чем в фирму /, на рисунке это заштрихованная область. Для покупателей из точек где ¿ = 1,2,3, Ц = 0,1, 2,

затраты от посещения фирм I к II равны, причем I характеризует долю покупателей, предпочитающих ту фирму, которая назначила меньшую цену на товар, т. е. фирму II:

сг + 1 - I = с2 + 1 + г,

откуда

С1 - с2

Рис. 1.1. Дуополия в метрике Манхеттена, дискретный случай Функции выигрыша для игроков I и II имеют вид

Щсиъ) = |с1(4 + 6/) = |сх(4 + Зс2 - Зсх),

Н2{със2) = ^с2(8 -4 -61) = 4 - Зс2 + ЗС1),

Очевидно, что это вогнутые функции. Теперь можно найти равновесие по Нэшу из условий

^1 = 1(4-6С1 + ЗС2) = 0, дс2 8

г)М 1

^ = ^(4 + 3С1-6С2) = 0. дс\ 8

Отсюда следует, что с^ = с2 =

1.3. Модель Хотеллинга с расстоянием по Манхеттену. Непрерывный случай

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

в точках (2:1,2/1) = {ч/п, ¿\/п) и (2:2,2/2) = (¿2/п>.72/ть) соответственно, где 0 < Ч;,3к < п, к = 1,2. Без ограничения общности будем считать, что ¿1 < г2 и Л < 32-

Для заданных цен С1, с2 покупатели разобьются на два множества. Множество покупателей 51, предпочитающих фирму /, на рисунке 1.2 и 1.3 затемнено. Теорема 1.1. В игре Г1 =< I, II, с\, с2, Н\, Н2 > существует ситуация равновесия по Нэшу которая принимает следующие значения:

1. если 2/2 — 2/1 >2:2 — 2:1, то равновесие имеет вид

С1 = + 2/1 + 2/2 + XI - х2 + х\ - х\), с2 = ^(4- (2/1 + 2/2 + XI - х2 + 2:2 - ж?)) ,

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

Список литературы диссертационного исследования кандидат наук Мельник, Анна Владимировна, 2014 год

Список литературы

1. Hotelling Н. Stability in competition // The Economic Journal. 1929. Vol. 39. P. 41-57.

2. Петросян Л. А., Зенкевич H. А., Семина E. А. Теория игр: Учеб. пособие для ун-тов. Москва: Книжный дом "Университет 1998.

3. Мулен Э. Теория игр с примерами из математической экономики. Москва: Мир, 1985.

4. Мазалов В. В. Математическая теория игр и приложения. Санкт-Петербург: Лань, 2010.

5. Васин А. А., Морозов В. В. Теория игр и модели математический экономики. Москва: МАКС Пресс, 2005.

6. Sakaguchi М. Pure Strategy Equilibrium In a Location Game with Discriminatory Pricing // Game Theory and Applications. 2001. Vol. 6. P. 132-140.

7. Osborne M. J., Pitchik C. Equilibrium in Hotelling's Model of Spatial Competition // Econometrica. 1987. Vol. 53, no. 1. P. 1-26.

8. Ahn H. K., Cheng S. W., Cheong O. et al. Competitive facility location: The Voronoi game // Theoretical Computer Science. 2004. Vol. 310. P. 457-467.

9. Serra. D. Location Theory: A Unified Approach, by Stefan Nickel and Justo Puerto // Journal of Regional Science. 2007. Vol. 47. P. 3p.

10. D'Aspremontand C., Gabszewicz J. J., , Thisse J. F. On Hotelling\ Os Stability in Competition // Econometrica. 1979. Vol. 47. P. 1145-1150.

11. Искаков M. В., Павлов П. А. Равновесие в безопасных стратегиях в модели пространственной конкуренции Хотеллинга // Математическая теория игр и ее приложения. 2009. Т. 1, № 2. С. 38-65.

12. Искаков М. Б. Равновесие в безопасных стратегиях // Автоматика и телемеханика. 2005. № 3. С. 139-153.

13. Искаков М. Б. Равновесие в безопасных стратегиях и равновесия в угрозах и контругрозах в некооперативных играх // Автоматика и телемеханика.

2008. № 2. С. 114-134.

14. Kats A. More on Hotelling's stability in competition. 1995. Vol. 13. P. 89-93.

15. Economides N. Minimal and Maximal Product Differentiation In Hotelling's Duopoly // Economic Letters. 1986. Vol. 21. P. 67-71.

16. Salop S. C. Monopolistic Competition with Outside Goods // The Bell Journal of Economics. 1979. Vol. 10. P. 141-156.

17. Nickel S., Puerto J. Location Theory: A Unified Approach. Springer-Verlag, 2005.

18. Drezner Z. Competitive location strategies for two facilities. 1982. Vol. 12. P. 485-493.

19. Hakimi S. On locating new facilities in a competitive environment. 1983. Vol. 12. P. 29-35.

20. Mazalov V. V., Sakaguchi M. Location Game on the Plane // International Game Theory Review. 2003. Vol. 5, no. 1. P. 13-25.

21. Мазал OB В. В., Щипцова А. В., Токарева Ю. С. Дуополия Хотеллинга и задача о размещении на плоскости // Экономика и математические методы. 2010. Т. 46, № 4. С. 91-100.

22. Tabuchi Т. Multiproduct Firms in Hotelling's Spatial Competition // Journal of Economics and Management Strategy. 2012. Vol. 21. P. 445-467.

23. Швецов В. И. Математическое моделирование транспортных потоков // Автоматика и телемеханика. 2003. № 11. С. 3-46.

24. Афраймович JI. Г. Многоиндексные транспортные задачи с декомпозиционной структурой // Автоматика и телемеханика. 2013. № 1. С. 13-147.

25. Нурминский Е. А., Шамрай Н. Б. Прогнозное моделирование автомобильного трафика Владивостока // Труды МФТИ. 2010. Т. 2, № 4. С. 119-129.

26. Под ред. Гасникова А.В. Введение в математическое моделирование транспортных потоков. Москва: МЦНМО, 2013.

27. Skutella М. An introduction to network flows over time. 2009. P. 451-482.

28. Martens M., Skutella M. Flows on few paths: algorithms and lower bounds //

Networks. 2006. Vol. 48, no. 2. P. 68-76.

29. Корягин M. E. Конкуренция транспортных потоков // Автоматика и телемеханика. 2006. № 3. С. 143-151.

30. Altman Е., Basar Т., Jimenez Т., Shimkin N. Competitive routing in networks with polynomial costs // IEEE Transactions on Automatic Control. 2002. Vol. 47, no. 1. P. 92-96.

31. Hassin R., Haviv M. To Queue or Not to Queue Equilibrium Behavior in Queue-ing Systems. Springer, 2003.

32. Luski I. On partial equilibrium in a queueing system with two services // The Review of Economic Studies. 1976. Vol. 43, no. 3. P. 519-525.

33. Sridhar M. S. Waiting lines and customer satisfaction // SRELS journal of information management. 2001. Vol. 38. P. 99-112.

34. Altman E., Shimkin N. Individual Equilibrium and Learning in Processor Sharing Systems. 1998. Vol. 46. P. 776-784.

35. Altman E., Wynther L. Equilibrium, Games, and Pricing in Transportation and Telecommunication Networks // Networks and Spatial Economics. 2004. Vol. 4. P. 7-21.

36. Levhari D., Luski I. Duopoly pricing and waiting lines // European Economic Review. 1978. no. 11. P. 17-35.

37. U.S. Bureau of Public Roads. Traffic Assignment Manual. U.S. Department of Commerce, Washington, D.C.„ 1964.

38. Захаров В. В., Щегряев А. Н. Устойчивая кооперация в динамических задача маршрутизации транспорта // Математическая теория игр и ее приложения. 2012. Т. 4, № 2. С. 39-56.

39. Захаров В. В., Крылатов А. Ю. Системное равновесие транспортных потоков в мегаполисе и стратегии навигаторов: теоретико-игровой подход // Математическая теория игр и ее приложения. 2012. Т. 4, № 4. С. 23-44.

40. Буре В. М., Мазалов В. В., Плаксина Н. В. Вычисление характеристик пассажиропотоков в транспортных системах // Управление большими си-

стемами. ИПУ РАН. 2014. Т. 47. С. 77-91.

41. Wardrop J. G. Some theoretical aspects of road traffic research // ICE Proceedings: Engineering Divisions. 1952. Vol. 1. P. 325-362.

42. Papadimitriou C., Koutsoupias E. Worst-Case Equilibria // Lecture Notes in Computer Science. 1999. T. 1563. C. 404-413.

43. Gairing M., Monien В., Tiemann K. Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions // Proc. of 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006,. 2006. P. 501-512.

44. Papadimitriou C., Roughgarden T. Computing equilibria in multi-player games // ... of the sixteenth annual ACM-SIAM .... 2005. P. 82-91.

45. Koutsoupias E., Papadimitriou C. Worst-case equilibria // Computer Science Review. 2009. Vol. 3. P. 65-69.

46. Bennett L. D. The existence of equivalent mathematical programs for certain mixed equilibrium traffic assignment problems // Euro. J. Operat. Res. 1993. Vol. 71. P. 177-187.

47. Christodoulou G., Koutsoupias E. The price of anarchy of finite congestion games // Proceedings of the thirtyseventh annual ACM symposium on Theory of computing STOC 05. 2005. P. 67.

48. Christodoulou G., Koutsoupias E. On the price of anarchy and stability of correlated equilibria of linear congestion games // Lecture notes in computer science. 2005.

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

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

51. Мельник А. В. Равновесие в транспортной игре // Математическая теория

игр и ее приложения. 2014. Т. 6, № 1. С. 41-55. 52. Taxa X. А. Введение в исследование операций. Москва, Санкт-Петербург, Киев: Издательский дом "Вильяме 2005.

Список иллюстративного материала

1.1 Дуополия в метрике Манхеттена, дискретный случай..............18

1.2 Дуополия в метрике Манхеттена, симметричный случай ..........20

1.3 Дуополия в метрике Манхеттена, несимметричный случай .... 21

1.4 Дуополия в евклидовой метрике......................................26

1.5 График зависимости к от 7............................................32

3.1 Конкуренция игроков на сегменте....................................51

3.2 Конкуренция игроков на линейном маршруте........................56

3.3 Конкуренция игроков на графе ....................................65

4.1 Два параллельных маршрута..........................................72

4.2 Три параллельных маршрута..........................................74

4.3 т параллельных маршрутов..........................................77

4.4 Граф Эйлера............................................................95

111

Список таблиц

2.1 Значение [с{,с1) при А=10..............................................38

2.2 Значение (с1,с2) при А=10, со=1, /ло=3................................41

2.3 Значение ^(0),г;(1), -г;(2),^(12) при А=10, с0=1, /¿0=3................42

2.4 Значения у(3) при А=10, со=1, /¿о=3..................................45

3.1 Значение (с^, при Ах2 = 2, А13 = 3, Ах4 = 4 ....................63

3.2 Значение (с^, с^) при Ах2 = 2, А13 = 3, Хи = 4 ....................63

3.3 Значение (с^, с^) при А12 = 2, А13 = 3, А14 = 4 ....................64

3.4 Значение равновесных цен при А12 = 2, А13 = 3, А14 = 3, А15 = 4,

/¿2 = 9....................................................................67

4.1 Значение (с^Сз) при А=1, = с12 = 2, (3 = 1........................73

4.2 Значение (с^, с2, С3) при А=10, — 1, (1\ = с12 = с£3 = 2, /3 = 1 . . . 76

4.3 Значение с* г = 1,2,..., 10 при А=100, и = г, г = 1,2,..., 10, >0 = 1. 79

4.4 Значение А,- г = 1,2, ...ДО при А=100, и = г, г = 1,2, ...ДО, ¡3 = 1 . 79

4.5 Значение (с?, с2) при А=10, ¿1 = о?2 = 2, /3 = 2 ......................82

4.6 Значение (с^, с2, с*3) при А=10, ¿1 = 1, ^ = с/2 = ¿з = 2, /? = 2 . . . 84

4.7 Значение с* г = 1, 2,..., 10 при А=100, и = г, г = 1,2,..., 10, /3 = 2 . 86

4.8 Значение А» г = 1, 2,..., 10 при А=1, и = г, г = 1,2,..., 10, >3 = 2.. 86

4.9 Значение {с\,с*2) при А=10, ¿1 = = 2, Р = 3 ......................88

4.10 Значение (с^, с^, при А=10, Ь = 1, ^ = й2 = = 2, р = 3 . . . 90

4.11 Значение а г = 1,2,..., 10 при А=100, и = г, г = 1,2,..., 10, р = 3 . 92

4.12 Значение А; г = 1,2,..., 10 при А=1, и = г, г = 1,2,..., 10, р = 3 . . 92

4.13 Значение с*2) при А=10, <¿1 = й2 = 2, Р = 4 ......................93

4.14 Значение (с^, с2, при А=10, ¿1 = 1, = <12 = ¿3 = 2, р = 4 . . . 93

4.15 Значение а г = 1,2,..., 10 при А=100, и = г, г = 1,2,..., 10, /3 = 4 . 94

4.16 Значение А; % = 1,2,..., 10 при А=100, и = г, г = 1,2,..., 10, Р = 4 . 94

4.17 Значение с* г = 1,2,..., 10 при А=100, ^ = г, г = 1,2,..., 10, /5 = 4. 95

4.18 Значение А» г = 1,2,..., 10 при A=l, dt = i, % = 1,2,..., 10, ß = 4 . . 95

4.19 Значение (с^,^) в транспортной игре на графе Эйлера..... 99

4.20 Значение (cjg , с^) в транспортной игре на графе Эйлера.....100