Диссертация (1150526), страница 7
Текст из файла (страница 7)
Результаты приведены в таблице 2.3. В ней v(i) = Hi (c∗1 , c∗2 ) = λi c∗i , i = 0, 1, 2; c∗1 , c∗2– решение системы (2.18) и кооперативный выигрыш v(12) = H12 (c∗12 ) = λ12 c∗12 ,где c∗12 – решение системы (2.20), (2.21).Из табл. 2.3 видно, что v супераддитивная. Воспользуемся вектором Шепли, чтобы разделить выигрыш. При параметрах µ12 = 19 или µ1 = 10, а µ2 = 9получим11ϕ1 (v) = v(1) + (v(12) − v(2)) = 1.24,2211ϕ2 (v) = v(2) + (v(12) − v(1)) = 1.18.22Таким образом, игрокам I и II выгодно сформировать коалицию, при этомкооперативный выигрыш им следует разделить в данной пропорции.2.5. Конкуренция n игроковРассмотренную в п.
5 модель конкуренции двух серверов можно распространить на случай n игроков. Представим, что есть n конкурентных серверов,44которые обслуживают заявки с экспоненциальным распределением времени соответственно с параметрами µ1 , µ2 , ..., µn . Игроки назначают цены на своиуслуги c1 , c2 , ..., cn . Тогда посетители будут выбирать сервис с меньшими затратами и входящий поток разобьется на n пуассоновских потока с интенсивностями λ1 , λ2 ,..., λn , где λ1 + λ2 + .. + λn = λ. При этом затраты посетителя,воспользовавшегося i-м сервисом, будут равныci +1,µi − λii = 1, 2, ..., n.Тогда интенсивности потоков λ1 , λ2 , ..., λn для соответствующих сервисов можно найти из условияc1 +111= c2 += ...
= cn +.µ1 − λ1µ2 − λ2µn − λnКак и раньше, введем в рассмотрение особого игрока, который интерпретируется в модели как общественный транспорт. В случае, когда число игроковравно n, интенсивности λi , i = 1, ..., n, определяются уравнениямиc0 +ci +11= c1 +,µ0 − λ0µ1 − λ 111= ci+1 +,µi − λiµi+1 − λi+1n∑λ0 +λi = λ.i = 1, ..., n − 1,(2.22)i=1Дифференцируя (2.22) по ci и решая относительнополучим∑(µi − λi )2 ( nj=0,j̸=i (µj − λj )2 )dλi∑n=−,2dcii=0 (µi − λi )Приходим к системе уравнений(c∗i = λic∗i +dλ1 dλ2dci , dci ,i = 1, ..., n.11+2(µi − λi )2j=0,j̸=i (µj − λj )∑n11= c∗i+1 +,µi − λ iµi+1 − λi+1n... , dλdci , i = 1, ..., n,),i = 0, ..., n − 1,(2.23)45λ0 +n∑λi = λ.i=1Системой уравнений (2.23) определяются равновесные цены c∗1 ,..., c∗n .Как и для случая двух игроков, можно предложить кооперативную схемуобъединения всех игроков в одну коалицию с последующим дележом общегодохода для всех участников, используя вектор Шепли.
Рассмотрим, например,трех игроков, которые обслуживают заявки с экспоненциальным временем спараметрами µ1 = 4, µ2 = 6, µ3 = 9 соответственно. Игроки могут организовать∑коалицию, причем она обслуживает заявки с интенсивностьюµi , где S –Sразмер коалиции. Игрок O, как и раньше, обслуживает заявки с параметромµ0 = 3.Таблица 2.4.
Значения v(S) при λ=10, c0 =1, µ0 =3v(0)4.559c∗01λ04.559µ03v(1)0.039c∗10.064λ10.608µ14v(2)0.213c∗20.126λ21.694µ26v(3)0.590c∗30.188λ33.139µ39v(0)4.38c∗01λ04.38µ03v(12)0.389c∗120.13λ122.99µ1210v(0)4.507c∗01λ04.507µ03v(13)0.872c∗130.227λ133.842µ1313v(0)4.861c∗01λ04.861µ03v(23)1.525c∗230.371λ234.11µ2315v(0)5.569c∗01λ05.769µ03v(123) 2.416 c∗123 0.571 λ123 4.231 µ123 19Чтобы определить характеристическую функцию в кооперативной игре, нужно рассчитать ее значения для каждой коалиции S. Это можно сделать двумя46способами. Первый, традиционный, когда оставшиеся игроки объединяются вкоалицию и играют против S. В этом случае для коалиции N \ S собственный выигрыш не важен, ее задача минимизировать выигрыш коалиции S. Тогда коалиция N \ S в качестве своей стратегии может использовать cN \S = 0,увеличивая тем самым свой поток λN \S , но получая выигрыш, равный нулю.Выигрыш коалиции S в данном случае уменьшится.
В настоящей работе применяется другой подход, при котором характеристическая функция строитсяследующим образом. Предположим, что s игроков решили сформировать коалицию S. Она играет как один игрок, а остальные n − s игроков находятся вравновесии с ней, т. е. в качестве стратегий используются равновесные цены.Эти цены являются равновесием по Нэшу в игре n − s + 1 лиц и находятсяиз системы (2.23) при количестве игроков n − s + 1.
Тогда значение характеристической функции есть выигрыш рассматриваемого игрока или коалиции вситуации равновесия по Нэшу. Вычисления представлены в таблице 2.4.В кооперации игроки могут получить совместный доход, равный 2.416.После этого они могут его разделить. В качестве правила дележа можно использовать вектор Шепли. Для игры трех лиц этот дележ имеет вид1111ϕ1 (v) = v(1) + (v(12) − v(2)) + (v(13) − v(3)) + (v(123) − v(23)),36631ϕ2 (v) = v(2) +31ϕ3 (v) = v(3) +31(v(12) − v(1)) +61(v(13) − v(1)) +61(v(23) − v(3)) +61(v(23) − v(2)) +61(v(123) − v(13)),31(v(123) − v(12)),3где v – характеристическая функция в кооперативной игре. Из таблицы 2.4видно, что v супераддитивная. Для данной игры вектор Шеплиϕ1 (v) = 0.386,ϕ2 (v) = 0.799,ϕ3 (v) = 1.229,47причем плата за проезд будет общая для всех транспортных компаний и равнаc∗123 = 0.571.
Таким образом, частным компаниям выгодно сформировать коалицию. Из таблицы 2.4 видно, что увеличение конкуренции приводит к возрастанию потока пассажиров, которые предпочитают использовать конкурирующийтранспорт, а не общественный.2.6. Выводы ко второй главеИтак, найдено равновесие в задаче ценообразования, связанной с транспортной системой, которая представляет собой систему массового обслуживания M/M/2, в которой участвуют два конкурирующих сервера. В модель введен дополнительный игрок – муниципальный транспорт, у которого фиксированная цена на проезд и интенсивность обслуживания.
Моделирование проводится в условиях конкуренции и кооперации, и, так как характеристическаяфункция является супераддитивной, то игрокам выгодно вступать в коалиции.Показано, что увеличение конкуренции приводит к возрастанию потока пассажиров, которые предпочитают использовать конкурирующий транспорт, а необщественный.48Глава 3Равновесие в транспортной системе М/M/m3.1. Теоретико-игровая модель ценообразования втранспортной игреРассматривается бескоалиционная игра m лиц с ненулевой суммой, связанная с функционированием системы массового обслуживания M/M/m на графе.Определение 3.1.
Γ =< N, G, Zi,i∈N , Hi,i∈N > – транспортная игра, в которойN = {1, ..., m}-множество игроков (транспортные компании), обслуживающиепассажиров на графе G =< V, E >, где V – множество вершин и E – множестворебер.Будем считать, что все вершины пронумерованы, V = {v1 , ..., vn }. Длякаждого игрока i существует набор маршрутов Zi из вершины vs ∈ V в vt ∈ V ,которые обслуживает игрок i. Таким образом, Zi = (R1i , R2i , ..., Rki i ), i = 1, .., m.Каждый маршрут представляет собой путь,Определение 3.2.
Путем на графе G =< V, E > будем называть последовательность вершин, соединенных ребрами R = (vs , vs+1 , ..., vt ), в которой конецодного ребра является началом другого ребра, т.е. (vs , vs+1 ), ..., (vt−1 , vt ) ∈ E.Маршруты будем обозначать большими буквами R, а подпути обозначиммалыми буквами r. Чтобы подчеркнуть, что начало пути есть vs , а конец естьvt , будем обозначать такой путь Rst или rst .Определение 3.3. Будем говорить, что путь rs′ t′ является подпутем пути rstи писать rs′ t′ ⊂ rst , если путь rs′ t′ является подпоследовательностью вершин,содержащихся в rst .Обслуживание пассажиров игроком i имеет экспоненциальное распределение времени обслуживания с параметром µRi на каждом маршруте R ∈ Zi .Введем в рассмотрение матрицу интенсивностей {λst } потоков из точки vs в49точку vt для различных s, t = 1, ..., n0 λ21Λ= ...λn1λ12 ...
λ1n0 ... λ2n .... ... ... λn2 ... 0rИгрок i назначает цены на свои услуги cRi , ci на каждом маршруте R ∈ Ziи всех его подпутях r ⊂ R. Формируется профиль стратегий {cZi i } = {cri }, r ⊂R ∈ Zi , i = 1, ..., m. Предположим, что пассажиры минимизируют свои затраты, которые представляют собой цену на билеты плюс ожидаемое время обслуживания, и выбирают сервис, который дешевле остальных.Тогда входящий поток λst разбивается на пуассоновские потоки с интенсивm∑ностями λist , гдеλist = λst , причем, если ни в одном из маршрутов множестваi=1Zi игрока i нет подпути rst , то λist =0.Затраты посетителя, воспользовавшегося i-м сервисом по подпути r какого-то маршрута R ∈ Zi будут равныcri +∑e∈rµRi −1∑rst :e∈rst ⊂rλist,i = 1, 2, ..., n.Таким образом, в равновесии затраты всех пассажиров на конкурентныхнаправлениях будут совпадать для всех сервисов.
Отсюда можно найти интенсивности λist для всех сервисов i = 1, ..., m и подпутей rst . А именно,cri+∑e∈rµRi −1∑rst :e∈rst ⊂rλist=crj+∑′e∈rµRj −1∑rst :rst ⊂r′λjst,для всех i, j таких, что r ⊂ R ∈ Zi и r′ ⊂ R′ ∈ Zj . Если цена на маршрутекакого-то сервиса слишком высока, то поток пассажиров распределится между другими сервисами, и данный сервис не будет участвовать в конкуренции.Поэтому равновесные цены следует искать среди сбалансированных цен.50Выигрыш игрока i можно записать как доход в единицу времени от обслуживания всех потоков на всех маршрутах игрока, т.е.∑Hi ({cZi i }i∈N ) =λist cri .rst :rst ⊂r⊂R∈Zi3.2. Конкуренция игроков на сегментеНачнем исследование предложенной модели с простого примера, рассмотренного в предыдущей главе. Есть две конкурирующие транспортные компании, которые обслуживают пассажиров на сегменте G1 = {V1 , E1 }, изображенном на рисунке 3.1, с экспоненциальным распределением времени обслуживания с параметрами µ1 и µ2 соответственно.
В графе G1 есть две вершины v1 , v2и одно ребро e. У игроков маршруты совпадают, т.е. Zi = (v1 , v2 ) для i = 1, 2.Заявки на обслуживание образуют пуассоновский процесс с интенсивностью λ.Предположим, что λ < µ1 +µ2 . Игроки назначают цену на обслуживание c1 и c2соответственно, и посетители выбирают услугу игрока с меньшими затратами.Тогда входящий поток разобьется на два пуассоновских потока с интенсивностями λ1 и λ2 , где λ1 + λ2 = λ. При этом затраты посетителя, воспользовавшегосяi-м сервисом будут равныci +1,µi − λii = 1, 2,где 1/(µi − λi ) ожидаемое время пребывания пользователя в системе обслуживания [52]. Понятно, что еслиc1 +11< c2 + ,µ1 − λµ2то все пассажиры выберут первый сервис, или наоборотc2 +11< c1 + ,µ2 − λµ1то все пассажиры выберут второй. Такое решение тривиальное, так как в этомслучае конкуренции нет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
