d4-conf-ijcai-2018-0732 (d4-conf-ijcai-2018-0732)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), a directed visibility graph \(H=(T,A)\), single-minded valuations \(v_t\) with preferred integral bundle sizes \(q_t\le M\), and rational supply \(B\) per unit population, choose nonnegative prices \(p_t\) and nonnegative masses \(y_{t,j}\) assigned integral bundle sizes \(j\in\{0,\ldots,M\}\) to maximize \(\sum_{t,j} y_{t,j}v_t(j)\). Require \(\sum_j y_{t,j}=\mu_t\), \(\sum_{t,j}j y_{t,j}\le B\), \(p_t\le p_s\) for each \((t,s)\in A\), and positive \(y_{t,j}\) only when \(j\) maximizes \(v_t(j)-p_tj\); characterize the complexity in \(M, |T|, |A|\), and input bit length, or decide whether the optimum is at least a given rational \(K\).

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\) summing to \(1\); \(\tau=|T|\) is the support size, not the number of possible types.
Let \(m=M\ge1\) be the integral bundle-size bound. Each type has a preferred size \(q_t\in\{1,\ldots,m\}\) and value \(a_t\in\mathbb Q_{>0}\), with \(v_t(q_t)=a_t\) and \(v_t(j)=0\) for every other \(j\in\{0,\ldots,m\}\).
The remaining input is a directed visibility graph \(H=(T,A)\), supply \(B\in\mathbb Q_{>0}\) per unit population, and threshold \(K\in\mathbb Q\). Integers and rationals are binary encoded; \(L\) is the total input bit length.
An outcome chooses one finite price \(p_t\in\mathbb R_{\ge0}\) per type and masses \(y_{t,j}\in\mathbb R_{\ge0}\), satisfying \(\sum_{j=0}^{m}y_{t,j}=\mu_t\), \(\sum_{t\in T}\sum_{j=0}^{m}j y_{t,j}\le B\), and \(p_t\le p_s\) for every \((t,s)\in A\).
Require \(y_{t,j}>0\) only if \(j\in\operatorname*{argmax}_{k\in\{0,\ldots,m\}}\{v_t(k)-p_t k\}\). Tied maximizers may receive arbitrary shares of a type's mass; these choices belong to the outcome. Welfare is \(W=\sum_{t\in T}\sum_{j=0}^{m}y_{t,j}v_t(j)\).

Is deciding whether an outcome with \(W\ge K\) exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard under this binary encoding? Express running times in \(m,\tau,|A|,L\).

