New Theory of Cooperative Games

The paper proposes a new theory of cooperative games based on the notions of conflict equilibrium alone. In this theory, the solution always exists, and it is often unique. The study was sponsored by the Russian Fund for Basic Research, Project No. 03-01-00329, and according to the OITVS Program of the Russian Academy of Sciences, Project No. 1–3. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 156–167, September–October 2005.     

The concept of and search for the fair distribution in cooperative games

Well-known conflict equilibria are used to formulate the concept of fair distribution, and a technique is proposed to find it in an arbitrary cooperative game. Any cooperative game is shown to have only one fair distribution, which can always be found from the formulas of conflict equilibrium theory. The study was carried out in line with the OITVS RAN program (Project No. 1-3) and was sponsored by the Russian Foundation for Basic Research (Project No. 06-01-00821). Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 131–141, November–December 2008.     

Non-Cooperative Tree Creation

In this paper we consider the connection game, a simple network design game with independent selfish agents that was introduced by Anshelevich et al. (Proc. 35th Ann. ACM Symp. Theo. Comp. (STOC), pp. 511–520, 2003). Our study concerns an important subclass of tree games, in which every feasible network is guaranteed to be connected. It generalizes the class of single-source games considered by Anshelevich et al. We focus on the existence, quality, and computability of pure-strategy exact and approximate Nash equilibria. For tree connection games, in which every player holds two terminals, we show that there is a Nash equilibrium as cheap as the optimum network. In contrast, for single-source games, in which every player has at most three terminals, the price of stability is at least k−2, and it is -complete to decide the existence of a Nash equilibrium. Hence, we propose polynomial time algorithms for computing approximate Nash equilibria, which provide relaxed stability and cost efficiency guarantees. For the case of two terminals per player, there is an algorithm to find a (2+ε,1.55)-approximate Nash equilibrium. It can be generalized to an algorithm to find a (3.1+ε,1.55)-approximate Nash equilibrium for general tree connection games. This improves the guarantee of the only previous algorithm for the problem, which returns a (4.65+ε,1.55)-approximate Nash equilibrium. Tightness results for the analysis of all algorithms are derived. Our algorithms use a novel iteration technique for trees that might be of independent interest. This work has appeared in part as an extended abstract at the 31st Symposium on Mathematical Foundations of Computer Science (MFCS 2006) and the 17th International Symposium on Algorithms and Computation (ISAAC 2006). Supported by DFG Research Training Group 1042 “Explorative Analysis and Visualization of Large Information Spaces”.     

Brown�CRobinson method for interval matrix games

In this paper, two-person interval matrix games are considered, and by means of acceptability index, Brown–Robinson method to find a mixed-strategy equilibrium is adapted to interval matrix games. Numerical examples are also given.     

An approach to solution uniqueness in game problems

A new concept of strong conflict equilibrium is proposed that supplements the well-known fundamental system of conflict equilibria and considerably increases the possibility of finding a unique strongest equilibrium (solution) in any game problem. The efficiency of this new equilibrium is illustrated by static and dynamic game problems. This work was carried out under the program “Basic foundations of information technologies and systems” of the Russian Academy of Science (Project No. 1–3). Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 116–127, March–April 2009.     

Influence of a uniform taxation and effects of monopolies on approaching equilibrium in an economic system

An open economic system with monopolies and a uniform taxation system is investigated. The technologies with regular expenditures are taken into account. Based on a model of the economic system with regular interests of consumers, an optimal equilibrium state of the economy being investigated is found. The levels of the monopoly taxation that correspond to the optimal equilibrium state of the economy are determined. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 152–164, July–August 2008.     

Edge Pricing of Multicommodity Networks for Selfish Users with Elastic Demands

We examine how to induce selfish heterogeneous users in a multicommodity network to reach an equilibrium that minimizes the social cost. In the absence of centralized coordination, we use the classical method of imposing appropriate taxes (tolls) on the edges of the network. We significantly generalize previous work (Yang and Huang in Transp. Res. Part B 38:1–15, [2004]; Karakostas and Kolliopoulos in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 268–276, [2004]; Fleischer et al. in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 277–285, [2004]) by allowing user demands to be elastic. In this setting the demand of a user is not fixed a priori but it is a function of the routing cost experienced, a most natural assumption in traffic and data networks. Research supported by MITACS and a NSERC Discovery grant.     

