Optimization and Games for Controllable Markov Chains

The controlled Partly Observable Markov Decision Process (POMDP) architecture has shown to be effective in a variety of fields where one is required to disclose only partial knowledge about the problem’s structure and parameters. Since some state variables are difficult to track and measure correctly, it may be more beneficial to base judgments on less accurate information. This chapter focuses on the design of an observer for a class of partially observable ergodic homogeneous finite Markov chains. The major objective of the suggested approach is to derive the formulas for computing an observer and, as a consequence, the best control strategy. We create a new variable that combines the policy, the observation kernel, and the distribution vector in order to solve the issue. To retrieve the important variables, we derive the formulas. The POMDP model’s parameters are being learned in a dynamic context in this work. The development of the adaptive policies is based on an identification method, in which we count the number of unobserved events to estimate the components of the utility and transition matrices. The practical applications of the theoretical concerns addressed to a portfolio optimization problem are demonstrated through the use of a numerical example.

We provide an approach to locating the Nash equilibrium in this chapter. The technique depends on identifying a scalar \(\lambda ^{*}\) and the associated strategies \(d^{*}(\lambda ^{*})\) fixing particular boundaries (min and max) that belong to the Pareto front. Bounds refer to limits placed by the player over the Pareto front that form a specific decision region where the strategies can be selected. We first use a nonlinear programming issue to illustrate the Pareto front of the game, introducing a set of linear constraints for the Markov chain game based on the c-variable technique. We suggest using the Euler method and a penalty function with regularization to solve the strong Nash equilibrium issue. The convergence to a single (strong) equilibrium point is ensured using Tikhonov’s regularization method. The subsequent single-objective restricted problems that result from using the regularized functional of the game were then solved using a nonlinear programming technique. We use the gradient approach to resolve the first-order optimality requirements in order to accomplish the aim. The approach solves an optimization issue by adding linear constraints necessary to identify the best strong strategy, d (lambda d), starting from a utopia point (Pareto optimum point) given an initial lambda of the individual objectives. We demonstrate that the game’s functional in the regularized issue decreases and ultimately converges, demonstrating the presence and exclusivity of strong Nash equilibrium (Pareto-optimal Nash equilibrium). We also provide a method for calculating the Markov chain games’ strong Stackelberg/Nash equilibrium. The minimization of the \(L p-\)norm, which shortens the distance to the utopian point in Euclidian space, is taken into consideration while solving the cooperative n-leaders and m-followers Markov game. Next, we formulate a Pareto-optimal solution to the optimization issue. For finding the strong Lp-Stackelberg/Nash equilibrium, we use a bi-level programming technique that is carried out through extraproximal optimization.

The actions that players naturally and frequently choose to perform throughout a repeated game are the “best-reply strategy”. Making the determination that such strategies lead to an equilibrium point is a difficult and sensitive operation since, often, the behavior of a single cost-function when such best-reply techniques are used turns out to be non-monotonic. The convergence to a stable equilibrium is not always guaranteed, even in repeated games. In this chapter, we demonstrate that the best-reply actions surely lead to an equilibrium point for a type of finite controlled Markov Chains dynamic games. The Lyapunov Games concept, which is based on the design of a unique Lyapunov function (associated with a unique cost function) that monotonically reduces (non-increases) throughout the game, achieves this result. We provide a technique for creating a Lyapunov-like function that describes how players behave in a recurrent Markov chain game. The Lyapunov-like function replaces the components of the ergodic system, which simulate players’ anticipated behavior in one-shot games, for the recursive process. We first provide a non-converging state-value function that varies (increases and decreases) between states of the repeating Markov game in order to demonstrate our claim. Then, we demonstrate that using a one-step-ahead fixed-local-optimal approach, it is possible to describe that function in a recursive format. Thus, we show that the previous recursive expression for the repeated game can be used to construct a Lyapunov-like function; the resulting Lyapunov-like function is a monotonic function that can only decrease (or remain the same) over time, regardless of the initial distribution of probabilities. The best-reply methods examined in this study are connected to what are known as pure and stationary fixed-local-optimal actions, or, to put it another way, with one step ahead optimization algorithms that are extensively employed in the Artificial Intelligence theory. The Bank Marketing Campaigns Game and the Duel Game with Best-Reply Strategies Application serve as examples of the proposed strategy.

This chapter presents an analytical method for computing Bayesian incentive-compatible mechanisms where the private information is revealed following a class of controllable Markov games. We take into account a dynamic setting where decisions are made after a number of limited time periods. Our approach includes a new variable that denotes the outcome of the distribution vector, the strategies, and the mechanism design. We develop the relationships needed to calculate the relevant variables analytically. The issue becomes computationally tractable with the addition of this variable. The technique uses a Reinforcement Learning (RL) methodology to calculate a mechanism that is nearly optimum and in equilibrium with the game’s winning strategy. We employ the Bayesian-Nash equilibrium concept as the default equilibrium idea in the game. There are several equilibria, which presents an intriguing problem because there isn’t a single mechanism that is ideal for the goal of profit maximization. To address this issue, we apply Tikhonov’s approach and offer a regularization parameter. We show the game’s equilibrium and convergence to a single mechanism that is compatible with incentives. This results in numerous game theory issue areas having unique and significantly improved results, as well as incentive-compatible processes that are consistent with the equilibrium of the game. To illustrate the recommended method, we provide a numerical example in the context of a dynamic public finance model with incomplete knowledge.

