What are the minimum number of changes of coefficients to make a system of linear equations solvable?

Question

Question

I have a system of linear equations between ~1000 variables with ~1500 linear equations all of the form $a_0x + a_1y + a_2z ... = 0$.

I would like to change the minimum number of coefficients such that the system is solvable. Is there any known way to do this?

Motivation

I am taking all of the crafting recipes in a game and trying to work out numerical 'values' for each of the base items (the items which cannot be crafted only obtained from the environment) such that the game is consistent. IE there is no way to duplicate items by converting between them.

Each recipe is a linear equation.

I have all the recipes in the form $i_0x + i_1y + i_2z ... = o_0x + o_1y + o_2z ...$ where the $i_n$ coefficients are the amount of each item input to the recipe and the $o_n$ coefficients are the amount of each item output by the recipe.

As there are currently ways to duplicate items the system is not solvable, thus I wish to know how to make it solvable to prevent this.

PS

Any help or really just suggestions on where to look for answers would be great.

My other idea was to see if there was anything in graph theory that would help me (having each recipe as a node etc) but again I have no idea where to look.

(If it helps I have an undergraduate mathematics degree.)

Answer 1

~500. If you take your first thousand equations, that’ll define a unique solution for your thousand variables assuming there isn’t already a linear dependence in your equations. If there is some dependencies, add more equations. If your coefficients are random reals, this is unlikely (probability 0). If they’re nice numbers (like integers), you might get some overlap so you’ll need to throw some more equations in there which would reduce the amount you need to adjust. Then you can adjust one coefficient of a nonzero variable in each of the remaining around 500 equations to get them to work.

The simplest approach would be to add some money. Assign an approximate cost to each item (I.e. add up all the stats/rarities of your item or something - doesn’t have to be exact), and then charge the monetary difference of the input items and output items to the player whenever they convert. You can even make it so each transactions costs a bit on top of that to prevent needless cycles and reduce the incentives of players to excessively trade. This is equivalent to just adjusting the coefficient of a single variable for all your equations.

If you don’t want explicit coinage in the crafting process, you just need to make sure your inputs are always more valuable than your outputs according to any pricing system. I.e. assign prices either as above or randomly and then increase the material cost for any transaction whose outputs are too valuable.

Answer 2

Let's say a resource is an item class/object type only obtainable by the environment, and products are craftable (though may also be obtainable by environment).

There are a lot of ways take on your problem, but just as many possible complications depending on the design of the recipes.

The one that is probably easiest if each resource can be obtained infinitely from the environment is to put a numeric estimate for each resource, which roughly represents the effort (or time) necessary to obtain one item of that resource.

Then each recipe gives an inequality (if you were to use equalities and have multiple recipes for a product, the equations might be inconsistent - e.g. if one product was only unlocked later, but is better in all regards).

Say a recipe takes the input types $I_1,...,I_m$ and produces the output types $R_1,...,R_n$.

Then let's write the recipe as \begin{equation} \sum_{i=1}^m \alpha_i\cdot I_i \to \sum_{i=1}^n \beta_i\cdot R_i \tag{1} \end{equation}

In that case, we know that the effort necessary to produce $ \sum_{i=1}^n \beta_i\cdot R_i$ is at most the effort necessary to produce $\sum_{i=1}^m \alpha_i\cdot I_i $.

I.e. there may be a better recipe resulting in a lower cost for the RHS. There also may be a worse recipe resulting in a higher cost for the RHS, but in that case we can simply ignore that recipe.

Do this for all resources and you end up with a linear inequality system. For example from (1) we get the inequality $\sum_{i=1}^m \alpha_i\cdot I_i \ge \sum_{i=1}^n \beta_i\cdot R_i$, in which we can view the $I_i$ and $R_i$ as variables whose value is the effort necessary to produce them. So the variables are known for the resources, and unknown for the products.

Using your system of inequalities, you can check out for each resource what's the minimal effort of obtaining it.

Namely:
Let's assume there was a set of recipes $\mathcal{R}_i$, and multiplicies $m_i$ such that application of each recipe $\mathcal{R}_i$ exactly $m_i$ times duplicates some items.

I.e. if we compare our stored resources at the beginning and at the end, then at the end our stored resources are at least equal in resources, with at least one resource being strictly greater than it was at the beginning.

Let $\mathbf{L}_i$ be the LHS of the inequality corresponding to $\mathcal{R}_i$, and $\mathbf{R}_i$ be the RHS.

Them summing the inequalities of all recipes $\mathcal R_i$ weighted by each multiplicity $m_i$ gives us the inequality: $$ \sum_i m_i\cdot (\mathbf{L}_i -\mathbf{R}_i)\ge 0 \tag{2} $$

But since the LHS duplicates an item, we have that $\sum_i m_i\cdot (\mathbf{L}_i -\mathbf{R}_i)$ is a sum of products such that after simplification, each remaining summand has a negative factor. So multiplying (2) by $-1$, we see that the effort of producing $-\sum_i m_i\cdot (\mathbf{L}_i -\mathbf{R}_i)$ is at most 0.

In other words, afterwards you have to check that the maximum of the feasible set for each coordinate is $>0$.

Finally, note that this framework has a few drawbacks. For one, the minimum effort the inequality system gives you for a product ignores that in reality, your recipes produce stuff other than the product in question. So even if the inequality system says the effort for a product $x$ is $\le 0$, it needn't be that you can in reality duplicate the item. It could also mean that if you anyway need the other products of the recipe sequence used to get the inequality $x\le 0$, you basically get $x$ for free as side product.