Answer: Polynomial-time solvable in \(m,\tau,L\).
Theorem 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateStrategies 1 and 2 specify a SPE.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite outcome set \(O\) and a rational distribution \(\mu\) of support size \(\tau\) over matched pairs of strict rankings, compute a succinct equilibrium-strategy prescription for each supported pair and the exact mass \(\nu_o=\sum_{\theta:E(\theta)=o}\mu_\theta\) ending at each \(o\in O\), where each pair describes an independent full-information VAOV case.
Let \(O\) be a nonempty finite outcome set, with \(m=|O|\). A society is given by its support: a list of \(\tau\) ordered pairs \(\theta=(\succ_1,\succ_2)\) of strict rankings of \(O\), each with positive binary rational mass \(\mu_\theta\), where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible ranking pairs; \(L\) is the total input bit length.
For each supported pair, independently, two parties know both rankings and play the following VAOV game. Party \(1\) offers first; the parties alternate offering an available outcome. Acceptance ends the game with that outcome; rejection permanently removes it and makes the rejecting party the next proposer. The sole remaining outcome is accepted automatically. Lotteries are inadmissible, and both parties prefer every agreement to disagreement; preferences depend only on the final outcome.
Compute, for each supported pair, a pure subgame-perfect equilibrium strategy profile, represented by a polynomial-length algorithmic prescription that returns the prescribed offer or response at every legal history in polynomial time. Also compute every exact rational mass \(\nu_o=\sum_{\theta:E(\theta)=o}\mu_\theta\), where \(E(\theta)\) is the outcome induced by the returned profile, including zero masses.
Is this computation solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For a single full-information VAOV instance, explicit strategies form a subgame-perfect equilibrium, and the prescribed action at a given history can be computed in time linear in \(m\); the equilibrium outcome is unique. These are individual-instance results, without an explicit support-input mass-computation statement. [Source](https://arxiv.org/abs/1805.00913v1).
The computation is polynomial-time solvable. The individual-instance equilibrium theorem supplies compact strategy prescriptions; explicit support permits computing the outcome separately for each supported pair and summing its mass exactly.
Fix an ordering of the outcome labels to make every choice deterministic. For a supported pair, store both rankings.
At a nonterminal offering history, let \(S\) be the remaining outcomes, let \(p\) be the proposer, and let \(q=3-p\). Define \(B_p\) and \(B_q\) as the lowest-ranked \(\lfloor(|S|-1)/2\rfloor\) and \(\lfloor|S|/2\rfloor\) outcomes in their respective rankings restricted to \(S\).
Define \(P(S,p)\) to select the first labeled outcome in \(B_p\cap B_q\) when this intersection is nonempty, and otherwise the outcome worst for \(q\) in \(S\).
For nonempty \(S\), define \(F(S,p)\) by repeatedly deleting \(P(S,p)\) and switching proposers until one outcome remains; return that outcome.
Prescribe the offer \(P(S,p)\). On receiving an offer \(x\), prescribe acceptance exactly when
\(x\succ_q F(S\setminus\{x\},q)\).
With one remaining outcome, prescribe automatic acceptance.
These are the cited paper’s Strategies 1 and 2, with deterministic selection within the intersection. Its Theorem 10 states that they constitute a pure subgame-perfect equilibrium. [Erlich, Hazon, and Kraus, Section 4](https://arxiv.org/pdf/1805.00913v1).
The theorem’s hypotheses hold for every supported pair:
The definition of \(F\) uses hypothetical forced rejections to evaluate a response. Actual play follows the acceptance rule above.
Every legal nonterminal history determines the available set and the proposer: remove all previously rejected outcomes from \(O\), and use the parity of their number to identify whose turn it is. At a response history, also read the pending offer. These operations take polynomial time because there are at most \(m-1\) rejected offers.
Thus, for each supported pair, the output can consist of its two ranking arrays and the fixed program implementing the prescription. The program specifies actions at every legal history, including histories reached after deviations. Subgame perfection follows from the cited theorem, rather than merely from correctness along the initial play path.
After relabeling outcomes by integers, the ranking data occupy \(O(m\log(m+1))\) bits per supported pair. The total strategy representation therefore has polynomial length.
We only need a polynomial implementation; the sharper linear-time individual-instance result is unnecessary.
By scanning the stored rankings, one can compute \(P(S,p)\) in \(O(m)\) elementary operations. Evaluating \(F(S,p)\) makes at most \(m-1\) deletions, so a straightforward implementation takes \(O(m^2)\) operations. Consequently, every prescribed action can be evaluated in polynomial time.
For each supported pair \(\theta\), simulate the returned profile from the initial history. Each round either terminates with acceptance or removes one outcome. Hence there are at most \(m\) rounds. Using the straightforward evaluator, this simulation takes \(O(m^3)\) elementary operations per pair, and \(O(\tau m^3)\) overall.
Let its terminal outcome be \(E(\theta)\). By construction, this is precisely the outcome induced by the returned strategy profile. For \(m=1\), the unique outcome is accepted automatically.
Index the support by \(j\in\{1,\ldots,\tau\}\), and write each input mass as
\(\mu_j=a_j/b_j\), where \(a_j,b_j\) are positive binary integers. Reduction to lowest terms is unnecessary.
Form the common denominator
\(Q=\prod_{j=1}^{\tau}b_j\).
For every \(o\in O\), initialize \(N_o=0\). After computing \(E(\theta_j)\), add
\(a_j(Q/b_j)\)
to \(N_{E(\theta_j)}\). Output
\(\nu_o=N_o/Q\)
for every outcome, using \(0/1\) when \(N_o=0\). Fractions may optionally be reduced by greatest common divisors.
The division \(Q/b_j\) is exact. Moreover, the resulting mass is correct because
\(\displaystyle \frac{N_o}{Q}
=\sum_{\{j:E(\theta_j)=o\}}\frac{a_j}{b_j}
=\nu_o\).
It remains to bound the arithmetic size. Since denominator encodings are part of the input,
\(\log_2 Q=\sum_j\log_2 b_j\le L\).
Thus \(Q\) has \(O(L)\) bits.
Normalization gives
\(\displaystyle \sum_{j=1}^{\tau}a_j(Q/b_j)=Q\).
All summands are positive integers. Therefore every partial accumulator satisfies
\(0\le N_o\le Q\),
so its bit length is also \(O(L)\). Integer multiplication, exact division, addition, and optional fraction reduction all take polynomial time on these operands.
The complete mass output has \(O(m(L+1))\) bits, including outcomes of zero mass.
The strategy representations, their action evaluators, the simulations for all \(\tau\) supported pairs, and the exact rational aggregation all have polynomial cost in \(m,\tau,L\). No enumeration of unsupported ranking pairs is required.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The returned strategies are compact pure subgame-perfect equilibrium prescriptions, their actions are computable in polynomial time at every legal history, and the exact outcome masses can be computed in polynomial time. No major or minor issues were found.
The cited result applies to the stated game: two parties have strict, fully known rankings over finitely many outcomes; rejected outcomes are removed; the rejecting party becomes the next proposer; and the final outcome is accepted automatically. These hypotheses match the task.
The prover’s bottom-set sizes correctly reproduce the paper’s definitions. Writing \(n=|S|\), the proposer’s size is
\[
\left\lfloor\frac{n-1}{2}\right\rfloor
=
\begin{cases}
(n-1)/2,&n\text{ odd},\\
n/2-1,&n\text{ even},
\end{cases}
\]
and the responder’s size is \(\lfloor n/2\rfloor\). The intersection-based offer and fallback to the responder’s worst outcome match Strategy 1. Selecting deterministically within the intersection is permitted.
The forced-rejection evaluation defining \(F(S\setminus\{x\},q)\) matches the continuation used in Strategy 2. The paper uses weak preference for acceptance, whereas the prover writes strict preference. This difference is harmless: \(x\) has been removed, so the continuation outcome cannot equal \(x\); strict rankings therefore make the two tests equivalent. The singleton rule handles the case where rejection would otherwise leave an empty set.
Theorem 10 asserts that Strategies 1 and 2 specify a subgame-perfect equilibrium. The prover identifies those strategies and verifies their applicable hypotheses, so this citation justifies the equilibrium claim. [Source: Section 4, Strategies 1–2 and Theorem 10](https://arxiv.org/pdf/1805.00913v1).
The remaining set is determined by removing precisely the previously rejected offers. The proposer is determined by the parity of the number of rejections, since party \(1\) starts and every rejection switches proposers.
At a response history, the pending offer is still available until rejected. Thus the expression \(F(S\setminus\{x\},q)\) uses exactly the state resulting from rejection.
The prescription depends on this state rather than on whether earlier actions followed the prescription. It consequently specifies actions after deviations as required for subgame perfection.
The forced-rejection procedure terminates: each iteration removes one outcome, and it stops at a singleton. Its argument is nonempty whenever it is invoked by a nonterminal response rule.
After assigning integer identifiers to outcomes, each ranking can be stored in \(O(m\log(m+1))\) bits. Two rankings per supported pair and a fixed evaluator therefore give polynomial-length representations.
With a membership array for \(S\), scanning the rankings determines both bottom sets and their intersection in \(O(m)\) elementary operations. The deterministic label choice also takes at most \(O(m)\) operations.
Evaluating \(F\) requires at most \(m-1\) such iterations, giving the stated \(O(m^2)\) operation bound. Reading the history and comparing the offered outcome with the continuation outcome also have polynomial cost.
These are elementary-operation bounds; the associated indices and ranking entries have polynomial bit length, so they imply polynomial bit complexity as well.
Each simulated round either accepts an outcome or rejects and removes one. Hence at most \(m\) rounds occur.
Using the stated action evaluator yields the valid upper bound \(O(m^3)\) elementary operations per supported pair and \(O(\tau m^3)\) overall. This need not be optimal to settle the task.
The terminal outcome is, by the simulation’s definition, the outcome induced by the returned profile. The case \(m=1\) is explicitly handled by automatic acceptance. Outcome uniqueness is unnecessary for this aggregation, since the task asks for the outcomes of the returned profiles.
The common denominator \(Q=\prod_j b_j\) is positive, and every division \(Q/b_j\) is exact. Therefore the accumulator construction gives
\[
\frac{N_o}{Q}
=
\sum_{\{j:E(\theta_j)=o\}}\frac{a_j}{b_j},
\]
which is exactly the required mass.
The denominator-size estimate is correct: \(\log_2 Q\le L\), so its binary representation has \(O(L+1)\) bits.
Normalization gives \(\sum_j a_j(Q/b_j)=Q\). Since all contributions are positive, each contribution and every partial accumulator are bounded by \(Q\). Thus the arithmetic operands remain polynomial in input length, and the multiplication, division, addition, and optional reduction operations have polynomial bit complexity.
Initializing all \(m\) accumulators and emitting every outcome explicitly includes zero masses. The claimed \(O(m(L+1))\) bound for the mass representations is valid.
No repair is required. The strict-versus-weak acceptance comparison is equivalent on its stated domain, and all boundary cases needed for the computation are covered.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.