d4-conf-ijcai-2022-0127 (d4-conf-ijcai-2022-0127)

Given rational masses \(\mu_t\) of advertiser types \(t=(w,v,b)\), slot-class supplies \(q_k\), group-specific click-through rates \(\alpha_{wk}\), quality factors \(\gamma_w\), and \(\beta\leq 1\), compute group allocations \(x_{wk}\) with \(x_{hk}+x_{\ell k}=q_k\). For each group \(w\), define \(V_w(z)\) as the maximum of \(\sum_{t\in T_w,k}\gamma_w\alpha_{wk}b_t y_{tk}\), subject to \(\sum_{t\in T_w}y_{tk}=z_k\), \(\sum_k y_{tk}\leq\mu_t\), and \(y_{tk}\geq0\). Require \(V_h(x_h)\geq\beta V_h(x_\ell)\) and \(V_\ell(x_\ell)\geq\beta V_\ell(x_h)\).

A society is given by its support: the list of \(\tau\) advertiser types \(t=(w,v_t,b_t)\) with positive binary-rational masses \(\mu_t\), where \(w\in\{h,\ell\}\) and \(v_t,b_t\geq0\) are rational. Here \(\tau\) is the support size, not the number of possible types; masses need not sum to one. Valuations \(v_t\) do not enter the fairness criterion, which uses reported bids \(b_t\).
There are \(m\geq1\) divisible slot classes with positive rational supplies \(q_k\). Put \(T_w=\{t:w_t=w\}\) and \(Q=\sum_{k=1}^m q_k\), and require \(\sum_{t\in T_w}\mu_t\geq Q\) for both groups.
All input numbers are binary rationals; \(L\) denotes their total encoding length. Quality factors satisfy \(\gamma_w\in[0,1]\), click-through rates satisfy \(1\geq\alpha_{w1}\geq\cdots\geq\alpha_{wm}\geq0\) for both groups in the same class order, and \(0<\beta\leq1\).
For \(0\leq z_k\leq q_k\), define \(V_w(z)=\max\{\sum_{t\in T_w}\sum_{k=1}^m\gamma_w\alpha_{wk}b_t y_{tk}:\sum_{t\in T_w}y_{tk}=z_k\ (\forall k),\ \sum_{k=1}^m y_{tk}\leq\mu_t\ (\forall t\in T_w),\ y_{tk}\geq0\}\). Each comparison evaluates this maximum independently.
The computational problem is to find rational allocations \(x_{wk}\geq0\) satisfying \(x_{hk}+x_{\ell k}=q_k\) for every class and \(V_h(x_h)\geq\beta V_h(x_\ell)\), \(V_\ell(x_\ell)\geq\beta V_\ell(x_h)\).

Can such an allocation be computed in time polynomial in \(m,\tau,L\), or is this search problem \(\mathrm{NP}\)-hard?

