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 package set \(O\), two binary-rational distributions \(\mu^1,\mu^2\) over complete strict rankings of \(O\), and a valid current VAOV history, suppose each distribution induces a strict transitive majority ranking. What move does the Theorem 10 SPE prescribe at that history, and what agreement outcome follows if both representatives continue using its strategies?
Let \(O=\{o_1,\ldots,o_m\}\), with \(m\geq2\). Each of two societies is given by its support: a list of \(\tau_k\) complete strict rankings with positive binary-rational masses summing to \(1\). Write \(\tau=\tau_1+\tau_2\) for total support size, not the number of possible rankings, and \(L\) for total input bit length.
Representative \(p_k\) prefers \(x\) to \(y\) exactly when the \(\mu^k\)-mass ranking \(x\) above \(y\) exceeds \(1/2\). These majority relations are promised to be complete, strict and transitive; both representatives know both relations and use them as their preferences.
In VAOV, \(p_1\) offers first; an offer is a single available package. Acceptance ends negotiation; rejection permanently removes that package and switches the proposer. The sole remaining package is accepted automatically. Both representatives prefer every agreement to disagreement; lottery offers are forbidden.
The input history consists of distinct rejected offers \(H\), optionally followed by a pending offer \(x\in S=O\setminus H\); no agreement has occurred. The current proposer is determined by the parity of \(|H|\).
At any state with proposer \(p_i\), responder \(p_j\), and \(n=|S|\geq2\), let \(B_j\) be the responder's bottom \(\lfloor n/2\rfloor\) packages in \(S\). Let \(B_i\) be the proposer's bottom \(\lfloor n/2\rfloor\) packages when \(n\) is odd, and bottom \(n/2-1\) when \(n\) is even.
The prescribed offering strategy selects the smallest-index package in \(B_i\cap B_j\) when that intersection is nonempty, and otherwise the responder's least preferred available package.
For a pending offer \(x\), define \(a\) as the sole survivor after rejecting \(x\) and then repeatedly using the prescribed offering strategy and rejecting every subsequent offer until one package remains. The prescribed response accepts exactly when \(x\succeq_j a\), where \(\succeq_j\) includes equality. At a singleton state, offer or accept its package.
Can the prescribed current move and the agreement reached when both representatives subsequently follow these strategies be computed in time polynomial in \(m,\tau,L\), or is this computation NP-hard?
For two explicitly given strict preference orders, these strategies form an SPE, and its move at any history is computable in \(O(m)\) time; the equilibrium agreement is unique ([2018 result](https://arxiv.org/pdf/1805.00913)).
The [2024 full version](https://u.cs.biu.ac.il/~krauss/data/articles/AIJ-2024.pdf) retains the discrete result. No result specifically treating the distribution-input problem above was located.
The prescribed current move and the subsequent agreement are computable in deterministic polynomial time in \(m,\tau,L\).
The proof has two parts: recover the representatives’ orders by exact majority calculations, then compute the negotiation using a single sequence of hypothetical rejections.
For society \(k\in\{1,2\}\), write its support as rankings \(R_{k1},\ldots,R_{k\tau_k}\), with masses \(w_{k\ell}=u_{k\ell}/v_{k\ell}\). Numerators and denominators are positive integers encoded in binary; finite binary fractions are included in this representation.
Precompute the position of every package in every supported ranking. Then whether \(R_{k\ell}\) ranks \(x\) above \(y\) can be determined by comparing their positions.
Define
\(D_k=\prod_{\ell=1}^{\tau_k}v_{k\ell}\), and \(W_{k\ell}=u_{k\ell}(D_k/v_{k\ell})\).
These are integers. Because the masses sum to one,
\(\sum_{\ell=1}^{\tau_k}W_{k\ell}=D_k\).
For every distinct pair \(x,y\), compute
\(A_k(x,y)=\sum_{\ell:\,R_{k\ell}\text{ ranks }x\text{ above }y}W_{k\ell}\).
The representative’s preference is therefore determined exactly by
\(x\succ_k y\quad\Longleftrightarrow\quad 2A_k(x,y)>D_k\).
There is no numerical approximation in this comparison.
Bit complexity. The binary length of \(D_k\) is at most one plus the sum of the binary lengths of the denominators, hence is \(O(L)\). Positivity and normalization imply that every \(W_{k\ell}\) and every \(A_k(x,y)\) lies between zero and \(D_k\), so these integers also have \(O(L)\) bits. All pairwise comparisons require \(O(\tau m^2)\) arithmetic and table operations. Exact integer addition, multiplication, division, and comparison on these lengths take polynomial time.
By the promise, the resulting relation is a strict total order. To turn it into an explicit ordered list, define
\(r_k(x)=1+\bigl|\{y\in O:y\succ_k x\}\bigr|\).
These ranks faithfully represent preference. Indeed, if \(x\succ_k y\), transitivity implies that every package preferred to \(x\) is preferred to \(y\), and \(x\) itself is an additional package preferred to \(y\). Thus \(r_k(x)<r_k(y)\). Completeness makes all ranks distinct; because they lie in \(\{1,\ldots,m\}\), they fill that set exactly.
Consequently,
\(x\succeq_k y\quad\Longleftrightarrow\quad r_k(x)\leq r_k(y)\).
Restricting these lists to any available set gives precisely the representatives’ preferences on that set.
Let \(F(T,i)\) denote the prescribed offer when the available set is \(T\) and the proposer is \(p_i\).
For \(|T|\geq2\), scan the two preference lists from worst to best, skipping unavailable packages. This identifies both bottom sets with exactly the cardinalities specified in the question. Mark their members, then scan package indices in increasing order:
For a singleton, return its sole member.
Each invocation uses \(O(m)\) elementary table operations. In particular, the even case with two available packages correctly gives the proposer an empty bottom set.
The function \(F\) is deterministic and depends only on the available set and proposer. This observation also handles arbitrary histories: previously rejected offers affect future offering decisions through their removal and the proposer’s parity.
Let \(S=O\setminus H\), let \(n=|S|\), and let \(i_0\) be the current proposer, determined by the parity of \(|H|\). Assume first that \(n\geq2\).
Construct a hypothetical sequence \(q_0,\ldots,q_{n-1}\) as follows. Set \(T_0=S\).
Write \(z=q_{n-1}\). The sequence is well defined because each rejection removes one available package.
Lemma. At every nonfinal offer \(q_t\) along this hypothetical sequence, the package \(a\) appearing in the prescribed response rule is \(z\).
Proof. Rejecting \(q_t\) leaves exactly the state \((T_{t+1},i_{t+1})\). The definition of \(a\) then uses the prescribed offering function and rejects every subsequent offer. Since \(F\) is deterministic and depends only on the current available set and proposer, this continuation is exactly the already constructed suffix \(q_{t+1},\ldots,q_{n-1}\). Its sole survivor is \(z\). This also applies at \(t=0\) when the pending offer was arbitrary. ∎
Let \(j_t=3-i_t\) be the responder at position \(t\). By the lemma, the response to each nonfinal offer is acceptance exactly when
\(r_{j_t}(q_t)\leq r_{j_t}(z)\).
Scan the constructed sequence from its beginning. Let \(t^\ast\) be the first position satisfying
\(t^\ast<n-1\quad\text{and}\quad r_{j_{t^\ast}}(q_{t^\ast})\leq r_{j_{t^\ast}}(z)\).
If no such position exists, set \(t^\ast=n-1\). Return \(q_{t^\ast}\) as the agreement.
Correctness. Actual play starts with \(q_0\), either because it is pending or because it is the prescribed offer. At every position before \(t^\ast\), the response inequality fails, so the prescribed response rejects. Removal and alternation then produce exactly the next constructed state, whose prescribed offer is the next sequence member. This proves inductively that actual play follows the sequence until \(t^\ast\). There it accepts by the response inequality, or accepts automatically if only one package remains.
The current move is obtained simultaneously:
If \(S\) is a singleton, its package is immediately offered or accepted, according to whether an offer is pending, and is the agreement.
Constructing the hypothetical sequence requires at most \(m-1\) calls to \(F\), hence \(O(m^2)\) elementary table operations. Checking the response inequalities requires only \(O(m)\) additional operations.
Together with exact majority preprocessing, the whole computation is polynomial in \(m,\tau,L\). A conservative bound, charging schoolbook arithmetic and index operations at \(O((L+1)^2)\) each, is
\(O\bigl((\tau+1)m^2(L+1)^2\bigr)\).
The crucial input feature is that \(\tau\) counts explicitly listed support rankings: each majority comparison sums over that list.
For the equilibrium interpretation, the recovered orders satisfy completeness, strictness, and transitivity; both representatives know them; and the protocol matches the explicit-order setting. The specified index choice selects a permitted intersection member. Thus the cited SPE result applies as well. [Erlich, Hazon, and Kraus, Strategies 1–2 and Theorem 10](https://arxiv.org/pdf/1805.00913). The algorithm above directly proves the requested computational conclusion.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The output supplies a correct polynomial-time algorithm for both the prescribed current move and the subsequent agreement. No major or minor mathematical issues were found.
The common-denominator construction is valid. Each denominator divides \(D_k\), so every \(W_{k\ell}\) is an integer. Normalization gives
\[
\sum_{\ell=1}^{\tau_k}W_{k\ell}=D_k.
\]
Consequently, the comparison \(2A_k(x,y)>D_k\) exactly implements the stipulated strict-majority rule.
The bit-length argument is also correct. The product’s binary length is bounded by one plus the sum of the denominator lengths. Thus \(D_k\) has \(O(L)\) bits. Positivity and normalization bound every scaled weight and every partial majority sum by \(D_k\). Intermediate products used to construct the denominator and scaled weights also have polynomially bounded bit length.
The promise supplies completeness, strictness, and transitivity; the algorithm does not need to establish these properties independently. In particular, majority ties and cycles are excluded on valid inputs.
The rank construction is justified: if \(x\succ_k y\), every package above \(x\) is above \(y\), and \(x\) supplies an additional predecessor of \(y\). Therefore \(r_k(x)<r_k(y)\). Completeness makes the ranks distinct, so they are exactly the integers from \(1\) through \(m\). The stated rank comparison faithfully represents weak preference, including equality.
Scanning the full preference lists while skipping unavailable packages correctly identifies the bottom sets within the current available set. Their stated cardinalities match both parity cases in the task.
Marking membership and scanning package indices implements the specified intersection tie-breaking rule. When the intersection is empty, the responder’s worst available package is correctly selected.
The claimed \(O(m)\) table-operation cost per invocation is valid, including initialization or clearing of membership marks. The two-package case correctly gives the proposer an empty bottom set; the singleton case is handled separately.
The sequence construction is well defined:
The suffix lemma is correct. After rejecting \(q_t\), the available set and proposer coincide with the next constructed state. Because the offering function is deterministic and depends only on those state components, the hypothetical continuation in the response definition is precisely the constructed suffix. Its survivor is therefore the same package \(z\).
This reasoning also covers an arbitrary pending offer: the pending offer need not itself have been selected by the prescribed offering function.
No identification of the hypothetical survivor with an actual continuation agreement is assumed. The argument uses the survivor exactly as defined in the task.
Replacing the response comparison with \(r_{j_t}(q_t)\leq r_{j_t}(z)\) is valid by the suffix lemma and the recovered preference ranks.
The induction describing actual play is sound. Before the first accepting position, each prescribed response rejects; the resulting removal and proposer switch produce the next constructed state. At the first accepting position, negotiation ends with that package. If none occurs earlier, automatic acceptance at the singleton state supplies the agreement.
Both forms of current move are covered: an offer when no offer is pending, and acceptance or rejection when one is pending. Singleton histories are explicitly handled. A history with no available package would contradict the stipulated automatic singleton acceptance and the assumption that no agreement has occurred.
The majority preprocessing requires \(O(\tau m^2)\) arithmetic and table operations on polynomially bounded integers. Constructing and scanning the rejection sequence requires \(O(m^2)\) further table operations.
The conservative bound \(O((\tau+1)m^2(L+1)^2)\) accommodates schoolbook integer arithmetic, rank construction, and sequence computation. The argument correctly relies on explicitly listed support rankings; it makes no enumeration over all possible rankings.
The supplementary SPE attribution matches the cited source: its Definition 1, Strategies 1–2, and Theorem 10 use the same bottom sets, offering choices, and hypothetical-survivor response rule. Its assumptions match the promised strict orders, full information, and protocol here. Selecting the smallest-index intersection member is a permitted deterministic selection. [Erlich, Hazon, and Kraus](https://arxiv.org/pdf/1805.00913)
The computational conclusion is independently established by the written algorithm. No repair or additional clarification is needed.
⟨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.