Santa's life used to be much easier. He would split his funds for the year equally between all children and give each child some gifts from their wishlist amounting to roughly that value.
But the corporate rules are creeping in also beyond the Polar Circle and the Customer Satisfaction Department decided that from this year on every child should simply get all the presents they asked for in their letter, and they will even give Santa a budget exactly sufficient for that. While this method is also very simple, Santa is fuming: it is unfair, unsustainable in the long run and most of all against the spirit of Christmas. So after long negotiations the corporation made some concessions for Santa, so that the new distribution rules should balance between two objectives:
- each child should receive gifts of total value similar to what they wished for,
- children living close to each other should receive gifts of similar value.
Santa has since calmed down but he still has to find the right tradeoff of the objectives to both convince the corporate and not betray his ideals (too much). You have been tasked with helping him. The children live on an $n\times m$ grid, each one requested gifts of total value normalized to the interval $[0,1]$ and your budget is the total value of the requests.
Suppose the children have wishes of value $w(i,j)$, $i=1,\ldots,n$, $j=1,\ldots,m$ and Santa will assign them gifts of value $g(i,j)$, to be optimized. Then Santa (who is a big fan of SOCP and only ever works with the $L_2$-norm) would like to try an optimization problem such as $$\begin{array}{ll}\textrm{minimize} & \gamma_{\mathrm{ful}}\cdot \|g-w\|_2 + \gamma_{\mathrm{fair}} \cdot \|(\ldots,g_{i+1,j}-g_{i,j},g_{i,j+1}-g_{i,j},\ldots)_{i,j}\|_2 \\ \textrm{subject to} & \mathrm{sum}(g)=\mathrm{sum}(w).\end{array}$$
The first objective term represents fulfilment, and measures the gap between the gifts and expectations while the second represents fairness, and measures the total variation between each child and its immediate neighbours in the grid in terms of gift value, taken over the whole grid. Santa wants to experiment with the choices of weights, where setting $(\gamma_{\mathrm{ful}}, \gamma_{\mathrm{fair}}) = (0,1)$ will result in his good old equitable division and $(\gamma_{\mathrm{ful}}, \gamma_{\mathrm{fair}}) = (1,0)$ solves for the corporate idea of perfect fulfilment.
Fortunately for Santa this is straightforward in the MOSEK Fusion API for Python:
Now he is ready to experiment with the datasets for various areas, which he represents as heat maps with more red shift meaning more valuable gifts and more blue shift meaning cheaper gifts.
First column: the wishlists. Remaining columns: gift distributions from more emphasis on fairness to more emphasis on fulfilment.
Equipped with this knowledge Santa will have to propose some weights $(\gamma_{\mathrm{ful}}, \gamma_{\mathrm{fair}})$ and we leave him here with these considerations. Remember, if you don't like the direction Santa's service is going you can always switch to one of the many independent vendors, and you will find a list here: List of Christmas gift-bearers (Wikipedia) .