For indivisible slots, group envy-cycle elimination computes a group \(\beta\)-EFX allocation: each group values its bundle at least \(\beta\) times its optimal assignment value for the other bundle after removal of any one slot. [Birmpas et al.](https://arxiv.org/pdf/2107.08271)
For a different model with online arrivals and binary matching preferences, fractional class envy-freeness admits a \(1-1/e\) approximation. [Hosseini et al.](https://arxiv.org/abs/2203.03751) The search located no result addressing exactly the mass-allocation problem above.

Result. The search problem is polynomial-time solvable. Equal division settles the full stated model, including arbitrary support sizes, bids, masses, and class supplies.

Construction. For every class \(k\), output
\[ x_{hk}=x_{\ell k}=\frac{q_k}{2}. \]
These rational allocations are nonnegative and satisfy \(x_{hk}+x_{\ell k}=q_k\).

Proof that the comparison values are well-defined. Fix a group \(w\) and any vector \(z\) satisfying \(0\le z_k\le q_k\). Write \(M_w=\sum_{t\in T_w}\mu_t\). The assumptions give \(M_w\ge Q>0\). Define
\[ y_{tk}=\frac{\mu_t z_k}{M_w}. \]
Then
\[ \sum_{t\in T_w}y_{tk}=z_k, \qquad \sum_{k=1}^{m}y_{tk} =\frac{\mu_t\sum_{k=1}^{m}z_k}{M_w} \le\mu_t, \]
because \(\sum_k z_k\le Q\le M_w\). Thus the feasible set defining \(V_w(z)\) is nonempty. It is closed and bounded: each variable satisfies \(0\le y_{tk}\le\mu_t\). Consequently the linear objective attains a finite maximum. Its coefficients are nonnegative, so \(V_w(z)\ge0\).

Proof of fairness. Let \(r=(q_1/2,\ldots,q_m/2)\). Since \(x_h=x_\ell=r\), both independent comparisons for group \(w\) evaluate exactly the same optimization problem. Therefore
\[ V_h(x_h)-\beta V_h(x_\ell) =(1-\beta)V_h(r)\ge0, \]
and
\[ V_\ell(x_\ell)-\beta V_\ell(x_h) =(1-\beta)V_\ell(r)\ge0. \]
Both required inequalities hold, including when \(\beta=1\).

Complexity and scope. The algorithm performs \(m\) divisions by two; each resulting rational has encoding length at most a constant larger than that of its input supply. Reading the input and producing the allocation therefore takes time polynomial in \(m,\tau,L\). Computing the maxima is unnecessary.

This construction applies to every permitted instance. A further requirement such as welfare optimization would create an additional question, but no such requirement occurs in the stated search problem.

⟨structured verdict parsed — rendered above⟩

The prover fully resolves the stated search problem. The equal-division construction is correct, satisfies every required constraint, and has polynomial running time. No mathematical gaps were found.

• The construction satisfies the allocation constraints.

For every class \(k\), the prover sets \(x_{hk}=x_{\ell k}=q_k/2\). Since \(q_k>0\), both allocations are nonnegative rational numbers, and \(x_{hk}+x_{\ell k}=q_k\). Each coordinate also lies in the domain required for evaluating \(V_w\).

• The comparison problems are feasible for every permitted argument.

Fix either group \(w\) and any vector \(z\) with \(0\leq z_k\leq q_k\). The assumption \(M_w=\sum_{t\in T_w}\mu_t\geq Q>0\) ensures that the denominator in the proposed feasible assignment is positive.

For \(y_{tk}=\mu_t z_k/M_w\), nonnegativity follows from the input assumptions. Summing over types gives \(\sum_{t\in T_w}y_{tk}=z_k\). Summing over classes gives \(\sum_k y_{tk}=\mu_t(\sum_k z_k)/M_w\leq\mu_t\), because \(\sum_k z_k\leq Q\leq M_w\). Thus all assignment constraints hold. This argument also covers zero coordinates of \(z\) and the boundary case \(M_w=Q\).

• Each comparison value is finite, attained, and nonnegative.

The feasible set has finitely many variables. Its linear equalities and weak inequalities make it closed, and the capacity constraints imply \(0\leq y_{tk}\leq\mu_t\), making it bounded. Together with nonemptiness, these facts ensure that the continuous linear objective attains a finite maximum.

Every objective coefficient \(\gamma_w\alpha_{wk}b_t\) is nonnegative under the stated assumptions, so \(V_w(z)\geq0\). Zero bids, zero quality factors, and zero click-through rates introduce no exception.

• Both fairness inequalities follow exactly as written.

With \(r=(q_1/2,\ldots,q_m/2)\), both group allocation vectors equal \(r\). For each fixed group \(w\), the two comparisons therefore have identical feasible sets and objective functions. Evaluating the maxima independently does not change their values; no common maximizing assignment is needed.

Each required difference equals \((1-\beta)V_w(r)\), which is nonnegative because \(0<\beta\leq1\) and \(V_w(r)\geq0\). This includes \(\beta=1\), when both differences are zero.

• The polynomial-time claim is justified.

The output requires only halving each of the \(m\) rational supplies and writing two copies. Halving a binary-encoded rational increases its encoding length by at most a constant under the usual numerator–denominator or binary-fraction representation. The total output length and bit-operation cost are polynomial in the stated input parameters.

Computing any maximum is unnecessary. Neither welfare optimization nor a requirement to output internal assignments appears in the task, so their omission is appropriate.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