# Find the max and min value for a total of a set of values when there is overlap between the values

I work for a charity which sets up projects. One piece of data for each project is the number of people it hopes to impact. Given a set of projects (typically between 3 and 40), there may be some overlap between the people they hope to impact. So project A hopes to impact 40 people, project B hopes to impact 100 people, but 20 people from project A are also in project B. So the total is 120 people impacted, not 140.

I have a matrix with each project along the top, and also down the side, in the same order. Each cell contains the overlap between the two projects. The matrix is reflected in the diagonal. The diagonal cells (same project column & row) contain the number of people to be impacted by that project.

My first thought was that the total number of people impacted would be the total of the diagonal minus the total of all the overlap figures below the diagonal (or above the diagonal, makes no difference). However that takes no account of the fact that there may be overlaps between the overlaps.

Given such a matrix, where all the overlaps between pairs of projects are known, but the overlaps between overlaps is not known, it must be possible to put upper and lower bounds on the total number of people impacted by all the projects, but I can't figure out how to do that.

I'm guessing I'm not the first person to come up against this, and maybe there are some established formulas for it? Or some different, better way of approaching the problem?

Let $$S_1$$ be the sum of the sizes of the projects' impacts (the diagonal), and let $$S_2$$ be the sums of the sizes pairwise intersections (the numbers strictly above the diagonal). Then $$S_1-S_2\le \text{# people impacted}\le S_1$$ These are the first two Bonferroni inequalities, and they are the best you can say in general without knowing the sizes of the three-way intersections.