Fair Allocation based on Diminishing Differences (d4-conf-ijcai-2017-0039)

Given a finite item-type catalogue \(G\), preference-type set \(T\), integer bundle size \(k\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational per-capita supplies \(\sigma_g\) with \(\sum_g\sigma_g=k\), and a strict ranking \(\succ_t\) for each \(t\in T\), let \(\mathcal{B}_k=\{B\subseteq G:\lvert B\rvert=k\}\). Decide whether there exist masses \(x_{t,B}\ge 0\) satisfying \(\sum_{B\in\mathcal{B}_k}x_{t,B}=\mu_t\), \(\sum_{t\in T}\sum_{B\ni g}x_{t,B}=\sigma_g\), and, whenever \(x_{t,B}>0\) and \(x_{t',B'}>0\), \(B\succeq_t^{NDD}B'\).

Let \(G\) be a catalogue of \(m\) item types and let \(2\le k\le m\) be an integer. A bundle contains at most one item of each type: \(\mathcal B_k=\{B\subseteq G:|B|=k\}\).
A society is given by its support: the list \(T\) of \(\tau\) preference types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Each type reports a strict ranking of all of \(G\). Supplies \(\sigma_g\ge0\) are binary rationals with \(\sum_{g\in G}\sigma_g=k\); let \(L\) be the total input bit length.
Write the ranking of type \(t\) as \(g_{t,1}\succ_t\cdots\succ_t g_{t,m}\). Let \(\mathcal U_t^{DD}\) consist of strictly positive additive real utilities consistent with this ranking and satisfying \(u(g_{t,j})-u(g_{t,j+1})\ge u(g_{t,j+1})-u(g_{t,j+2})\) for \(1\le j\le m-2\). Define \(B\succeq_t^{NDD}B'\) iff \(u(B)\ge u(B')\) for every \(u\in\mathcal U_t^{DD}\); utility ties are allowed in this comparison.
The decision problem asks whether real masses \(x_{t,B}\ge0\) exist such that \(\sum_{B\in\mathcal B_k}x_{t,B}=\mu_t\) for every \(t\), \(\sum_{t\in T}\sum_{B\ni g}x_{t,B}=\sigma_g\) for every \(g\), and \(x_{t,B}>0\land x_{t',B'}>0\implies B\succeq_t^{NDD}B'\) for every ordered pair, including \(t=t'\).

Is this decision problem solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?

For a finite list of \(n\ge3\) agents and at least \(2n\) distinct indivisible items, deciding whether a complete necessarily-DD-envy-free allocation exists is NP-complete. [Source](https://arxiv.org/html/1705.07993)
No result settling the exact mass-allocation problem above was located in the literature search.

Result

The decision problem is NP-complete, already for $k=2$ and dyadic masses and supplies.

The crucial point is that the comparisons with $t=t'$ force every preference type to receive exactly one bundle. Thus allowing real allocation masses does not provide fractional freedom within a type.

1. Every type receives a single bundle

Fix a type $t$ and define the additive utility
$$ v_t(g_{t,j})=2^{m-j}. $$
Its item utilities are strictly positive and strictly decreasing. Its consecutive differences satisfy
$$ v_t(g_{t,j})-v_t(g_{t,j+1}) = 2\bigl(v_t(g_{t,j+1})-v_t(g_{t,j+2})\bigr), $$
so $v_t\in\mathcal U_t^{DD}$.

Distinct bundles have distinct $v_t$-values. Indeed, the highest power of two corresponding to an item in their symmetric difference exceeds the sum of all lower powers, so their utility difference cannot vanish.

Suppose both $x_{t,B}>0$ and $x_{t,B'}>0$. Applying the stipulated condition to both ordered pairs gives
$$ B\succeq_t^{NDD}B' \quad\text{and}\quad B'\succeq_t^{NDD}B. $$
Consequently, $v_t(B)=v_t(B')$, which implies $B=B'$.

Since $\mu_t>0$, the mass constraint therefore forces a unique bundle $B_t$ with
$$ x_{t,B_t}=\mu_t, \qquad x_{t,B}=0\quad\text{for }B\ne B_t. $$

Hence the original problem is equivalent to finding bundles $B_t\in\mathcal B_k$ satisfying
$$ \sum_{\{t:\,g\in B_t\}}\mu_t=\sigma_g \quad\text{for every }g, $$
and
$$ B_t\succeq_t^{NDD}B_s \quad\text{for every }t,s\in T. $$

2. NDD comparisons admit polynomial verification

We derive a finite characterization directly from the utility definition.

Fix a type $t$ and equal-size bundles $B,B'$. Write
$$ a_j=\mathbf 1_{\{g_{t,j}\in B\}}-\mathbf 1_{\{g_{t,j}\in B'\}}, \qquad A_\ell=\sum_{j=1}^{\ell}a_j, \qquad D_r=\sum_{\ell=1}^{r}A_\ell. $$
Equal cardinality gives $\sum_{j=1}^{m}a_j=0$.

For any $u\in\mathcal U_t^{DD}$, let
$$ d_\ell=u(g_{t,\ell})-u(g_{t,\ell+1}). $$
Then
$$ d_1\ge d_2\ge\cdots\ge d_{m-1}>0. $$
Expanding each item utility from the bottom-ranked item and using equal cardinality yields
$$ u(B)-u(B')=\sum_{\ell=1}^{m-1}d_\ell A_\ell. $$
Since
$$ d_\ell=d_{m-1}+\sum_{r=\ell}^{m-2}(d_r-d_{r+1}), $$
we obtain
$$ u(B)-u(B') = d_{m-1}D_{m-1} + \sum_{r=1}^{m-2}(d_r-d_{r+1})D_r. $$

It follows that
$$ B\succeq_t^{NDD}B' \quad\Longleftrightarrow\quad D_r\ge0 \quad\text{for every }1\le r\le m-1. $$

For sufficiency, every coefficient in the displayed utility difference is nonnegative.

For necessity, if $D_{m-1}<0$, take all gaps equal to $1$, with bottom utility $1$. This is an admissible utility and gives a negative difference. If instead $D_r<0$ for some $r\le m-2$, choose
$$ d_\ell= \begin{cases} 1+\lambda,&\ell\le r,\\ 1,&\ell>r, \end{cases} $$
where $\lambda>0$ is sufficiently large. With bottom utility $1$, these gaps define a strictly positive, strictly ranking-consistent DD utility, and
$$ u(B)-u(B')=D_{m-1}+\lambda D_r<0. $$

A certificate consists of the $\tau$ bundles $B_t$, using $O(\tau k\log m)$ bits. The supply equalities can be checked by exact rational arithmetic, and every ordered NDD comparison can be checked using the inequalities above. All these checks take polynomial time in $m,\tau,k,L$. Thus the problem belongs to $\mathrm{NP}$.

3. The source hardness result

We use the following restricted consequence of the cited theorem:

For a variable number $n$ of agents with strict rankings on exactly $2n$ distinct items, deciding whether a complete necessarily-DD-envy-free allocation exists is NP-hard, even when all agents have different first-ranked items.

The restriction follows from the paper’s explicit reduction: Appendix C constructs $3s$ agents and $6s$ items, with a different top dummy item for each agent. Its utility assumptions agree with those in the present question. See [Segal-Halevi, Hassidim and Aziz, Theorem 7.4 and Appendix C](https://arxiv.org/html/1705.07993#A3).

Every complete necessarily-DD-envy-free allocation in such an instance gives each agent exactly two items. To verify this, for agent $i$ consider the admissible utilities
$$ u_i(g_{i,j})=C+(2n-j), \qquad C>0. $$
All consecutive gaps equal $1$. If $|X_i|<|X_j|$, then
$$ u_i(X_i)-u_i(X_j) = C\bigl(|X_i|-|X_j|\bigr) + \sum_{g\in X_i}(2n-\operatorname{rank}_i(g)) - \sum_{g\in X_j}(2n-\operatorname{rank}_i(g)) $$
is negative for sufficiently large $C$. This contradicts necessary DD envy-freeness. All bundle sizes must therefore agree, and completeness on $2n$ items makes their common size $2$.

4. Reduction using only dyadic data

Let $H$ be the source catalogue, with $|H|=2n$, and agents indexed by $1,\ldots,n$.

Introduce two new items $a,b$ and one additional preference type $0$. Set
$$ G=H\cup\{a,b\}, \qquad k=2, \qquad q=\left\lceil\log_2(4n)\right\rceil, \qquad \alpha=2^{-q}, \qquad \beta=1-n\alpha. $$
Then $n\alpha\le1/4$, so $\beta\ge3/4>\alpha$.

Give each original type mass $\alpha$ and type $0$ mass $\beta$:
$$ \mu_i=\alpha\quad(1\le i\le n), \qquad \mu_0=\beta. $$
Set supplies
$$ \sigma_h=\alpha\quad(h\in H), \qquad \sigma_a=\sigma_b=\beta. $$
These data satisfy
$$ \sum_t\mu_t=n\alpha+\beta=1, \qquad \sum_{g\in G}\sigma_g=2n\alpha+2\beta=2=k. $$

Each original type preserves its ranking on $H$ and places $a,b$ last, in that order. Type $0$ ranks
$$ a\succ_0 b\succ_0\text{all items of }H, $$
with any strict order on $H$.

The original rankings remain distinct because their first-ranked items are distinct; type $0$ has a new first-ranked item. Thus this construction is a valid support of preference types.

All masses and supplies are dyadic and have $O(\log n)$ encoding length. The construction has polynomial size.

Preservation of comparisons on original bundles

For any original type $i$ and bundles $X,Y\subseteq H$, extending the ranking by $a,b$ at the bottom preserves their NDD comparison exactly.

One direction follows because restricting any admissible utility on $G$ to $H$ gives an admissible utility on the original ranking.

For the other direction, take any admissible original utility $u$. Let $c>0$ be its utility for the last-ranked original item, and let $d>0$ be its last consecutive gap. Choose
$$ 0<\varepsilon<\min\{d,c/2\}, $$
and extend it by
$$ u(a)=c-\varepsilon, \qquad u(b)=c-2\varepsilon. $$
The added consecutive gaps both equal $\varepsilon$ and do not exceed $d$. The extension is strictly positive, strictly consistent with the extended ranking, and DD. It leaves the utilities of $X,Y$ unchanged.

Consequently,
$$ X\succeq_i^{NDD}Y \text{ on }H \quad\Longleftrightarrow\quad X\succeq_i^{NDD}Y \text{ on }G. $$

Forward implication

Suppose the source instance has a complete necessarily-DD-envy-free allocation $X_1,\ldots,X_n$. Each $X_i$ has size $2$.

Assign bundle $X_i$ to type $i$ with mass $\alpha$, and $\{a,b\}$ to type $0$ with mass $\beta$.

Every original item belongs to exactly one $X_i$, so all supply constraints hold. Comparisons between original types hold by preservation of NDD comparisons.

Every original type ranks every item in its bundle above both $a$ and $b$, so it strictly prefers its bundle to $\{a,b\}$ under every admissible utility. Conversely, type $0$ ranks both $a,b$ above every original item, so it strictly prefers $\{a,b\}$ to every original bundle. Thus all required comparisons hold.

Reverse implication

Suppose the constructed mass instance is feasible. Section 1 gives a single bundle $B_t$ for every type.

Type $0$ cannot receive any original item $h$: its mass $\beta$ alone would contribute more than that item’s supply $\alpha$. Since its bundle has size $2$, necessarily
$$ B_0=\{a,b\}. $$
This consumes the entire supplies of $a,b$, so no original type can receive either new item.

For each $h\in H$, its supply equality now reads
$$ \alpha\bigl|\{i\in\{1,\ldots,n\}:h\in B_i\}\bigr|=\alpha. $$
Therefore every original item belongs to exactly one original bundle. The bundles $B_1,\ldots,B_n$ form a complete allocation of $H$.

Their pairwise NDD comparisons hold in the mass instance, and hence in the original instance by comparison preservation. They therefore form a complete necessarily-DD-envy-free allocation.

5. Conclusion

The construction is a polynomial-time many-one reduction from an NP-hard problem, and it uses only $k=2$ and dyadic masses and supplies. Together with membership in $\mathrm{NP}$, this proves NP-completeness. A polynomial-time algorithm for the general problem would consequently imply $\mathrm P=\mathrm{NP}$.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output resolves the exact decision problem in USER_TASK. Its argument establishes $\mathrm{NP}$-completeness, already for $k=2$ with dyadic masses and supplies. I found no major or minor issues requiring repair.

1. A single bundle per preference type

The utility
$$ v_t(g_{t,j})=2^{m-j} $$
is admissible: all item utilities are positive, the ranking is strict, and the consecutive-gap identity holds for every $1\le j\le m-2$. When $m=2$, the DD condition is vacuous, so this boundary case is also covered.

The claim that distinct bundles have distinct utility values is correct. Because bundles contain no repeated items, their utility difference has coefficients in $\{-1,0,1\}$. The largest power occurring in the symmetric difference exceeds the sum of all smaller available powers, so cancellation is impossible. The restriction to bundles that are sets is essential here and is satisfied by USER_TASK.

For two positive-mass bundles of the same type, the two ordered self-comparisons require opposite weak inequalities for every admissible utility, including $v_t$. Thus their $v_t$-values must agree, forcing the bundles to coincide.

The remaining inference is justified: $\mathcal B_k$ is finite, and the positive total mass $\mu_t$ ensures that some bundle has positive mass. Consequently, exactly one bundle receives the full mass $\mu_t$.

The resulting discrete formulation is equivalent to the original problem in both directions. In particular, assigning mass $\mu_t$ to each selected bundle reproduces precisely the displayed supply equalities and pairwise comparisons. Self-comparison of the selected bundle is reflexive.

Assessment: correct and complete. Real allocation variables do not leave any freedom to split a type among different bundles.

2. Polynomial verification of NDD comparisons

The definitions of $a_j$, $A_\ell$, and $D_r$ are unambiguous. Equal cardinality supplies the required cancellation of the bottom utility.

Both displayed expansions are correct:
$$ u(B)-u(B')=\sum_{\ell=1}^{m-1}d_\ell A_\ell $$
and
$$ u(B)-u(B') = d_{m-1}D_{m-1} + \sum_{r=1}^{m-2}(d_r-d_{r+1})D_r. $$
In the second expansion, the coefficient of each gap difference is exactly the sum of the preceding $A_\ell$ terms, as defined by $D_r$.

The sufficiency argument correctly uses
$$ d_{m-1}>0,\qquad d_r-d_{r+1}\ge0. $$
Weak inequalities for the $D_r$ therefore guarantee a nonnegative utility difference, including utility ties.

The necessity argument covers every way the proposed characterization can fail:

• If $D_{m-1}<0$, constant positive gaps yield a negative utility difference.
• If $D_r<0$ for some $r\le m-2$, the stated gap sequence is positive and nonincreasing. Its utility difference is $D_{m-1}+\lambda D_r$, which becomes negative for sufficiently large positive $\lambda$.

Taking bottom utility $1$ makes every constructed item utility strictly positive. Neither construction violates strict ranking consistency.

For $m=2$, the second sum and second counterutility case are empty, and the first case supplies the complete characterization. There is no missing boundary case.

Assessment: the finite characterization is fully justified.

3. Membership in $\mathrm{NP}$

The certificate consists of $\tau$ explicitly listed bundles, each containing $k$ item indices. Its stated size is polynomial.

Supply verification involves only sums of input rationals and exact comparisons. Their intermediate encoding lengths remain polynomial in the total input bit length. The comparison characterization requires polynomial work per ordered type pair, with $\tau^2$ such pairs.

The discrete equivalence from Section 1 is what justifies these certificates despite the original formulation using real masses.

Assessment: membership in $\mathrm{NP}$ is established.

4. The cited restricted hardness result

The restriction needed by the reduction is supported by the cited source. Appendix C constructs $3s$ agents and $6s$ items, after renaming its triplet-count parameter to $s$. Each agent has a different first-ranked dummy item. Thus its hard instances have exactly twice as many items as agents and distinct first-ranked items. The paper also specifies strictly positive additive utilities, strict ranking consistency, and the same consecutive-gap DD condition. [Source: preliminaries, Definition 3.1, Theorem 7.4, and Appendix C](https://arxiv.org/html/1705.07993).

The prover therefore does not improperly infer hardness of this restricted family merely from hardness of a larger family: it identifies the restrictions actually satisfied by the published reduction.

The separate argument forcing two items per source agent is valid. The proposed utilities are admissible for every $C>0$. If an agent receives fewer items than another, its utility difference has a negative coefficient of $C$, with the remaining term independent of $C$. Necessary envy-freeness is therefore contradicted for sufficiently large $C$.

Completeness on exactly $2n$ items then forces the common bundle size to be $2$. This argument also excludes empty or otherwise unequal bundles.

Assessment: the source theorem is stated sufficiently precisely, and the required restrictions and utility hypotheses are verified.

5. Validity and size of the constructed instance

The parameter choices give
$$ 0<\alpha\le\frac1{4n}, \qquad \beta=1-n\alpha\ge\frac34>\alpha. $$
All type masses are positive. The mass and supply normalization calculations are correct:
$$ n\alpha+\beta=1, \qquad 2n\alpha+2\beta=2. $$

The original types remain distinct because their first-ranked items remain distinct. The additional type has a new first-ranked item, so it cannot duplicate an original type. This addresses the requirement that the input is a support of preference types rather than an arbitrary list of separately labeled agents.

All numbers are dyadic with polynomial encoding length. The catalogue and ranking lists also have polynomial size, and $k=2$ satisfies the target domain restrictions.

Assessment: the construction is a valid polynomial-size target instance.

6. Preservation of original comparisons

Restriction of an admissible extended utility to $H$ preserves positivity, strict ranking consistency, and every original DD inequality.

Conversely, the proposed extension of an original utility is valid. The choice
$$ 0<\varepsilon<\min\{d,c/2\} $$
ensures positive utilities for both added items, strict ranking at the two new boundaries, and nonincreasing gaps across the original and added portions.

The last original gap $d$ exists because the source catalogue contains $2n$ items with $n\ge3$. The extension leaves original item utilities unchanged.

These restriction and extension statements establish both directions of the claimed universal comparison equivalence. No normalization assumption on utilities is silently introduced.

Assessment: comparison preservation is complete.

7. Forward and reverse implications

In the forward direction, the source allocation partitions $H$ into two-item bundles, so assigning mass $\alpha$ to each satisfies every original supply. The additional bundle satisfies both new supplies.

Original pairwise comparisons transfer by the established equivalence. Each comparison involving the additional type is justified by strict itemwise ranking and equal bundle sizes: both items of the preferred bundle rank above both items of the other bundle.

In the reverse direction, Section 1 legitimately supplies one bundle per type. Since $\beta>\alpha$, any original item in the additional type’s bundle would exceed that item’s supply. Its bundle must therefore be $\{a,b\}$.

That bundle exhausts both new supplies. Nonnegativity and positive original type masses exclude either new item from every original bundle. The remaining supply equations force each original item to appear in exactly one original bundle. Thus these bundles form a complete indivisible allocation, and comparison preservation transfers their necessary DD envy-freeness back to the source.

Assessment: both implications hold without missing feasibility or quantifier conditions.

The polynomial many-one reduction and polynomial certificate verification together establish the claimed $\mathrm{NP}$-completeness. No additional clarification or mathematical argument is needed.

⟨structured verdict parsed — rendered above⟩