d4-journals-geb-2011-0084 (d4-journals-geb-2011-0084)

Given a finite ordered agenda \(A\), a finite support \(T\) of complete weak preference orders with singleton peaks, and binary-rational masses \(\mu_t\) summing to \(1\), promised to be peak-monotonic relative to the order on \(A\), compute the weighted-median peak alternatives and return them as Condorcet winners under mass-weighted majority, counting indifferent mass on both sides.

Let \(A\) be a nonempty finite agenda with a supplied linear order \(<\), and put \(m=|A|\). A society is given by its support: the list \(T\) of \(\tau\) complete weak preference orders \(\succeq_t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type has a singleton top \(p_t\) on \(A\). Write \(\operatorname{top}_t(S)\) for its maximal alternatives in \(S\), and let \(F=\{p_t:t\in T\}\).
The peak-monotonicity promise is the following: for every \(S\) equal to \(A\) or a three-element subset of \(F\), every \(t,u\in T\), and every \(x\in\operatorname{top}_t(S)\), \(y\in\operatorname{top}_u(S)\), \(z\in S\), if \(x<y<z\) or \(z<y<x\), then \(y\succeq_t z\) when \(z\in\operatorname{top}_t(S)\cup\operatorname{top}_u(S)\), and \(y\succ_t z\) otherwise.
Define the weighted-median peak set by \(M=\{a\in F:\sum_{t:p_t<a}\mu_t\leq\tfrac12\text{ and }\sum_{t:p_t>a}\mu_t\leq\tfrac12\}\); retain every such peak, without tie-breaking.
For pairwise majority, let \(V(a,b)=\sum_{t:a\succeq_t b}\mu_t\), so indifferent mass counts on both sides. A Condorcet winner is an alternative \(a\) satisfying \(V(a,b)\geq V(b,a)\) for every \(b\in A\). The prescribed output is all of \(M\), rather than an exhaustive list of Condorcet winners.

Does every promised society have every element of \(M\) as a Condorcet winner? Is computing this prescribed output with that guarantee solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For finite electorates, peak monotonicity guarantees that median peaks are Condorcet winners; top monotonicity more generally guarantees Condorcet winners among extended weak medians ([Barberà–Moreno](https://bse.eu/sites/default/files/working_paper_pdfs/297_v3.pdf)).
No result for exactly this rational-mass computational problem was located in the literature search.

1. Result

Yes: every element of \(M\) is a Condorcet winner, and computing all of \(M\) is polynomial-time solvable in \(m,\tau,L\).

The proof is self-contained. It uses the peak-monotonicity promise for \(S=A\). The additional promises on three-element subsets of \(F\) are therefore sufficient but unnecessary for this conclusion. For context, [Barberà–Moreno](https://bse.eu/sites/default/files/working_paper_pdfs/297_v3.pdf) study median-based Condorcet guarantees under top monotonicity.

2. The preference implication

Write \(a\succ_t b\) when \(a\succeq_t b\) and \(b\not\succeq_t a\). Because each preference is a complete weak order with singleton top \(p_t\), we have \(p_t\succ_t b\) for every \(b\neq p_t\).

Fix a peak \(a\in F\), and choose a type \(u\) with \(p_u=a\). We claim:

• If \(a<b\) and \(p_t\leq a\), then \(a\succ_t b\).
• If \(b<a\) and \(a\leq p_t\), then \(a\succ_t b\).

For the first claim, if \(p_t=a\), singleton maximality gives the conclusion. Otherwise \(p_t<a<b\). Apply the promise with \(S=A\), \(x=p_t\), \(y=a\), and \(z=b\). Here \(\operatorname{top}_t(A)\cup\operatorname{top}_u(A)=\{p_t,a\}\), so \(b\) lies outside that union. The strict clause of the promise gives \(a\succ_t b\).

For the second claim, the case \(p_t=a\) again follows from singleton maximality. Otherwise \(b<a<p_t\). The same choices satisfy \(z<y<x\), and \(b\notin\{p_t,a\}\); hence the strict clause again gives \(a\succ_t b\).

3. Every weighted-median peak is a Condorcet winner

Fix \(a\in M\) and \(b\neq a\). Define the masses of strict supporters and indifferent types by \(P=\sum_{t:a\succ_t b}\mu_t\), \(Q=\sum_{t:b\succ_t a}\mu_t\), and \(I=\sum_{t:a\sim_t b}\mu_t\).

Completeness of the preferences partitions the types into these three classes. Consequently, \(P+Q+I=1\), \(V(a,b)=P+I\), and \(V(b,a)=Q+I\). Thus it suffices to prove \(P\geq Q\).

If \(a<b\), the first implication above shows that all types with \(p_t\leq a\) strictly support \(a\) against \(b\). Since \(a\in M\), their total mass satisfies
\(P\geq\sum_{t:p_t\leq a}\mu_t=1-\sum_{t:p_t>a}\mu_t\geq\tfrac12\).

If \(b<a\), the second implication instead gives
\(P\geq\sum_{t:p_t\geq a}\mu_t=1-\sum_{t:p_t<a}\mu_t\geq\tfrac12\).

In either case, \(Q=1-P-I\leq1-P\leq P\). Therefore \(V(a,b)\geq V(b,a)\). For \(b=a\), equality holds automatically. As \(b\) was arbitrary, \(a\) is a Condorcet winner.

This argument includes the boundary case \(P=\tfrac12\): indifferent mass counts equally on both sides and cancels from the comparison.

4. Characterizing the entire prescribed output

List the distinct peaks as \(f_1<\cdots<f_k\). Let \(q_i=\sum_{t:p_t=f_i}\mu_t\), and define prefix masses \(H_0=0\) and \(H_i=\sum_{r=1}^{i}q_r\).

Each \(q_i\) is positive, so \(0=H_0<H_1<\cdots<H_k=1\). Directly from the definition of \(M\),
\(f_i\in M\) if and only if \(H_{i-1}\leq\tfrac12\leq H_i\): the mass strictly left of \(f_i\) is \(H_{i-1}\), and the mass strictly right is \(1-H_i\).

Let \(j\) be the smallest index with \(H_j\geq\tfrac12\). Such an index exists because \(H_k=1\).

• If \(H_j>\tfrac12\), then \(M=\{f_j\}\). Earlier indices have \(H_i<\tfrac12\), and later indices have \(H_{i-1}>\tfrac12\).
• If \(H_j=\tfrac12\), then \(j<k\) and \(M=\{f_j,f_{j+1}\}\). These two indices satisfy the defining inequalities; all earlier and later indices fail them by strict increase of the prefixes.

Thus \(M\) is nonempty and consists of either one peak or two consecutive peaks in \(F\). Both peaks must be retained in the equality case.

5. Exact polynomial-time computation

Represent each input mass as \(\mu_t=n_t/d_t\), with positive binary integers \(n_t,d_t\). Set \(D=\prod_{t\in T}d_t\) and \(W_t=n_t(D/d_t)\). These are exact integers satisfying \(W_t=D\mu_t\) and \(\sum_tW_t=D\).

The bit length of \(D\) is at most \(1+\sum_t\log_2d_t\), hence is \(O(L)\). Moreover, \(0<W_t\leq D\), so all accumulated weights also have \(O(L)\) bits. The possibly large numerical value of \(D\) therefore causes no exponential bit complexity.

The algorithm is:

• Read each singleton peak and aggregate \(W_t\) by its peak.
• Traverse the supplied order, retaining the alternatives with positive aggregate weight to obtain \(f_1,\ldots,f_k\).
• Let \(C_i=\sum_{r=1}^{i}\sum_{t:p_t=f_r}W_t\). Find the first \(j\) with \(2C_j\geq D\).
• Output \(f_j\). If \(2C_j=D\), also output \(f_{j+1}\).

Section 4 proves that this outputs exactly \(M\), and Section 3 proves that every output alternative is a Condorcet winner.

There are polynomially many parsing operations and \(O(m+\tau)\) integer arithmetic operations on \(O(L)\)-bit integers. Standard exact integer arithmetic therefore gives a running time polynomial in \(m,\tau,L\). No expansion into an electorate of \(D\) voters is required.

⟨structured verdict parsed — rendered above⟩

The prover fully resolves the task. The proof establishes that every element of \(M\) is a Condorcet winner and gives an exact polynomial-time algorithm for the prescribed output. No mathematical gaps or incorrect steps were found.

Step-by-step verification

1. Use of the peak-monotonicity promise

The proof uses only the promise for \(S=A\), which is explicitly included in the task. It does not need the promises for three-element subsets of \(F\).

The Barberà–Moreno reference is contextual; no external theorem is used to justify a proof step. The conclusion therefore does not depend on verifying additional hypotheses from that paper.

2. Singleton tops and the preference implications

For a complete weak order with singleton maximal set \(\{p_t\}\), the statement \(p_t\succ_t b\) for every \(b\neq p_t\) is correct. Maximality gives \(p_t\succeq_t b\); if also \(b\succeq_t p_t\), transitivity would make \(b\) maximal, contradicting singleton maximality.

Fixing \(a\in F\) permits the choice of a type \(u\) with \(p_u=a\), by the definition of \(F\).

For \(a<b\) and \(p_t<a\), the chosen alternatives satisfy \(x=p_t<y=a<z=b\). Moreover,
\[ \operatorname{top}_t(A)\cup\operatorname{top}_u(A)=\{p_t,a\}, \]
and \(b\) lies outside that set. The strict clause of the promise consequently gives \(a\succ_t b\). When \(p_t=a\), singleton maximality supplies the same conclusion.

For \(b<a<p_t\), the chosen alternatives satisfy \(z<y<x\), and the same exclusion from the union of tops holds. The second implication follows correctly as well.

All quantifiers, membership conditions, and strict inequalities needed for these applications are satisfied.

3. Weighted-median peaks are Condorcet winners

Completeness of each weak order partitions the types into strict supporters of \(a\), strict supporters of \(b\), and indifferent types. Thus the identities
\[ P+Q+I=1,\qquad V(a,b)=P+I,\qquad V(b,a)=Q+I \]
are correct under the task’s convention that indifferent mass counts on both sides.

If \(a<b\), every type with \(p_t\leq a\) strictly prefers \(a\) to \(b\). The median condition gives
\[ P\geq 1-\sum_{t:p_t>a}\mu_t\geq \frac12. \]
If \(b<a\), the symmetric implication and the other median condition give the same bound.

Since \(I\geq0\),
\[ Q=1-P-I\leq1-P\leq P. \]
Consequently \(V(a,b)\geq V(b,a)\), as required.

The proof covers alternatives \(b\) outside \(F\), because the promise for \(S=A\) allows any \(z=b\in A\). The case \(b=a\) is correctly handled by equality. The boundary case \(P=\frac12\) also causes no gap.

4. Characterization of the complete output

The support is nonempty because its positive masses sum to one. Hence \(F\) is nonempty and \(k\geq1\).

Each aggregate peak mass \(q_i\) is positive, so the prefixes increase strictly from zero to one. The equivalence
\[ f_i\in M\quad\Longleftrightarrow\quad H_{i-1}\leq\frac12\leq H_i \]
follows exactly from the two inequalities defining \(M\).

The first crossing index \(j\) exists. Both cases are correct:

• If \(H_j>\frac12\), only \(f_j\) satisfies both inequalities.
• If \(H_j=\frac12\), then \(j<k\), since \(H_k=1\). Exactly \(f_j\) and \(f_{j+1}\) satisfy both inequalities.

This also covers a single distinct peak and a one-alternative agenda. The algorithm’s access to \(f_{j+1}\) is therefore valid whenever that output is requested.

5. Exact computation and bit complexity

The common denominator construction is valid without any coprimality assumption. Each \(d_t\) divides \(D\), so \(W_t=n_t(D/d_t)\) is an exact positive integer. Normalization implies
\[ \sum_t W_t=D. \]

The stated bit-length bound for \(D\) is correct. Because the denominator encodings contribute to \(L\), \(D\) has \(O(L)\) bits. Each \(W_t\) and each accumulated weight is at most \(D\), so those integers also have \(O(L)\) bits. Doubling a prefix adds at most one bit.

Constructing the weights, aggregating them by peak, and traversing the supplied order require polynomially many operations. Exact multiplication, division, addition, and comparison on these bounded-length integers take polynomial time. Extracting peaks from the explicitly supplied preference orders also takes polynomial time in the input length.

The comparisons \(2C_j\geq D\) and \(2C_j=D\) implement the median characterization exactly and preserve both peaks in the equality case. No electorate expansion is needed.

Repair feedback

None is required. The guarantee, all prescribed output cases, and the polynomial bit-complexity claim are justified as written.

⟨structured verdict parsed — rendered above⟩