## 5 Branch-and-Bound Algorithm for \(\epsilon\)-Proper Equilibrium Computation
### The \(\epsilon\)-Proper Branch-and-Bound Algorithm  
Let \(P\) be defined as a master linear program obtained after relaxation of the 0-1 conditions in \((\mathfrak{L_{\bullet}})\). The proposed \(\epsilon\)-proper Branch-and-Bound algorithm follows a principal branching tree scheme and many secondary branching trees. At every vertex on the principal tree, a binary branching is performed on one of the 0-1 variables. At every vertex of the principal tree, the algorithm solves a master linear program \(P\) with at most two constraints fixing one or more binary variables and cutting one or more binary variables combinations. Each time a Nash equilibrium \(\hat{X}\) is obtained, the objective function value \(\sigma\) is compared to a recorded maximum \(\bar{\sigma}\). In the case where the optimal objective \(\sigma\) is equal to zero or lower than \(\bar{\sigma}\), the given principal tree vertex and its sons cannot provide any \(\epsilon\)-proper equilibrium with a larger \(\sigma\) than \(\bar{\sigma}\). The current \(\bar{\sigma}\) stored serves as a bound to shorten the algorithm's execution. At every vertex of a secondary tree node, a linear sub-program \(Q\) is solved. This linear sub-program \(Q\) results from the master linear program \(P\), with one combination of binary variables fixing constraints and at most two constraints fixing one or more continuous \(x\) variables. If a Nash equilibrium \(\hat{X}\) is obtained, the objective function value \(\sigma\) is compared to a recorded maximum \(\bar{\sigma}\). Again, in the case where the optimal objective \(\sigma\) is equal to zero or lower than \(\bar{\sigma}\), the given secondary tree vertex and its sons cannot provide any \(\epsilon\)-proper equilibrium with a larger \(\sigma\) than \(\bar{\sigma}\). The \(\epsilon\)-proper Branch-and-Bound algorithm is formally stated as follows. **Step 1: Initialization. **  
**Define:**  
* \(P\); Master linear program defined by the relaxation of the 0-1 conditions in \((\mathfrak{L_{\bullet}})\). * \(Q\); Sub-program defined by a secondary linear program where the \(U\) and \(V\) variables in \(P\) are fixed. * \(\hat{X}\), \(X\); \(\mathfrak{L_{\bullet}}\)'s real decision variables. * \(U\), \(V\); \(\mathfrak{L_{\bullet}}\)'s binary decision variables. * \(E=\emptyset\); List of Nash equilibria visited. * \(E_{\epsilon}=\emptyset\); List of \(\epsilon\)-proper Nash equilibria obtained. * \(D=0\); Depth level reached in the principal tree. * \(CR\); Principal tree root node. * \(C\); Current node. * \(\hat{x}_{k_{P}}\), \(x_{ik}\); Real decision variables on the \(k^{th}\) strategy of player \(i\)\((i=1,\ldots,n)\). * \(v^{i}_{i}\); Binary decision variables on the \(q^{th}\) strategy of player \(i\)\((i=1,\ldots,n)\). * \(u^{i}_{k_{P}}\); Binary decision variables on the \(k^{th}\) and \(q^{th}\) strategies of player \(i\)\((i=1,\ldots,n)\). * \(\bar{\sigma}\); Best value of \(\sigma\) found. **Set C = CR, \(\bar{\sigma}=0\) and Go to step 2. **  
**Step 2: Solving master program. **  
If \(D\leq|\hat{X}|+|U|\), solve current node's program \(P\). * If the program \(P\) is infeasible or the optimal objective \(\sigma\) is equal to 0; **STOP. **
* Else;
* If \(D<|\hat{X}|+|U|\), **Go to step 3. **
* Else, **Let \(S=(\hat{X};X;V)\)** be the solution obtained;
* If the optimal objective \(\sigma\) of \(P\) is less than \(\bar{\sigma}\), **STOP. **
* Else, if the optimal objective \(\sigma\) of \(P\) is \(\geq\bar{\sigma}\),  
**Update \(\bar{\sigma}=\sigma\), Add \(X\) to \(E\) and \(X_{\sigma}\) to \(E_{\epsilon}\) and Go to step 4. **  
**Step 3: Principal Branching. **  
**Select a binary variable \(v^{q}_{i}\in V\) or \(u^{i}_{k_{Q}}\in U\) over which no principal branching was performed. **Let \(p=D+1\)**:  
If \(p\leq|\hat{X}|+|U|\)**set \(D=p\) and  
**- Set \(v^{q}_{i}\in V\) or \(u^{i}_{k_{Q}}\in U\) selected to 1 in \(P\) and Go to step 2. **  
**- Set \(v^{q}_{i}\in V\) or \(u^{i}_{k_{Q}}\in U\) selected to 0 in \(P\) and Go to step 2. **  
**Step 4: Secondary Branching.