All issues

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

The problem of the Nash equilibrium in bimatrix game is considered. The search for a solution is associated with a problem of nonlinear programming. Application of the method of feasible directions for the solution of such a problem is investigated.

В работе описывается двухстадийная модель равновесного распределения транспортных потоков. Модель состоит из двух блоков, где первый блок — модель расчета матрицы корреспонденций, а второй блок — модель равновесного распределения транспортных потоков по путям. Первая модель, используя матрицу транспортных затрат (затраты на перемещение из одного района в другой, в данном случае — время), рассчитывает матрицу корреспонденций, описывающую потребности в объемах передвижения из одного района в другой район. Для решения этой задачи предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийную модель. Вторая модель на базе равновесного принципа Нэша–Вардропа (каждый водитель выбирает кратчайший для себя путь) описывает, как именно потребности в перемещениях, задаваемые матрицей корреспонденций, распределяются по возможным путям. Таким образом, зная способы распределения потоков по путям, можно рассчитать матрицу затрат. Равновесием в двухстадийной модели транспортных потоков называют неподвижную точку цепочки из этих двух моделей. Практически ранее отмеченную задачу поиска неподвижной точки решали методом простых итераций. К сожалению, на данный момент вопрос сходимости и оценки скорости сходимости для этого метода не изучен. Кроме того, при численной реализации алгоритма возникает множество проблем. В частности, при неудачном выборе точки старта возникают ситуации, в которых алгоритм требует вычисления экстремально больших чисел и превышает размер доступной памяти даже в самых современных вычислительных машинах. Поэтому в статье предложены способ сведения задачи поиска описанного равновесия к задаче выпуклой негладкой оптимизации и численный способ решения полученной задачи оптимизации. Для обоих методов решения задачи были проведены численные эксперименты. Авторами использовались данные для Владивостока (для этого была обработана информация из различных источников и собрана в новый пакет) и двух небольших городов США. Методом простой прогонки двух блоков сходимости добиться не удалось, тогда как вторая модель для того же набора данных продемонстрировала скорость сходимости $k^{−1.67}$.

Authors describe a two-stage traffic assignment model. It contains of two blocks. The first block consists of a model for calculating a correspondence (demand) matrix, whereas the second block is a traffic assignment model. The first model calculates a matrix of correspondences using a matrix of transport costs (it characterizes the required volumes of movement from one area to another, it is time in this case). To solve this problem, authors propose to use one of the most popular methods of calculating the correspondence matrix in urban studies — the entropy model. The second model describes exactly how the needs for displacement specified by the correspondence matrix are distributed along the possible paths. Knowing the ways of the flows distribution along the paths, it is possible to calculate the cost matrix. Equilibrium in a two-stage model is a fixed point in the sequence of these two models. In practice the problem of finding a fixed point can be solved by the fixed-point iteration method. Unfortunately, at the moment the issue of convergence and estimations of the convergence rate for this method has not been studied quite thoroughly. In addition, the numerical implementation of the algorithm results in many problems. In particular, if the starting point is incorrect, situations may arise where the algorithm requires extremely large numbers to be computed and exceeds the available memory even on the most modern computers. Therefore the article proposes a method for reducing the problem of finding the equilibrium to the problem of the convex non-smooth optimization. Also a numerical method for solving the obtained optimization problem is proposed. Numerical experiments were carried out for both methods of solving the problem. The authors used data for Vladivostok (for this city information from various sources was processed and collected in a new dataset) and two smaller cities in the USA. It was not possible to achieve convergence by the method of fixed-point iteration, whereas the second model for the same dataset demonstrated convergence rate $k^{-1.67}$.

