Диссертация (1150526), страница 8

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

Текст из файла (страница 8)

Для того, чтобы создать конкуренцию, игроки должны балансировать цены таким образом, чтобы эти условия не выполнялись.51В работе рассмотрен конкурентный случай, когда пассажиры используют обасервиса.Рис. 3.1. Конкуренция игроков на сегментеБез ограничения общности положим c = 1. Тогда интенсивности потоковλ1 и λ2 для соответствующих сервисов можно найти из условийc1 +11= c2 +,µ1 − λ1µ2 − λ 2λ1 + λ2 = λ.(3.1)(3.2)Выигрыши игроков имеют видH1 (c1 , c2 ) = λ1 c1 ,H2 (c1 , c2 ) = λ2 c2 .Пусть для определенности µ1 > µ2 .

Зафиксируем c2 и найдем наилучшийответ первого игрока. В отличии от предыдущей главы, в которой использовался традиционный подход, когда ситуации равновесия находились путем дифференцирования функций выигрыша, мы воспользуемся методом Лагранжа,который позволит определить стационарные точки задачи оптимизации с ограничениями в виде равенств [52].

Формально схема этого метода представима вследующем виде. Найдем максимум функции H1 , при ограничениях (3.1)-(3.2))(11− c2 −.L1 = c1 λ1 + k1 c1 +µ1 − λ1µ2 − λ + λ 2Дифференцируем∂L1= λ1 + k1 = 0,∂c1k1 = −λ1 ,52∂L1= c 1 + k1∂λ1откудаc∗1 = λ1((11+(µ1 − λ1 )2 (µ2 − λ2 )211+(µ1 − λ1 )2 (µ2 − λ2 )2),).Аналогично находим цену для второго игрока()11c∗2 = λ2.+(µ1 − λ1 )2 (µ2 − λ2 )2Из (3.3)-(3.4) следует, что(3.3)(3.4)c∗c∗1= 2,λ1λ2т.

е. в равновесии интенсивности пропорциональны установленным ценам. Отсюдаλ1 = λc∗1,c∗1 + c∗2λ2 = λc∗2.c∗1 + c∗2Подставив в (3.3)-(3.4), приходим к уравнению()11+.c∗1 + c∗2 = λ∗c∗2122λ)λ)(µ1 − c∗c+c(µ−∗2c∗ +c∗121(3.5)2С другой стороны, из (3.1) получаемc∗1 − c∗2 =1µ2 −c∗2∗c1 +c∗2λ−1µ1 −c∗1∗c1 +c∗2 λ.(3.6)Системой уравнений (3.5)-(3.6) однозначно определяются равновесные цены c∗1и c∗2 .3.3. Затраты, в которых учитывается время нахождения вочередиВ настоящем параграфе покажем, как изменится вид равновесных цен,если рассматривать не задержки пассажиров в системе, а задержки в очереди. Как и раньше, рассмотрим бескоалиционную игру двух лиц с ненулевой53суммой.

Игроки I и II обслуживают входящий поток, при этом их время обслуживания имеет экспоненциальный вид с интенсивностями µ1 и µ2 . Игрокиназначают цены на свои услуги c1 и c2 соответственно. Тогда посетители будутвыбирать сервис с меньшими затратами, и входящий поток разобьется на двапуассоновских потока с интенсивностями λ1 и λ2 , где λ1 + λ2 = λ. При этомзатраты посетителя, воспользовавшегося i-м сервисом, будут равныci +λi,µi (µi − λi )i = 1, 2,здесь λi /µi (µi − λi ) – ожидаемое время пребывания пользователя в очереди наобслуживание [52]. Тогда интенсивности потоков λ1 и λ2 = λ − λ1 для соответствующих сервисов можно найти из условияc1 +λ1λ2= c2 +.µ1 (µ1 − λ1 )µ2 (µ2 − λ2 )Выигрыши игроков равныH1 (c1 , c2 ) = λ1 c1 ,H2 (c1 , c2 ) = λ2 c2 .Равновесие по НэшуНайдем наилучший ответ первого игрока на стратегию c2 второго игрока используя метод множителей Лагранжа.

Для фиксированного c2 функцияЛагранжа имеет вид(L1 = λ 1 c 1 + k c 1 +λ1λ2− c2 −µ1 (µ1 − λ1 )µ2 (µ2 − λ2 ))+ γ(λ1 + λ2 − λ).Дифференцируем∂L1= λ1 + k = 0,∂c1∂L1kkλ1= c1 +++ γ = 0,∂λ1µ1 (µ1 − λ1 ) µ1 (µ1 − λ1 )2kkλ2∂L1=−−+ γ = 0.∂λ2µ2 (µ2 − λ2 ) µ2 (µ2 − λ2 )2(3.7)54Симметричный случайПусть оба сервиса одинаковые, т. е. µ1 = µ2 = µ. Из симметрии задачиочевидно, что в равновесии должно быть c∗1 = c∗2 = c∗ и λ1 = λ2 = λ2 .

Тогдарешением системы (3.7) будет)(λ2λ,c∗ =+2 µ(µ − λ2 ) µ(µ − λ2 )2преобразуя это выражение, получаемc∗ =λ.(µ − λ2 )2Несимметричный случайПредположим, что сервисы неодинаковы. В этом случае решением (3.7)являетсяc∗1 = λ1(1λ1λ21+++2µ1 (µ1 − λ1 ) µ2 (µ2 − λ2 ) µ1 (µ1 − λ1 )µ2 (µ2 − λ2 )2()11= λ1+.(µ1 − λ1 )2 (µ2 − λ + λ1 )2)=Аналогично для второго игрока()11λλ12c∗2 = λ2+++=µ1 (µ1 − λ1 ) µ2 (µ2 − λ2 ) µ1 (µ1 − λ1 )2 µ2 (µ2 − λ2 )2()11= λ2+.(µ1 − λ1 )2 (µ2 − λ + λ1 )2Таким образом видим, что модели конкуренции двух обслуживающих сервисов с задержками в очереди и задержками в системе полностью совпадают.3.4. Конкуренция m игроков на сегментеРассмотренную выше модель конкуренции двух серверов несложно распространить на случай m игроков. Представим, что есть m конкурентных серверов,которые обслуживают заявки с экспоненциальным распределением времени обслуживания соответственно с параметрами µ1 , µ2 , ..., µm .

Игроки назначают55цены на свои услуги c1 , c2 , ..., cm соответственно. Тогда посетители будут выбирать сервис с меньшими затратами и входящий поток разобьется на m пуассоновских потоков с интенсивностями λ1 , λ2 ,..., λm , где λ1 + λ2 + .. + λm = λ. Приэтом затраты посетителя, воспользовавшегося i-м сервисом будут равныci +1,µi − λii = 1, 2, ..., m.Тогда интенсивности потоков λ1 , λ2 , ..., λm для соответствующих сервисов можно найти из условия111= c2 += ...

= cm +.µ1 − λ 1µ2 − λ2µm − λ mc1 +(3.8)Выигрыш i-ого игрока имеет видHi (c1 , c2 , ..., cm ) = λi ci ,i = 1, ..., m.Воспользовавшись методом Лагранжа, найдем наилучший ответ первогоигрока. Зафиксируем ci i = 2, 3, ..., m. Найдем максимум функции H1 , приограничениях (3.8)L 1 = c1 λ 1 +m∑i=2(ki11− ci −c1 +µ1 − λ 1µi − λi)m∑+ γ(λi − λ).i=1Условия на экстремум первого порядка дают равенства∑∂L1= λ1 +ki = 0,∂c1i=2mm∑ki∂L1i=2= c1 ++ γ = 0,∂λ1(µ1 − λ1 )2ki∂L1=−+ γ = 0,∂λi(µi − λi )2i = 2, ..., m.Проделывая аналогичную процедуру для каждого игрока приходим к системе, которая позволяет определить равновесные цены и интенсивности пото-56ков на G1()11∗ci = λi ∑m,2 + (µ −λ )2iij=0,j̸=i (µj −λj )11c∗i + µi −λ= c∗i+1 + µi+1 −λ, i = 0..m − 1,ii+1m∑ λi = λ.i=13.5.

Конкуренция m игроков на линейном маршрутеРассмотрим поведение m игроков на линейном маршруте G2 = {V2 , E2 },представленном на рисунке 3.2. В качестве иллюстрации можно представитьдвижение на междугородных маршрутах, в которых пассажиры садятся на начальной станции и постепенно выходят на промежуточных остановках.

Здесьмножество вершин V2 = {v1 , v2 , ..., vn } и множество ребер E2 = {e12 , e23 , ..., en−1n }.Игроки обслуживают пассажиров с экспоненциальным распределением времени обслуживания с параметром µ(i) , i = 1, ..., m. Предположим, что у всех игроков один и тот же линейный маршрут Zi = (v1 , v2 , ..., vn ) для i = 1, 2, ..., m.Заявки на обслуживание образуют пуассоновский процесс с матрицей интенсивностей пуассоновских потоков ΛРис. 3.2. Конкуренция игроков на линейном маршруте0 λ12 λ130 00Λ=0 000 00... λ1n.........0 .0 057(i)Игроки назначают цену на обслуживание c1s , i = 1, 2, ..., m, s = 2, 3, ..., n,и посетители выбирают услугу игрока с меньшими затратами.

Тогда входящийm∑(i)поток Λ разобьется на потоки с интенсивностями λ1s =λ1s , s = 2, 3, ..., n.i=1При этом затраты пассажира, воспользовавшегося i-м сервисом на пути r1jбудут равны(i)c1j+j−1∑(i)ak ,i = 1, ..., m,j = 2, ..., n,k=1где1n∑(i)ak =µ(i)−,k = 1, ..., n − 1,i = 1, ..., m,(i)λ1ss=k+1это задержки на ребре ekk+1 .Балансовые уравнения примут вид(1)c1j+j−1∑(1)ak−(i)c1j−k=1j−1∑(i)ak = 0,i = 2, ..., m,j = 2, ..., n.k=1Выигрыш i-ого игрока равен(m)(1)Hi (cZ , ..., cZ )=n∑(i) (i)c1j λ1j .j=2Построим функцию Лагранжа для игрока 1 при ограничениях (3.9).( m)nn∑∑∑(1) (1)(i)L1 =c1j λ1j +γjλ1j − λ1j +j=2+m ∑n∑j=2(kji(1)c1j +j−1∑i=2 j=2i=1(1)(i)ak − c1j −k=1j−1∑)(i)ak.k=1Запишем условия на экстремум первого порядка∂L1(1)∂c1s∂L1(1)∂λ1s=(1)c1s=(1)λ1s+m∑ksi = 0,s = 2, ..., n,i=2+s−2 ∑m ∑n∑kji(1)l=0 i=22j=2+l (al+1 )+ γs ,s = 2, ..., n,(3.9)58∂L1(k)∂λ1s=−s−2 ∑m ∑n∑(k)kji (al+1 )2 + γs ,s = 2, ..., n,k = 2, ..., m.l=0 i=2 j=2+lСимметричный случайПусть игроки обслуживают пассажиров с экспоненциальным распределением времени обслуживания с одинаковым параметром µ.

Тогда очевидно, что(i)(s)в равновесии λ1j = λ1j =λ1jm(s)(i)и c1j = c1j для любых j = 2, ..., n, i, s = 1, ..., m,и решением системы являетсяc∗1ss−2n1 ∑ ∑=λ1j (al+1 )2 ,m−1(3.10)s = 2, ..., n,l=0 j=2+lгде1ak =.n∑µ−λ1ss=k+1mУравнения Лагранжа дают необходимые условия для определения стационарных точек функции Hi при ограничениях(i)(i)gj (cZ , λZ )=(1)c1j+j−1∑(1)ak−(i)c1j−k=1j−1∑(i)ak = 0,i = 2, ..., m,j = 2, ..., n.k=1Достаточные условия можно сформулировать следующим образом:Определение 3.4 Матрица вида0 PH=TP Q,(k+p)×(k+p)где▽g1 (X)▽g2 (X).P =..▽gk (X)k×p,(Q=59)∂ 2 Li (X,k),∂xi ∂xjp×p∀i, j,называется окаймленной матрицей Гессе.Пусть имеется стационарная точка (X0 , k0 ) функции Лагранжа и окаймленная матрица Гессевычислена в этой стационарной точке. Тогда точка(X0 , k0 ) является1.

Точкой максимума, если, начиная с углового минора порядка 2k+1, последующие p − k угловых миноров окаймленной матрицы Гессе H образуютзнакопеременный числовой ряд, в котором знак первого члена определяется множителем (−1)k+1 .2. Точкой минимума, если, начиная с углового минора порядка 2k + 1, последующие p − k угловых миноров матрицы H имеют знаки, определяемыемножителем (−1)k .Эти условия являются достаточными для определения экстремальной точки.Утверждение 3.1. Решение системы (3.10) является точкой максимумафункции выигрыша H(cZ ).Доказательство. Для упрощения выкладок предположим, что число игроковравно 2. Тогда решение будет точкой максимума, если, начиная с углового минора порядка 2n − 1, последующие n − 2 угловых миноров окаймленной матрицыГессе образуют знакопеременный числовой ряд, в котором знак первого членаопределяется множителем (−1)n .

Для двух игроков равновесием будетi−1n∑∑c∗1i =(ak )2 λ1j  , i = 2, ..., n,k=1j=k+1гдеak =µ−1n∑j=k+1.λ1j260Заметим, что матрица Гессе имеет блочный0En−1 n−1H = En−1 0n−1An−1 En−1видAn−1En−1  ,0n−1где E-единичная матрица размерности (n − 1 × n − 1), 0 нулевая матрица размерности (n − 1 × n − 1) иa1a1a1a1 a1 + a2a1 + a2An−1 = a1 a1 + a2 a1 + a2 + a3 .........a1 a1 + a2 a1 + a2 + a3 ..Рассмотрим определитель матрицы 0 ... 0 0 ...

Характеристики

Список файлов диссертации