For finite lists of indivisible buyers, welfare and revenue maximization with these valuations and fairness constraints are strongly \(\mathrm{NP}\)-hard ([Flammini–Mauro–Tonelli](https://www.ijcai.org/proceedings/2018/0034.pdf)); discrete welfare maximization also admits a PTAS ([Mauro](https://iris.gssi.it/retrieve/dfe4cef6-f6f5-ea31-e053-6605fe0a48e4/2019_Mauro.pdf)).
No result settling this exact mass formulation was identified in the literature search.

Proven result. The decision problem is in \(\mathrm P\). A common price implements a welfare-maximizing outcome, regardless of the visibility graph. The ability to split a type’s mass between tied maximizers is essential.

1. Characterizing demand. Define the value per unit and the maximum resource consumption of type \(t\) by
\[ r_t=\frac{a_t}{q_t}, \qquad w_t=\mu_tq_t. \]

For any price \(p_t\ge0\), only bundle sizes \(0\) and \(q_t\) can maximize utility. Indeed, when \(p_t>0\), every other positive size \(j\) has utility \(-p_tj<0\), whereas size \(0\) has utility \(0\). When \(p_t=0\), size \(q_t\) has utility \(a_t>0\), exceeding the utility of every other size.

Comparing the utilities of \(0\) and \(q_t\) therefore gives:

• If \(p_t<r_t\), all mass must receive \(q_t\).
• If \(p_t=r_t\), any fraction may receive \(q_t\), with the remainder receiving \(0\).
• If \(p_t>r_t\), all mass must receive \(0\).

Consequently, writing \(x_t=y_{t,q_t}\), every feasible outcome satisfies
\[ 0\le x_t\le\mu_t,\qquad S:=\sum_tq_tx_t\le B,\qquad W=\sum_ta_tx_t. \]

Temporarily dropping price implementability gives an upper bound on achievable welfare. We will construct prices attaining that bound.

2. Constructing an optimal outcome. Sort the types so that
\[ r_{t_1}\ge r_{t_2}\ge\cdots\ge r_{t_\tau}, \]
breaking ties arbitrarily, and let \(C_i=\sum_{h=1}^iw_{t_h}\), with \(C_0=0\).

If \(B\ge C_\tau\), assign every type its preferred bundle and set every price to \(0\). This outcome is feasible and attains \(\sum_t\mu_ta_t\), which is an upper bound because each type’s valuation never exceeds \(a_t\).

Suppose instead that \(B<C_\tau\). Let \(k\) be the first index with \(C_k\ge B\), and put \(\lambda=r_{t_k}>0\). Assign
\[ x_{t_i}= \begin{cases} \mu_{t_i},&i<k,\\ (B-C_{k-1})/q_{t_k},&i=k,\\ 0,&i>k. \end{cases} \]
The choice of \(k\) ensures \(0<x_{t_k}\le\mu_{t_k}\), and total resource consumption is exactly \(B\).

Set \(p_t=\lambda\) for every type. Every type with \(r_t>\lambda\) receives its entire mass’s preferred bundle; every type with \(r_t<\lambda\) receives nothing. Types with \(r_t=\lambda\) are indifferent, so all the assigned shares are permitted. Set \(y_{t,0}=\mu_t-x_t\) and all remaining allocation variables to zero.

The common price satisfies \(p_t\le p_s\) on every arc. Thus the construction is a feasible outcome for any \(H\), including graphs with cycles.

3. Proving optimality. For any feasible outcome, the characterization above implies
\[ W=\lambda S+\sum_t(a_t-\lambda q_t)x_t. \]
Since \(\lambda\ge0\), \(S\le B\), and \(0\le x_t\le\mu_t\),
\[ W\le \lambda B+ \sum_{t:r_t>\lambda}(a_t-\lambda q_t)\mu_t. \]

To justify the second term, positive coefficients are bounded using \(x_t\le\mu_t\); negative coefficients contribute at most zero; and zero coefficients contribute zero.

Our constructed outcome attains this bound: it uses exactly \(B\) resources, fully serves every type with a positive coefficient, and serves no type with a negative coefficient. Hence it is globally optimal, even among allocations obtained by dropping all price constraints.

Its welfare is
\[ W^\star= \sum_{i<k}\mu_{t_i}a_{t_i} +\frac{a_{t_k}}{q_{t_k}}(B-C_{k-1}) \]
when \(B<C_\tau\), and \(W^\star=\sum_t\mu_ta_t\) otherwise. The decision answer is yes exactly when \(W^\star\ge K\).

4. Binary running time. Sorting requires \(O(\tau\log(\tau+1))\) exact rational comparisons. Computing prefix sums, the optimum, and its comparison with \(K\) requires \(O(\tau)\) further rational operations.

All intermediate rationals can be maintained with \(O(L)\)-bit numerators and denominators: denominators of prefix sums divide products of the input denominators, whose total bit length is \(O(L)\). The additional products and divisions in the optimum formula preserve this bound.

Using elementary exact arithmetic, a conservative bit-operation bound, including reading the input, is
\[ O\!\left((\tau\log(\tau+1)+|A|+1)L^2\right). \]
There is no iteration over \(1,\ldots,m\); the numerical value of \(m\) affects the bound only through its binary encoding in \(L\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned decision problem correctly. The common-price construction is feasible for every visibility graph, attains the stated welfare upper bound, and can be computed in polynomial time under the specified binary encoding. No major or minor mathematical issues were found.

1. Demand characterization

The demand argument covers every allowed price and bundle size.

For \(p_t>0\), every positive size \(j\ne q_t\) has utility \(-p_tj<0\), while size \(0\) has utility \(0\). Such a size therefore cannot maximize utility. For \(p_t=0\), the preferred size has utility \(a_t>0\), while every other size has utility \(0\). Positivity of \(a_t\), explicitly assumed in the task, is essential here and is correctly used.

The comparison between the remaining sizes is exactly
\(a_t-p_tq_t=q_t(r_t-p_t)\).
Since \(q_t>0\), the three stated demand cases follow, including the equality case permitting arbitrary splitting.

Consequently, all feasible outcomes are correctly represented by \(x_t=y_{t,q_t}\), with bounds \(0\le x_t\le\mu_t\), supply consumption \(\sum_tq_tx_t\le B\), and welfare \(\sum_ta_tx_t\). Dropping implementability gives a valid upper bound.

2. Construction and edge cases

If \(B\ge C_\tau\), assigning every type its preferred size respects supply. At common price \(0\), each preferred size is the unique maximizer. The valuation bound \(v_t(j)\le a_t\), together with total mass \(\mu_t\), proves the asserted welfare upper bound.

If \(B<C_\tau\), the index \(k\) exists. Because every \(w_t=\mu_tq_t\) is positive and \(B>0\), its definition gives
\(C_{k-1}<B\le C_k\).
Thus the proposed partial allocation satisfies
\(0<x_{t_k}\le\mu_{t_k}\), and its total consumption is exactly \(B\).

The sorted order ensures that every type with \(r_t>\lambda\) occurs before \(k\), and every type with \(r_t<\lambda\) occurs after \(k\). The construction therefore gives those types precisely the allocations required at price \(\lambda\). Types with \(r_t=\lambda\) may receive any of the specified shares, including zero or their full mass. Arbitrary ordering within ties causes no problem.

Setting \(y_{t,0}=\mu_t-x_t\) completes the mass constraints. Since \(q_t\ge1\), these two allocation coordinates are distinct. The common price is finite, positive in this branch, and satisfies every visibility inequality by equality.

The construction also covers \(\tau=1\), \(m=1\), exact prefix-sum equality \(B=C_k\), equal ratios, and graphs with cycles.

3. Optimality

The identity
\(W=\lambda S+\sum_t(a_t-\lambda q_t)x_t\)
is algebraically correct.

Replacing \(\lambda S\) by \(\lambda B\) is valid because \(\lambda\ge0\). For each remaining term:

• A positive coefficient permits the upper bound obtained by replacing \(x_t\) with \(\mu_t\).
• A negative coefficient contributes at most zero because \(x_t\ge0\).
• A zero coefficient contributes zero.

This proves the stated upper bound for every feasible allocation in the relaxation.

The constructed outcome attains every part of that bound: it consumes \(B\), fully serves all types with positive coefficients, and gives zero preferred-bundle mass to all types with negative coefficients. Hence it is optimal in the relaxation and in the original problem.

The displayed formula for \(W^\star\) follows directly from the allocation. Comparing this attained maximum with \(K\) is therefore equivalent to the requested existence decision, for every rational \(K\).

4. Binary running time

The operation counts are correct: sorting uses \(O(\tau\log(\tau+1))\) rational comparisons, and the remaining calculations use \(O(\tau)\) rational operations.

The claimed intermediate bit-length bound is also valid. Prefix-sum denominators divide products of input denominators, and their numerator sizes remain \(O(L)\). Multiplying by preferred sizes, forming ratios, computing the welfare expression, and comparing with \(K\) preserve \(O(L)\) bit lengths when fractions are maintained in reduced form. Exact comparison and elementary rational arithmetic can consequently be performed within the stated conservative quadratic cost per operation.

Thus
\(O((\tau\log(\tau+1)+|A|+1)L^2)\)
is a valid conservative bit-operation bound, including input reading. No enumeration of bundle sizes is required, so dependence on \(m\) occurs only through its encoded contribution to \(L\).

The supplied literature context requires no additional theorem application: the argument is self-contained and uses the mass-splitting provision explicitly.

Required clarification

None. The output establishes the claimed polynomial-time classification.

⟨structured verdict parsed — rendered above⟩