共查询到20条相似文献,搜索用时 15 毫秒
1.
Fabien Lange 《Discrete Mathematics》2009,309(12):4037-108
The paper proposes a general approach of interaction between players or attributes. It generalizes the notion of interaction defined for players modeled by games, by considering functions defined on distributive lattices. A general definition of the interaction transform is provided, as well as the construction of operators establishing transforms between games, their Möbius transforms and their interaction indices. 相似文献
2.
Bezalel Peleg 《Israel Journal of Mathematics》1963,1(4):197-200
In this paper an analogue of the bargaining setM
1
i
is defined for cooperative games without side payments. An existence theorem is proved for games of pairs, while it is shown
by an example that no general existence theorem holds. 相似文献
3.
The game Euclid, introduced and named by Cole and Davie, is played with a pair of nonnegative integers. The two players move alternately, each subtracting a positive integer multiple of one of the integers from the other integer without making the result negative. The player who reduces one of the integers to zero wins. Unfortunately, the name Euclid has also been used for a subtle variation of this game due to Grossman in which the game stops when the two entries are equal. For that game, Straffin showed that the losing positions (a,b) with a<b are precisely the same as those for Cole and Davie’s game. Nevertheless, the Sprague–Grundy functions are not the same for the two games. We give an explicit formula for the Sprague–Grundy function for the original game of Euclid and we explain how the Sprague–Grundy functions of the two games are related. 相似文献
4.
5.
We prove an asymptotic Lipschitz estimate for value functions of tug-of-war games with varying probabilities defined in Ω ? ?n. The method of the proof is based on a game-theoretic idea to estimate the value of a related game defined in Ω ×Ω via couplings.
相似文献6.
Jacek Krawczyk 《Computational Management Science》2007,4(2):183-204
This paper is about games where the agents face constraints in the combined strategy space (unlike in standard games where
the action sets are defined separately for each player) and about computational methods for solutions to such games. The motivation
examples for such games include electricity generation problems with transmission capacity constraints, environmental management
to control pollution and internet switching to comply to buffers of bounded capacity. In each such problem a regulator may
aim at compliance to standards or quotas through taxes or charges. The relevant solution concept for these games has been
known under several names like generalised Nash equilibrium, coupled constraint equilibrium and more. Existing numerical methods converging to such an equilibrium will be explained. Application examples of use of
NIRA, which is a suite of Matlab routines that implement one of the methods, will be provided.
相似文献
7.
By extracting combinatorial structures in well-solved nonlinear combinatorial optimization problems, Murota (1996,1998) introduced the concepts of M-convexity and L-convexity to functions defined over the integer lattice. Recently, Murota–Shioura (2000, 2001) extended these concepts to polyhedral convex functions and quadratic functions in continuous variables. In this paper, we consider a further extension to more general convex functions defined over the real space, and provide a proof for the conjugacy relationship between general M-convex and L-convex functions.Mathematics Subject Classification (1991): 90C10, 90C25, 90C27, 90C35This work is supported by Grant-in-Aid of the Ministry of Education, Culture, Sports, Science and Technology of Japan 相似文献
8.
Bezalel Peleg 《Israel Journal of Mathematics》1963,1(1):48-53
In this paper the notion ofm-quota game with a continuum of players is defined and the theory of bargaining sets is generalized to this new class of games.
We discuss only the bargaining setM
0 and our results are similar to those obtained in the finite case. Our main result is that for maximal coalition structures
the stable payoff functions are exactly those in which almost every non-weak player receives no more than his quota and the
weak players receive zero. 相似文献
9.
《International Journal of Approximate Reasoning》2014,55(6):1458-1468
The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations. 相似文献
10.
Investigation of partial multiplace functions by algebraic methods plays an important role in modern mathematics, where we consider various operations on sets of functions, which are naturally defined. The basic operation for n -place functions is an (n + 1)-ary superposition [ ], but there are some other naturally defined operations, which are also worth of consideration. In this article we consider binary Mann's compositions ⊕1,…,⊕ n for partial n-place functions, which have many important applications for the study of binary and n-ary operations. We present methods of representations of such algebras by n-place functions and find an abstract characterization of the set of n-place functions closed with respect to the set-theoretic inclusion. Communicated by V. Artamonov. 相似文献
11.
α-Well-posedness for Nash Equilibria and For Optimization Problems with Nash Equilibrium Constraints
We present the concepts of α-well-posedness for parametric noncooperative games and for optimization problems with constraints defined by parametric Nash equilibria. We investigate some classes of functions that ensure these types of well-posedness and the connections with α-well-posedness for variational inequalities and optimization problems with variational inequality constraints. 相似文献
12.
Tadeusz Radzik 《International Journal of Game Theory》2000,29(2):211-227
This paper gives a full characterization of matrices with rows and columns having properties closely related to the (quasi-)
convexity-concavity of functions. The matrix games described by such payoff matrices well approximate continuous games on
the unit square with payoff functions F (x, y) concave in x for each y, and convex in y for each x. It is shown that the optimal strategies in such matrix games have a very simple structure and a search-procedure is given.
The results have a very close relationship with the known theorem of Debreu and Glicksberg about the existence of a pure Nash
equilibrium in n-person games.
Received: May 1997/Final version: August 1999 相似文献
13.
The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core. 相似文献
14.
We introduce μ-convexity, a new kind of game convexity defined on a σ-algebra of a nonatomic finite measure space. We show that μ-convex games are μ-average monotone. Moreover, we show that μ-average monotone games are totally balanced and their core contains a nonatomic finite signed measure. We apply the results
to the problem of partitioning a measurable space among a finite number of individuals. For this problem, we extend some results
known for the case of individuals’ preferences that are representable by nonatomic probability measures to the more general
case of nonadditive representations. 相似文献
15.
N. I. Naumova 《International Journal of Game Theory》2005,33(4):523-534
Let f be a single valued solution for cooperative TU games that satisfies inessential game property, efficiency, Hart Mas-Colell
consistency and for two person games is strictly monotonic and individually unbounded. Then there exists a family of strictly
increasing functions associated with players that completely determines f. For two person games, both players have equal differences between their functions at the solution point and at the values
of characteristic function of their singletons. This solution for two person games is uniquely extended to n person games due to consistency and efficiency. The extension uses the potential with respect to the family of functions
and generalizes potentials introduced by Hart and Mas Colell [6]. The weighted Shapley values, the proportional value described
by Ortmann [11], and new values generated by power functions are among these solutions.
The author is grateful to anonymous referee and Associate Editor for their comments and suggestions. 相似文献
16.
In this paper, we further study a class of generalized constrained multiobjective games where the number of players may be finite or infinite, the strategy sets may be general FC-spaces without local convexity structure, and all payoff functions get their values in infinite-dimensional topological vector spaces. By using an existence theorem of maximal elements for a family of set-valued mappings in FC-spaces due to the author, an existence theorem of solutions for a system of generalized vector quasivariational inclusions is first proved in general FC-spaces. By applying the existence result of solutions of the system of generalized vector quasivariational inclusions, some existence theorems of (weak) Pareto equilibria for the generalized constrained multiobjective games are established in noncompact product FC-spaces. Some special cases of our results are also discussed. Our results are new and different from the corresponding known results in the literature. 相似文献
17.
A class of zero-sum, two-person stochastic games is shown to have a value which can be calculated by transfinite iteration
of an operator. The games considered have a countable state space, finite action spaces for each player, and a payoff sufficiently
general to include classical stochastic games as well as Blackwell’s infiniteG
δ games of imperfect information.
Research supported by National Science Foundation Grants DMS-8801085 and DMS-8911548. 相似文献
18.
Ahmed Salem 《Linear and Multilinear Algebra》2013,61(6):683-696
The main goal of this article is to extend the concept of q-special functions of complex variable to q-special matrix functions through the study of a q-gamma and a q-beta matrix function. The q-shifted factorial, q-gamma and q-beta matrix functions are defined and some of their properties are investigated. 相似文献
19.
Rainer BUCKDAHN 《应用数学学报(英文版)》2011,27(4):647-678
In this paper we first investigate zero-sum two-player stochastic differential games with reflection, with the help of theory
of Reflected Backward Stochastic Differential Equations (RBSDEs). We will establish the dynamic programming principle for
the upper and the lower value functions of this kind of stochastic differential games with reflection in a straightforward
way. Then the upper and the lower value functions are proved to be the unique viscosity solutions to the associated upper
and the lower Hamilton-Jacobi-Bellman-Isaacs equations with obstacles, respectively. The method differs significantly from
those used for control problems with reflection, with new techniques developed of interest on its own. Further, we also prove
a new estimate for RBSDEs being sharper than that in the paper of El Karoui, Kapoudjian, Pardoux, Peng and Quenez (1997),
which turns out to be very useful because it allows us to estimate the L
p
-distance of the solutions of two different RBSDEs by the p-th power of the distance of the initial values of the driving forward equations. We also show that the unique viscosity solution
to the approximating Isaacs equation constructed by the penalization method converges to the viscosity solution of the Isaacs
equation with obstacle. 相似文献
20.
A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting
w: E? \mathbb R+{w: E\to {\mathbb R}_+}. The player set is N and the value of a coalition S í N{S \subseteq N} is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n
2 log n) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core member if the core is nonempty. This algorithm improves previous work based on
the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments.
Second we show that the nucleolus of an n-player matching game with a nonempty core can be computed in O(n
4) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas
the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general
matching games. 相似文献