Linear-quadratic Gaussian Games with Asymmetric Information:
Belief Corrections Using the Opponents Actions111We thank Sam Cohen and Yanwei Jia for helpful discussions and comments on the paper.
Abstract
We consider two-player non-zero-sum linear-quadratic Gaussian games in which both players aim to minimize a quadratic cost function while controlling a linear and stochastic state process using linear policies. The system is partially observable with asymmetric information available to the players. In particular, each player has a private and noisy measurement of the state process but can see the history of their opponent’s actions. The challenge of this asymmetry is that it introduces correlations into the players’ belief processes for the state and leads to circularity in their beliefs about their opponents beliefs. We show that by leveraging the information available through their opponent’s actions, both players can enhance their state estimates and improve their overall outcomes. In addition, we provide a closed-form solution for the Bayesian updating rule of their belief process. We show that there is a Nash equilibrium which is linear in the estimation of the state and with a value function incorporating terms that arise due to errors in the state estimation. We illustrate the results through an application to bargaining which demonstrates the value of these information corrections.
1 Introduction
In the realm of game theory, two-player bargaining games have been extensively studied due to their practical implications in various domains [16, 4, 21, 9]. The types of game of interest here typically occur in negotiations between large organizations. One example is the negotiation of extraction rights between a host country and a foreign mining company. The host country seeks to maximize its economic benefits while ensuring sustainable resource management, while the foreign company aims to secure profitable extraction agreements. Another relevant scenario is the negotiation of rebates on pharmaceutical purchases between a manufacturer and a retail chain. The manufacturer desires to maximize its sales volume and market share, while the retail chain seeks competitive pricing to attract customers. To capture these situations we consider negotiations over a good whose value changes through time and assume that there are a fixed number of rounds of negotiation, where at each round both players present their bids simultaneously. In practice, both players possess limited and potentially asymmetric information about the good under negotiation. This provides compelling motivation for the mathematical modeling and analysis of two-player stochastic games where there is asymmetric information, which can shed light on the negotiation dynamics, identify the key parameters affecting the bargaining outcome, and provide insights into the search for information.
In the game setting where the underlying state dynamics are only partially observed, the players’ observation histories expand over time, leading to strategies with expanding domains due to the dynamic and sequential nature of such games. To address this issue, a commonly employed technique is to summarize the time-expanding histories into sufficient statistics. This enables the application of the Dynamic Programming Principle (DPP), allowing such sequential decision-making problems to be solved through nested sub-optimization problems using the Bellman equation. The sufficient statistics may vary from player to player, depending on the observations available to each player. In the case of symmetric information in extensive form games, the concept of a Markov perfect equilibrium has been introduced [10], in which the players’ strategies are determined solely by past events that are relevant to their payoffs, rather than the entire history. See also [3, 15]. However, for games with asymmetric information, identifying the appropriate sufficient statistics poses a significant challenge.
A quantity commonly used as the sufficient statistic is a posterior belief of the state dynamics, constructed using the available observations and Bayes formula. The main difficulty in this context is the emergence of private beliefs, the fact that different agents in the system may have different (private) observations about the same unknown quantity, which introduces dependence among the agents’ beliefs. One way to avoid this problem is to consider models in which private beliefs either do not exist (such as considering symmetric information games, or asymmetric but independent observations [18, 19]), or, if they do exist, they are not taken into account in the agents’ strategies (see for example the concept of “public perfect equilibrium” [1]). Another closely related line of work considers common-information based Markov perfect equilibria, which breaks the history into the common and private parts. This idea was first introduced in [11] for finite games and then generalized in [7] to linear-quadratic games. See [12] for an extension to a more general setting and [6] for an application to cyber-physical systems. One key assumption made in this approach is that players’ posterior beliefs about the system state, conditioned on their common information, are independent of the strategies used by the players in the past. This decouples the sequential rationality and belief consistency, resulting in a simplification in calculating the equilibria, and obviating the need to define (possibly correlated) private beliefs.
To better understand the challenge posed by having private beliefs, let us consider the following simplified scenario. We have two players, and , who collect private information about an unknown variable at each time step. Player acts based on her own private belief about , and expects that Player will do the same. Although both players can observe each other’s actions, they cannot observe each other’s private beliefs. This means that Player must form a belief about Player ’s private belief in order to interpret the actions from player , and take this into account when making her own decisions. However, this creates a chain of “belief about belief” that must be taken into consideration, which extends as long as each player’s beliefs remain private. Due to the symmetry of the information structure, Player must do the same. Thus, Player needs to form beliefs about beliefs about beliefs of Player , creating an increasingly complex hierarchy of beliefs. This chain only stops when a belief in one step becomes a public function of the beliefs in the previous steps.
Indeed, stochastic games with private beliefs have been identified as an open problem in the past decade [13, 14]. There have been a few attempts to address this challenging issue. In [8] a model with an unknown (but static) state of the world is considered, where each player has a private noisy observation of at timestamp . The private observations are independent given . The authors specialize this setting to the case of a linear-quadratic Gaussian non-zero-sum game where is a Gaussian variable and players’ observations are generated through a linear Gaussian model from . The main contribution of the paper is to show that, due to the conditional independence of the private signals given , the private belief chain stops at the second step and players’ beliefs about others’ beliefs are public functions of their own beliefs (the first step beliefs). In addition, the authors show that the perfect Bayesian equilibrium (PBE) for their model is a linear function of a players’ private Kalman filter estimator. For a more general setting when the (partially) unknown quantity is the underlying stochastic process itself, [13] considers a zero-sum two-player game formulation in which each agent observes a private linear signal of the underlying process with non-degenerate Gaussian noise. The private signals at each time step are independent conditioned on the true value of the state at the same time. Similarly, the author shows that the private belief chain stops at the second step. However, the sufficient statistics developed in [13] are not completely correct, impeding the application of the DPP and making it impossible to derive the Nash equilibrium solutions. We will give a detailed technical discussion in Section 2.2.
Our Contributions.
Motivated by bargaining games, we consider a two-player non-zero-sum game with linear dynamics and quadratic cost functions. Both players cannot directly observe the dynamics but instead rely on private signal processes that are linear in the state process with some additive Gaussian noise. In addition, both players adopt linear policies to control the partially observable dynamics and each player can also observe the past actions taken by the other player.
The novelty of our approach is that we show how to use the opponent’s actions as additional information to correct the state estimate of the previous time step via a modified Kalman filtering procedure. For the partially observable setting, we formally derive the updating rule for the belief process and provide an explicit formula for the projection of the unknown state process onto the filtration generated by the information flow that is available to each player in Theorem 2.4. In addition, we prove a conditional version of the DPP that works in the game setting in Theorem 3.1. With the sufficient statistics and DPP in hand, we are able to derive a Nash equilibrium solution for the two-player game in Theorem 3.4. Finally, in Section 4, we extend the above-mentioned results to a more general setting where part of the state is fully observable and part of the state is partially observable through the signal process. In the mixed partially and fully observable setting, we establish parallel findings– specifically, the updating rule for the sufficient statistics in Theorem 4.2 and the Nash equilibrium in Theorem 4.3. To the best of our knowledge, this is the first work that rigorously characterizes the equilibrium solution under private belief when the underlying state dynamics are partially observable. To demonstrate the performance of our framework, we conclude the paper in Section 5 by discussing a bargaining game example and give a numerical illustration of the effects of using information corrections.
2 Problem Set-up
We consider a general setting for games with two players, and , under partial observations and asymmetric information. The joint dynamics of the state process takes a linear form :
| (2.1) |
with initial value , and the controls of and are and , respectively. Here, for each , the process noise is an i.i.d. sample from with and we have the model parameters , , and .
Information Structure.
At the time , player is not able to observe but instead believes that the initial state is drawn from a Gaussian distribution. Namely, from the view point of player ,
| (2.2) |
where is their own initial constant and is a known constant covariance matrix. After that, player observes the following noisy state signal (or measurement) :
| (2.3) |
with a sequence of i.i.d. random variables. Here and . Similarly, player believes that the initial state is drawn from a Gaussian distribution:
| (2.4) |
with their own initial constant and known constant . Thereafter player observes the following noisy state signal :
| (2.5) |
with a sequence of i.i.d. random variables. For simplicity we assume that are independent from . In addition, and .
We follow [13] to define games with perfect, imperfect, and partial observations:
-
(a)
If the observation matrices and are both the identity matrix and there is no measurement noise, that is, the covariance matrices and , we have a game with full (or perfect) observation. In other words, the players’ observation is .
-
(b)
If the observation matrices and are the identity matrix and there is measurement noise, we have a game with imperfect observation. Namely, the players’ observations are of the form
-
(c)
If the observation matrices are not the identity and there is measurement noise, as in
we have a game with partial observation.
Both players make their decisions based on the public and private information available to them. We write and for the private signals players P and E receive up to time , respectively. Let and denote the control history of player and player up to time , respectively.
We assume is the information (or history) available to player and is the information available to player for them to make decisions at time , where and follow:
| (2.6) |
Note that the covariance matrices are known to both players. In the posterior update of a Gaussian distribution, sufficient statistics involve both the mean and covariance matrix. Knowing is essential for both players to update their posterior covariance matrices. In addition, we highlight that both players know all the model parameters.
Cost Function.
We consider a non-zero sum game between player and player where they strive to minimize their own cost functions. Player ’s () cost function is given by
| (2.7) |
with cost parameters , , and .
For the well-definedness of the game, we summarize the assumptions on the model parameters, initial state, and noise.
Assumption 2.1 (Parameters, Initial State, and Noise).
For ,
-
1.
and are zero-mean, i.i.d. Gaussian random variables that are independent from and each other and such that is positive definite and is positive definite;
-
2.
Both matrices and have rank for .
-
3.
The matrices are non-singular for ;
-
4.
The cost matrices , for are positive semi-definite, and for are positive definite.
Under the assumptions we make on and , we exclude the perfect information case as we require and to be positive definite. This is a challenging scenario to study as the agent cannot get precise information for any coordinate of the state process. On the other hand, since and have rank , the signal process will reveal aggregated information from all of the coordinates. Hence the agent is still capable of gradually learning each coordinate of the state process.
2.1 Sufficient Statistics: Decentralized Kalman Filtering with Information Correction
To better demonstrate the sufficient statistics of Kalman filtering in the game setting, we start with a brief discussion of some existing results in the single-agent setting.
2.1.1 Preliminary: Single-agent setting
Suppose there is a single player who controls the state dynamics (2.1):
| (2.8) |
where is the initial position and are the controls from player .
Information Structure.
In this single-player case player believes that the initial state is drawn from a Gaussian distribution at the time :
| (2.9) |
and thereafter player observes the following noisy state signal :
| (2.10) |
with a sequence of i.i.d. random variables. Here and .
Assume the information available to player to make a decision at time follows:
| (2.11) |
then we have the following result characterizing player ’s belief in the state.
Theorem 2.3.
[17, (5.3-39)-(5.3-42)] The sufficient statistic for player P at decision time is . Namely player P believes that . For time , the distribution of the physical state calculated by player , by conditioning on the private information available to him at time , is given by
| (2.12) |
where
| (2.13a) | ||||
| (2.13b) | ||||
| (2.13c) | ||||
| (2.13d) | ||||
| (2.13e) | ||||
with initial condition and .
Note that is the state estimate obtained before the measurement update, namely, using information up to time . This term is often called the pre-estimate in the literature. With the new measurement information at time , the agent updates the state estimate to , which is a linear combination of and . This term is often called the post-estimate [17]. Here the second term on the RHS of (2.13d) is independent of the first term . The only decision variable in the coefficients is chosen so that the conditional mean-square error is minimized. Namely,
| (2.14) |
In terms of quantifying the uncertainty in the state estimate, we have and representing the covariance before and after measurement updates, respectively.
2.1.2 Two-player setting
There are a few challenges for the belief updates in the game setting. In this paper we focus on the case where both players and adopt linear feedback policies:
| (2.15) |
with some policy matrices and .
From player ’s perspective, the new information collected at time is and . Intuitively, player should be able to use as some additional information to improve their estimate of . Note that player is aware that player adopts a linear feedback policy , for which the opponent’s policy matrix (a function of model parameters) is known but the state estimate is unknown to player . In order to utilize the information contained in , player also needs to infer the distribution of using . We will show later on in Section 2.2 that this idea of using the opponent’s actions to make an information correction is not only a possible approach to improve the estimation precision but also a necessary step to guarantee that the conditional expectations based on the information filtrations satisfy the tower property and hence that the DPP holds.
Let us start at decision time . Player reasons as follows. He models his initial belief of the initial state as
| (2.16) |
where is the true physical state and is player ’s estimation error, whose distribution, in view of (2.2), is . In the same way, player ’s belief of the initial state follows
| (2.17) |
where, as before, is the true physical state and is player ’s estimation error, whose distribution, in view of (2.4), is . The Gaussian random variables and are independent by our assumptions.
From player ’s perspective, is known but is a random variable. Subtracting (2.16) from (2.17), at time player concludes that as far as he is concerned, player ’s estimate, upon which he will decide his optimal control, is the random variable
| (2.18) |
As far as is concerned, ’s estimate of the initial state is a Gaussian random variable
| (2.19) |
Thus, at time player has used his private information and the public information to calculate the distribution of the sufficient statistic of player . Similarly, as far as player is concerned, at time the distribution of the initial state estimate of player follows .
In addition to (2.15), we further restrict the admissible set of policy matrices to the following:
For time , we have the following result.
Theorem 2.4 (Sufficient Statistics in Two-player Games).
Assume the sufficient statistic of player at decision time is . In addition, assume both players are applying linear strategies. Namely, and for some matrices and . Then, for time , the distribution of the physical state calculated by player conditioning on the private information available to him at time follows
| (2.20) |
where, for ,
| (2.21a) | ||||
| (2.21b) | ||||
| (2.21c) | ||||
| (2.21d) | ||||
| (2.21e) | ||||
| (2.21f) | ||||
| (2.21g) | ||||
| (2.21h) | ||||
| (2.21i) | ||||
| (2.21j) | ||||
| (2.21k) | ||||
where is positive definite. The values of , and , depend on the ranks of and as follows:
-
(i)
The pair
-
(ii)
The pair
In addition, the initial conditions are , , and . Finally, in player ’s view, the posterior distribution for the state estimate of player is
| (2.22) |
Remark 2.5.
- 1.
-
2.
The post-estimates of the state and covariance after the measurement/signal update (2.21g)-(2.21h) take similar forms to the single-agent case (2.13d)-(2.13e). The differences occur in the input state and covariance estimates. In particular, the post-estimate for the single-agent setting uses the pre-estimate as the input whereas the post-estimate for the two-player setting uses the improved-estimate as the input.
- 3.
-
4.
When , players and will not be able to recover the opponent’s state estimate via observing the action taken by the opponent. Instead, from player ’s viewpoint, the posterior distribution for the state estimate of player follows a Gaussian distribution with mean and variance .
-
5.
Consider the special case that
(2.23) In this case, player can fully recover the state estimate from player by observing her actions, as the RHS of the following equation is fully known to player :
(2.24) Observing that , we have
This shows that Player P and Player E have the same improved estimate after observing each other’s actions. In this case, information is fully shared between the players.
Proof.
There are four possible combinations under the conditions (i)-(ii) stated in Theorem 2.4. Here we only show the proof for the following combination as the proof for each of the other combinations follows the same logic:
| (2.25) |
In addition, under condition (2.25), we only prove the results for player here as the results for player follow in the same way.
We handle the new information and , in an incremental fashion. More precisely, we first adjust the estimate using , denoted by , and then derive using and .
After player observes the action from player , player updates:
| (2.26) |
Following the convention in filtering theory [17], we write:
| (2.27) |
where is a matrix to be determined to minimize . To calculate , we have
Note that minimizing is equivalent to minimizing . Taking the derivative with respect to and setting it to zero, we have
which is equivalent to the following equation (since is symmetric by its definition)
| (2.28) |
When is of rank (which will be shown at the end of the proof), we have
| (2.29) |
Using the expression in (2.29), we have
Then we have the pre-estimate:
| (2.30) |
The post-estimate after observing the signal/measure at time is defined as:
| (2.31) |
with a variance
| (2.32) |
In the same way as for the derivation of , we can show that the following choice of minimizes the quantity :
| (2.33) |
The corresponding covariance takes the form:
| (2.34) |
To update player ’s belief of player ’s state, define similarly to the case (2.18) when ,
| (2.35) |
where and are the estimation errors from players and , respectively. Given that (2.35) is equivalent to the following:
| (2.36) |
Player ’s posterior distribution for the state estimate of player is
| (2.37) |
where the estimation error covariance matrix is defined as
| (2.38) |
in which , , , , and . We will see that satisfies a recursive linear matrix equation which is a Lyapunov equation:
| (2.39) |
with
| (2.40) | |||||
The equations (2.39) and (2.40) hold since given (2.21d)-(2.21h), we have
| (2.41) |
and hence
| (2.42) | |||||
Similarly, we have
| (2.43) |
Calculating using (2.42) and (2.43) and taking the expectation lead to (2.39) and (2.40).
Now we simplify (2.40) to obtain (2.21j). As for (2.28), we have
| (2.44) |
By substituting and into (2.40) and by using the fact that , we can rewrite as:
| (2.45) | |||||
| (2.49) | |||||
Given the fact that , we have
| (2.51) | |||||
Similarly, leads to the following relationship
| (2.53) | |||||
Combine (2.51) and (2.49), we have
| (2.54) |
Combine (2.53) and (2.49), we have
| (2.55) |
It is easy to check that Combining with (2.51) and (2.53), we have
| (2.56) |
Finally we show that is positive definite, which guarantees that is of rank . To see this, we have
with defined as
It is easy to see that is positive semi-definite. is positive definite since has rank and is positive definite. Similarly, is also positive definite. ∎
2.2 Conditional Expectation and Tower Property
In partially observable game settings, players face the difficult task of incrementally estimating unknown quantities through information filtering, and then using those estimates to make informed decisions. In the linear-quadratic framework, each player needs to determine
| (2.57) |
for any given matrix . This requires projection of the unknown quantity into the space spanned by the information filtration . Given that contains information on the opponent’s action , the critical challenge boils down to how to utilize this information so that the conditional expectation can be calculated in a valid incremental form to facilitate further analysis and renders the game amenable to solution by dynamic programming.
Theorem 2.4 provides an explicit formula to calculate (2.57) in an incremental format:
| (2.58) |
with and following the explicit recursive formats in (2.21g) and (2.21h), respectively.
Indeed, a similar setup was first studied in [13], in which zero-sum linear-quadratic dynamic games with partial observations and asymmetric information are considered. The players’ initial state estimate and their measurements are private information, but each player is able to observe his opponent’s past control inputs, so the players’ past controls are shared information. However, when the conditional expectation is calculated, the recursive format proposed in [13] follows the single-agent Bayes formula (see Equations (11)-(20) in [13] or similarly (2.13a)-(2.13e)) and does not utilize the observable information of the opponent’s past controls to improve their state estimation, leading to an incorrect formula and hence the tower property fails to hold, let alone the DPP.
To be mathematically more concrete, we do a sanity check to show that the tower property holds when using the recursive expression in (2.21a)-(2.21k). Namely, from player ’s perspective, we have
| (2.59) |
holds when using (2.21a)-(2.21k) to unwind the conditional expectations. To do so, we will first calculate both the LHS and the RHS of (2.59) using (2.21a)-(2.21k), and then match all the terms to prove that the LHS equals the RHS. Finally, we will show that the tower property fails to hold when using the formulas in Equations (11)-(20) of [13] to unwind the conditional expectations.
Calculations using (2.21a)-(2.21k).
For the LHS of (2.59), by (2.21g),
where (2.2) holds by definition of given in (2.3), and (2.21d). We will just consider the case when has rank and has rank for all , as the other cases will follow the same logic. Define , then (2.28) becomes
| (2.61) |
We can then rewrite (2.21b) as
Using this equation in (2.2) we obtain
| (2.62) |
with
| (2.63) | |||||
| (2.64) |
Then substituting (2.62) into the LHS of (2.59), we have
| (2.65) | |||||
For the RHS of (2.59), we have by expanding directly,
Calculations using the result in [13].
In [13], the authors used the following recursive formulas which are essentially the same as the single agent case (see Theorem 2.3):
| (2.67) |
where and are updated according to (2.13a)-(2.13e) Now we use the recursive formula listed in (2.13a)-(2.13e) to calculate the LHS and RHS of (2.59). For the LHS, by direct calculation,
| (2.68) | |||||
On the other hand,
| (2.69) | |||||
By routine calculations similar to those used for Step 3 in Appendix A, we see that (2.68) and (2.69) differ from each other by:
| (2.70) |
Hence the recursive formula (2.13a)-(2.13e) adopted in [13] does not lead to the correct conditional expectation, let alone the tower property and DPP.
3 Equilibrium Solution
Now that we have the information corrections in the updating scheme, we will use these to discuss the DPP and the Nash equilibrium in this section.
3.1 Dynamic Programming Principle
Although both players do not have access to the true state and their controls are related to their state estimates which causes extra correlated randomness, we are still able to derive the individual DPP for the two-player general-sum linear-quadratic Gaussian game under a fixed linear and Markovian strategy from the opponent. This is because the sufficient statistics derived from Theorem 2.4 leads to a valid tower property given in (2.59). This equips us with sufficient tools to prove the DPP.
To start, denote the value function of player (), under a fixed strategy from player () and at any given time , as
| (3.1) |
subject to (2.1) and , with the terminal value
| (3.2) |
Now we prove the DPP in the two-player general-sum linear-quadratic Gaussian game under partial observations and asymmetric information.
Theorem 3.1 (Dynamic Programming Principle).
For any given time , the value function for player , under a fixed policy from player , satisfies
| (3.3) |
with , , and terminal value given in (3.2).
Proof.
We take the perspective of player and the result for player follows the same logic. By definition of the value function in (3.1) we have,
| (3.6) | |||||
where (3.6) holds since is adapted to , (3.6) holds by the tower property (2.59), and (3.6) holds since is adapted to . Finally (3.6) leads to the DPP (3.3) by the definition of . ∎
3.2 Nash Equilibrium
In this section, we will show that the Nash equilibrium strategy for the game (2.1)-(2.2)-(2.3)-(2.5)-(2.7) is related to the solution of a coupled Riccati system. Assumption 3.2 is the existence and uniqueness of this solution and we provide a sufficient condition for this assumption in Remark 3.3.
Assumption 3.2.
There exists a unique solution set with and with to the following set of linear matrix equations:
| (3.7) | |||||
| (3.8) |
where and are obtained recursively backwards from
| (3.9) | |||||
| (3.10) |
with terminal conditions for .
Remark 3.3.
Using the DPP formula in Theorem 3.1, we have the following result for the Nash equilibrium strategy and the corresponding value function for the game (2.1)-(2.2)-(2.3)-(2.5)-(2.7).
Theorem 3.4.
Suppose Assumptions 2.1 and 3.2 hold. We also assume that both players are applying linear strategies. Then the unique Nash equilibrium policy can be expressed as for
| (3.11) |
with and given in (3.7) and (3.8). The corresponding optimal value function of player is quadratic :
| (3.12) |
where and , the matrices are given in (3.9) and (3.10), and the scalars are given by
| (3.13) | |||||
The terminal condition for player is .
Remark 3.5 (Discussion of linear policies).
- 1.
-
2.
We note that the optimal policies and given in (3.7) and (3.8), and the Riccati equations given in (3.9) and (3.10), are the same as the optimal policies and Riccati equations in the case of full observation ([2, Corollary 6.4]). However, the linear-quadratic Gaussian game under partial observation (defined in (2.1)-(2.2)-(2.3)-(2.5)-(2.7)) differs from the linear-quadratic game with full information in [2, Corollary 6.4] in the sense that the Nash equilibrium strategy is linear in the state estimate rather than the true state, and the scalars and in the value function involve more terms due to the errors in state estimation.
Proof.
We prove the theorem by backward induction. We take the perspective of player and let player use the linear strategy defined in (3.8). At time , (3.12) holds by the terminal condition given in (3.2). At time , by Theorem 3.1, we have the DPP for player :
and by (2.62),
with and defined as and , where is defined as . Hence
| (3.14) | |||||
Since , we have
| (3.15) |
Expanding terms in the expectation, (3.15) becomes
| (3.16) | |||||
We note that all the constant terms are independent of , since , , and are independent of the policy . Thus these constant terms will not be involved in the minimization problem. Applying the first order condition to the minimization part in (3.16) leads to
Similarly, we can derive the optimal policy of the player when fixing player P’s strategy :
Substituting into (3.16) we obtain the optimal value function given as
| (3.17) | |||||
| (3.18) |
where (3.18) holds by a similar calculation to that proving (2.65) is equivalent to (LABEL:eqn:RHS_tower) in Section 2.2. Similarly we can also show that (3.12) holds for player at time .
At time , recall that is defined as . We further define and as and . Then similarly to (2.62) we have
| (3.20) |
We apply the DPP again at time , then by (3.19) and (3.20) we have
Expanding the terms in the expectation we obtain
| (3.21) | |||||
We note that all the constant terms including the accumulated sum are independent of , since , , and () are independent of the sequence .
We can apply the first-order condition to obtain the following optimal response:
| (3.22) |
Similarly, player E minimizes his value function to find his optimal response to player P’s strategy . We can show that the optimal strategy of player E is given by
| (3.23) |
Plugging into (3.21) and after manipulations similar to those in the proof that (2.65) is equivalent to (LABEL:eqn:RHS_tower) in Section 2.2, we can rewrite the value function as
with and given in (3.9) and (3.13). Similarly, we can show that (3.13) also holds for player . Therefore by backward induction, the statements hold for all . ∎
4 A Mixed Partially and Fully Observable Setting
In this section, we consider a more general setting for games with two players, and . Now part of the state process is fully observable and part of the state process is partially observable. The joint dynamics takes a linear form :
| (4.1) |
with initial value , and the controls of and are and , respectively. Here, for each , the noise is an i.i.d. sample from with and we have the model parameters , , and . We assume that is the partially observable part and is the fully observable part with .
Information Structure.
At the time , player observes and believes that is drawn from a Gaussian distribution , and thereafter player observes part of the state and the noisy state signal :
| (4.2) |
with a sequence of i.i.d. random variables. Here and . Similarly, player observes and believes that is drawn from a Gaussian distribution . Then player observes part of the state and the noisy state signal :
| (4.3) |
with a sequence of i.i.d. random variables. For simplicity we assume that are independent from . In addition we have and .
Both players make their decisions based on the public and private information available to them. We write and for the private signals players P and E receive up to time , respectively. Let and denote the control history from the buyer and seller up to time , respectively. Also let be the public information that is available to both players.
We assume is the information (or history) available to player P and is the information available to player E for them to make decisions at time , where and follow:
| (4.4) |
Note that the covariance matrices are known to both players.
Cost Function.
Each player () strives to minimize their own cost function:
| (4.5) |
with cost parameters , and .
Rewrite the earlier model as with , , and . Similarly, rewrite with and , and with , , and with and . For the cost parameters, with , , and for .
For the mixed case we make the following assumptions on the parameters, initial state, and noise.
Assumption 4.1 ([Mixed Setting] Parameters, Initial State, and Noise).
For ,
-
1.
and are zero-mean, i.i.d. Gaussian random variables that are independent from and each other and such that and are positive definite;
-
2.
Both matrices and have rank for .
-
3.
The matrices are non-singular for ;
-
4.
The cost matrices , for are positive semi-definite, and for are positive definite.
We now give the main results and omit the proofs as they follow naturally by applying the ideas in Sections 2 and 3 to the partially observable part of the state process.
Theorem 4.2 (Sufficient Statistics in Two-player Games).
Assume that both players are applying linear strategies in that and for some matrices of rank , , of rank , and . The sufficient statistic of player for at decision time is . For time , the distribution of as calculated by player , conditioning on the private information available to him at time , is given by
| (4.6) |
where, for ,
| (4.7a) | ||||
| (4.7b) | ||||
| (4.7c) | ||||
| (4.7d) | ||||
| (4.7e) | ||||
| (4.7f) | ||||
| (4.7g) | ||||
| (4.7h) | ||||
| (4.7i) | ||||
| (4.7j) | ||||
| (4.7k) | ||||
where is positive definite. The values of , and , depend on the ranks of and as follows:
-
(i)
The pair
-
(ii)
The pair
Finally, the initial conditions are , , and .
Theorem 4.3 (Nash Equilibrium).
Suppose Assumption 4.1 holds and there exists a unique solution and to (3.7)-(3.8) with of rank and of rank . Further assume that both players apply linear policies. Then the unique Nash equilibrium policy is
| (4.8) |
The corresponding optimal value functions are quadratic :
| (4.9) |
with matrices given in (3.9) and (3.10). Here for and , the scalar is given by
where , and with
where . The terminal conditions are for .
5 Numerical Experiment: the Bargaining Game
In this section, we perform some numerical experiments on a bargaining game example which can be cast into the framework introduced in Section 4. Consider a two-player bargaining or negotiation game where a buyer and a seller must agree on the value of a good. Each party has a target price, that is the price they want to achieve by agreement at the deadline. The target price depends on their view of the project’s true value. The buyer (resp. seller) does not know the target price of the seller (resp. buyer) or the true value of the good. The challenge is to establish a model for the bargaining situation and find the optimal bidding strategies when both parties have partial information about their counterparties, under some uncertainties (e.g. market fluctuations).
In this section we focus on the case when the opponent’s state estimate can be inferred. The case where , where this is not the case, has similar results and these are deferred to Appendix B.
5.1 Mathematical Set-up
We now cast this bargaining game into the mathematical framework introduced in Section 4. Assume we have two players, a buyer and a seller , who aim to reach an agreement on the value (or the price) of a good. The negotiation takes place over a finite period of time . At each timestamp , the buyer and seller simultaneously offer prices. We let be the price offered by the buyer and be the price offered by the seller. The dynamics of the offers follow
| (5.1) |
Here is the change in the buyer’s offer and is the change in the seller’s offer at time . The random variables and are IID, representing the noise in both parties offers with and , respectively. We note that and serve as regularization terms to guarantee the non-degeneracy of the state noise. Another way of thinking about this is to consider and as the intended change of their offers when players can not completely control the differences between their offers (for example, due to some external restrictions). Both players can observe each other’s exact offers. Thus corresponds to the fully observable part in Section 4.
We assume the value of the good is not available to both players and its dynamics follow:
| (5.2) |
where is a sequence of IID Gaussian random variables with zero mean and covariance . Both the buyer and the seller do not have access to the true value of the good. Instead, they observe a noisy version of the value using their private information. At time , player () believes that the initial value , and after that player observes the following noisy signal:
| (5.3) |
where is a sequence of IID random variables, and and are independent of each other. Thus corresponds to the partially observable part in (4.1) of Section 4, with .
We formulate player ’s () objective in the game as
| (5.4) |
where and are the scalars that determine the buyer’s and the seller’s target price at terminal time . The constants and are the penalties for not reaching an agreement, and and are the penalties for deviating from their target prices. The quadratic terms and can be viewed as a relaxation of the hard constraint . The parameters and measure the cost of adjusting the offer price at each time step, thus the final terms represent the penalty for making concessions. The filtrations and represent the information available at time .
Both players have the incentive to reach an agreement at terminal time . The desire to reach this agreement is characterized by the value of and , which may be different for the buyer and the seller. The hard constraint can be recovered by letting and tend to infinity. The seller wants to sell the good at a price that is higher than (his estimate of) the true price and thus . Similarly as the buyer has the incentive to buy at a price lower than his estimated true price.
5.2 Experiments
In this section, we present some numerical experiments and discuss the effect of observation noise and our information corrections for the bargaining game introduced in Section 5.1. We focus on the case , where the dynamics of the value of the good and the players’ noisy observations are defined in (5.2)-(5.3). The bargaining model considered in this section satisfies the conditions for the special case described in point 5. of Remark 2.5, where each player can fully recover the opponent’s state estimate in the previous step.
Experimental Set-up.
In the experiments we let , , , , and , so the players care more about reaching an agreement with each other. We set the penalty function to be for with and . The penalty function decays over time which allows players to be more flexible near the deadline to reach an agreement. For the initial state we set , , . We also set for the noise in the dynamics of the true value of the good, and . The reason for adding the small noise to and is to guarantee the well-definedness of the problem. In practice we can set , and the numerical experiments will still work.
To see the effect of the observation noise, we let the buyer have a much more noisy observation of the true price ( and ). We also set with for the buyer and with for the seller, thus the buyer has a far more inaccurate guess of the initial state. In the figures and tables we will write IC for information corrections.
Effect of Observation Noise.
Since the buyer receives relatively noisy signals of the true price, their price estimate (indicated in orange) will be more inaccurate than the seller’s (indicated in blue) in the example shown in Figure 1. The behaviour of both players is similar to that in the full information case, since the buyer utilizes the seller’s accurate information to improve their own state estimate.
Effect of Information Corrections.
A key contribution of our work is information corrections, where players correct their estimate of the state after observing their opponent’s actions. We demonstrate the power of the information corrections in Figure 2. When the buyer skips steps (4.7a)-(4.7c), their state estimate will rely purely on their own observations and thus can be very inaccurate. However, with information corrections, they can obtain a better estimate which is less affected by the noisy observations. Hence they are more likely to reach an agreement with the seller at a reasonable price.
We now show some statistics for the buyer’s estimation error in Table 1, where both the average mean squared error and average mean absolute error of 500 experiments (each experiment consists of 10 rounds of bargaining) are smaller when information corrections are used. We also show the effect of using information corrections on the outcomes of the bargaining game in Table 2. If the difference between the players’ final offers is less than 3, we consider them to have reached an agreement. We can see that with information corrections the players are more likely to reach an agreement. The difference is shown in Figure 2. We can see that with information correction the final offers of the buyer and the seller are closer to each other and they have made the deal, while without information correction they are not able to reach an agreement in the end.
| Mean squared error | Mean absolute error | |
|---|---|---|
| With information correction | 17.43 | 3.10 |
| Without information correction | 35.91 | 4.83 |
Furthermore, the above setting is an “asymmetric” case, where the buyer has a more inaccurate estimate of the initial state and receives noisier signals during the negotiation. We now compare the number of agreements obtained in this case (Table 2) with that obtained in two symmetric cases, which can be considered as benchmarks. In the symmetric case where both players have “accurate” information with small observation noises, we let for both players, and set , and with ; in the symmetric where they both have inaccurate information, we set , , and with . We run 500 experiments in each case, and the number of agreements when they both have “accurate” information is the same regardless of whether they utilize the observed actions from their opponent. However, when both players receive very noisy signals, having information corrections significantly improves the number of agreements. This further demonstrates the need for incorporating information corrections especially when players have different levels of observation noise, as is often the case in practice since players may have a variety of different information sources. We also note that the number of agreements reached in the asymmetric case is closer to that in the inaccurate symmetric case. Although the players have improved their state estimate at the previous time step, when the players make offers they are based on their current noisy observation.
| Asymmetric | Symmetric (“accurate”) | Symmetric (inaccurate) | |
|---|---|---|---|
| With IC | 371 | 470 | 367 |
| Without IC | 253 | 470 | 247 |
We can also compare the players’ cost in the asymmetric and symmetric cases (see Table 3). The costs are calculated empirically based on (5.4) In the asymmetric case and the symmetric case when they both have very noisy observations, both players achieve significantly lower costs when using information corrections.
| Asymmetric | Symmetric (“accurate”) | Symmetric (inaccurate) | |
|---|---|---|---|
| With IC (Buyer/Seller) | 2250/2235 | 1923/2053 | 2505/2715 |
| Without IC (Buyer/Seller) | 3068/2819 | 1924/2053 | 3244/3359 |
Aiming at Beneficial Prices.
In the above experiments we focused on the case where both players strive to reach an agreement with their opponent ( for ). However, in some situations players may be more keen on achieving their target price or a more beneficial price in negotiations and not be so concerned if an agreement is reached. We now let the buyer focus more on pursuing their target price and let the seller mainly seek an agreement with the buyer. We let , , , , and . We also let the buyer have far more inaccurate information than the seller by setting , , , , , and . Other parameters are set to be the same as in the previous experiments.
In Table 4, we can see that the information corrections significantly improve the number of agreements achieved. Here we set the agreement price achieved to be the average of and . For a fair comparison we only consider situations where an agreement is achieved in both cases (with and without information corrections). We observe that there is a gap between the confidence intervals of the agreement prices, which illustrates that the buyer can obtain a better deal by using the information corrections to more effectively exploit the seller’s willingness to sacrifice their target price in their desire to reach an agreement.
| Number of agreements | Mean of APs | 95% confidence interval of APs | |
|---|---|---|---|
| With IC | 442 | 48.58 | (48.31, 48.84) |
| Without IC | 342 | 49.61 | (49.34, 49.88) |
References
- [1] Dilip Abreu, David Pearce, and Ennio Stacchetti. Toward a theory of discounted repeated games with imperfect monitoring. Econometrica: Journal of the Econometric Society, pages 1041–1063, 1990.
- [2] Tamer Başar and Geert Jan Olsder. Dynamic Non-Cooperative Game Theory. Society for Industrial and Applied Mathematics, 1998.
- [3] Ulrich Doraszelski and Juan F Escobar. A theory of regular Markov perfect equilibria in dynamic stochastic games: Genericity, stability, and purification. Theoretical Economics, 5(3):369–402, 2010.
- [4] Qi Fu, Chee-Khian Sim, and Chung-Piaw Teo. Profit sharing agreements in decentralized supply chains: A distributionally robust approach. Operations Research, 66(2):500–513, 2018.
- [5] Drew Fudenberg and Jean Tirole. Game Theory. MIT press, 1991.
- [6] Abhishek Gupta, Cédric Langbort, and Tamer Başar. Dynamic games with asymmetric information and resource constrained players with applications to security of cyberphysical systems. IEEE Transactions on Control of Network Systems, 4(1):71–81, 2016.
- [7] Abhishek Gupta, Ashutosh Nayyar, Cédric Langbort, and Tamer Basar. Common information based Markov perfect equilibria for linear-Gaussian games with asymmetric information. SIAM Journal on Control and Optimization, 52(5):3228–3260, 2014.
- [8] Nasimeh Heydaribeni and Achilleas Anastasopoulos. Structured equilibria for dynamic games with asymmetric information and dependent types. arXiv preprint arXiv:2009.04253, 2020.
- [9] Mingming Leng and Mahmut Parlar. Allocation of cost savings in a three-level supply chain with demand information sharing: A cooperative-game approach. Operations Research, 57(1):200–213, 2009.
- [10] Eric Maskin and Jean Tirole. Markov perfect equilibrium: I. observable actions. Journal of Economic Theory, 100(2):191–219, 2001.
- [11] Ashutosh Nayyar, Abhishek Gupta, Cedric Langbort, and Tamer Başar. Common information based Markov perfect equilibria for stochastic games with asymmetric information: Finite games. IEEE Transactions on Automatic Control, 59(3):555–570, 2013.
- [12] Yi Ouyang, Hamidreza Tavafoghi, and Demosthenis Teneketzis. Dynamic games with asymmetric information: Common information based perfect Bayesian equilibria and sequential decomposition. IEEE Transactions on Automatic Control, 62(1):222–237, 2016.
- [13] Meir Pachter. LQG dynamic games with a control-sharing information pattern. Dynamic Games and Applications, 7(2):289–322, 2017.
- [14] Meir Pachter and Khanh Pham. Informational issues in decentralized control. In Dynamics of information systems: computational and mathematical challenges, pages 45–76. Springer, 2014.
- [15] Ariel Pakes and Paul McGuire. Stochastic algorithms, symmetric Markov perfect equilibrium, and the “curse” of dimensionality. Econometrica, 69(5):1261–1281, 2001.
- [16] Ariel Rubinstein. Perfect equilibrium in a bargaining model. Econometrica: Journal of the Econometric Society, pages 97–109, 1982.
- [17] Robert F Stengel. Optimal control and estimation. Courier Corporation, 1994.
- [18] Deepanshu Vasal and Achilleas Anastasopoulos. Signaling equilibria for dynamic LQG games with asymmetric information. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 6901–6908. IEEE, 2016.
- [19] Deepanshu Vasal, Abhinav Sinha, and Achilleas Anastasopoulos. A systematic process for evaluating structured perfect Bayesian equilibria in dynamic games with asymmetric information. IEEE Transactions on Automatic Control, 64(1):81–96, 2018.
- [20] Hans S Witsenhausen. A counterexample in stochastic optimum control. SIAM Journal on Control, 6(1):131–147, 1968.
- [21] Xianrong Zheng, Patrick Martin, Wendy Powley, and Kathryn Brohman. Applying bargaining game theory to web services negotiation. In 2010 IEEE International Conference on Services Computing, pages 218–225. IEEE, 2010.
Appendix A Tower Property
We return to the calculation of (2.65) and (LABEL:eqn:RHS_tower). Recall that we consider the case when has rank and has rank for all .
Matching LHS with RHS.
We can see the first term (quadratic in ) on the LHS and RHS are the same. Thus we are left to show that the constants terms in (2.65) and (LABEL:eqn:RHS_tower) are the same. We prove this in the following steps.
Step 1: Expanding and on the LHS.
We first calculate the three terms in (2.65) that involves and using (2.63) and (2.64). The first term is given by
For the second term, we first note that by adding and subtracting , we obtain
Then, the second term is given by
Similarly the third term is given by
Now we observe that all the constant terms on RHS except can be cancelled with (2b), (1a), and (3a) on LHS, that is
| (A.1) |
Therefore, our goal now is to show that equals the rest of terms on LHS. Before matching the terms, we first merge and simplify some of the terms on LHS.
Step 2: Merging quadratic terms of on LHS.
Recall that is defined as . Thus we have
| (A.2) |
This provides a way to reduce the order of on LHS. Collecting terms which are quadratic in we obtain
| (A.3) | |||||
| (A.4) |
where (A.3) holds by definition of given in (2.38), and (A.4) holds by (A.2). Now we observe that the term in (A.4) will be cancelled with a half of the sum , since
Therefore in summary, we have
Step 3: Merging the last three terms on LHS.
Going back to (2.65), we now consider the last three constant terms that do not involve and . We now add the first two terms to (2c), which leads to
| (A.5) | |||||
To simply the first term in the above sum, we use the following two facts.
Fact 1.
Fact 2.
Step 4: Collecting all the terms on LHS.
Recall that (2b) + (1a) + (3a) can be cancelled with RHS in Step 1, the sum of (1b) + (2a) + (3b) + (2d) + (3c) is given in Step 2, and the sum of the last three terms on LHS and (2c) is given in Step 3. We are now ready to sum up all the terms on LHS using the simplified forms obtained from Steps 2 and 3.
| Constant terms on LHS | ||||
We observe that by adding (part of the terms in) (A), (A), (A), and (A) together, we can obtain the sum
where in the last equation we use the trick (A.2) again. This sum will be further cancelled with part of (A) and (A). After these manipulations we have
| Constant terms on LHS | (A.22) | ||||
Now adding terms in (A.22) and (A.22) together we have
Also, adding (A.22), (A.22), and (A.22) together leads to
Therefore, the constant terms on LHS can be further simplified as
| Constant terms on LHS | (A.23) | ||||
where the second last equality holds since , and the last equality holds by (A.7).
Appendix B Bargaining Game with
In Section 5 we examined a bargaining model where the players only have noisy observations of the true value of the good (), and they can fully recover the opponent’s state estimate. In this section we introduce a more complex setting, where the true value of the good depends on a set of factors and the players can only observe noisy versions of the factors. We will first construct the bargaining model which involves high dimensional factors, and then focus on the case when . In contrast to Section 5, here players cannot fully recover their opponent’s state estimate. We will finally present some numerical results to show the effect of observation noise and information corrections.
Dynamics of the Value of the Good When .
Assume that that the value of the good takes the form
| (B.1) |
with a set of factors that determines the value of the good with coefficient . For the value of common commodities, the factors could include weather, government policies, international events, consumer preferences, shifting input costs, and supply and demand imbalance. We assume the factors follow a simple model:
where is a sequence of IID Gaussian random variables with zero mean and covariance .
Both the buyer and the seller do not have access to the true value of the good nor the precise value of the factors. Instead, they observe a noisy version of the factors using their private information. At time , player () believes that the initial factor signal:
| (B.2) |
and thereafter player observes the following noisy factor signal:
| (B.3) |
where is a sequence of IID random variables, and and are independent.
We Note that this case does not degenerate to the case as players have different noisy factor signals leading to different value estimates
The Bargaining Model when .
Now we focus on the case where the value of the good depends on a set of two factors and players can only observe a noisy version of the factors. The dynamics of the value of the good and the noisy signals are defined in (B.1)-(B.3). In contrast to the previous section, here the players are not able to fully recover their opponent’s state estimate.
We set the coefficient and the model parameters to be, for
and
Also we have for .
For comparison we let , , , , and the penalty function to be the same as in Section. We also set . For the initial state we set , , . We also set for the noise in the dynamics of the factors, and .
To see the effect of the observation noise, we let the buyer have a much noisier observation of the true price by setting
For the players’ belief about the initial state, we set and with
thus the buyer has a far more inaccurate guess of the initial state.
Effect of Observation Noise.
As for the case when , the seller has a more accurate state estimate since he receives less noisy signals. The behaviour of the players is similar to that in the full information case.
Effect of Information Corrections.
With information corrections the buyer’s estimate of the value is less affected by the noisy observations (see Figure 4) and players are more likely to achieve an agreement in each of the asymmetric and symmetric case (see Table 5). Compared with the case when , the gap between the number of agreements achieved in the asymmetric and symmetric (inaccurate) case is larger, since players receive noisy signals from the different factors.
| Asymmetric | Symmetric (“accurate”) | Symmetric (inaccurate) | |
|---|---|---|---|
| With IC | 329 | 439 | 315 |
| Without IC | 237 | 440 | 207 |