Distributing art collection amongst heirs, aiming for specific distribution, minimizing mean square error

Question

Suppose we have a legacy art collection consisting of a number of distinct pieces of art. This legacy is to be divided amongst a number of heirs, trying to match a desired distribution as closely as possible.

Say we have 10 paintings, whose estimated values (in dollars) are in an array:

[45000,92000,85000,78500,140000,8000,17500,32000,54000,11500]

And we have 4 heirs: Alice, Bob, Charlie and Dave. The will of the deceased person states they would ideally wish to let each person inherit a specific percentage:

{ "Alice":40, "Bob":30, "Charlie":20, "Dave":10 }

Now given the current value of the paintings, it's most likely not possible to match these percentages exactly.

Considering the total sum value of the legacy is 563500 dollars, following the desired distribution, we would have these target values:

{ "Alice":225400, "Bob":169050, "Charlie":112700, "Dave":56350 }

The will declares an optimal distribution of the paintings is to be used as to minimize the mean square error.

Is there an efficient approach or algorithm to find an optimum distribution?

I'm especially interested in a general case solution, i.e. for any number of items to be distributed amongst any number of heirs (all with given values and percentages).

I guess for low numbers a brute force search would be possible, but as the numbers get larger this will be infeasible.

Answer 1

Following up on my comment earlier, the MSE objective is convex, hence it's possible to solve this as a mixed-integer quadratic program. I put some sample code in Python 3/CVXOPT below. Unfortunately you'll need a non-free solver as I write this (May 2021), since the free options only support linear objectives. I used a trial license for MOSEK, but I think Gurobi would also work. I have no affiliation with either.

import cvxpy as cp
import numpy as np

paintings = np.array(
    [45000, 92000, 85000, 78500, 140000, 8000, 17500, 32000, 54000, 11500]
)
heirs = {"Alice": 40, "Bob": 30, "Charlie": 20, "Dave": 10}
names, percents = zip(*heirs.items())
targets = np.sum(paintings) * np.array(percents) / 100

x = cp.Variable((len(paintings), len(targets)), boolean=True)
problem = cp.Problem(
    cp.Minimize(cp.sum_squares(paintings @ x - targets)),
    [cp.sum(x, axis=1) == np.ones(len(paintings))],
)
problem.solve()
print(dict(zip(names, map(round, (paintings @ x - targets).value))))