Статті в журналах з теми "Absorbing games with vector payoffs"

This article is about the full analysis of one concrete class of general non-cooperative lexicographic games and its computer programming. In such game, the payoffs of players are lexicographic vector payoffs — m scalar criteria vectors. At the same time, these criteria are strictly ranked on the set of the situations with lexicographic preference. In some such kind of game a Nash's equilibrium may not exist. In the given article the full analysis of one class of dyadic lexicographic games is worked out. Such kind of class is the non-cooperative lexicographic games, where each player has got two pure strategies and the payoff of each player solely depends on the strategies of two players in each situation. Therefore, the player's payoffs are given by 2 × 2 matrices, the elements of which are lexicographic utilities.

The paper is devoted to the study of multicriteria cooperative games with vector payoffs and coalition partition. The imputation which is based on the concept of the Owen value is proposed. We use it for the definition of stable coalition partition for bicriteria games. In three person cooperative game with 0-1 characteristic function the conditions under which the coalition partition is stable are found.

Cooperation plays an important role in dynamic games related to resource management problems. To construct the cooperative behavior in asymmetric (when players possess different discount factors) and multicriteria (when players have vector payoff functions) dynamic games the standard approaches are not applicable. The paper presents the methods based on bargaining schemes to determine the cooperative equilibria in such games. The cooperative strategies and payoffs in asymmetric dynamic games are obtained via the Nash bargaining scheme, while for the multicriteria dynamic games the modified bargaining schemes are applied. To illustrated the presented approaches, dynamic bioresource management problems (fish wars problem) with asymmetric players and vector payoff functions is investigated.

Uncertainty accompanies almost every situation in our lives and it influences our decisions. On many occasions uncertainty is so severe that we can only predict some upper and lower bounds for the outcome of our (collaborative) actions, i.e., payoffs lie in some intervals. Cooperative interval games have been proved useful for solving reward/cost sharing problems in situations with interval data in a cooperative environment. In this paper we propose two procedures for cooperative interval games. Both transform an interval allocation, i.e., a payoff vector whose components are compact intervals of real numbers, into a payoff vector (whose components are real numbers) when the value of the grand coalition becomes known (at once or in multiple stages). The research question addressed here is: How to determine for each player his/her/its payoff generated by cooperation within the grand coalition – in the promised range of payoffs to establish such cooperation – after the uncertainty on the payoff for the grand coalition is resolved? This question is an important one that deserves attention both in the literature and in game practice.

Players’ choices in quantum game schemes are often correlated by a quantum state. This enables players to obtain payoffs that may not be achievable when classical pure or mixed strategies are used. On the other hand, players’ choices can be correlated due to a classical probability distribution, and if no player benefits by a unilateral deviation from the vector of recommended strategies, the probability distribution is a correlated equilibrium. The aim of this paper is to investigate relation between correlated equilibria and Nash equilibria in the MW-type schemes for quantum games.

One of the properties characterizing cooperative game solutions is consistency connecting solution vectors of a cooperative game with finite set of players and its reduced game defined by removing one or more players and by assigning them the payoffs according to some specific principle (e.g., a proposed payoff vector). Consistency of a solution means that any part (defined by a coalition of the original game) of a solution payoff vector belongs to the solution set of the corresponding reduced game. In the paper the proportional solutions for TU-games are defined as those depending only on the proportional excess vectors in the same manner as translation covariant solutions depend on the usual Davis–Maschler excess vectors. The general form of the reduced games defining consistent proportional solutions is given. The efficient, anonymous, proportional TU cooperative game solutions meeting the consistency property with respect to any reduced game are described.

In stochastic games, the player’s payoff is a stochastic variable. In most papers, expected payoff is considered as a payoff, which means the risk neutrality of the players. However, there may exist risk-sensitive players who would take into account “risk” measuring their stochastic payoffs. In the paper, we propose a model of stochastic games with mean-variance payoff functions, which is the sum of expectation and standard deviation multiplied by a coefficient characterizing a player’s attention to risk. We construct a cooperative version of a stochastic game with mean-variance preferences by defining characteristic function using a maxmin approach. The imputation in a cooperative stochastic game with mean-variance preferences is supposed to be a random vector. We construct the core of a cooperative stochastic game with mean-variance preferences. The paper extends existing models of discrete-time stochastic games and approaches to find cooperative solutions in these games.

