Answer: polynomial-time solvable
Proposition 10 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe time-specific lawyer offering stable mechanism is stable and (group) strategy-proof. If in addition lawyers’ preferences are weakly im- patient, then the time-specific stable mechanism is lawyer-optimal stable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of lawyer types (Theta), rational masses (mu_theta), common strict preferences over court-period contracts and the outside option, court-specific priority categories, and rational per-period capacity shares (q_{c,t}), compute a feasible mass allocation (x_{theta,c,t}) with no positive-mass blocking set under the extended time-specific choice rule.
Let \(C\) be a nonempty set of \(m\) courts and \(T=\{1,\ldots,h\}\), with \(h\geq1\). A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
All lawyers share an explicitly given strict preference order \(P\) over \((C\times T)\cup\{\varnothing\}\), with no impatience restriction. Each court has ordered priority categories containing all types; ties between types are broken by their order in the support list. Capacities \(q_{c,t}\in[0,1]\) are binary rationals, and all contracts are acceptable to courts.
Represent type \(\theta\) by the atomless interval \(\{\theta\}\times[0,\mu_\theta)\), with Lebesgue mass. Within each type, smaller interval coordinates have higher priority at every court. A contract specifies a lawyer, a court and a period.
For any measurable offer set, the extended time-specific choice \(\operatorname{Ch}_c\) processes periods in increasing order. In period \(t\), it accepts the highest-priority offered lawyer mass up to \(q_{c,t}\), splitting at the priority cutoff if necessary, and removes every other offer of each accepted lawyer before processing later periods.
An allocation \(Y\) measurably assigns each lawyer at most one contract, leaving others at \(\varnothing\); assigned contracts must be preferred to \(\varnothing\), and each court-period mass must respect its capacity. Require also \(\operatorname{Ch}_c(Y)=Y(c)\) for every court, where \(Y(c)\) denotes its assigned contracts.
A blocking set is a measurable allocation \(Z\) involving one court \(c\), such that \(Z=\operatorname{Ch}_c(Y\cup Z)\), every lawyer assigned in \(Z\) weakly prefers that contract to her assignment in \(Y\), and \(Z\setminus Y\) involves positive lawyer mass. All conditions are interpreted up to null sets.
A rational mass matrix \(x_{\theta,c,t}\geq0\) is stable if it has a measurable realization \(Y\) satisfying these conditions and admitting no blocking set; its entries are the masses assigned from each type to each court-period.
Is computing a stable mass allocation polynomial-time in \(m,\tau,h,L\), or NP-hard?
For finite lawyers, the cumulative offer mechanism with time-specific choice is stable and group strategy-proof; under weak impatience it is also lawyer-optimal stable. [Dimakopoulos–Heller](https://epub.ub.uni-muenchen.de/58080/1/68.pdf)
Continuum matching existence is known under convex, continuous firm choice, but no complexity result for exactly the problem defined here was located. [Che–Kim–Kojima](https://economics.sas.upenn.edu/sites/default/files/filevault/u483/Continuum-rev.pdf)
Computing a stable mass allocation is polynomial-time solvable. The common strict preference order permits a greedy construction, even when preferences do not satisfy impatience.
Let \(A=\bigsqcup_{\theta=1}^{\tau}\{\theta\}\times[0,\mu_\theta)\) denote the lawyer population, and let \(\lambda\) denote its mass measure.
List precisely the acceptable court-period pairs in decreasing preference order:
\(a_1\succ_P a_2\succ_P\cdots\succ_P a_K\succ_P\varnothing,\qquad K\leq mh.\)
Write \(a_k=(c_k,t_k)\). The algorithm processes pairs in this preference order, rather than chronological order.
Initially every lawyer is unassigned. At step \(k\), let \(U_k\) be the still-unassigned population. Assign to \(a_k\) the highest-priority subset \(I_k\) of \(U_k\) at court \(c_k\), of mass
\(\lambda(I_k)=\min\{q_{c_k,t_k},\lambda(U_k)\}.\)
Set \(U_{k+1}=U_k\setminus I_k\). After all steps, leave the remaining lawyers unmatched.
This construction has a compact exact implementation. Maintain, for each type, a coordinate \(s_\theta\), initially zero. Its unassigned lawyers always form the suffix
\(\{\theta\}\times[s_\theta,\mu_\theta).\)
At step \(k\), scan types in court \(c_k\)'s strict priority order, obtained from its categories and support-list tie breaking. With residual capacity \(b\), initially \(q_{c_k,t_k}\), assign the interval
\(\{\theta\}\times[s_\theta,s_\theta+d),\qquad d=\min\{b,\mu_\theta-s_\theta\},\)
and update \(s_\theta\leftarrow s_\theta+d\) and \(b\leftarrow b-d\). Stop when the residual capacity is zero or all types have been scanned.
Let \(Y\) be this interval allocation, and output
\(x_{\theta,c,t}=\lambda\bigl(\{u\in[0,\mu_\theta):Y(\theta,u)=(c,t)\}\bigr).\)
The construction gives a measurable allocation: each assigned set is a finite union of intervals. Assigned intervals are disjoint, every assigned pair is acceptable, and each court-period mass respects its capacity.
Moreover, \(\operatorname{Ch}_c(Y)=Y(c)\) for every court \(c\). Indeed, each lawyer has at most one offer in \(Y\). Consequently, acceptance in an earlier period cannot remove an offer assigned to a later period. Each period's offered mass is within capacity, so the court accepts all of it.
We will use the following additional property.
Priority separation. If \(U_k\setminus I_k\) has positive mass, then
\(\lambda(I_k)=q_{c_k,t_k},\)
and every lawyer in \(I_k\) has higher priority at \(c_k\) than every lawyer in \(U_k\setminus I_k\), apart from irrelevant endpoint conventions.
To verify this, the algorithm exhausts each higher-priority type's available suffix before moving to a lower-priority type. Within the possibly partially selected type, it takes the smallest available coordinates. Thus the selected population is an initial segment of the available population in court priority. If any available mass remains, the algorithm must have exhausted capacity.
Suppose, for contradiction, that a blocking allocation \(Z\) exists at a court \(c\).
For each acceptable pair \(a_j\), let \(B_j\) be the lawyers assigned to \(a_j\) in \(Z\) whose assignment in \(Y\) differs from \(a_j\).
Every such lawyer strictly prefers \(a_j\) to her assignment in \(Y\): weak preference between distinct assignments is strict because \(P\) is strict. In particular, every newly proposed pair is acceptable, since the lawyer's assignment in \(Y\) is either acceptable or \(\varnothing\).
The positive mass condition on \(Z\setminus Y\), together with the finite number of pairs, implies that some \(B_j\) has positive mass. Choose the smallest such index \(k\). Thus
\(\lambda(B_k)>0,\qquad \lambda(B_j)=0\text{ for every }j<k.\)
Necessarily \(a_k=(c,t_k)\).
Every lawyer in \(B_k\) strictly prefers \(a_k\) to her final assignment in \(Y\). She therefore was not assigned at any earlier construction step: all those steps assign pairs preferred to \(a_k\).
She also was not assigned at step \(k\), because her assignment in \(Y\) differs from \(a_k\). Consequently,
\(B_k\subseteq U_k\setminus I_k\)
up to null sets.
Because \(B_k\) has positive mass, priority separation implies that \(I_k\) fills capacity \(q_{c,t_k}\) and outranks every lawyer in \(B_k\).
Consider a lawyer in \(I_k\). Her assignment in \(Y\) is \(a_k\).
If \(Z\) assigns her a different contract, weak improvement requires a pair \(a_j\) with \(j<k\). She would then belong to \(B_j\). By the minimality of \(k\), the union of all these exceptional sets has zero mass.
Therefore, outside a null set, each lawyer in \(I_k\) has exactly one offer in \(Y\cup Z\) at court \(c\): her original offer for period \(t_k\). This remains true whether \(Z\) retains her original contract or omits her.
In particular, chronological processing cannot accept such a lawyer before period \(t_k\). The entire mass of \(I_k\) remains available when that period is processed.
The offers for pair \(a_k\) in \(Y\cup Z\) consist precisely of \(I_k\cup B_k\), up to null sets. Some lawyers in \(B_k\) might already have been accepted in earlier periods, but that only removes potential new applicants.
At period \(t_k\), the available population \(I_k\):
The court therefore accepts \(I_k\) and no positive mass from \(B_k\).
This contradicts \(Z=\operatorname{Ch}_c(Y\cup Z)\), since \(Z\) assigns the positive mass \(B_k\) to \(a_k\).
Hence no blocking allocation exists, and the output matrix has the stable measurable realization \(Y\).
After preprocessing the courts' type orders, each of the at most \(mh\) construction steps scans at most \(\tau\) types. Thus the construction uses \(O(mh\tau)\) rational arithmetic operations. Preprocessing the explicitly supplied preference and priority orders also takes polynomial time.
To check bit complexity, let \(D\) be the product of the positive denominators appearing in the input masses and capacities. Its binary length is \(O(L)\), because denominator encoding lengths contribute to the total input length \(L\).
All input masses and capacities are integer multiples of \(1/D\). The algorithm uses only comparisons, minima, additions, and subtractions, so every interval endpoint and output entry remains an integer multiple of \(1/D\). All these quantities lie in \([0,1]\), so their scaled integer numerators lie between zero and \(D\) and have \(O(L)\) bits.
Computing the scaled inputs and performing all subsequent arithmetic therefore takes polynomial bit time. The output has \(m h\tau\) entries, each of polynomial encoding length.
This proves polynomial-time solvability in the stated parameters, directly for the specified atomless model.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The greedy construction produces a rational mass matrix with a stable measurable realization, and its implementation runs in polynomial bit time. No major or minor issues were found.
The proof uses the common strict preference order essentially. It does not assume impatience or invoke an external existence or stability theorem.
The acceptable pairs are exactly those ranked above \(\varnothing\). Their enumeration in decreasing preference order is well defined because \(P\) is strict and explicitly supplied.
The interval implementation correctly selects the highest-priority available population at each court:
Consequently, the maintained coordinates \(s_\theta\) represent the unassigned population exactly throughout the construction. The assigned mass at each step is indeed
\[
\min\{q_{c_k,t_k},\lambda(U_k)\}.
\]
The construction terminates after at most \(mh\) steps. Its intervals are measurable and pairwise disjoint as lawyer sets. Each assigned contract is acceptable, and each court-period capacity is respected.
The assertion \(\operatorname{Ch}_c(Y)=Y(c)\) is justified.
Every lawyer has at most one contract in \(Y\), so accepting her in one period cannot remove another offer belonging to her. At each period, the offered mass is within capacity, and all contracts are acceptable to courts. Thus chronological choice accepts all the contracts assigned at that court.
The claimed separation follows from the stated implementation. At step \(k\), the algorithm selects an initial segment of the available population in court \(c_k\)’s priority order.
If positive available mass remains after selection, the algorithm could not have stopped by exhausting that population. It must have exhausted capacity, giving
\[
\lambda(I_k)=q_{c_k,t_k}.
\]
The selected lawyers precede all remaining available lawyers in priority, with endpoint conventions immaterial to mass.
This statement also accommodates zero capacity: then \(I_k\) is empty, its mass equals capacity, and the priority comparison is vacuous.
For a lawyer whose contract in \(Z\) differs from her assignment in \(Y\), weak improvement implies strict improvement because preferences are strict.
Such a new contract must be acceptable: it is preferred either to \(\varnothing\) or to an assignment already preferred to \(\varnothing\). Therefore the sets \(B_j\) cover all new contracts relevant to the blocking condition.
There are finitely many acceptable pairs. Hence positive mass in \(Z\setminus Y\) implies positive mass in at least one \(B_j\), and the smallest such index \(k\) exists. The preceding exceptional sets have a null union because there are finitely many of them.
The inclusion
\[
B_k\subseteq U_k\setminus I_k
\]
up to null sets is correct.
A lawyer in \(B_k\) cannot have been assigned at an earlier construction step, since that would give her a contract preferred to \(a_k\), contradicting improvement. She cannot have been assigned at step \(k\), since then her assignment in \(Y\) would already be \(a_k\).
Positive mass in \(B_k\) therefore triggers priority separation: \(I_k\) fills capacity and outranks the new applicants.
This is the critical step accounting for chronological choice, and it is valid.
A lawyer originally assigned \(a_k\) can receive a different contract in \(Z\) only if that contract is preferred to \(a_k\). Its preference index must then be smaller than \(k\), placing her in one of the null sets \(B_j\) with \(j<k\).
Thus, outside a null set, lawyers in \(I_k\) have only their original period-\(t_k\) offer at court \(c\) in \(Y\cup Z\). Omitting that contract from \(Z\) does not remove it from the union. They cannot be accepted at an earlier chronological period and remain available at \(t_k\).
The offers at \(a_k\) are precisely \(I_k\cup B_k\), up to null sets. Earlier chronological acceptance may remove some members of \(B_k\), but it does not remove positive mass from \(I_k\).
At period \(t_k\), the available original assignees fill capacity and outrank every remaining new applicant. The court therefore accepts no positive mass from \(B_k\) at that period. This contradicts
\[
Z=\operatorname{Ch}_c(Y\cup Z),
\]
because \(Z\) assigns positive mass \(B_k\) there.
The proof consequently excludes every blocking allocation allowed by the task.
The operation count \(O(mh\tau)\) is correct after polynomial-time preprocessing.
The denominator argument also establishes polynomial bit complexity. The product \(D\) of input denominators has binary length \(O(L)\). All maintained quantities remain integer multiples of \(1/D\), since the algorithm uses comparisons, minima, addition, and subtraction. Their values remain within \([0,1]\), so scaled numerators have \(O(L)\) bits.
Computing \(D\), scaling the inputs, performing the stated operations, and emitting \(mh\tau\) rational entries all take polynomial time in the stated parameters.
The empty acceptable-pair list, exhausted population, zero capacities, and null-set endpoint conventions do not invalidate any step.
None. No additional lemma, hypothesis, or computation is needed to verify the claimed result.
⟨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.