Detecting conservation, loss, or gain in a crafting game with items and recipes

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 c

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (a) every element is $\ge 0$ and (b) at least one element is $> 0$.

(Notice that the order of the operations doesn't matter: Running them in some order might cause the quantity of some item to dip below zero, but we can just look for the low-water-mark and suppose that we have at least that many of each item to start with.)

I think this can be solved by linear programming: Make a variable for each coefficient, add $\ge 0$ constraints for each element in the output vector (each element is a dot product of coefficient variables and constant coefficients from recipes), more $\ge 0$ constraints for each coefficient variable, and set the function to maximise to be the sum of all elements. To make it bounded, set the sum of coefficient variables to some constant, e.g. 1. Iff the solution value is $> 0$, you have non-conservation!

Note that fractional values are not an issue: They must be rational, so you can always multiply through by all denominators to get a pure-integer solution.

StackExchange Computer Science Q#125011, answer score: 4