Blackwell approachability is a framework for reasoning about repeated games with vector-valued payoffs. We introduce predictive Blackwell approachability, where an estimate of the next payoff vector is given, and the decision maker tries to achieve better performance based on the accuracy of that estimator. In order to derive algorithms that achieve predictive Blackwell approachability, we start by showing a powerful connection between four well-known algorithms. Follow-the-regularized-leader (FTRL) and online mirror descent (OMD) are the most prevalent regret minimizers in online convex optimization. In spite of this prevalence, the regret matching (RM) and regret matching+ (RM+) algorithms have been preferred in the practice of solving large-scale games (as the local regret minimizers within the counterfactual regret minimization framework). We show that RM and RM+ are the algorithms that result from running FTRL and OMD, respectively, to select the halfspace to force at all times in the underlying Blackwell approachability game. By applying the predictive variants of FTRL or OMD to this connection, we obtain predictive Blackwell approachability algorithms, as well as predictive variants of RM and RM+. In experiments across 18 common zero-sum extensive-form benchmark games, we show that predictive RM+ coupled with counterfactual regret minimization converges vastly faster than the fastest prior algorithms (CFR+, DCFR, LCFR) across all games but two of the poker games, sometimes by two or more orders of magnitude.

<abstract><p>A new class of fuzzy constrained multi-objective games with fuzzy payoffs (FCMGFPs) is considered in this paper. First, Berge's maximum theorem for the fuzzy-vector-valued function is obtained. Based on this theorem and the Fan-Glicksberg fixed point theorem, the existence theorem of the fuzzy Pareto-Nash equilibrium for the FCMGFP is established. Second, the abstract rationality function for the FCMGFP is given by using a nonlinear scalarization function of interval vectors. Finally, a series of results, such as structural stability ($ (\gamma, \epsilon) $-stability) and robustness to $ \epsilon $-equilibrium ($ (\gamma, \epsilon) $-robustness), are obtained.</p></abstract>

Consider N players, respectively owning x1, x2, …, xN monetary units, who play a sequence of games, winning from and losing to each other integer amounts according to fixed rules. The sequence stops as soon as (at least) one player is ruined. We are interested in the ruin process of these N players, i.e. in the probability that a given player is ruined first, and also in the expected ruin time. This problem is called the N-player ruin problem. In this paper, the problem is set up as a multivariate absorbing Markov chain with an absorbing state corresponding to the ruin of each player. This is then discussed in the context of phase-type distributions where each phase is represented by a vector of size N and the distribution has as many absorbing points as there are ruin events. We use this modified phase-type distribution to obtain an explicit solution to the N-player problem. We define a partition of the set of transient states into different levels, and on it give an extension of the folding algorithm (see Ye and Li (1994)). This provides an efficient computational procedure for calculating some of the key measures.

ConsiderNplayers, respectively owningx1,x2, …,xNmonetary units, who play a sequence of games, winning from and losing to each other integer amounts according to fixed rules. The sequence stops as soon as (at least) one player is ruined. We are interested in the ruin process of theseNplayers, i.e. in the probability that a given player is ruined first, and also in the expected ruin time. This problem is called theN-player ruin problem. In this paper, the problem is set up as a multivariate absorbing Markov chain with an absorbing state corresponding to the ruin of each player. This is then discussed in the context of phase-type distributions where each phase is represented by a vector of sizeNand the distribution has as many absorbing points as there are ruin events. We use this modified phase-type distribution to obtain an explicit solution to theN-player problem. We define a partition of the set of transient states into different levels, and on it give an extension of the folding algorithm (see Ye and Li (1994)). This provides an efficient computational procedure for calculating some of the key measures.

