Proportionally Fair Makespan Approximation (aaai25-33513)

Given rational machine-type masses \(\mu_i\) summing to one, rational job-class supplies \(\lambda_j\), and costs \(c_{ij}\) satisfying \(\sum_j \lambda_j c_{ij} = C\) for every type \(i\), choose a finite-support flow \(x\) over integral configurations \(b \in \mathbb{Z}_{\ge 0}^r\) with \(\sum_b x_{i,b} = \mu_i\) and \(\sum_{i,b} b_j x_{i,b} = \lambda_j\), together with payments \(p_{i,b}\), minimizing makespan \(\max\{\sum_j c_{ij} b_j : x_{i,b} > 0\}\), subject to proportionality for every used \((i,b)\): \(\sum_j c_{ij} b_j - p_{i,b} \le \sum_{u,b'} x_{u,b'}(\sum_j c_{ij} b'_j - p_{u,b'})\), and, for the normalized anchor, attaining the unconstrained optimum.

A society is a nonatomic population of total mass \(1\), given by its support: \(\tau\) machine types with positive binary-rational masses \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) counts supported types, not possible types.
There are \(m\geq1\) job classes with binary-rational supplies \(\lambda_j>0\) per unit population and costs \(c_{ij}\in\mathbb{Q}_{\geq0}\), satisfying \(\sum_j\lambda_jc_{ij}=C\) for every type, with \(C\geq0\). Let \(L\) be the total input bit length; express any running times in \(m,\tau,L\) and any additional parameters.
A configuration is \(b\in\mathbb{Z}_{\geq0}^{m}\), including the empty configuration; its cost to type \(i\) is \(\ell_i(b)=\sum_jc_{ij}b_j\).
An allocation is a nonnegative real flow \(x_{i,b}\) with finite support, satisfying \(\sum_bx_{i,b}=\mu_i\) and \(\sum_{i,b}b_jx_{i,b}=\lambda_j\). Thus population mass can split among configurations, but each configuration contains integral job counts.
Payments \(p_{i,b}\in\mathbb{R}\) are unrestricted, with no budget constraint. Proportionality requires, for every used pair \((i,b)\), \(\ell_i(b)-p_{i,b}\leq\sum_{u,b'}x_{u,b'}(\ell_i(b')-p_{u,b'})\).
The makespan is \(M(x)=\max\{\ell_i(b):x_{i,b}>0\}\). Define \(\operatorname{OPT}\) as the infimum of \(M(x)\) over allocations satisfying the flow constraints alone.

Does every normalized mass instance admit a proportional allocation with payments and makespan \(\operatorname{OPT}\), giving approximation ratio \(1\), or can proportionality prevent attainment of the unconstrained optimum?

