Weighted fair division with matroid-rank valuations: Monotonicity and strategyproofness

The strongest positive case is the paper’s main algorithmic result, Theorem 4.4, which is proved in this paper. It states:

Under matroid-rank valuations, for every concave strictly increasing function \(f\), Algorithm 1 computes an \(\mathcal{R}^{\mathrm{tie}}_f\) allocation in polynomial time.

Here the input has finitely many agents with positive weights, finitely many indivisible goods, and matroid-rank valuation oracles. The rule maximizes \(\sum_i w_i f(v_i(A_i))\), applies the paper’s special handling when \(f(0)=-\infty\), lexicographically maximizes the utility vector, and removes redundant goods. The algorithm processes goods one at a time, using exchange graphs and shortest augmenting paths; the proof gives running time \(O(mn(m^2+n))\), under the paper’s value-oracle convention.

My mirror is therefore:

Continuum Weighted Matroid-Welfarist Allocation. An instance consists of a finite type set \(T\), masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), a positive entitlement weight \(w_t\), and a matroid-rank valuation \(r_t\) for each type. There is also a finite set \(G\) of standardized indivisible good classes, with per-capita supply \(q_g\). A solution is a collection \(x_{t,B}\ge 0\), where \(x_{t,B}\) is the mass of type \(t\) receiving the integral bundle \(B\), subject to

\[ \sum_B x_{t,B}=\mu_t \]

for every \(t\), and

\[ \sum_{t,B:g\in B}x_{t,B}\le q_g \]

for every good \(g\). We may restrict to independent bundles \(B\) of the matroid \(r_t\), because redundant goods never improve welfare. The objective is

\[ \max_x\ \sum_{t\in T}\sum_{B}x_{t,B}w_t f(r_t(B)). \]

When \(f(0)=-\infty\), the rule first maximizes the mass receiving positive utility, with a fixed type-order analogue of the paper’s index tie-breaking, and then maximizes weighted welfare and lexicographically refines the type-average utilities.

This is genuinely the high-multiplicity version of the paper’s allocation problem. A finite realization with \(M\) agents contains approximately \(M\mu_t\) agents of type \(t\), \(Mq_g\) copies of good \(g\), and gives each individual an integral bundle. The variables \(x_{t,B}\) are only type-level proportions; they do not give fractional bundles to individual agents. Thus the mirror preserves indivisibility, weights, matroid-rank preferences, concave welfarism, and the paper’s tie-breaking logic.

A convincing regime is a large university system allocating many copies of course seats to students. A type records a student’s degree programme, eligibility constraints, entitlement weight, and course-demand matroid. Thousands of students may share exactly the same type, while the number of degree/eligibility profiles is much smaller. The supply of seats scales with the student population. Public-housing allocation with many households sharing eligibility and entitlement profiles gives a similar scenario.

The continuous problem is likely in Class A. Its configuration formulation is a linear program with exponentially many bundle variables, but its pricing problem is tractable. Given dual prices \(p_g\), type \(t\)'s pricing problem is

\[ \max_{B\in\mathcal I_t} \left(w_t f(|B|)-\sum_{g\in B}p_g\right), \]

where \(\mathcal I_t\) is the independent-set family of the matroid. For each possible cardinality \(k\), a minimum-cost independent set of size \(k\) can be found by the matroid greedy algorithm. Trying all \(k\) therefore gives polynomial-time pricing, enabling column generation or ellipsoid optimization under standard rational-encoding assumptions. This is precisely the kind of exponential-variable LP whose tractability depends on a solvable pricing problem, and it retains the paper’s underlying problem rather than replacing it with additive valuations or divisible individual bundles.

The authors would plausibly recognize this as their problem: the continuous model is obtained by grouping agents who are identical in every relevant respect and taking the high-multiplicity limit of the same weighted welfare objective. The matroid structure is not weakened. Indeed, the continuum makes the paper’s repeated-agent regime explicit and exposes a natural optimization formulation that complements their exchange-graph algorithm.

This mirror covers Theorem 4.4 emphatically, but not every theorem in the paper. The monotonicity and group-strategyproofness results suggest further continuous questions, such as whether increasing \(q_g\) weakly increases every type’s average utility, or whether no positive-mass coalition can benefit from misreporting its matroid type. I would not use those as anchors here because their continuum tie-breaking and coalition definitions require additional modelling choices.

The weakest point is that the paper’s algorithm is for named finite agents and its proof relies on individual exchange paths. The configuration-LP argument is therefore a new justification for the continuum result, not a direct limiting version of Algorithm 1. A referee could also object that the type-level lexicographic tie-break is not uniquely forced by the finite rule. Those are real qualifications, but they do not undermine the mirror itself: high multiplicity is exactly the regime in which type-level mass allocations and configuration LPs are the natural mathematical object.