<p>A brute-force algorithm might not be the right way to go. Sometimes it is not even feasible for finding Nash equilibria with perfect information. This is because even if players and types are finite, BNE's are a profile of (possibly mixed) strategies that maximize the expected payoff. If the game is sequential, this expectation may depend on the own strategies and the strategies of other players. So the space over which you are looking for best responses is quite large. Moreover, the equilibrium is a fixed point for which, in general, we don't know a lot. For example:</p>

<p>Do you know if the equilibrium exists? is it unique? can you define a contraction operator to update players' strategies that will take you to the equilibrium?</p>

<p>Coding will only work if equilibrium exists, and it will work nicely if your game defines a contraction. In contrast, if it is not unique, you will have to be more careful about the algorithm you use to find/approximate a fixed point. </p>

<p>A more useful approach would be to make assumptions (informed guesses) on how the equilibrium will look like and then verify that such an equilibrium exists. Some common assumptions are: "Symmetry": similar players playing similar strategies in equilibrium, "naive strategies": the equilibrium strategies are relatively simple (for example maximizing instantaneous payoff even though the game is dynamic), etc. </p>

<p>This is no simple task, but often you learn more this way. Keep in mind that often you have a multiplicity of equilibria and BNE must be refined to perfect BNE or sequential BNE or other refinements depending on the application. </p>

CC BY-SA 4.0
2020-01-16T19:17:55.220Z
2020-01-16T19:17:55.220Z
Regio
<p>I am working on a Bayesian game with a finite number of players and discrete types, but the complexity of the equations is not allowing me to find the BNEs by hand.</p>

<p>I read a paper describing algorithms to find approximate BNE in such games but could not understand how to implement it using code.</p>

<p>It would be a great help if someone could inform me about any program for the purpose, or help me with code if possible. Thank you!</p>

CC BY-SA 4.0
2020-01-13T06:17:53.187Z
Seems like you already have your algorithm, and your question is about programming, not economics.
Giskard
CC BY-SA 4.0
2020-01-15T09:55:46.070Z
I'm voting to close this question as off-topic because it is about programming languages.
Giskard
<bayesian-game><algorithms>
Algorithm to find Bayesian Nash Equilibria
Ishan Kashyap Hazarika
# Algorithm to find Bayesian Nash Equilibria

(Asked by: username_0 on 2020-01-12)

I am working on a Bayesian game with a finite number of players and discrete types, but the complexity of the equations is not allowing me to find the BNEs by hand.

I read a paper describing algorithms to find approximate BNE in such games but could not understand how to implement it using code.

It would be a great help if someone could inform me about any program for the purpose, or help me with code if possible. Thank you!

**Tags:** bayesian-game, algorithms
> **Comments:**
> **username_1**: Seems like you already have your algorithm, and your question is about programming, not economics.  
> **username_1**: I'm voting to close this question as off-topic because it is about programming languages.  

---

## 1 answers

### Answer by username_2 on 2020-01-16. Score: 2 | Accepted answer

A brute-force algorithm might not be the right way to go. Sometimes it is not even feasible for finding Nash equilibria with perfect information. This is because even if players and types are finite, BNE's are a profile of (possibly mixed) strategies that maximize the expected payoff. If the game is sequential, this expectation may depend on the own strategies and the strategies of other players. So the space over which you are looking for best responses is quite large. Moreover, the equilibrium is a fixed point for which, in general, we don't know a lot. For example:

Do you know if the equilibrium exists? is it unique? can you define a contraction operator to update players' strategies that will take you to the equilibrium?

Coding will only work if equilibrium exists, and it will work nicely if your game defines a contraction. In contrast, if it is not unique, you will have to be more careful about the algorithm you use to find/approximate a fixed point.

A more useful approach would be to make assumptions (informed guesses) on how the equilibrium will look like and then verify that such an equilibrium exists. Some common assumptions are: "Symmetry": similar players playing similar strategies in equilibrium, "naive strategies": the equilibrium strategies are relatively simple (for example maximizing instantaneous payoff even though the game is dynamic), etc.

This is no simple task, but often you learn more this way. Keep in mind that often you have a multiplicity of equilibria and BNE must be refined to perfect BNE or sequential BNE or other refinements depending on the application.


---