For finite machines and indivisible jobs with equal total costs across machines, a proportional mechanism with unrestricted payments attains the unconstrained optimal makespan; this is an existence guarantee, not a polynomial-time guarantee. [Feldman–Garg–Narayan–Ponitka](https://arxiv.org/html/2412.08572v2)
No result settling this precise nonatomic configuration-flow analogue was located in the literature search.

An optimal proportional allocation always exists

The answer is yes: every instance in the question admits a finite-support proportional allocation with makespan \(\operatorname{OPT}\). Thus the approximation guarantee is \(1\).

We prove the stronger statement that any feasible allocation can be made proportional by redistributing its existing configurations among types, without increasing its makespan. The improvement-graph argument is adapted from the finite-machine proof in [Feldman–Garg–Narayan–Ponitka, Section 4.2](https://arxiv.org/html/2412.08572v2#S4.SS2); the mass-preserving redistribution is proved below.

1. Characterizing allocations that admit proportional payments

For a feasible allocation \(x\), define its average incurred cost by
\[ S(x)=\sum_{i,b}x_{i,b}\ell_i(b). \]

Here and below, sums over configurations have finite support.

Lemma 1. A feasible allocation \(x\) admits proportional payments if and only if \(S(x)\leq C\).

Proof. For any payments, let \(P=\sum_{i,b}x_{i,b}p_{i,b}\). The job-supply constraints and normalization imply that, for every type \(i\),
\[ \sum_{u,b'}x_{u,b'}\bigl(\ell_i(b')-p_{u,b'}\bigr) =\sum_jc_{ij}\lambda_j-P=C-P. \]

If proportionality holds, multiply each inequality for a used pair \((i,b)\) by \(x_{i,b}\), then sum. Because \(\sum_{i,b}x_{i,b}=1\), this gives \(S(x)-P\leq C-P\), hence \(S(x)\leq C\).

Conversely, suppose \(S(x)\leq C\). Set
\[ p_{i,b}=\ell_i(b)-S(x) \]
on every used pair. Then \(P=S(x)-S(x)\sum_{i,b}x_{i,b}=0\). Each used pair has net cost \(S(x)\), while its proportional benchmark is \(C-P=C\). Thus proportionality holds. \(\square\)

2. Redistributing configurations without increasing makespan

Lemma 2. For every feasible finite-support allocation \(x^0\), there exists a feasible finite-support allocation \(y\) satisfying \(M(y)\leq M(x^0)\) and \(S(y)\leq C\).

Proof. Write \(T=M(x^0)\). Let \(B\) be the finite set of configurations appearing in \(x^0\), and let
\[ z_b=\sum_i x^0_{i,b}\qquad(b\in B) \]
be the total population mass assigned configuration \(b\).

A finite minimization problem

Consider all arrays \(y=(y_{i,b})_{i\in[\tau],\,b\in B}\) satisfying:

• \(y_{i,b}\geq0\);
• \(\sum_{b\in B}y_{i,b}=\mu_i\) for every type \(i\);
• \(\sum_i y_{i,b}=z_b\) for every configuration \(b\);
• \(y_{i,b}=0\) whenever \(\ell_i(b)>T\).

This set is nonempty because it contains \(x^0\). It is closed and bounded in a finite-dimensional space: every coordinate lies between \(0\) and \(\mu_i\). Therefore it is compact, and the continuous linear function \(S(y)\) attains a minimum on it. Fix a minimizer \(y\).

Every such array preserves the job supplies, since
\[ \sum_{i,b\in B}b_jy_{i,b} =\sum_{b\in B}b_jz_b =\lambda_j. \]
It also has makespan at most \(T\).

The improvement graph is acyclic

Construct a directed graph on the supported types. Put an edge \(i\to k\) if some configuration \(b\in B\) satisfies
\[ y_{i,b}>0 \quad\text{and}\quad \ell_k(b)<\ell_i(b). \]

Suppose this graph contains a directed cycle with distinct vertices \(i_1,\ldots,i_r\), where \(i_{r+1}=i_1\). For each edge, choose a witnessing configuration \(b_t\), so that
\[ y_{i_t,b_t}>0, \qquad \ell_{i_{t+1}}(b_t)<\ell_{i_t}(b_t). \]

Choose \(0<\varepsilon\leq\min_t y_{i_t,b_t}\). For each \(t\), move population mass \(\varepsilon\) carrying configuration \(b_t\) from type \(i_t\) to type \(i_{t+1}\). These moves are performed simultaneously.

The resulting array remains feasible:

• every type loses and gains exactly \(\varepsilon\) population mass;
• every configuration retains its total mass;
• all coordinates remain nonnegative;
• each added pair satisfies \(\ell_{i_{t+1}}(b_t)<\ell_{i_t}(b_t)\leq T\).

Its change in average incurred cost is
\[ \varepsilon\sum_{t=1}^r \bigl(\ell_{i_{t+1}}(b_t)-\ell_{i_t}(b_t)\bigr)<0. \]
This contradicts the choice of \(y\). Hence the graph is acyclic.

A type that evaluates every used configuration at least as highly

A finite acyclic directed graph has a vertex \(k\) with no incoming edges: otherwise, repeatedly following an incoming edge would eventually produce a directed cycle.

For this type \(k\), every used pair \((i,b)\) satisfies \(\ell_i(b)\leq\ell_k(b)\). Indeed, a strict reverse inequality would create the incoming edge \(i\to k\); when \(i=k\), equality holds.

Consequently,
\[ S(y) \leq\sum_{i,b\in B}y_{i,b}\ell_k(b) =\sum_jc_{kj}\sum_{i,b\in B}b_jy_{i,b} =\sum_jc_{kj}\lambda_j =C. \]

This proves the lemma. In particular, unequal type masses cause no difficulty: each cycle exchanges the same sufficiently small population mass at every participating type. \(\square\)

3. The unconstrained infimum is attained

We now verify attainment, including instances with zero costs.

First, a finite-support feasible allocation exists. Independently for each job class \(j\), choose an integer-valued random variable \(B_j\) supported on \(\lfloor\lambda_j\rfloor\) and \(\lceil\lambda_j\rceil\), with expectation \(\lambda_j\). When \(\lambda_j\) is integral, take \(B_j=\lambda_j\) deterministically.

The resulting distribution \(\pi\) on configurations has at most \(2^m\) support points. Setting \(x_{i,b}=\mu_i\pi_b\) gives the required type masses and job supplies. Its makespan is finite.

Next, choose a positive integer \(D\) such that \(Dc_{ij}\) is integral for every \(i,j\); such a common denominator exists because all costs are rational. Every configuration cost, and therefore every finite-support makespan, belongs to
\[ \{n/D:n\in\mathbb Z_{\geq0}\}. \]

Fix the makespan \(U\) of the feasible allocation just constructed. The set of achievable makespans at most \(U\) is nonempty and contained in the finite set
\[ \{n/D:0\leq n\leq\lfloor DU\rfloor\}. \]
It therefore has a smallest member, achieved by some feasible finite-support allocation \(x^*\). Every other feasible allocation either belongs to this set or has makespan greater than \(U\). Thus \(M(x^*)=\operatorname{OPT}\).

Unbounded counts in zero-cost coordinates do not affect this argument: rationality discretizes costs, and every individual allocation under consideration already has finite support.

4. Combining the results

Apply Lemma 2 to \(x^*\). It produces a feasible finite-support allocation \(y\) with
\[ M(y)\leq\operatorname{OPT}, \qquad S(y)\leq C. \]
By the definition of \(\operatorname{OPT}\), feasibility also implies \(M(y)\geq\operatorname{OPT}\). Hence \(M(y)=\operatorname{OPT}\).

Finally, assign \(p_{i,b}=\ell_i(b)-S(y)\) to every used pair. Lemma 1 proves proportionality. These payments have mass-weighted total zero.

Therefore proportionality does not prevent attainment of the unconstrained optimum. The makespan equality also covers \(\operatorname{OPT}=0\), without requiring division by the optimum.

⟨structured verdict parsed — rendered above⟩

The argument is correct and resolves the existence question. Every lemma holds under the stated assumptions, including unequal type masses, zero costs, and zero optimal makespan. I found no major or minor mathematical issues.

• Lemma 1: characterization of proportional payments.

The benchmark calculation is valid: finite support permits rearranging the sums, the supply constraints give each type’s average evaluation as \(C\), and the mass-weighted payment average is \(P\). Thus every type has benchmark \(C-P\).

Multiplying the proportionality inequalities by the corresponding masses and summing correctly gives \(S(x)-P\leq C-P\). This proves necessity.

For sufficiency, the proposed payments \(p_{i,b}=\ell_i(b)-S(x)\) have average \(P=0\), because total population mass is \(1\). Every used pair consequently has net cost \(S(x)\leq C\). The payments are permitted by the task and require no additional assumption.

• Lemma 2: existence of a minimizing redistribution.

The optimization uses only the finite configuration set already present in \(x^0\). Its feasible set is nonempty, closed, and bounded in a finite-dimensional real space. The compactness and continuous-minimum facts invoked therefore have their hypotheses satisfied.

Preserving each configuration’s total mass preserves every job supply exactly. The forbidden-pair constraints ensure makespan at most \(T\). Consequently the minimizer is a feasible finite-support allocation within the required makespan bound.

• Lemma 2: cycle exchange.

Every witnessing mass is positive, so the stated positive choice of \(\varepsilon\) exists. Distinct cycle vertices ensure each type loses and gains exactly \(\varepsilon\), regardless of its prescribed mass.

Repeated witnessing configurations do not invalidate the exchange: each decremented coordinate has a distinct originating type, so no coordinate suffers multiple decrements. Simultaneous additions can only improve nonnegativity. Each configuration’s total mass remains fixed.

Every newly used destination pair has strictly smaller cost than its source pair and therefore respects \(T\). The displayed change in average incurred cost is strictly negative, contradicting minimality. Acyclicity follows.

• Lemma 2: the vertex with no incoming edges.

The graph is finite, and strict improvement excludes self-loops. The stated incoming-edge argument correctly guarantees a vertex \(k\) with no incoming edges.

The direction of the resulting inequality is correct. For every used pair, \(\ell_k(b)<\ell_i(b)\) would create an incoming edge to \(k\); hence \(\ell_i(b)\leq\ell_k(b)\). Summing these inequalities and applying the preserved supply constraints gives \(S(y)\leq C\).

The attribution to the finite-machine improvement-graph argument is accurate. The nonatomic exchange is proved explicitly here, so the proof does not rely on transferring an external theorem without checking its hypotheses. [Feldman–Garg–Narayan–Ponitka, Section 4.2](https://arxiv.org/html/2412.08572v2#S4.SS2).

• Attainment of the unconstrained infimum.

The floor–ceiling construction gives integer configuration counts with expectations \(\lambda_j\). Its product distribution has at most \(2^m\) support points. Multiplication by \(\mu_i\) gives exactly the prescribed type masses and aggregate supplies, establishing a finite feasible makespan \(U\).

Rational costs admit a common positive integer denominator \(D\). Every configuration cost is a nonnegative integer multiple of \(1/D\). Because every allocation has finite, nonempty used support, its makespan is also such a multiple.

Achievable makespans at most \(U\) therefore form a nonempty finite set of values. Its minimum is achieved by definition of “achievable,” and every feasible makespan outside that set exceeds \(U\). This establishes global attainment without requiring bounded configuration counts or compactness of the full allocation space.

Zero-cost coordinates create no gap: they can enlarge the configuration set but cannot destroy the discreteness of attainable makespan values.

• Final combination and scope.

Lemma 2 applied to the attained optimum produces a feasible allocation with makespan at most \(\operatorname{OPT}\). Feasibility supplies the reverse inequality, giving equality. Lemma 1 then supplies proportional payments.

The conclusion also covers \(\operatorname{OPT}=0\), since no division is used. The stronger redistribution claim is established as well.

No repair or additional clarification is needed. The output establishes existence and exact makespan preservation, but gives no computational complexity classification or running-time claim. Under the requested JSON definition, the complexity field is therefore "unresolved".

⟨structured verdict parsed — rendered above⟩