Household groceries problem

Question

This might not be the right forum for this, so please feel free to point me in the right direction. I actually studied math and CS as an undergrad and as part of that took classes in operations research and this problem reminded me of that, so I thought of posting it here.

I am in charge of doing my household budget but there are some constraints that make this not as straightforward and I am not sure what the right technique is.

We are $N$ housemates, people spend $x_i$ per month, but also spend variable time at the house, say $d_i$ days, where $i \in \{1,\ldots,K\}$, $K$ is the number of housemates. There are a couple of additional complications.

1. Kitty: we make a community breakfast that we make for our neighbors every Friday morning, and the neighbors contribute a variable amount to a kitty, which then gets divided in between the housemates proportionally to how long they were at home that month.
2. However, since usually most of the groceries are purchased by 1 or 2 housemates, to make it easier for them, the other housemates want their kitty contribution to be used directly as part of the payment they owe. That way, all the kitty cash itself goes to the 1 or 2 housemates that spent the money, and the other housemates just need to pay for the rest.

Obviously, I am in charge of doing the calculations!!

This is an example from last month:

 KITTY  130     

       Days     Total
       at home  Spent   Owe
 Robert 27      39.83   99.63
 Paula  30      516     -361.04
 Josh   30      0       154.96
 Amanda 22      5.58    108.05
 Ana    30      0       154.96
 Bob    24      280.52  -156.55
            

Where the amount owed is easily calculated as $\sum x_i \frac{d_i}{\sum d_i} - x_i$ (i.e. how much they are supposed to pay minus how much money they spent already)

And the kitty would be distributed like this:

        Kitty   
 Robert 21.53   
 Paula  23.93   
 Josh   23.93   
 Amanda 17.55   
 Ana    23.93   
 Bob    19.14   

Which is just the total kitty distributed proportionally according to how many each housemate was in the house.

I just don't know how to "analytically" deal with the constraints (1) and (2) above. The result I had was (obviously the kitty cash should go to Paula and Bob, but the kitty amount that each housemate is entitled to should be part of their payment):

Robert owes Paula   78.10
Josh owes Paula 131.03
Amanda owes Paul    90.51
Ana owes Bob    131.03

Kitty to Paula  86.93
Kitty to Bob    44.67   
            

Which I calculated semi-manually. I am looking for a more mathematical way of doing this yet I am not sure how to frame this last part mathematically and what method to use for solving it. It seems like an optimization problem of some kind, any suggestions?

Answer 1

I'm not sure this is what you are looking for, but I'll take a shot. The following model parameters are computed as you have done above (which can easily be done in a spreadsheet, for instance).

• $i\in\left\{ 1,\dots,I\right\} $ indexes housemates
• $E_{i}$ is the prorated amount of expenses owed by $i$ (before accounting for any spending)
• $s_{i}$ is the amount i spent
• $K_{i}\ge 0$ is the prorated share of the kitty going to $i$

We'll start with two sets of variables.

• $x_{ij}\ge0$ is the amount $i$ pays directly to $j$ ($x_{ii}=0$)
• $y_{ij}\ge0$ is the amount that $i$ allocates to $j$ from $i$'s share of the kitty ($y_{ii}$ is the amount of kitty money $i$ retains from their share)

Two equations govern the allocations.

• We have to account for all of $i$'s kitty allotment (including any amount $i$ keeps for themself): $$\sum_{j=1}^{I}y_{ij}=K_{i}$$
• For each housemate, direct spending plus reallocation to others equals that person's share of expenses: $$s_{i}+\sum_{j\neq i}x_{ij}-\sum_{j\neq i}x_{ji}+\sum_{j\neq i}y_{ij}-\sum_{j\neq i}y_{ji}=E_{i}$$

Any solution to those equations that satisfies the nonnegativity requirements of the variables will work for you. There are multiple ways to get a solution, including solving a linear program with those variables and constraints and the trivial objective of minimizing the constant function 0.

If, say, you want to minimize the number of direct person-to-person payments (meaning it's better for Robert to pay Paula only and Joshua to pay Bob only than for Robert and Joshua to both pay Paula and both pay Bob), you can turn this into an integer linear program. Add binary variables $z_{ij}\in\left\{ 0,1\right\} $ where $z_{ij}= 1$ if and only if $i$ makes a non-kitty payment to $j$ along with the additional constraints $$x_{ij}\le E_{j}z_{ij}$$ and minimize the objective function $\sum_{i\neq j} z_{ij}$ (the number of direct payments made).

Answer 2

Don't have individuals pay other individuals, as that gets messy. There is no unique solution, and it makes it so that the each payment depends on every other payment. At the end of the month, even if I know exactly how much I owe, it won't be possible for me to determine who to pay by myself. Whether I need to pay Paula or Bob depends on whether anyone else has paid Paula or Bob already. In the example, Ana cannot know that she needs to pay Bob, unless she also knows that Robert, Josh, and Amanda all paid Paula. You allude in the comments that trust may be an issue, and this system requires trust - at the end of the month, no individual can actually confirm they've paid the right person, unless they check all the payments made that month. If someone accidentally tells Ana to pay Paula $131.03 instead of Bob, she knows her balance is settled but has no way to identify that she's making an incorrect payment.

Treating the money as non-fungible and earmarking it as "kitty cash", "Bob's cash", or "Paula's cash" adds unnecessary complexity, since every dollar bill is identical - there's really no need to make sure that the kitty specifically is split proportionally, for example, so long as the total comes out right. It doesn't matter if I get \$20 from the kitty and \$80 from Bob or vice versa, so long as I have \$100 in the end.

Instead, have everyone pay into a central fund, and get paid from a central fund. This is already what you're doing with the kitty, it's absolutely no different. Simply have everyone who owes money pay their share of the total cost (which you've already calculated) minus their share of the kitty (which you've already calculated). Then have everyone who is owed money take their share of the pot, plus their share of the kitty. Everybody makes or receives exactly one payment, which doesn't depend at all on anybody else's payment.

Answer 3

Each housemate $i$ (except Bob/Paula) owe $\sum x_i \frac {d_i}{\sum d_i} - x_i$ to the pool (to be paid to Bob+Paula)

Subtract kitty $K$ cash from above for each of mate $i$, except Bob/Paula $s_i = (\sum x_i - K) \frac {d_i}{\sum d_i} - x_i $.

Pay Paula/Bob $\sum s_i \frac {x_j}{\sum_{j=1}^{2} x_{j}}$