d4-conf-atal-2016-0315 (d4-conf-atal-2016-0315)

Given a finite support of complete local allocation types \(\Theta\), with binary-rational masses \(\mu_\theta\) summing to one, where each type specifies an independent two-agent instance, compute the maximum population-average expected utility \(V=\max_{(\sigma_\theta)}\sum_{\theta\in\Theta}\mu_\theta E_\theta(\sigma_\theta)\) for the A-side participants.

A society is given by its support: a list \(\Theta\) of \(\tau\ge 1\) types with positive binary-rational masses \(\mu_\theta\) summing to one. Here \(\tau\) is the support size, not the number of possible types.
Each type specifies an independent instance with two agents \(A,B\), \(2m_\theta\) distinct indivisible items, \(m_\theta\ge 1\), a strict ranking of all items for \(B\), and pairwise distinct positive binary-rational item utilities for \(A\), extended additively to bundles.
There are \(m_\theta\) rounds. In each round an independent fair coin selects order \(AB\) or \(BA\); each agent picks one remaining item. Agent \(B\) always picks her highest-ranked remaining item, and \(A\) knows \(B\)'s ranking.
A feasible strategy \(\sigma_\theta\) chooses \(A\)'s item from the currently available items, using the observed current order and remaining items, without knowledge of future coin flips. Let \(E_\theta(\sigma_\theta)\) be her expected total utility, including randomness in the first round.
Strategies may be chosen separately for every type, with no constraints linking types. Compute exactly \(V=\max_{(\sigma_\theta)}\sum_{\theta\in\Theta}\mu_\theta E_\theta(\sigma_\theta)\). Let \(m=\max_\theta m_\theta\) and let \(L\) be the total input bit length.

Is exact computation of \(V\) polynomial-time in \(m,\tau,L\), or is deciding \(V\ge q\) for an input binary-rational threshold \(q\) NP-hard?

For a single finite two-agent instance with general additive utilities and a specified first-round order, maximum expected utility is computable in polynomial time in the number of rounds.

Proven result. Exact computation of \(V\) is polynomial-time in \(m,\tau,L\), using the single-instance polynomial-time result supplied in the question. Consequently, deciding \(V\ge q\) belongs to \(\mathrm{P}\).

1. Optimal strategies can depend only on the permitted observations.

Fix a type \(\theta\), and suppress its subscript. Write \(u(x)\) for \(A\)'s utility of item \(x\), and \(b(S)\) for \(B\)'s highest-ranked item in a nonempty set \(S\).

For an even-sized set \(S\), let \(F(S)\) be the optimal expected utility obtainable from \(S\), starting immediately before the next round's coin flip. Set \(F(\varnothing)=0\). Let \(G_{AB}(S)\) and \(G_{BA}(S)\) be the corresponding optimal values when that round's order has already been specified.

Backward induction gives, for nonempty even-sized \(S\),

\[ G_{AB}(S)= \max_{x\in S} \left( u(x)+F\bigl(S\setminus\{x,b(S\setminus\{x\})\}\bigr) \right), \]

\[ G_{BA}(S)= \max_{x\in S\setminus\{b(S)\}} \left( u(x)+F\bigl(S\setminus\{b(S),x\}\bigr) \right), \]

and

\[ F(S)=\frac{G_{AB}(S)+G_{BA}(S)}{2}. \]

Indeed, under order \(AB\), choosing \(x\) determines \(B\)'s subsequent pick uniquely. Under order \(BA\), \(B\) first removes \(b(S)\), after which \(A\) chooses \(x\). In both cases, future coin flips remain independent and fair, so the continuation value is precisely \(F\) of the remaining set. Every recursive argument has two fewer items, establishing the recurrences by induction.

These maxima are attained because their action sets are finite. Choose a maximizing action at every decision state, breaking ties by a fixed convention. This produces a deterministic optimal strategy using only the allowed observations. In particular, when \(A\) acts second and the currently available set is \(T\), her choice maximizes

\[ u(x)+F(T\setminus\{x\}),\qquad x\in T. \]

