How divide pie with constraints

Question

How divide a pie with constraints?

Hi I have rounded pie and would like to divide it, but am not able to figure out how to do it.

I have four friends: A,B,C,D I want to divide pie based on how I like them, so based on opinion.

1. Slice sizes:

   A= 1/22 of pie B= 10/22 of pie C= 1/22 of pie D= 10/22 of pie.

How to divide the pie when there are some constrains? Like B will tell me he wants < 10% of whole pie and D must have at least 85% of pie. A,C don't care.

In this case I can say ok, so D wants at least 85% 22*0.85= 18.7 so he will get this. Now I have only rest of the pie 22-18.7= 3.3 = 15% to divide and I don't want to give bigger slice than 10% to B. And I want still apply the ratios I proposed but only on rest of the pie as D must have at least 85%.

I think the ratios should be now applied after constrains are resolved.

A has no constraint so he can get from 0-100%
B wants 0-10%
C has no constraints 0-100%
D wants at least 85-100%

I can apply the ratios on slices under constrains like when B wants 0-10% then I can say the ratio will have influence to the size between 0-10% and for D will the ratio influence size (85%-100%).

|   friends: |    A   |    B     |     C     |   D    |
|constraints:|        |  <=0.1   |  >=0.85   |        |
|ranges:     | 0 to 1 | 0 to 0.1 | 0.85 to 1 | 0 to 1 |
|ratios:     |  1/22  |  10/22   |   1/22    | 10/22  |

Hopefully is the problem understandable. At the end I want to have whole pie divided among ABCD with not violated constrains, and with somehow applied ratios.

Answer 1

Let me propose a formalization of this problem as a quadratic program. Let x be the desired result. We want to minimize the L2 norm of x/ratio (element-wise) subject to lower ? x ? upper (element-wise) and x·1 = 1.

The idea behind this objective is that, by examining the optimality conditions, we can show that there exists some scalar z such that x = median(lower, ratio z, upper).

Below is some very poorly tested Python 3 code to approximately solve this quadratic program.

from fractions import Fraction


ratio = [1, 10, 2, 10]
lower = [0, 0, 0, 85]
upper = [100, 10, 100, 100]
# Want to minimize the L2 norm of x / ratio subject to lower <= x <= upper and
# sum(x) == 100

# Validation
assert 0 < len(ratio) == len(lower) == len(upper)
assert all(0 < r for r in ratio)
assert all(0 <= l <= u <= 100 for (l, u) in zip(lower, upper))
assert sum(lower) <= 100 <= sum(upper)

# Binary search
n = len(ratio)
critical = sorted(
    {Fraction(bound[i], ratio[i]) for bound in [lower, upper] for i in range(n)}
)
a = 0
b = len(critical)
while b - a > 1:
    m = (a + b) // 2
    z = critical[m]
    if sum(sorted([lower[i], ratio[i] * z, upper[i]])[1] for i in range(n)) <= 100:
        a = m
    else:
        b = m

x = [0] * n
z = critical[a]
divisor = 0
for i in range(n):
    value = ratio[i] * z
    if value < lower[i]:
        x[i] = lower[i]
    elif upper[i] <= value:
        x[i] = upper[i]
    else:
        divisor += ratio[i]
dividend = 100 - sum(x)
for i in range(n):
    if lower[i] <= ratio[i] * z < upper[i]:
        x[i] = Fraction(ratio[i], divisor) * dividend
print(x)

Output:

[Fraction(5, 3), 10, Fraction(10, 3), 85]