Effect of monopolism and taxation on an economic system in the case of nonlinear technologies

The presence of monopolists in an economic system and a nonlinear dependence of technological coefficients on output vectors are considered. An earlier tax theory is extended to this case. An algorithm of solving the equilibrium problem in such an economic system is proposed. The effect of monopolists and the tax system being used on the Ukrainian economy is investigated. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 155–166, January–February 2006.     

A novel approximate method of computing extended Nash equilibria

In this paper, we propose a new method of computing an approximate Nash equilibrium with additional features. Existing algorithms often fail to produce an exact solution for games involving more than 3 players. Similarly, existing algorithms do not permit additional constraints on the problem. The principle idea of this paper involves proposing a methodology for computing approximate solutions through evolutionary computation. To do so, we first provide formal definitions of these problems and their approximate versions. Following which, we present the details of our solution. One of the most important advantages of the proposed solution is flexibility, which provides solutions to problems related to Nash equilibrium extensions. The proposed idea is tested on several types of games that vary with difficulty and size. All test sets are generated based on the well-known Gamut program. Additional comparisons with classical algorithms are also performed. Results indicate that Differential Evolution is capable of obtaining satisfactory solutions to large random and covariant games. The results also demonstrate that there is a high probability that even large games, in which a set of strategies with a non-zero probability of being chosen are very small, have a solution. The computation time depends mainly on the problem size, and the original Nash equilibrium problem is unaffected by additional modifications.     

Generalized Cournot-Stackelberg-Nash equilibrium

The concept of the Cournot-Stackelberg-Nash equilibrium is proposed in which the leader’s payoff is no less than its payoff in the case of the Cournot-Nash equilibrium and the follower’s payoff is no less than its payoff in the case of the Stackelberg-Nash equilibrium. The generalized equilibrium coincides with the Cournot-Nash and Stackelberg-Nash equilibria for extreme values of a parameter. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 3–9, January–February 2006.     

不确定性下多主从博弈中均衡的存在性

在已知不确定参数变化范围的假设下,研究多主从博弈中均衡点的存在性问题.基于非合作博弈中NS均衡的定义,提出不确定性下多主从博弈中均衡的概念.基于Fan-Glicksberg不动点定理,证明均衡点的存在性.最后通过算例验证了所提出方法的可行性.     

Nonlocal sets of orthogonal multipartite product states with less members

Repeated quantum game theory addresses long-term relations among players who choose quantum strategies. In the conventional quantum game theory, single-round quantum games or at most finitely repeated games have been widely studied; however, less is known for infinitely repeated quantum games. Investigating infinitely repeated games is crucial since finitely repeated games do not much differ from single-round games. In this work, we establish the concept of general repeated quantum games and show the Quantum Folk Theorem, which claims that by iterating a game one can find an equilibrium strategy of the game and receive reward that is not obtained by a Nash equilibrium of the corresponding single-round quantum game. A significant difference between repeated quantum prisoner’s dilemma and repeated classical prisoner’s dilemma is that the classical Pareto optimal solution is not always an equilibrium of the repeated quantum game when entanglement is sufficiently strong. When entanglement is sufficiently strong and reward is small, mutual cooperation cannot be an equilibrium of the repeated quantum game. In addition, we present several concrete equilibrium strategies of the repeated quantum prisoner’s dilemma.

     

From Kalman—Mesarovic realization to a normal-hyperbolic linear model

The principles of the methodology are formulated, which underlie the procedures of the Kalman—Mesarovic realization for dynamic systems with state equations in the class of autonomous linear differential equations in the normalized Frechet space. In this connection, the key approaches to the solution of classical problems of realization theory regarding linear dissipation models of normal-hyperbolic type are interpreted. The study was sponsored by the Russian Fund for Basic Research (grant No. 05-01-00623), the “Integration” Russian Federal Target Program (grant No. B0077), and the Program for Basic Research of the Presidium of the Russian Academy of Sciences (program No. 19, project 2.5). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 137–157, November–December 2005.     