Thus it does not require knowing which item \(B\) just removed or any earlier history. If different histories reach the same available set and current order, the same optimal action works for both.

2. The random first-round order requires two conditional computations.

Let \(I_\theta\) be the initial item set, and define

\[ W_\theta^{AB}=G_{\theta,AB}(I_\theta), \qquad W_\theta^{BA}=G_{\theta,BA}(I_\theta). \]

The preceding backward-induction argument proves

\[ W_\theta:= \max_{\sigma_\theta}E_\theta(\sigma_\theta) = \frac{W_\theta^{AB}+W_\theta^{BA}}{2}. \]

For the upper bound, any feasible strategy has conditional expected utility at most \(W_\theta^{AB}\) or \(W_\theta^{BA}\), according to the first order. Averaging gives the displayed bound. For attainability, the state-based maximizing strategy constructed above attains both conditional optima.

Apply the supplied single-instance theorem once with first order \(AB\) and once with first order \(BA\). Its hypotheses hold: there are two agents, finitely many rounds, additive utilities, a known ranking for \(B\), and decisions without knowledge of future coin flips. The positivity and distinctness restrictions on \(A\)'s utilities are permitted special cases of general additive utilities. If the theorem requires numerical utilities for \(B\), assign decreasing integers along her ranking; these reproduce her choices and require only polynomial encoding length.

Thus \(W_\theta\) is computable using two polynomial-time single-instance calls.

3. Optimization separates across the explicitly listed types.

For every feasible strategy tuple,

\[ \sum_{\theta\in\Theta}\mu_\theta E_\theta(\sigma_\theta) \le \sum_{\theta\in\Theta}\mu_\theta W_\theta, \]

because every mass is positive and every typewise expected utility is bounded by its optimum.

Conversely, choose an optimal strategy for each type. The task imposes no constraints linking these choices, so this tuple is feasible and attains the upper bound. Therefore,

\[ \boxed{ V= \frac12\sum_{\theta\in\Theta} \mu_\theta\left(W_\theta^{AB}+W_\theta^{BA}\right). } \]

The algorithm makes exactly \(2\tau\) single-instance calls, followed by exact rational arithmetic.

4. Exact aggregation has polynomial bit complexity.

Write each item utility as \(a_{\theta,x}/b_{\theta,x}\), with positive integer denominator, and put

\[ D_\theta=\prod_{x\in I_\theta}b_{\theta,x}. \]

Every terminal bundle utility is an integer divided by \(D_\theta\). Conditional on a specified first order, a deterministic strategy has \(2^{m_\theta-1}\) equally likely future order sequences. Consequently, its conditional expected utility has the form

\[ \frac{N}{D_\theta 2^{m_\theta-1}} \]

for a nonnegative integer \(N\). This applies to the optimal conditional values because deterministic optimal strategies exist. Hence

\[ W_\theta= \frac{K_\theta}{D_\theta 2^{m_\theta}} \]

for a nonnegative integer \(K_\theta\).

Write \(\mu_\theta=c_\theta/d_\theta\). A common denominator for the final sum is

\[ R= 2^m \left(\prod_{\theta\in\Theta}d_\theta\right) \left(\prod_{\theta\in\Theta}D_\theta\right). \]

Indeed, each denominator \(d_\theta D_\theta 2^{m_\theta}\) divides \(R\). The total binary length of all input denominators is at most \(L\), so \(R\) has \(O(L+m)\) bits.

The numerator also has polynomial length. Each positive input utility is less than \(2^L\), and \(A\) receives at most \(m\) items. Since the masses sum to one,

\[ 0\le V\le m\,2^L. \]

Writing \(V=N_V/R\) therefore gives a numerator with \(O(L+m+\log(m+1))\) bits. The same bound controls partial sums because all summands are nonnegative. Products, denominator conversions, additions, and optional fraction reduction consequently take polynomial bit time.

Together with the supplied exact single-instance algorithm, this proves polynomial-time exact computation in \(m,\tau,L\). For a threshold \(q=a_q/b_q\), with \(b_q>0\), decide \(V\ge q\) by the exact integer comparison \(N_Vb_q\ge a_qR\), also in polynomial time.

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned task correctly, using the single-instance polynomial-time result explicitly supplied in the question. I found no major or minor mathematical issues.

