Answer: A counterexample exists, already with \(|M|=|W|=4\) and \(0<\alpha<\mu_W(w_0)\).
Theorem 4 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet ≻′ w be an optimal manipulation with respect to ≻ for woman w. Let ≻′′ w be another preference list derived from her true list ≻w by promoting the man Prop(w, ≻′, 2) to the position right after Prop(w, ≻′, 1) while making no other changes. Then, ≻′′ w is the inconspicuous equiva- lent of ≻′ w, i.e., µ′′(w) = µ′(w), where µ′ = GS(≻′) and µ′′ = GS(≻′′). Going back to Example 1, it can be observed that w1 can achieve her optimal partner (i.e., m1) by reporting the list m1 ≻m4 ≻m2 ≻m3, derived from her true list ≻w by pro- moting the man m4 and making no other changes.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational mass distributions \(\mu_M\) and \(\mu_W\) over finite sets of strict ranking types, with a marked female submass \(\alpha>0\) sharing true ranking \(t\), find a common reported ranking \(r\) maximizing the cohort's average true utility under mass deferred acceptance, while all other agents report truthfully. Can an optimal report always be chosen so that the same cohort-to-male-type allocation flow results from changing \(t\) only by promoting the cohort's second male type with positive proposal flow to immediately below its first?
Let \(M,W\) be finite sets of labelled male and female ranking types, each containing at least two types. Every ranking is a strict complete order over the opposite set; \(\mu_M,\mu_W\) are positive rational masses, each summing to \(1\).
A society is given by its support: the list of its \(\tau=|M|+|W|\) positive-mass types and their binary rational masses, not the universe of possible rankings. Let \(m\) be the maximum ranking length after the split below and \(L\) the total input bit length; measure running times in \(m,\tau,L\).
A marked cohort has rational mass \(0<\alpha\leq\mu_W(w_0)\) and true ranking \(t\). Split \(w_0\) into a cohort block \(c\) of capacity \(\alpha\) and a truthful remainder of capacity \(\mu_W(w_0)-\alpha\). In every male ranking, replace \(w_0\) by \(c\) followed immediately by the remainder, omitting a zero remainder.
Mass deferred acceptance proceeds in synchronous rounds: initially all male mass proposes to its first block; each block retains, from held and new proposals, its capacity of mass in reported male-type order, splitting the cutoff type if necessary. Rejected portions propose to their next block in the next round. Stop when no rejection occurs; fractions within one male type are interchangeable.
Only \(c\) may report a permutation \(r\) of \(t\); everyone else is truthful. Write \(x_i(r)\) for the final mass from male type \(i\) held by \(c\). Input utilities \(u_i\in\mathbb{Q}_{>0}\) strictly respect \(t\); maximize \(U(r)=\alpha^{-1}\sum_{i\in M}u_i x_i(r)\). Restrict to instances with \(\max_r U(r)>U(t)\).
Let \(P(r)\) contain every male type sending positive proposal mass to \(c\), including rejected proposals. Its first two types \(p(r),q(r)\) are ordered by \(r\), not by arrival time or \(t\). Define \(S(r)\) by moving \(q(r)\) in \(t\) immediately below \(p(r)\), preserving every other relative order; this requires \(q(r)\) to lie below \(p(r)\) in \(t\), and permits no change if already adjacent. If \(|P(r)|<2\), set \(S(r)=t\).
Does every such instance admit a utility-maximizing report \(r\) for which \(S(r)\) is defined and \(x_i(S(r))=x_i(r)\) for every \(i\in M\), or is there a counterexample?
For one discrete woman, every strictly improving optimal permutation has an equivalent report obtained by promoting her second-best proposer immediately below her best proposer, preserving her assigned partner ([Vaish–Garg](https://www.ijcai.org/proceedings/2017/0062.pdf)).
The [fuller treatment](https://rohitvaish.in/Publications/ThesisChapter-5.pdf) confirms this statement and supplies omitted proofs. No result settling the specified mass/cohort statement was located.
The proposed statement is false. The counterexample below has four distinct male rankings, four distinct female rankings, and \(0<\alpha<\mu_W(w_0)\). We prove that every utility-maximizing report fails the required condition.
Let \(M=\{m_1,m_2,m_3,m_4\}\) and \(W=\{w_0,a,b,d\}\). The male masses and truthful rankings are:
| Type | Mass | Ranking |
|---|---|---|
| \(m_1\) | \(1/8\) | \(w_0\succ a\succ d\succ b\) |
| \(m_2\) | \(2/8\) | \(d\succ w_0\succ b\succ a\) |
| \(m_3\) | \(4/8\) | \(w_0\succ b\succ d\succ a\) |
| \(m_4\) | \(1/8\) | \(b\succ w_0\succ a\succ d\) |
The female masses and truthful rankings are:
| Type | Mass | Ranking |
|---|---|---|
| \(w_0\) | \(3/8\) | \(m_1\succ m_2\succ m_3\succ m_4\) |
| \(a\) | \(1/8\) | \(m_3\succ m_4\succ m_1\succ m_2\) |
| \(b\) | \(1/8\) | \(m_2\succ m_1\succ m_3\succ m_4\) |
| \(d\) | \(3/8\) | \(m_3\succ m_2\succ m_4\succ m_1\) |
Both sides have total mass \(1\), and all masses are positive rational numbers.
Split \(w_0\) into a cohort \(c\) of capacity \(\alpha=2/8\) and a truthful remainder \(h\) of capacity \(1/8\). Thus every occurrence of \(w_0\) in a male ranking becomes \(c\succ h\). The cohort’s true ranking and utilities are
\(t:\ m_1\succ m_2\succ m_3\succ m_4,\qquad (u_1,u_2,u_3,u_4)=(4,3,2,1).\)
For the calculations, use units of mass \(1/8\). Male supplies are then \((1,2,4,1)\), and block capacities, in the order \((c,h,a,b,d)\), are \((2,1,1,1,3)\).
Write \(y_i(r)=8x_i(r)\). The cohort utility is
\(U(r)=\dfrac{4y_1(r)+3y_2(r)+2y_3(r)+y_4(r)}{2}.\)
Consider the report
\(r^\star:\ m_1\succ m_2\succ m_4\succ m_3.\)
In the following table, \(z\,m_i\to v\) means that \(z\) units of type \(m_i\) newly propose to block \(v\). A rejection entry identifies the rejecting block and the rejected mass. Unlisted blocks retain their previous holdings.
| Round | New proposals under \(r^\star\) | Rejections | Cohort holdings \((y_1,y_2,y_3,y_4)\) |
|---|---|---|---|
| \(1\) | \(m_1+4m_3\to c;\ 2m_2\to d;\ m_4\to b\) | \(c:3m_3\) | \((1,0,1,0)\) |
| \(2\) | \(3m_3\to h\) | \(h:2m_3\) | \((1,0,1,0)\) |
| \(3\) | \(2m_3\to b\) | \(b:m_3+m_4\) | \((1,0,1,0)\) |
| \(4\) | \(m_3\to d;\ m_4\to c\) | \(c:m_3\) | \((1,0,0,1)\) |
| \(5\) | \(m_3\to h\) | \(h:m_3\) | \((1,0,0,1)\) |
| \(6\) | \(m_3\to b\) | \(b:m_3\) | \((1,0,0,1)\) |
| \(7\) | \(m_3\to d\) | \(d:m_2\) | \((1,0,0,1)\) |
| \(8\) | \(m_2\to c\) | \(c:m_4\) | \((1,1,0,0)\) |
| \(9\) | \(m_4\to h\) | \(h:m_4\) | \((1,1,0,0)\) |
| \(10\) | \(m_4\to a\) | None | \((1,1,0,0)\) |
Every rejection follows directly from the displayed capacities and rankings. In particular, in round \(7\), block \(d\) has two units of \(m_3\) and two units of \(m_2\) available. Its capacity is three, and it ranks \(m_3\) above \(m_2\), so it rejects one unit of \(m_2\).
The final holdings are \(m_1+m_2\) at \(c\), \(m_3\) at each of \(h\) and \(b\), \(m_4\) at \(a\), and \(2m_3+m_2\) at \(d\). Hence
\(y(r^\star)=(1,1,0,0),\qquad U(r^\star)=7/2.\)
Under the truthful report \(t\), rounds \(1\)–\(3\) are identical. In round \(4\), however, \(c\) rejects \(m_4\) and retains \(m_1+m_3\). Meanwhile, \(d\) accepts the incoming unit of \(m_3\), filling its capacity with \(m_3+2m_2\). In round \(5\), \(h\) rejects \(m_4\), since it holds \(m_3\). In round \(6\), \(a\) accepts \(m_4\), and no rejection occurs.
Consequently,
\(y(t)=(1,0,1,0),\qquad U(t)=3<7/2.\)
Thus the instance satisfies the required strict-improvement restriction.
For every report \(r\), feasibility gives
\(y_i(r)\ge 0,\qquad s(r):=\sum_{i=1}^{4}y_i(r)\le 2,\qquad y_1(r)\le 1.\)
Therefore,
\(4y_1+3y_2+2y_3+y_4=3s+y_1-y_3-2y_4\le 3\cdot2+1=7.\)
It follows that \(U(r)\le 7/2\) for every report. Since \(r^\star\) attains this bound, it is globally optimal.
Moreover, the difference from the bound is
\(7-(4y_1+3y_2+2y_3+y_4)=3(2-s)+(1-y_1)+y_3+2y_4.\)
Every term on the right is nonnegative. Equality therefore forces \(s=2\), \(y_1=1\), and \(y_3=y_4=0\), whence \(y_2=1\).
Every utility-maximizing report consequently has allocation \(y(r)=(1,1,0,0)\).
Lemma. Fix a report at a block. If the block ever rejects positive mass of type \(m_j\), it cannot finally retain positive mass of any type ranked below \(m_j\).
Proof. Let \(H\) be the prefix of the block’s reported ranking ending at \(m_j\). Write \(C\) for its capacity, \(B_H(k)\) for its held mass from \(H\) after round \(k\), and \(A_H(k)\) for its new proposal mass from \(H\) in round \(k\).
Because every type in \(H\) precedes every type outside \(H\), the retention rule gives
\(B_H(k)=\min\{C,B_H(k-1)+A_H(k)\}.\)
If positive mass of \(m_j\) is rejected in round \(k\), the block fills its entire capacity from \(H\), so \(B_H(k)=C\). The displayed recurrence then implies \(B_H(\ell)=C\) for every subsequent round \(\ell\). No type outside \(H\) can be retained at termination. This proves the lemma.
In particular, if a positive proposer has zero final held mass, some positive mass of that type was rejected, and the lemma applies.
Let \(r\) be any utility-maximizing report. Section 3 gives
\(y_1(r)=y_2(r)=1,\qquad y_3(r)=y_4(r)=0.\)
Both \(m_1\) and \(m_2\) therefore belong to \(P(r)\).
Suppose another proposer preceded either \(m_1\) or \(m_2\) in \(r\). That proposer would be \(m_3\) or \(m_4\), whose final held mass is zero. Some positive mass of it must therefore have been rejected by \(c\). The lemma would prohibit the positive final holding of the lower-ranked \(m_1\) or \(m_2\), a contradiction.
Thus the first two types of \(P(r)\), ordered by \(r\), are precisely \(m_1,m_2\), in one of two orders:
These cases exhaust all optimal reports. Therefore no optimal report has both a defined \(S(r)\) and the same cohort allocation under \(S(r)\).
The mechanism differs from the [single-woman theorem](https://www.ijcai.org/proceedings/2017/0062.pdf): here both leading proposers are retained. The beneficial rejection chain is initiated by reversing \(m_3\) and \(m_4\), below both final held types.
⟨structured verdict parsed — rendered above⟩
The counterexample is correct and resolves the assigned question. Every utility-maximizing report fails the required condition. I found no major or minor mathematical issues.
All supplied rankings are strict complete orders over the opposite set, and the four rankings on each side are distinct. Both sets contain at least two types.
The male masses sum to \((1+2+4+1)/8=1\), and the female masses sum to \((3+1+1+3)/8=1\). Every mass is positive and rational.
The split is valid: \(\alpha=2/8<3/8=\mu_W(w_0)\), leaving a positive truthful remainder of mass \(1/8\). The stipulated replacement by \(c\succ h\) is used consistently.
The utilities satisfy \(4>3>2>1>0\), strictly respecting the cohort’s true ranking. With \(y_i=8x_i\), the normalization is correct:
\[
U(r)=\frac{4y_1(r)+3y_2(r)+2y_3(r)+y_4(r)}{2}.
\]
Every row of the ten-round execution under \(r^\star\) follows the specified synchronous rule.
The stated final holdings respect every capacity and conserve each male type’s supply. Consequently, \(y(r^\star)=(1,1,0,0)\) and \(U(r^\star)=7/2\).
The truthful execution agrees through round \(3\). In round \(4\), truthful \(c\) retains \(m_1+m_3\) and rejects \(m_4\); \(d\) accepts the incoming \(m_3\) without rejection. The rejected \(m_4\) then passes through \(h\) to \(a\), where it is accepted.
Thus \(y(t)=(1,0,1,0)\) and \(U(t)=3\). The strict-improvement restriction is satisfied because \(7/2>3\).
The feasibility inequalities \(y_i\geq0\), \(s\leq2\), and \(y_1\leq1\) apply to every report. The identity
\[
4y_1+3y_2+2y_3+y_4=3s+y_1-y_3-2y_4
\]
is correct and gives the universal upper bound \(7\) on the unnormalized objective.
The exhibited report attains that bound, proving global optimality.
The equality analysis is also correct:
\[
7-(4y_1+3y_2+2y_3+y_4)
=3(2-s)+(1-y_1)+y_3+2y_4.
\]
All terms are nonnegative. Equality forces \(s=2\), \(y_1=1\), and \(y_3=y_4=0\), hence \(y_2=1\). This establishes the allocation of every maximizing report without assuming uniqueness of the report.
The lemma is correctly stated for a fixed reported order. For its prefix \(H\), retaining mass in reported order gives exactly
\[
B_H(k)=\min\{C,B_H(k-1)+A_H(k)\}.
\]
Rejecting positive mass of the last type in \(H\) requires filling capacity entirely with types in \(H\). Once \(B_H(k)=C\), the recurrence preserves that equality in every subsequent round. Therefore, no lower-ranked type can have positive final holdings.
The subsequent observation is justified: positive proposal mass with zero final holdings must have been rejected, since held mass leaves a block only through rejection.
For any optimal report, both \(m_1,m_2\) are positive final holdings and therefore proposers. Any other proposer has zero final holdings.
If another proposer preceded either retained type, the lemma would prohibit that retained type’s positive final holdings. Thus the first two proposers are precisely \(m_1,m_2\), in some order.
Both cases are handled correctly:
This exhausts every optimal report and proves the asserted counterexample.
As an independent computational check, enumeration of all \(24\) reports reproduced both executions and found exactly two maximizing reports: \(m_1\succ m_2\succ m_4\succ m_3\) and \(m_2\succ m_1\succ m_4\succ m_3\).
The cited [single-woman result](https://www.ijcai.org/proceedings/2017/0062.pdf) is contextual; the counterexample does not depend on applying it. No clarification or repair is needed. The proof establishes failure of the proposed structural property, but does not classify the computational complexity of continuous utility maximization.
⟨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.