Suppose we’re designing a game like *Minecraft* where we have lots of items $ i_1,i_2,…,i_n\in I$ and a bunch of recipes $ r_1,r_2,…,r_m\in R$ . Recipes are functions $ r:(I\times\mathbb{N})^n\rightarrow I\times\mathbb{N}$ , that is they take some items with non-negative integer weights and produce an integer quantity of another item.

For example, the recipe for cake in *Minecraft* is:

3 milk + 3 wheat + 2 sugar + 1 egg $ \rightarrow$ 1 cake

… and the recipe for torches is:

1 stick + 1 coal $ \rightarrow$ 4 torches

Some recipes could even be reversible, for example: 9 diamonds $ \leftrightarrow$ 1 diamond block

If there’s some combination of recipes we can repeatedly apply to get more of the items that we started with then the game is poorly balanced and this can be exploited by players. It’s more desirable that we design the game with recipes that conserve items or possibly lose some items (thermodynamic entropy in the real world – you can’t easily un-burn the toast).

**Is there an efficient algorithm that can decide if a set of recipes will:**

- conserve items?
- lose items to inefficiency?
- gain items?

**Is there an efficient algorithm that can find the problematic recipes if a game is imbalanced?**

My first thoughts are that there is a graph structure / maximum flow problem here but it’s very complex, and that it resembles a knapsack problem. Or maybe it could be formulated as a SAT problem – this is what I’m considering to code it at the moment but something more efficient might exist.

We could encode recipes in a matrix $ \mathbf{R}^{m \times n}$ where rows correspond to recipes and columns correspond to items. Column entries are negative if an item is consumed by a recipe, positive if it’s produced by the recipe, and zero if it’s unused. Similar to a well known matrix method for graph cycle detection, we could raise $ \mathbf{R}$ to some high power and get sums of each row to see if item totals keep going up, stay balanced, or go negative. However, I’m not confident this always works.

Any discussion, code, or recommended reading is very appreciated.