• The backward-induction recurrences are correct.

For every nonempty even-sized set \(S\), there are at least two items. Thus, under order \(AB\), the set \(S\setminus\{x\}\) is nonempty and \(b(S\setminus\{x\})\) is defined. Under order \(BA\), the action set \(S\setminus\{b(S)\}\) is nonempty. Both transitions remove exactly two distinct items.

The immediate utility and continuation value are correctly specified in both recurrences. Independence and fairness of future coin flips justify using \(F\) for the continuation and averaging the two conditional values with equal weights.

The base case \(F(\varnothing)=0\) is correct. In particular, when there is one round, every continuation reaches this base case.

• The constructed optimal strategy satisfies the observation restriction.

Finite action sets and backward induction establish attainment by a deterministic strategy. Once the current order and available items are known, future opportunities depend only on the remaining set and independent future flips.

When \(A\) acts second, the available set \(T\) has odd cardinality, so \(T\setminus\{x\}\) has even cardinality and \(F(T\setminus\{x\})\) is defined. The displayed maximizing rule depends only on \(T\). It therefore does not require the identity of \(B\)'s preceding pick or earlier history.

This also justifies choosing consistent optimal actions when different histories reach the same permitted observation.

• The treatment of the random first-round order is valid.

Every feasible strategy has conditional values bounded above by the respective conditional optima. Averaging establishes the claimed upper bound.

Attainability is also justified: the state-based maximizing strategy is optimal at every decision state and hence attains both first-order conditional optima. The equality
\[ W_\theta=\frac{W_\theta^{AB}+W_\theta^{BA}}{2} \]
follows.

• The supplied single-instance result applies.

The question supplies polynomial-time computation of maximum expected utility for a single instance with general additive utilities and a specified first-round order. The prover applies it to precisely these two conditional problems.

Positive, distinct utilities are a permitted special case of general additive utilities. If numerical utilities for \(B\) are needed, decreasing positive integers reproduce the strict ranking, including on every remaining subset. Their encoding length is polynomial.

The backward-induction recurrences themselves may involve exponentially many subsets. This is not a runtime gap: the prover uses them to establish the strategy and conditioning identities, and uses the supplied theorem for polynomial-time computation.

• Optimization separates across types.

The upper bound follows term by term from positivity of the masses. Each typewise optimum is attained, and the task explicitly permits independent strategy choices across types. Consequently, the tuple of typewise optimal strategies attains the sum of the optima.

The formula for \(V\) and the count of \(2\tau\) single-instance calls are correct. The argument uses the explicitly listed support size, as required.

• The rational denominator and bit-length bounds are correct.

The product \(D_\theta\) is a common denominator for every bundle utility. With the first order fixed, there are exactly \(2^{m_\theta-1}\) equally likely future order sequences. This includes \(m_\theta=1\), when there is one empty future sequence. Deterministic optimal strategies therefore have the asserted conditional denominators.

Averaging the conditional values gives the denominator \(D_\theta2^{m_\theta}\). For every type,
\[ d_\theta D_\theta2^{m_\theta}\mid R, \]
because \(m_\theta\le m\) and the products defining \(R\) include the required factors.

The logarithms of the denominator factors sum to at most their total input encoding length, giving \(O(L+m)\) bits for \(R\). Positivity, the bound on each utility, and normalization of the masses establish
\[ 0\le V\le m2^L. \]
The numerator bound follows. Nonnegative partial sums satisfy the same magnitude bound, so exact aggregation takes polynomial bit time.

• The threshold comparison is correct.

Since \(R>0\) and \(b_q>0\), cross-multiplication preserves the inequality. The comparison is polynomial-time, including in the encoding length of \(q\).

No additional clarification or repair is needed. The conclusion is membership in \(\mathrm{P}\); the prover does not incorrectly claim that this unconditionally excludes NP-hardness.

⟨structured verdict parsed — rendered above⟩