Walrasian Equilibrium: Hardness,Approximations and Tractable Instances

We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004) showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria. In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still NP-hard for general graphs.     

Approximate CAPM When Preferences are CRRA

In general equilibrium models of financial markets, the capital asset pricing formula does not hold when agents have von Neumann–Morgenstern utility with constant relative risk aversion. In this paper we examine under which conditions on endowments and dividends the pricing formula provides a good benchmark for equilibrium returns. While it is easy to construct examples where equilibrium returns are arbitrarily far from those predicted by CAPM, we show that there is a large class of economies where CAPM provides a very good approximation. Although the pricing formula does not hold exactly for the chosen specification, it turns out that pricing-errors are extremely small. This paper is a substantial revision of our 2000 METEOR working paper, “The Robustness of CAPM – A Computational Approach”. The research of Jean-Jacques Herings has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences and a grant of the Netherlands Organisation for Scientific Research (NWO). While this paper was being written this author enjoyed the generous hospitality of the Cowles Foundation for Research in Economics at Yale University, of CORE at Universita’e Catholique de Louvain, and of CentER at Tilburg University. Felix Kubler gratefully acknowledges the financial support of the Cowles Foundation in the form of an Anderson dissertation fellowship.     

The Quantum Ultimatum Game

A quantum version of the ultimatum game is studied. Both a restricted version with classical moves and the unitary version are considered. With entangled initial states, Nash equilibria in quantum games are in general different from those of classical games. Quantum versions might therefore be useful as a framework for modeling deviations from classical Nash equilibrium in experimental games.PACS:02.50.Le; 03.67.-a     

Solution of a problem of geometric programming

The convergence of a method of solution of a geometric programming problem with one forced constraint is studied. The algorithm proposed can be used in searching for chemical equilibrium of an ideal system of gases. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 172–175, November–December 2005.     

Numerically Pricing Nonlinear Time-Fractional Black–Scholes Equation with Time-Dependent Parameters Under Transaction Costs

Computational Economics - One of the assumptions of the classical Black–Scholes (B–S) is that the market is frictionless. Also, the classical B–S model cannot show the memory...     

AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents

Two minimal requirements for a satisfactory multiagent learning algorithm are that it 1. learns to play optimally against stationary opponents and 2. converges to a Nash equilibrium in self-play. The previous algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action (repeated) games—assuming that the opponent’s mixed strategy is observable. Another algorithm, ReDVaLeR (which was introduced after the algorithm described in this paper), achieves the two properties in games with arbitrary numbers of actions and players, but still requires that the opponents' mixed strategies are observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have the two properties in games with arbitrary numbers of actions and players. It is still the only algorithm that does so while only relying on observing the other players' actual actions (not their mixed strategies). It also learns to play optimally against opponents that eventually become stationary. The basic idea behind AWESOME (Adapt When Everybody is Stationary, Otherwise Move to Equilibrium) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. We provide experimental results that suggest that AWESOME converges fast in practice. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing future multiagent learning algorithms as well. Editors: Amy Greenwald and Michael Littman     

多组对策系统非劣Nash策略的最优均衡解算法

多组对策系统中求解组与组之间的非劣Nash策略至关重要.如何针对一般问题解析求出非劣Nash策略还没有有效的方法.本文阐述了一种利用组与组之间的非劣反应集构造求解非劣Nash策略的迭代算法.为此首先引进多组对策系统组内部合作对策的最优均衡值和最优均衡解的概念,然后通过证明最优均衡解是组内部隐含某一权重向量的合作对策的非劣解,得到求解合作对策的单目标规划问题.进一步说明在组内部该问题的解不仅是非劣解而且对所有局中人都优于不合作时的Nash平衡策略.最后给出了验证该算法有效性的一个实际例子.