Purpose In recent decades, development of effective methods for optimizing a set of conflicted objective functions has been absorbing an increasing interest from researchers. This refers to the essence of real-life engineering systems and complex natural mechanisms which are generally multi-modal, non-convex and multi-criterion. Until now, several deterministic and stochastic methods have been proposed to cope with such complex systems. Advanced soft computational methods such as evolutionary games (cooperative and non-cooperative), Pareto-based techniques, fuzzy evolutionary methods, cooperative bio-inspired algorithms and neuro-evolutionary systems have effectively come to the aid of researchers to build up efficient paradigms with application to vector optimization. The paper aims to discuss this issue. Design/methodology/approach A novel hybrid algorithm called synchronous self-learning Pareto strategy (SSLPS) is presented for the sake of vector optimization. The method is the ensemble of evolutionary algorithms (EA), swarm intelligence (SI), adaptive version of self-organizing map (CSOM) and a data shuffling mechanism. EA are powerful numerical optimization algorithms capable of finding a global extreme point over a wide exploration domain. SI techniques (the swarm of bees in our case) can improve both intensification and robustness of exploration. CSOM network is an unsupervised learning methodology which learns the characteristics of non-dominated solutions and, thus, enhances the quality of the Pareto front. Findings To prove the effectiveness of the proposed method, the authors engage a set of well-known benchmark functions and some well-known rival optimization methods. Additionally, SSLPS is employed for optimal design of shape memory alloy actuator as a nonlinear multi-modal real-world engineering problem. The experiments show the acceptable potential of SSLPS for handling both numerical and engineering multi-objective problems. Originality/value To the author’s best knowledge, the proposed algorithm is among the rare multi-objective methods which fosters the use of automated unsupervised learning for increasing the intensity of Pareto front (while preserving the diversity). Also, the research evaluates the power of hybridization of SI and EA for efficient search.

