Say, that there is a group of $n$ people who decides to share Christmas gifts. Each person has a budged, he/she will spend at most $m_i \in \mathbb{Q}$ coins on gifts. Each person must give, exactly $1\leq g\leq n-1$ gifts, and each person must receive $g$ gifts. Furthermore, the total worth $w$ of gifts received must be equal for each person. How do one maximize $w$?

Clearly, if $g=n-1$ then each person $i$ will give a gift of value $m_i/(n-1)$ to every other person. Thus, $w$ is the arithmetic mean of the $m_i$:s. However, if $g=1,$ then every person cannot give more than $\min_i m_i$ so $w=\min_i m_i$ in this case.

The case when all $m_i$ are equal is also simple, just give $g$ gifts of value $w=m_i/g$ so that everyone receives $g$ gifts, and $w$ is maximized.

However, what can be said in the general case? Is this equivalent to some known problem, like knapsack or max-flow?

As a graph-theoretical problem, one may view this as a directed 2g-regular graph, on $n$ vertices, where each vertex has out-degree g. Each vertex is a source and a sink, and one wants to maximize the flow so that all sinks receive the same amount.

-