Mechanism design for fair division: allocating divisible items without payments (d4-conf-sigecom-2013-0057)

Given divisible resources, a finite type set \(T\), rational masses \(\mu_t\), weights \(b_t\), per-capita capacities \(q_j\), and concave degree-one homogeneous valuation functions \(v_t\), compute a feasible type-level allocation \(x_t\) maximizing \(\sum_t \mu_t b_t\log v_t(x_t)\), or an \(\epsilon\)-approximation to its optimum, and classify the complexity in \(m\), \(|T|\), input length, and \(\log(1/\epsilon)\).

Definitions. Let \(T\) be a finite set of types with rational masses \(\mu_t>0\), \(\sum_t\mu_t=1\), weights \(b_t>0\), and \(m\) divisible resources with per-capita capacities \(q_j\). A type-level allocation is \(x_t\in\mathbb{R}_{\ge0}^m\), feasible when \(\sum_{t\in T}\mu_t x_{tj}\le q_j\) for every \(j\). Each \(v_t\) is concave and degree-one homogeneous. Maximize \(F(x)=\sum_{t\in T}\mu_t b_t\log v_t(x_t)\), over allocations with positive valuations. An \(\epsilon\)-approximation satisfies \(F(\tilde x)\ge F(x^*)+\log(1-\epsilon)\).

Target. Is this finite-type mass proportional-fair allocation problem solvable in time polynomial in \(m\), \(|T|\), the input length, and \(\log(1/\epsilon)\), or is it NP-hard?

Nearest known results. For finitely many individual agents with concave degree-one homogeneous valuations, Lemma 3.12 gives a polynomial-time \(\epsilon\)-approximation in the corresponding product objective. That result is stated for an explicit finite agent list, rather than masses aggregated by type.

Result and computational scope

The mass formulation is polynomial-time solvable in the same computational model as the cited finite-agent result. There is an approximation-preserving reduction using exactly one agent per type; expanding rational masses into individual agents is unnecessary.

A necessary qualification is that “input length” requires an encoding. The conclusion below uses binary-encoded rational weights and capacities, and the valuation representation or oracle assumptions under which Lemma \(3.12\) applies. Concavity and homogeneity alone, without computational access to the valuations, do not define a computational problem.

Assume \(0<\epsilon<1\) and that a positive-valuation optimum exists, as presupposed by the question’s \(x^*\).

1. Replace per-capita allocations by total allocations

For each \(t\in T\), define

\(y_t=\mu_t x_t,\qquad w_t=\mu_t b_t.\)

Because every \(\mu_t>0\), this is an invertible transformation, with inverse \(x_t=y_t/\mu_t\). Moreover,

\(\sum_{t\in T}\mu_t x_{tj}\le q_j \quad\Longleftrightarrow\quad \sum_{t\in T}y_{tj}\le q_j.\)

Thus feasible allocations correspond bijectively to allocations among \(|T|\) individual agents with resource capacities \(q_j\).

Degree-one homogeneity gives

\(v_t(y_t)=\mu_t v_t(x_t).\)

In particular, positivity of every valuation is preserved. Define

\(G(y)=\sum_{t\in T}w_t\log v_t(y_t), \qquad C=\sum_{t\in T}w_t\log\mu_t.\)

Then

\(G(y)=\sum_{t\in T}\mu_t b_t\bigl(\log\mu_t+\log v_t(x_t)\bigr)=F(x)+C.\)

The constant \(C\) is independent of the allocation. Consequently, optimal allocations correspond, and for any two corresponding allocation pairs,

\(G(\widetilde y)-G(y^*)=F(\widetilde x)-F(x^*).\)

This identity already proves exact preservation of additive log-objective error.

2. Put the instance into the finite-agent theorem’s form

