Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)
You shouldn't need to keep track of state. This can all be handled with capacity constraints over the nodes. The network can be structured as follows:

Start with the graph where one partition consists only of the "men" nodes and the other partition consists of the "women" nodes. Now, add a node for each broker $b$ and for each marriage pair $(m, w)$ on $b$'s list create two edges $(m, b)$ and $(b, w)$. Finally add a source node connected to all men and a sink node connected to all women (you can add another arc between those to simplify constraint cases if you want, but it's not necessary).

So now we have a graph, but to have a proper flow-network we need capacity constraints. For each man and women node we have a capacity constraint of 1, since they can each only marry at most one person. For the $i$th broker node, add a capacity constraint of $b_i$. This way the total number of flows (marriages) going through the broker is at most $b_i$.

Compute maximum flow over this graph and you should be good to go.