The fundamental methodological development of the categorical matrix as one of the most powerful and the most effective i n s t r u m e n t s of reflexive thought-activity, philosophical and scientific thought-activity and professional methodologization was carried out in the problem field of two oppositely directed and at the same time most promising trends in the methodology development as a newly appeared w o r l d of birth, development and manifestation of hitherto unexplored possibilities of conscious ability and hidden resources of humans pure thinking actualization. The first direction in the formation of this unique world is connected with the emergence of the s p h e r e of professional methodologization as a unique reflexive p r a c t i c e of the methodology itself, the essence of which is in the freedom of thought existence of a person or a group with the forms, methods, means of consciously and self-consciously carried out activity, the second – in the creation of all possible i d e a l s of meta-theorizing and meta-methodologization, where the subject of the last is an a r s e n a l of the latest means and tools of constantly renewed at the “meta-” level of methodological reflection on previously acquired tools of thought-activity. It is argued that the synthesis result of these two trends is the formation of the categorical order of a methodology in its central link – in the innovative form of the categorical m a t r i x, which integrates the essential, worldview universal and culturally significant k n o w l e d g e in mutually complementary unity of the methodology-as-an-action and methodology-as-a-practice. Based on the principles, regularities and standards of the author’s concept of creating a categorical matrix, a thought-reflexive substantiation received the first and the second v e r s i o n s of the philosophically oriented, epistemically integral, actionally organized and canonically perfected vita-cultural methodology as a s t a n d a r d of modern methodology in general in their constructive comparison as stages of the newest evolution of ratio-humanitarian knowledge about the forms, methods, norms, means and tools of professional methodologization. In general, the methodological o p t i c s of the argued typological creation of the named matrix is constructed according to the canons and parameters of post-non-classical scientific rationality and in the form of a five-module set of lenses-instruments of reflexive thought-activity from relatively simple to the most complex at the following levels: specific (quaternary or quintet thought-scheme), individual (the very construction of the matrix in the unity of its clearly classified according to the dialectical categories of the inner part and the outer contour), special (the typological approach in the indivisibility of its concepts, principles, procedures and intellectual tools), general (the sphere of professionally implemented methodologization), universal (vitacultural methodology as the canonical form of methodology in general). T h e f i r s t version of the categorical matrix of the world of methodology and the sphere of methodologization, which was created in early 2012 and first presented to the general public of researchers, has five main a d v a n t a g e s: a) in the harmonized picture of conceptual-categorical means highlights the dialectical complementarity and ontophenomenal unity of methodology and methodologization that enables a high functional self-organization of consciousness of the methodologists’ group in its synergistic existential environment – in reality of pure thinking; b) in the central part of the matrix, by the principle of quintet, arranges five methodological categories in horizontal and vertical, organizing them into separate categorical t a x a, and thus fixes the essential categoric mosaic of the modern methodology; c) successfully names the binary poles of the matrix’s outer contour: “the world of methodology – the sphere of methodologization” and “thinking-activity as the basis of culture – a step-by-step implemented vitacultural methodologization”; d) establishes the latest methodological disciplines – methodosophy, methodologics, methodoengineering – and outlines their subject fields in the text; e) at the intersection of the three fundamentals of the methodology in the lower right corner of the matrix, it places the fourth foundation – philosophical methodologizations and methodology, which at the level of comprehensively significant goes beyond empirics and social experience into conscious acts of the substance existence of pure thinking, the existential c o r r e l a t e of which is a methodological thinking. T h e s e c o n d version of the categorical matrix of vitacultural methodology, which was designed this year, has more extensive and perfect cartography, which primarily from now on concerns the two-axis – semantic and categorical – its outer contour. This newly created matrix has five reflexively reasoned a d v a n t a g e s, which at the same time clearly establish the evolutionary shift in the development of methodological knowledge over the past decade of thinking-deed creativity: 1) fundamental categorical universals, consolidating the self-development unity of the world of the methodology and the sphere of methodologization of the outer contour, received clarifying conceptual-terminological definitions, covering six attributedly inherent features in the general direction of creating a particularly favorable, modular-developmental, space of actualization and existentializing the expanded conscious ability of each participant of problem-conflict communication; 2) the upper and lower poles of the matrix’s outer contour are considered, on the one hand, the methodology as an obligatory component of culture in eight coordinates of worldview here-existence and in its semantic, graphic-schematic, means-instrumental and conceptual-categorical enrichment, on the other – a five-level organization of methodological knowledge (philosophical, general scientific, subject-scientific, subject-thematic and specific-situational methodologies), the operation of which is most fully implemented in the metasystem of vitacultural (canonical) methodologization; 3) the latest methodology, essentially based on philosophical knowledge, one of the most important directions of its development justifies the need for methodological reconstruction of the main problems of philosophy, but from a special, supersubjective, reflexive, point of view: from the completeness of the a d e q u a c y of consciously applied foundations, principles, rules, conceptual resources and categorical means of the complexity or comprehended primacy of a separate fundamental problem; a number of such problems are fixed in the outline of the matrix: “being – consciousness,” “human – world,” “culture – life,” “philosophy – social experience,” “science – art,” “theory – practice,” “consciousness (thinking) – activity,” “thinking – commitment,” “thought – act”; at the same time, super-reflexive transformations in these problematic niches of methodologization should be based on the innovative achievements of advanced methodological training, namely, on the modern achievements of the philosophical methodology, the reflexive-action scenario of metamethodologization has been worked out, the emergence of the metatheory of consciousness, the methodological optics of the post-non-classical type of scientific rationality and on the establishment of professional methodologization as a unique freedom-practice of the methodology itself, as well as compliance with the requirements of the author’s principle of the thinking and performance unity, that received an essential reflection in the concept and categorical concept of “thinking-activity,” containing a set of advantages: enriches the arsenal of categorical means, makes possible the implementation of a cyclic-action approach and the prospects for the implementation of organizational-action games, reorients the intellectual resources of consciousness to the canonical rhythms of methodologization; 4) the methodology in its separate formation now goes to the realisation of exemplary, canonically completed events of its own here-existence, that is, to the construction of the general scheme of the methodological canon and the substantiation of their more or less complete systematics; it is proved that any repeated reflexivity and especially postaction super-reflexivity in a competent methodological performance gravitate to an deed canon, which is a methodological i n v a r i a n t as one of its vitacultural standards, that is differently implemented in objectified products of professional methodologization and pure thinking itself (a vivid example of such a canon is the author’s methodological optics of a five-module set of lenses-tools of this study as an effective thinking-activity); it is argued the intransitive significance of the logical structure of the psychological canon and the premises of the emergence of the V.A. Romenets’ canonical psychology and our experience in carrying out the metatheoretic reconstruction of the subject field of the last; through a chain of generalizations, it is confirmed that the vitacultural methodology, covering transcendent and immanent, noumenal and phenomenal, conscious and active, is a great thinking-act c a n o n, confirming the following preliminary conclusions: a) any canonization as a mandatory procedure is a matter of methodology, b) each philosophically mature, scientifically comprehensive and empirically validated methodology constitutes a great canon, c) from the idea of the methodological canon it is necessary to move to the elaboration of the hierarchical system of such canons as the most perfect organizations of realizing the conscious ability of a person, d) a holistic metasystem of methodology as a canon of a great deed can be obtained only by using all available resources of professional methodologization and at the final stage of its super-reflexive postact, e) the methodological canon in its global dimensions, organizing the interpenetration of methodology and methodologization as two mega-realities, has a hierarchically modular, step-by-step construction (methodological and metamethodological stages of development, three methodological optics of scientific rationality, a set of methodological approaches, five methodological modules, various layers of methodological tools), f) in any case, the methodological canon is a consciously mature, with access to reflection and self-reflection, the source of a standard carried out thinking-activity, an integral engine of the act of full-fledged methodologization; 5) the vitacultural methodology in its canonical provision achieves the complete realisation of the a c t i o n s of thinking-activity, methodological reflection, competent methodologization in their single and exceptional step-by-step, mostly covital, existence as responsible thinking-activity; so the ideal-real, exemplary authentic reality of methodologization appears, which all the time is being created anew in the event e x i s t e n c e of compatible thought communication on the verge of transcendental and immanent, noumenal and phenomenal, spiritual and natural, substantive and random, unknown and understandable, objective and subjective, organized and chaotic, developing and ossified, that is, in the situational flow of the here-existence of the step-by-step-dependent substances of consciousness, thinking, thought according to the canon “here-now-full-always”; in this interpretation, the newly created categorical matrix constitutes one of the most instrumentally perfect methodological canons of the methodology itself, where the act of methodologization unfolds as a component-by-component evolution of a fully realized e v e n t, which covers: p r e-s i t u a t i o n – the experience of transcendence of the thinking person as a base of the co-rhythmic actualization of their intentional fields of consciousness and thinking; s i t u a t i o n – the acting-cyclical creation of the modular-developmental space of team thinking-implementation as a regularly stable restoration of the special problem-communication tension of human essential forces, characterized by common significance, transcendental source, collision, drama; m o t i v a t i o n – overcoming the conflict of problem-situational reality, overcoming the chaos of polymotivation of participants in thought-communication and choosing the general direction of movement-progress forward, which is confirmed in such features of methodologization as the elimination of conflict conditions and the formation of a single goal of further cooperation, the development of synthetic inspiration for joint entry into the substance flows of pure productive thinking and the correlation of the main vector of the polymotivation field with a reflexive ideal of methodological creativity; d e e d a c t i o n – a thinking-active action that significantly disrupts the problem-conflict situation through the creation of favorable conditions for the spontaneous fountain of thoughts, ideas, meanings, and thought-schemes of communicants, but in the self-organizational weaving of the pulsation of the consciousness functionals on the verge of the apogee of ecstatic, self-absorbing, tension of spiritual forces and mental abilities of each, combining four attributive characteristics of methodologization: implementation of the very act-event of thinking-activity, variable-changeable scenario of the course of this step-by-step action in order to obtain the desired products of pure thinking and polyreflexification, achievement of creative ecstasy of the team search for ways and means of solving the worked-out problem, personal growth and enrichment of the transcendental experience of participants; a f t e r a c t i o n – final reflection and the resulting self-reflection of productivity and success of team or individually performed thinking-activity and coverage with an expanded conscious view in a position over k n o w l e d g e of four types: about objects, about the activity itself, reflective and purely personal; at the same time, the incompleteness of the act of methodologization after achieving the goal and solving the dual task of intellectual cooperation has several reasons (ontological inexhaustibility of being, its phenomenal diversity, epistemological infinity of the path to truth, epistemological unlimitedness and relativity of the world, psychological ambivalence of feelings after the commited, the impossibility of creating an absolutely universal methodological optics), while its attributive canon is the implementation of reflexive-action closure of methodological thinking with various reflexive identifications.