The cited Lemma \(3.12\) concerns a weighted product objective and gives a feasible approximation in time polynomial in the problem size and \(\log(1/\epsilon)\). [Cole, Gkatzelis, and Goel, *Mechanism Design for Fair Division*, Lemma \(3.12\)](https://www.cs.drexel.edu/~vg399/PF_journal.pdf).

We account explicitly for unit resource capacities and weights bounded below by one.

First, discard coordinates with \(q_j=0\): feasibility forces their allocations to be zero. For the remaining coordinates set

\(z_{tj}=y_{tj}/q_j.\)

Let \(D\) map \(z_t\) to the original resource coordinates by multiplying coordinate \(j\) by \(q_j\) and inserting zeros in discarded coordinates. Define the individual agent’s valuation by

\(u_t(z_t)=v_t(Dz_t).\)

The constraints become \(\sum_t z_{tj}\le1\). For any nonnegative bundles \(z,z'\) and any \(\lambda\in[0,1]\), concavity of \(v_t\) gives

\(u_t(\lambda z+(1-\lambda)z') =v_t(\lambda Dz+(1-\lambda)Dz') \ge\lambda u_t(z)+(1-\lambda)u_t(z').\)

For every \(a\ge0\), homogeneity gives

\(u_t(az)=v_t(aDz)=a\,u_t(z).\)

Thus the required valuation properties are preserved.

Next, set

\(c=\max\{1,1/\min_{t\in T}w_t\}, \qquad \beta_t=cw_t.\)

Every \(\beta_t\ge1\). The resulting finite-agent log objective is

\(H(z)=\sum_{t\in T}\beta_t\log u_t(z_t)=c\,G(y).\)

Since \(c>0\), its maximizers correspond to those of the original problem.

3. Transfer the approximation guarantee

Apply Lemma \(3.12\) to these \(|T|\) agents, with weights \(\beta_t\), valuations \(u_t\), and approximation parameter \(\epsilon\). Its output satisfies

\(\prod_{t\in T}u_t(\widetilde z_t)^{\beta_t} \ge(1-\epsilon)\prod_{t\in T}u_t(z_t^*)^{\beta_t}.\)

The optimal product is positive, so the output valuations are positive and logarithms are well-defined. Taking logarithms yields

\(H(\widetilde z)\ge H(z^*)+\log(1-\epsilon).\)

Recover the original allocation by

\(\widetilde x_t=D\widetilde z_t/\mu_t.\)

It is feasible by the transformations above. Using the objective identities gives

\(F(\widetilde x)-F(x^*) =\frac{H(\widetilde z)-H(z^*)}{c} \ge\frac{\log(1-\epsilon)}{c} \ge\log(1-\epsilon).\)

The last inequality follows because \(c\ge1\) and \(\log(1-\epsilon)<0\). This is exactly the requested guarantee.

4. Encoding length and running time

The transformed instance has \(|T|\) agents and at most \(m\) resources. Products, reciprocals, and comparisons of the input rationals produce \(w_t\), \(c\), and \(\beta_t\) with polynomial encoding length. Although their numerical magnitudes may be large, their binary lengths remain polynomial.

Each transformed valuation is the original valuation composed with an explicitly given rational diagonal map. Under the cited theorem’s computational model, allowing this elementary change of coordinates preserves polynomial access costs. Recovering \(\widetilde x_t\) also requires only rational scaling.

Therefore, the reduction and the finite-agent algorithm run in time polynomial in \(m\), \(|T|\), the input length, and \(\log(1/\epsilon)\). The denominators of the masses never determine the number of agents.

⟨structured verdict parsed — rendered above⟩

The allocation transformation and approximation arithmetic are correct. However, the write-up does not fully verify that the transformed instance satisfies the cited theorem’s hypotheses or that its computational assumptions yield the claimed bit-complexity bound. The result is partial: a valid mathematical reduction, with an incompletely justified polynomial-time conclusion.

• Scope and assumptions

Restricting to \(0<\epsilon<1\) is appropriate for the stated approximation guarantee. Assuming an attained optimum with positive valuations is consistent with the task’s use of \(x^*\).

Binary-encoded rational weights and capacities are an explicit additional restriction: the task specifies rational masses but does not specify these encodings. The prover acknowledges this qualification, so it is not a concealed assumption. Nevertheless, its conclusion applies only under that qualification.

• Replacement of per-capita allocations by total allocations: correct

Because every \(\mu_t>0\), the maps \(y_t=\mu_t x_t\) and \(x_t=y_t/\mu_t\) are inverse and preserve nonnegativity. The resource constraints correspond exactly.

Homogeneity justifies \(v_t(y_t)=\mu_t v_t(x_t)\), including preservation of positive valuations. With \(w_t=\mu_t b_t\), the identity \(G(y)=F(x)+C\) is correct. Consequently, optimal allocations and additive objective differences correspond exactly.

There is no need to compute the possibly irrational constant \(C\). Its use is purely analytical.

• Capacity normalization: correct

A zero-capacity coordinate must receive zero allocation because every summand in its resource constraint is nonnegative. Removing those coordinates and scaling the others gives the stated unit-capacity constraints.

The displayed arguments correctly establish concavity and degree-one homogeneity of \(u_t=v_t\circ D\).

Negative capacities would contradict the assumed existence of a feasible optimum. If all capacities were zero, homogeneity would force every valuation at the only feasible bundle to be zero, again contradicting the positive-optimum assumption. Thus these cases do not create an additional gap.

• Weight normalization: correct

The finite, nonempty type set and positive weights ensure that \(c\) is finite and well-defined. The definitions imply \(c\ge1\), \(\beta_t\ge1\), and \(H=cG\). Multiplication by positive \(c\) preserves maximizers.

• Application of the finite-agent theorem: a missing mathematical hypothesis — major

The cited paper assumes that valuations are nonnegative on every feasible allocation. It also uses unit capacities and weights at least one. The latter two conditions are handled correctly, but nonnegativity is neither stated in USER_TASK nor verified by the prover. See the paper’s [Section 2 and Lemma 3.12](https://arxiv.org/pdf/1212.1522).

Concavity, degree-one homogeneity, and existence of a positive-valuation optimum do not imply nonnegativity on all feasible bundles.

A concrete permitted instance has one type, \(\mu_t=1\), \(b_t=2\), capacities \(q_1=1\), \(q_2=2\), and \(v_t(x)=x_1-x_2\). This valuation is linear and degree-one homogeneous. The positive-domain log objective has an optimum at \((1,0)\), but the feasible bundle \((0,2)\) has valuation \(-2\).

This also exposes the limitation of Section 3’s statement that a positive product guarantees positive individual valuations. Here the transformed exponent is \(2\), so a negative valuation has a positive square. With general rational exponents, negative valuations can instead make the product undefined over the reals.

Minimum clarification required: explicitly identify global nonnegativity as an intended valuation assumption and limit the theorem application accordingly. If signed valuations remain within the target, the cited theorem application is not justified by this write-up.

• Approximation transfer: correct conditional on a valid theorem application

For nonnegative valuations, a strictly positive product with positive exponents implies that every output valuation is positive. Taking logarithms is then legitimate.

The reconstruction preserves feasibility, and the equality between objective differences is correct. In particular, the final inequality has the correct direction: since \(\log(1-\epsilon)<0\) and \(c\ge1\), division by \(c\) makes the allowed negative error smaller in magnitude.

Thus applying the stated unnormalized product guarantee with the same \(\epsilon\) suffices. There is no approximation-parameter error in the reduction.

• Encoding and computational access: insufficiently specified — major

The rational arithmetic claim is correct: forming products, reciprocals, and comparisons introduces only polynomial encoding length. Large mass denominators do not increase the agent count.

The remaining assertion—that composing valuations with \(D\) preserves the computational access required by the theorem—is not verifiable as written. No particular valuation representation, oracle interface, precision convention, or output representation is specified.

The cited lemma states the weighted product guarantee, but its proof appeals to approximate convex programming without spelling out a complete valuation-access or bit-complexity model. Consequently, referring to “the cited theorem’s computational model” does not supply the missing specification. See the [proof of Lemma 3.12](https://arxiv.org/pdf/1212.1522).

Minimum clarification required: state the concrete computational model being assumed, the precise applicable algorithmic guarantee, and why the required access operations and output precision remain polynomial after the coordinate transformation. Efficient evaluation alone must not silently stand in for whatever additional access the optimization algorithm requires.

The genuine progress is the exact reduction using one agent per type and the correct transfer of approximation error. No algebraic error undermines those contributions. The outstanding issues concern the admissible valuation class and the computational theorem needed to turn that reduction into the requested complexity classification.

⟨structured verdict parsed — rendered above⟩