MTT Table Rebalancing (second half)

Overview

The Greedy method introduced last time can be considered a solid approach for MTT table rebalancing, as it at least maintains a balance in the number of players per table. However, it cannot necessarily be called the optimal method in terms of fairness among players or the desirability of seat changes. Therefore, let’s consider an algorithm that defines the cost of seat changes, solves an optimization problem to minimize that cost, and then performs the seat changes.

Table Rebalancing Objective Function

The costs associated with moving seats (unfairness between players and time lost due to movement) are thought to be based on the following criteria:

1. Position Change: The difference in a player’s position change (seat difference from BTN) before and after a move.
2. Blind Fairness: The number of plays before becoming the big blind.
3. Number of moves per player: Adjust the number of moves to be as even as possible (more moves means more inactivity).
4. Table Size Difference: Minimize the difference in player numbers between tables.
5. System Constraints: Minimize cross-server moves as much as possible.

Combining these, the cost of moving the table can be expressed. The cost of moving a player currently in seat \(\small i \) to seat \(\small j \) is denoted by \(\small c_{ij}\), and is given by

\[\small c_{ij} = w_1 |p_i – p_j| + w_2 |b_i – b_j| + w_3 m_i + w_4 |t_i – t_j| + w_5 1_{\{s_i \neq s_j\}}. \]

Here, \(\small p_i\) represents the position of seat \(\small i\) in the next game, \(\small b_i\) represents the number of games until BB in the next game for seat \(\small i\), \(\small m_i\) represents the total number of moves for the player in seat \(\small i\), \(\small t_i\) represents the number of players at the table for seat \(\small i\), and \(\small s_i\) represents the server at the table for seat \(\small i\).

 Of course, this is just one example, and it is also possible to define a cost function that uses the stack distribution status, etc. to achieve characteristic table rebalancing.

Optimal Assignment Problems and the Hungarian Method

MTT table rebalancing can be formulated as a mathematical problem: assigning players \(\small i \in I\) to seats \(\small j \in J\) so as to minimize cost. Generally, the number of players and the number of seats are different, but if we formulate it so that the number of players plus the number of empty seats equals the number of seats, we can assume without loss of generality that the number of players and the number of seats equal each other. A mathematical problem such as this, which involves allocating \(\small n\) resources to \(\small n\) objects with the least cost, is called an optimal assignment problem.

 There is an efficient algorithm known for solving the optimal assignment problem, known as the Hungarian Algorithm. Below, we will provide an overview of the Hungarian algorithm. Formally, the Hungarian Algorithm is an algorithm for solving the minimum-cost perfect matching problem in a bipartite graph, and calculates the solution to the optimal allocation problem by repeatedly performing row and column operations on the cost matrix.

 First, assume that the cost of allocating resource \(\small i\) to target \(\small j\) is given by the matrix \(\small [c_{ij}]\) (if the numbers do not match, adjust by adding a dummy row). The specific algorithm of the Hungarian method is as follows:

1. Transforming the cost matrix and creating zero points: By repeatedly subtracting the minimum value from each row and column of the cost matrix, it becomes easier to find zero assignments.
   • Row reduction: Find the minimum value in each row and subtract it from all elements in that row. This ensures that each row has at least one zero.
   • Column reduction: After row reduction, find the minimum value of each column and subtract it from all elements in that column. This will result in at least one zero in each column.
2. Draw minimum covering lines and check optimality: Find the minimum number of lines (horizontal or vertical) \(\small K\) required to cover all zeros in the current cost matrix.
   • Checking optimality: If \(\small K=n\), the optimal solution has been found and the solution is identified in step 3.
   • If \(\small K<n\), adjust the cost matrix in step 4.
3. Identifying the optimal allocation: If the number of lines covering zero is \(\small n\), select a unique combination of elements \(\small (i,j)\) whose cost matrix is ​​zero (the solution is not necessarily unique). The solution found in this way is the optimal allocation that minimizes the cost.
4. Rescale the cost matrix: Find the minimum \(\small h\) in the area not covered by the line. Use this to adjust each element of the cost matrix as follows. After this operation, go back to step 2 and check the optimality again.
   • Subtract \(\small h\) from all uncovered elements
   • Add \(\small h\) to elements that are crossed by two lines (double covered elements)
   • Elements covered by a single line remain unchanged
5. Repeat steps 2-4 until the optimal allocation is found.

 Since libraries exist for many programming languages, it may not be necessary to implement it yourself, but the above algorithm can mechanically calculate the optimal allocation, so you can rebalance the table by calculating the optimal seat allocation for each player at the end of each game.

Summary

As a method different from the Greedy method, by defining various cost functions, it is possible to define a table rebalancing method with unique characteristics. For example, there could be an algorithm that is overly concerned with fairness in the number of seat changes, an algorithm that emphasizes fairness in the number of times the blinds are used, or, conversely, an algorithm that prioritizes system convenience. The algorithm can be implemented to minimize these costs using the Hungarian method.

 In reality, the Greedy method often doesn’t result in seat changes that feel particularly jarring. However, there might be cases where playing with a deliberately skewed table rebalancing algorithm is enjoyable as an option. While fairness is prioritized in most games, allocation algorithms that ignore fairness could also be interesting. It could be interesting to introduce randomness, like deliberately assigning more players to the BTN or more players to the SB/BB, creating an unfair algorithm. Eventually, I’d like to explore table rebalancer algorithms that are clearly different from the norm—like one that assigns players with low stacks to the blinds, aiming to quickly eliminate them.