In this paper, we extend previous results on weak approachability in generalized quitting games with vector payoffs to the general case of absorbing games. Specifically, we show that a necessary condition and a different sufficient condition for weak approachability of a convex set, established by Flesch, Laraki, and Perchet, remain valid in the general case. To do so, we extend results on Blackwell approachability to a setup in which stage weights depend on past actions as well as the current action of player 1 (the approaching player). Additionally, we prove that the strategy used to approach the convex set can be defined in blocks of fixed length, and so it has bounded memory and can be implemented by a finite automata.

A seminal study showed repeated games with vector payoffs, which has had wide-ranging applications to decision making under uncertainty. Although this study characterized the achievable guarantees in such games under the long-run average payoff criterion, the characterization and computation of these guarantees under the discounted payoff criterion have remained a significant gap in the literature. In “An Approximate Dynamic Programming Approach to Repeated Games with Vector Losses,” V. Kamble, P. Loiseau, and J. Walrand develop a set-valued dynamic programming approach along with an approximation framework to fully address this problem. This theory results in new algorithms that beat the state of the art for applications such as exact regret minimization in the well-known problem of prediction under expert advice.

Regret matching is a widely-used algorithm for learning how to act. We begin by proving that regrets on actions in one setting (game) can be transferred to warm start the regrets for solving a different setting with same structure but different payoffs that can be written as a function of parameters. We prove how this can be done by carefully discounting the prior regrets. This provides, to our knowledge, the first principled warm-starting method for no-regret learning. It also extends to warm-starting the widely-adopted counterfactual regret minimization (CFR) algorithm for large incomplete-information games; we show this experimentally as well. We then study optimizing a parameter vector for a player in a two-player zero-sum game (e.g., optimizing bet sizes to use in poker). We propose a custom gradient descent algorithm that provably finds a locally optimal parameter vector while leveraging our warm-start theory to significantly save regret-matching iterations at each step. It optimizes the parameter vector while simultaneously finding an equilibrium. We present experiments in no-limit Leduc Hold'em and no-limit Texas Hold'em to optimize bet sizing. This amounts to the first action abstraction algorithm (algorithm for selecting a small number of discrete actions to use from a continuum of actions---a key preprocessing step for solving large games using current equilibrium-finding algorithms) with convergence guarantees for extensive-form games.

AbstractBerge’s notion of equilibrium represents a complementary alternative to the Nash equilibrium when modeling socioeconomic behavior and human interactions. While the notion of Nash equilibrium is based on self-interest, as players seek to maximize their own payoffs given the action of the other players, the idea behind Berge equilibrium is mutual support, as given the action of one of the players, all others select their actions looking for her best interest. However, because of the demanding conditions involved, the existence of Berge equilibria is rarely guaranteed. In this paper, we propose vector-valued normal-form games as a unified framework in which to study and extend the concept of Berge equilibrium. Based on the equilibria of the so-called altruistic game, we introduce new equilibrium concepts which constitute different relaxations of Berge’s notion, although they still retain the underlying idea of mutual support. We establish the links between these new equilibria, Nash equilibrium, Berge equilibrium, and other related concepts already existing in the literature. Our approach has the advantage that it permits the incorporation of preference information to identify the equilibria which are consistent with different altruistic attitudes of the players.