An intelligent agent suggests an autonomous entity, which manages and learns actions to be taken towards achieving goals. The issue is that it is difficult to build a method that can calculate effective judgments that maximize the overall reward of interacting agents upon an environment with unknown, partial, and uncertain information, according to reports in the literature on Artificial Intelligence (AI). This chapter offers a solution to these problems: a foundation for Bayesian Partially Observable Markov Games (BPOMGs) supported by an AI strategy. The nucleus’s structure is governed by three essential concepts: game theory, learning, and inference. The first thing we do is provide a brand-new general Bayesian strategy that is designed for games that take into account both the partial information provided by the Bayesian model and the incomplete information on the states of the Markov system. This approach uses a Partly Observable Markov Game (POMG) to deal with execution uncertainty. Second, we expand design theory to include joint observer design and mechanism design (both unknown). Because agents behave in their own self-interest, the mechanism is created to persuade them not to divulge their personal information and to get a certain result. The purpose of the joint observer design is to depict the possibility that agents may not be motivated to deliver accurate information about their states. The transition matrices, which are also unknown, are estimated by the agents using a model that uses a Reinforcement Learning (RL) technique at each time step. The result is an expanded POMG model that adds a new variable and suggests an analytical method for computing both the observer design and the mechanism design (both unknown). The suggested expansion makes the computationally challenging game theory issue tractable. The variables of relevance for each agent, such as the observation kernels, joint observers, mechanisms, strategies, and distribution vectors, are derived relations in order to retrieve them analytically. By simulating a game-theoretic examination of the patrolling issue that involves developing the mechanism, calculating the observers, and using an RL technique, the utility and efficacy of the suggested nucleus are confirmed.

The term “bargaining game” describes a scenario in which participants may reach a win-win agreement. There is a conflict of interest here over whether an agreement should be reached or whether no agreement should be reached without the consent of each player. Amazingly, negotiating protocols, duopoly market games, business transactions, arbitration, and other key scenarios have all used bargaining and its game-theoretic solutions. The underpinning for all of these research applications is equilibrium computation. This chapter explores the theory behind bargaining games and offers a way for solving the game-theoretic models of bargaining put out by Nash and Kalai-Smorodinsky, which suggest a beautiful axiomatic solution to the problem based on several fairness standards. We consider a class of continuous-time, controllable, and ergodic Markov games. The Nash bargaining solution is first introduced and axiomatized. The Kalai-Smorodinsky approach, which adds the monotonicity postulate to the Nash’s model, is then presented. We recommend using a bargaining solver to resolve the issue, which is carried out iteratively using a set of nonlinear equations represented by the Lagrange principle and the Tikhonov regularization approach to guarantee convergence to a particular equilibrium point. Each equation in this solver is an optimization problem for which the necessary condition of a minimum is solved using the projection gradient method. This chapter’s key finding illustrates how equilibrium calculations work in bargaining games. We specifically discuss the convergence analysis and rate of convergence of the suggested technique. A numerical example contrasting the Nash and Kalai-Smorodinsky bargaining solution problem is used to illustrate the value of the considered method.

In a conventional non-cooperative negotiating scenario, two or more forward-thinking participants make offers and counteroffers alternately until an agreement is achieved, with a penalty taking into account the length of time it takes players to make a decision. We provide a game that helps myopic participants achieve equilibrium as if they were forward-thinking agents. One of the game’s main mechanics is that players are penalized for deviating from their prior best reply plan as well as for the amount of time they spend to make decisions at each stage of play. Our chapter adds to existing research on typical myopic agent bargaining while also broadening the class of processes and functions that may be used to define and apply Rubinstein’s non-cooperative bargaining solutions.

The Nash bargaining game theory technique is used in this chapter to examine and provide a solution to the transfer pricing problem. We analyze a company with sequential transfers among its several divisions, where central management decides on the transfer price to maximize operational profitability. Throughout the negotiation process, the price shifting between divisions is a tool for bargaining. First, we take into account a point of contention (status quo) between the firm’s divisions, which serves as a deterrent. We offer a methodology and framework for calculating the disagreement point that are based on the Nash equilibrium approach. Then, we introduce the bargaining solution, which is a single-valued function that chooses an outcome from each bargaining problem’s feasible pay-offs. This solution is the result of cooperation between the company divisions involved in the transfer pricing problem. The agreement achieved by the divisions in the game is the most desirable option within the range of plausible outcomes that results in a distribution of the transfer price between divisions that maximizes profit. We provide an optimization approach for computing the negotiating solution. The method’s usefulness is demonstrated through a number of examples, including Markov models in both continuous and discrete time.