Еще в середине позапрошлого десятилетия ученые, изучавшие функционирование сообществ насекомых, выделили 4 основных паттерна организационной структуры таких сообществ. (i) Сотрудничество более развито в группах с сильным родством. (ii) Кооперация у видов с большими размерами колоний зачастую развита больше, чем у видов с малыми размерами колоний. Причем в колониях малого размера зачастую наблюдаются больший внутренний репродуктивный конфликт и меньшая морфологическая и поведенческая специализация. (iii) В пределах одного вида численность выводка (т. е. в некотором смысле эффективность) на душу населения обычно снижается по мере увеличения размера колонии. (iv) Развитая кооперация, склонная проявляться при ограниченности ресурсов и жесткой межгрупповой конкуренции. Думая о функционировании группы организмов как о двухуровневом рынке конкуренции, в котором в процессе индивидуального отбора особи сталкиваются с проблемой распределения своей энергии между инвестициями в межгрупповую конкуренцию и инвестициями во внутригрупповую конкуренцию, т. е. внутреннюю борьбу за долю ресурсов, полученных в результате межгрупповой конкуренции, можно сопоставить подобной биологической ситуации экономический феномен coopetition — кооперацию конкурирующих агентов с целью в дальнейшем конкурентно поделить выигранный вследствие кооперации ресурс. В рамках экономических исследований были показаны эффекты, аналогичные (ii): в рамках соревнования большой и маленькой групп оптимальной стратегией большой будет полное выдавливание второй группы и монополизация рынка (т. е. большие группы склонны действовать кооперативно); (iii) существуют условия, при которых размер группы оказывает негативное влияние на продуктивность каждого ее индивида (такой эффект называется парадоксом размера группы, или эффект Рингельмана). Общей идеей моделирования подобных эффектов является идея пропорциональности: каждый индивид (особь / рациональный агент) решает, какую долю своих сил инвестировать в межгрупповую конкуренцию, а какую — во внутригрупповую. При этом выигрыш группы должен быть пропорционален ее суммарным инвестициям в конкуренцию, тогда как выигрыш индивида пропорционален его вкладу во внутривидовую борьбу. Несмотря на распространенность эмпирических наблюдений, до сих пор не была введена теоретико-игровая модель, в которой можно было бы подтвердить наблюдаемые эмпирически эффекты. В рамках данной работы предлагается модель, которая устраняет проблемы ранее существующих, а моделирование равновесных по Нэшу состояний в рамках предложенной модели позволяет пронаблюдать перечисленные выше эффекты в ходе численных экспериментов.

At the middle of the 2000-th, scientists studying the functioning of insect communities identified four basic patterns of the organizational structure of such communities. (i) Cooperation is more developed in groups with strong kinship. (ii) Cooperation in species with large colony sizes is often more developed than in species with small colony sizes. And small-sized colonies often exhibit greater internal reproductive conflict and less morphological and behavioral specialization. (iii) Within a single species, brood size (i. e., in a sense, efficiency) per capita usually decreases as colony size increases. (iv) Advanced cooperation tends to occur when resources are limited and intergroup competition is fierce. Thinking of the functioning of a group of organisms as a two-level competitive market in which individuals face the problem of allocating their energy between investment in intergroup competition and investment in intragroup competition, i. e., an internal struggle for the share of resources obtained through intergroup competition, we can compare such a biological situation with the economic phenomenon of “coopetition” — the cooperation of competing agents with the goal of later competitively dividing the resources won in consequence In the framework of economic researches the effects similar to (ii) — in the framework of large and small group competition the optimal strategy of large group would be complete squeezing out of the second group and monopolization of the market (i. e. large groups tend to act cooperatively) and (iii) — there are conditions, in which the size of the group has a negative impact on productivity of each of its individuals (this effect is called the paradox of group size or Ringelman effect). The general idea of modeling such effects is the idea of proportionality — each individual (an individual/rational agent) decides what share of his forces to invest in intergroup competition and what share to invest in intragroup competition. The group’s gain must be proportional to its total investment in competition, while the individual’s gain is proportional to its contribution to intra-group competition. Despite the prevalence of empirical observations, no gametheoretic model has yet been introduced in which the empirically observed effects can be confirmed. This paper proposes a model that eliminates the problems of previously existing ones and the simulation of Nash equilibrium states within the proposed model allows the above effects to be observed in numerical experiments.