Answer: —
Theorem 8 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMUDAN terminates within time $O(n^2+|E|)$, satisfies IC, IR, ND, NW, and $1/m$-weak efficiency.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed finite rooted directed network template, a finite menu of community profiles with rational valuations and rational population shares, a supply density \(q\), and a specified tie-breaking rule, form societies by replicating the communities and connecting their entry roles to seller \(s\). With \(m_k=\lfloor qhk\rfloor\) items for \(k\) copies of an \(h\)-buyer template, compute the limiting allocation and payment mass for each role when MUDAN runs as \(k\) grows through compatible denominators. Determine its worst-case limiting welfare factor over the allowed profiles against the top-\(q\)-mass benchmark, evaluating each tagged buyer's incentive comparison in the finite replicas before taking the limit.
Input a directed template with \(h\geq1\) buyer roles and nonempty entry set \(R\), from which every role is reachable; a finite menu \(C\) of nonnegative rational valuation vectors \((v_{c,r})_{r=1}^h\); rational community shares \(\alpha_c\geq0\) summing to \(1\); and rational supply density \(0<q\leq1\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Here types are community-role pairs \((c,r)\), with mass \(\alpha_c/h\); \(\tau\) is support size, not the number of possible types.
For integers \(k\) with every \(k\alpha_c\) integral, make \(k\alpha_c\) disjoint copies of profile \(c\), connect seller \(s\) to every copy's entry roles, and supply \(m_k=\lfloor qhk\rfloor\) items; each buyer demands one item. No edges connect different copies.
Use priority \(\sigma_i=|r_i'|\), where \(r_i'\) is the reported outgoing neighbour set. Input fixed orders on communities and roles; resolve all ties lexicographically by community, role, then copy index, independently of reports.
MUDAN starts with explored set \(A=r_s\), winners \(W=\varnothing\), and residual supply \(\ell=m_k\). Set \(P=W\cup\operatorname{Top}_{\ell}(A\setminus W)\), taking all available buyers if fewer than \(\ell\) exist and ranking by reported valuation with the specified ties.
While \(\ell>0\), repeatedly expand each not-yet-expanded buyer in \(W\cup(A\setminus P)\) by adding its reported neighbours to \(A\), recomputing \(P\) after each expansion. If \(P\setminus W=\varnothing\), stop; otherwise choose its highest-priority buyer \(w\), charge the current \((\ell+1)\)-st highest reported valuation in \(A\setminus W\) (zero if absent), add \(w\) to \(W\), decrement \(\ell\), and recompute \(P\). Winners receive one item; all other allocations and payments are zero.
At truthful reports, define \(a_{c,r}(\alpha)=\lim_k (hk)^{-1}\sum_{i\text{ of type }(c,r)}\pi_i\) and \(p_{c,r}(\alpha)=\lim_k (hk)^{-1}\sum_{i\text{ of type }(c,r)}p_i\), along the compatible integers. Let \(B_q(\alpha)=\max\{\sum_{c,r}v_{c,r}x_{c,r}:0\leq x_{c,r}\leq\alpha_c/h,\ \sum_{c,r}x_{c,r}=q\}\).
For the fixed template, menu, density and orders, define the worst-case factor \(\rho=\inf_{\alpha\in\mathbb Q_{\geq0}^{C},\ \sum_c\alpha_c=1,\ B_q(\alpha)>0}\bigl(\sum_{c,r}v_{c,r}a_{c,r}(\alpha)\bigr)/B_q(\alpha)\); require that the menu contains a positive valuation.
Tagged-buyer incentive comparisons use utility \(v_i\pi_i-p_i\) in each finite replica before taking limits: allow joint deviations to any nonnegative rational bid and any subset of true outgoing neighbours, hold other reports fixed, and silence buyers made unreachable by the deviation.
Do these replica limits always exist, and are the decision problems asking whether a designated limiting allocation mass, payment mass, or \(\rho\) is at least an input rational threshold in \(\mathrm P\) or NP-hard? State running times in \(m\), \(\tau\), total binary input length \(L\), \(h\), template edge count, and menu size; here finite supply is \(m=m_k\), and replica expansion size is not the continuous input size.
Discrete MUDAN runs in \(O(n^2+|E|)\), is incentive compatible, individually rational, non-deficit and non-wasteful, and guarantees \(1/m\) of the top-\(m\) welfare among buyers not separated from the seller by the last winner. [Source](https://arxiv.org/pdf/2302.08924v2).
No result settling this replica-limit problem was located.
The general existence and complexity questions remain unresolved here. The main additional result is a complete solution for a nontrivial subclass: a directed star with one community, arbitrary nonnegative rational role valuations, arbitrary role order, and arbitrary rational density.
For this subclass, all allocation and payment limits exist, and all three threshold problems are in $\mathrm P$. The payment formulas account for exact supply boundaries; at such boundaries, an error of one item in the allocation count can change the payments of a positive population mass.
I also prove general structural facts and the unrestricted welfare bound from the notes, including the zero-supply case identified by the verifier.
Fix a society $\alpha$ and a compatible integer $k$. Write
$$
n=hk,\qquad m=\lfloor qhk\rfloor,\qquad
\mu_{c,r}=\frac{\alpha_c}{h}.
$$
Let $e$ be the template edge count and let $d$ be the number of communities with positive share. Then
$$
\tau=hd,\qquad |E_k|=k(e+|R|).
$$
Define the finite normalized outcomes
$$
a^{(k)}_{c,r}
=\frac1n\sum_{i\text{ of type }(c,r)}\pi_i,
\qquad
p^{(k)}_{c,r}
=\frac1n\sum_{i\text{ of type }(c,r)}p_i.
$$
All statements below concern truthful reports unless explicitly stated otherwise. Valuation ranking always includes the prescribed tie order.
An explored, unallocated buyer is exhausted when it lies outside the current top-$\ell$ set.
Once a buyer is exhausted, it can never become a potential winner again. Indeed, at exhaustion at least $\ell$ explored, unallocated buyers precede it in valuation ranking. Exploration cannot reduce that count. Selecting a winner reduces the count by at most one and reduces $\ell$ by exactly one. The count therefore remains at least the residual supply.
This also proves independence from the order of eligible expansions. With winners and residual supply fixed, put
$$
D(A)=A\setminus
\bigl(W\cup\operatorname{Top}_{\ell}(A\setminus W)\bigr).
$$
If $A\subseteq A'$, then $D(A)\subseteq D(A')$. Consequently,
$$
F(A)=A\cup\bigcup_{i\in W\cup D(A)}r_i
$$
is monotone.
Iteration of $F$ from the explored set at the beginning of the expansion stage reaches its least fixed point. Every individual permitted expansion stays within this fixed point. Conversely, an exhaustive expansion sequence ends at a fixed point: all eligible buyers have been expanded, and the neighbors of previously expanded buyers are already explored. Its final explored set is therefore exactly the least fixed point. Winner tie-breaking then determines the run uniquely.
For $m=0$, this is immediate.
Otherwise, suppose the algorithm stops after expansion with $\ell>0$ and no potential winner. Then $A\setminus W=\varnothing$, so $A=W$. Every explored buyer has been expanded, and no outgoing edge from $A$ leads outside $A$. All seller neighbors belong to $A$.
Seller reachability therefore implies that all $n$ buyers belong to $A=W$. But stopping with positive residual supply means
$$
|W|<m\leq n,
$$
a contradiction.
Thus exactly $m$ buyers win.
Suppose a winner is removed from the current top-$\ell$ set. If the current $(\ell+1)$-st buyer exists, that buyer becomes the $\ell$-th buyer after the removal. Since residual supply becomes $\ell-1$, this is precisely the next price position before further exploration. Exploration cannot decrease an order statistic. If the old price position was absent, its price was zero.
Hence successive winner prices are nondecreasing. Also, every truthful winner satisfies
$$
0\leq p_i\leq v_i,
$$
because it belongs to the top-$\ell$ set when charged the next valuation.
Let
$$
V=\max_{c,r}v_{c,r},
$$
and let $\operatorname{OPT}_k$ be the sum of the top $m$ valuations among all $n$ buyers.
Proposition. Every truthful replica satisfies
$$
\sum_i v_i\pi_i\geq \frac{\operatorname{OPT}_k}{h}-V.
$$
If $m=0$, both welfare and $\operatorname{OPT}_k$ are zero, so the assertion holds. Assume henceforth that $m>0$.
Fix $t\in(0,V]$. Let $K(t)$ count copies containing a buyer valued at least $t$, and let $H(t)$ count final winners valued at least $t$.
Consider a state after exhaustive expansion and before winner selection. Write $H_{\mathrm{cur}}(t)$ for the number of previously selected winners valued at least $t$.
If the current price is below $t$, every explored, unallocated buyer valued at least $t$ is potential. Otherwise, such a buyer outside the top-$\ell$ set would imply a price at least $t$.
Consider a copy counted by $K(t)$ that has not yet received a winner valued at least $t$. Choose a buyer in it valued at least $t$.
If this buyer is explored, it is an unallocated potential winner. If it is unexplored, take a seller-to-buyer path and its first unexplored buyer. Its predecessor is explored and unexpanded. At the end of exhaustive expansion, that predecessor must be an unallocated potential winner. The predecessor lies in the same copy, since the seller’s entry neighbors are already explored.
Distinct copies supply distinct potential buyers. At most $H_{\mathrm{cur}}(t)$ copies have received a winner valued at least $t$. Therefore
$$
K(t)-H_{\mathrm{cur}}(t)\leq\ell.
$$
If the first winner price is at least $t$, all $m$ winners have valuation at least $t$. Otherwise, consider the first selection state whose price reaches $t$, if one exists. At the preceding selection state,
$$
H_{\mathrm{cur}}(t)+\ell\geq K(t).
$$
The intervening selection decreases this sum by at most one. Every subsequent winner is valued at least $t$, so the sum is preserved thereafter and becomes $H(t)$ at termination.
If no price reaches $t$, apply the same inequality immediately before the last selection, where $\ell=1$. In either case,
$$
H(t)\geq \min\{m,K(t)\}-1.
$$
Let $N(t)$ count all buyers valued at least $t$. Each copy has $h$ buyers, so
$$
N(t)\leq hK(t).
$$
It follows that
$$
H(t)\geq \frac1h\min\{m,N(t)\}-1.
$$
Integrating the buyer indicators gives
$$
\sum_i v_i\pi_i=\int_0^V H(t)\,dt,
\qquad
\operatorname{OPT}_k=\int_0^V\min\{m,N(t)\}\,dt.
$$
Integration proves the proposition. $\square$
For any density $z\in[0,1]$, define $B_z(\alpha)$ by the benchmark in the question with $q$ replaced by $z$. Filling types in decreasing valuation order is optimal: transferring mass from a lower-valued filled type to a higher-valued unfilled type cannot decrease welfare.
At density $m/n$, capacities and target mass are integer multiples of $1/n$, so
$$
B_{m/n}(\alpha)=\frac{\operatorname{OPT}_k}{n}.
$$
Additional allocated mass has marginal value between zero and $V$. Thus
$$
B_q(\alpha)-\frac Vn
\leq \frac{\operatorname{OPT}_k}{n}
\leq B_q(\alpha).
$$
Consequently,
$$
\frac{B_q(\alpha)}h-\frac{(1+1/h)V}{hk}
\leq
\sum_{c,r}v_{c,r}a^{(k)}_{c,r}
\leq B_q(\alpha).
$$
The normalized allocation and payment vectors lie in a fixed bounded box, so jointly convergent subsequences exist. Every subsequential limit $(a,p)$ satisfies
$$
0\leq a_{c,r}\leq\mu_{c,r},
\qquad
0\leq p_{c,r}\leq v_{c,r}a_{c,r},
\qquad
\sum_{c,r}a_{c,r}=q,
$$
and
$$
\frac{B_q(\alpha)}h
\leq\sum_{c,r}v_{c,r}a_{c,r}
\leq B_q(\alpha).
$$
These statements do not establish uniqueness of the subsequential limits. Conditional on existence for every society, they imply
$$
\frac1h\leq\rho\leq1.
$$
Assume $h\geq2$. Rename the roles as $0,1,\ldots,h-1$. Role $0$ is the unique entry role, with edges to every other role; leaves have no outgoing edges. There is exactly one community, so $\alpha=1$ and every positive integer $k$ is compatible.
Write
$$
d=h-1,\qquad u=v_0.
$$
List the leaf roles in decreasing valuation order, resolving ties by the given role order. Write their valuations as
$$
z_1\geq z_2\geq\cdots\geq z_d.
$$
Subscripts here identify this sorted list of leaf roles.
Define
$$
g=
\#\{\text{leaf roles preceding role }0
\text{ in the full valuation ranking}\}.
$$
Thus a leaf contributes to $g$ if its valuation exceeds $u$, or if its valuation equals $u$ and its role precedes role $0$.
Roots have priority $d>0$, while leaves have priority zero. Therefore every selected winner is a root whenever any root remains potential.
Let $w_k$ be the number of root winners. Then
$$
w_k=
\begin{cases}
\min\{m,k\},&g=0,\\
0,&g\geq1\text{ and }m<k,\\
\min\left\{k,\left\lfloor\frac{m-k}{g}\right\rfloor+1\right\},
&g\geq1\text{ and }m\geq k.
\end{cases}
$$
The case $m=0$ is immediate.
If $g=0$, every leaf ranks below every root. Leaf discoveries therefore cannot displace a potential root. Exactly $\min\{m,k\}$ roots win.
Now suppose $g\geq1$. Once any root becomes exhausted, exhaustive expansion exhausts all remaining unallocated roots. To see this, at a state with an exhausted root, the potential set is full and contains no leaf below the roots: such a leaf would rank below the exhausted root. Expanding an exhausted root reveals $g$ new leaves above every root. If a root remains potential, at least one of these new leaves displaces a root, which becomes eligible for expansion. Repeating this argument exhausts all remaining roots.
If $m<k$, some root is exhausted initially, so this cascade occurs before any root can win.
If $m\geq k$, initially no root is exhausted. After $r$ roots have won and been expanded, provided no root has yet become exhausted, the explored unallocated buyers consist of
$$
k-r\text{ roots},\qquad
r\text{ buyers of each leaf role}.
$$
Residual supply is $m-r$. All remaining roots are potential exactly when
$$
(k-r)+gr\leq m-r,
$$
equivalently,
$$
gr\leq m-k.
$$
While this holds, a root wins next. The first root selection that makes it fail is selection
$$
\left\lfloor\frac{m-k}{g}\right\rfloor+1.
$$
Before another winner can be selected, the exhaustion cascade removes all remaining roots from potential competition. If all $k$ roots win first, the count is capped at $k$. This proves the formula. $\square$
Put
$$
L_k=m-w_k.
$$
If $L_k>0$, every root has been expanded before the first leaf winner is selected: roots have either won or become exhausted. Hence all $dk$ leaves are explored.
No leaf expansion reveals another buyer. Therefore the leaf winners are exactly the top $L_k$ leaf buyers. The number of winners of sorted leaf role $j$ is
$$
T_{j,k}
=
\min\{k,\max\{0,L_k-(j-1)k\}\}.
$$
This formula also holds when $L_k=0$.
All leaf winners pay the same price:
$$
b_k=
\begin{cases}
z_{\lfloor L_k/k\rfloor+1},&0<L_k<dk,\\
0,&L_k=0\text{ or }L_k=dk.
\end{cases}
$$
Indeed, removing a member of a fixed top-$L_k$ set and decrementing supply leaves its original next valuation unchanged as the price. Thus the total payment of leaf role $j$ is
$$
b_kT_{j,k}.
$$
If $m<k$, every root winner pays $u$: an exhausted root supplies the next valuation. This case has root winners only when $g=0$.
Suppose $m\geq k$, and put $D=m-k$. Immediately before root winner $r+1$, where
$$
0\leq r<w_k,
$$
no root has yet become exhausted. The candidates consist of $k-r$ roots and $r$ buyers of each leaf role. Since $gr\leq D$, the price position lies below the root block.
The price is $z_j$ for the smallest $j$ satisfying
$$
jr>D,
$$
or zero if no such $j$ exists.
Define
$$
N_{1,k}=\max\{0,w_k-D-1\},
$$
and, for $2\leq j\leq d$,
$$
N_{j,k}
=
\max\left\{
0,\
\min\left\{w_k-1,\left\lfloor\frac D{j-1}\right\rfloor\right\}
-\left\lfloor\frac Dj\right\rfloor
\right\}.
$$
These count precisely the integers $r$ satisfying
$$
0\leq r<w_k,\qquad
jr>D,\qquad
(j-1)r\leq D.
$$
Consequently, total root payment is
$$
\sum_{j=1}^d z_jN_{j,k}.
$$
These are exact finite formulas, requiring no replica construction.
Put
$$
s=qh.
$$
Define the limiting number of root winners per copy by
$$
x=
\begin{cases}
\min\{s,1\},&g=0,\\
0,&g\geq1\text{ and }s\leq1,\\
(s-1)/g,&g\geq1\text{ and }1<s<g+1,\\
1,&g\geq1\text{ and }s\geq g+1.
\end{cases}
$$
The finite root formula and $m/k\to s$ give
$$
\frac{w_k}{k}\longrightarrow x.
$$
Put
$$
y=s-x.
$$
Then $L_k/k\to y$, and $0\leq y\leq d$.
The root and sorted leaf allocation masses are
$$
a_0=\frac{x}{h},
$$
and
$$
a_j=\frac1h\min\{1,\max\{0,y-j+1\}\},
\qquad 1\leq j\leq d.
$$
These follow directly from the finite allocation formulas and continuity of clipping. In particular,
$$
a_0+\sum_{j=1}^d a_j=q.
$$
If $s<1$, then
$$
p_0=
\begin{cases}
uq,&g=0,\\
0,&g\geq1.
\end{cases}
$$
Indeed, eventually $m<k$, and the exact finite root payment is respectively $um$ or zero.
Suppose $s\geq1$. Define
$$
\lambda_1=x-\min\{x,s-1\},
$$
and, for $2\leq j\leq d$,
$$
\lambda_j
=
\min\left\{x,\frac{s-1}{j-1}\right\}
-
\min\left\{x,\frac{s-1}{j}\right\}.
$$
Then
$$
p_0=\frac1h\sum_{j=1}^d z_j\lambda_j.
$$
To justify the limit, for $j\geq2$ the exact count $N_{j,k}$ counts integers in
$$
\left(\frac D j,\frac D{j-1}\right]\cap[0,w_k-1].
$$
The difference between the number of integers in an interval and its length is bounded by two. Since
$$
\frac Dk\longrightarrow s-1,\qquad
\frac{w_k}{k}\longrightarrow x,
$$
division by $k$ gives $N_{j,k}/k\to\lambda_j$. The displayed formula for $N_{1,k}$ gives the same conclusion for $j=1$. Taking the finite weighted sum proves the payment formula.
If $y=0$, every limiting leaf allocation and payment mass is zero. Assume $y>0$.
When $g\geq1$ and $s<g+1$, define
$$
b=z_{\lceil y\rceil}.
$$
In all other cases, define
$$
b=
\begin{cases}
z_{\lfloor y\rfloor+1},&y<d,\\
0,&y=d.
\end{cases}
$$
Then all leaf payment limits exist and satisfy
$$
p_j=b\,a_j.
$$
For nonintegral $y$, the assertion follows immediately from $L_k/k\to y$: eventually $\lfloor L_k/k\rfloor=\lfloor y\rfloor$.
For integral $y$, the finite offset must be determined rather than discarded.
First suppose all roots win asymptotically in the branch $s\geq g+1$, or in the branch $g=0$, $s\geq1$. In these branches all roots win exactly, so
$$
L_k=\lfloor sk\rfloor-k=\lfloor(s-1)k\rfloor.
$$
If $y=s-1$ is an integer, then $L_k=yk$. The price is the next leaf role’s valuation, or zero when $y=d$.
Now suppose $g\geq1$ and $s<g+1$. If $s<1$, then $y=s\in(0,1)$ is nonintegral. It remains to consider $s\geq1$ and integral $y=j$.
Here
$$
j=s-\frac{s-1}{g},
\qquad
(g-1)s=gj-1.
$$
For all sufficiently large $k$, the cap at $k$ is inactive, and
$$
w_k=\left\lfloor\frac{m-k}{g}\right\rfloor+1.
$$
Moreover,
$$
(gj-1)k-(g-1)m
=(g-1)(sk-\lfloor sk\rfloor).
$$
This quantity belongs to $[0,g-1)$ when $g>1$ and equals zero when $g=1$. Therefore
$$
g(m-jk)\leq m-k<g(m-jk+1),
$$
which proves
$$
\left\lfloor\frac{m-k}{g}\right\rfloor=m-jk.
$$
Consequently,
$$
L_k=m-w_k=jk-1.
$$
Thus the finite next leaf is still in role $j$, and its price is $z_j$, as claimed.
This establishes all allocation and payment limits for the subclass.
Because the menu has one community, the society simplex contains only $\alpha=1$. Hence $\rho$ is the ratio for this single society.
Sort all $h$ role valuations, including the root, as
$$
t_1\geq t_2\geq\cdots\geq t_h.
$$
Define
$$
F=
\sum_{j=1}^h
t_j\min\{1,\max\{0,s-j+1\}\}.
$$
The greedy benchmark proof in Section 2 gives
$$
B_q=\frac Fh.
$$
The menu contains a positive valuation and $q>0$, so $F>0$. Therefore
$$
\rho=
\frac{
ux+\displaystyle\sum_{j=1}^d
z_j\min\{1,\max\{0,y-j+1\}\}
}{F}.
$$
Every expression above is rational and obtained by sorting, rational arithmetic, clipping, and integer comparisons. Thus the designated allocation-mass, designated payment-mass, and welfare-factor threshold problems are all in $\mathrm P$ for this subclass.
Take $h=4$, root value zero, and leaf values
$$
3,\quad 2,\quad 1.
$$
Let $q=5/8$. Then
$$
g=3,\qquad s=\frac52,\qquad x=\frac12,\qquad y=2.
$$
The limiting allocations, listed as root followed by the sorted leaves, are
$$
\left(\frac18,\frac14,\frac14,0\right).
$$
Root payment is zero. Since $y=2$ is an integer in the partial-root branch, the leaf price is $2$, not $1$. The limiting payment masses are
$$
\left(0,\frac12,\frac12,0\right).
$$
Indeed, the exact finite identity is $L_k=2k-1$.
Achieved welfare is $5/4$, whereas the benchmark is
$$
B_{5/8}=\frac{3+2+1/2}{4}=\frac{11}{8}.
$$
Hence
$$
\rho=\frac{10}{11}.
$$
Thus the solved subclass includes inefficient outcomes, as well as nontrivial payment boundaries.
For arbitrary templates, a finite replica can be simulated using two balanced trees for the potential set, one ordered by valuation and one by priority, together with a queue of buyers awaiting expansion.
Permanent exhaustion means that exhausted buyers never need reinsertion. Each buyer is discovered once, exhausted at most once, and expanded at most once. The price is the maximum exhausted valuation when exhausted buyers exist, and zero otherwise. Thus finite simulation uses
$$
O\bigl(n\log(m+2)+|E_k|\bigr)
=
O\bigl(hk\log(m+2)+k(e+|R|)\bigr)
$$
operations. The case $m=0$ returns zero outcomes immediately; explicit per-buyer output still requires $O(n)$ time.
Since $hk<(m+1)/q$, this is also bounded by
$$
O\left(
\frac{m+1}{q}\log(m+2)
+
\frac{(m+1)(e+|R|)}{qh}
\right).
$$
A conservative bit bound, including reading the input, is
$$
O\left(
L+
\bigl[hk\log(m+2)+k(e+|R|)\bigr]
\bigl(L+\log(k+1)\bigr)^2
\right).
$$
This is a finite-replica bound, not a polynomial continuous-input algorithm. Binary encoding does not bound $k$ or $1/q$ polynomially in $L$ or $\tau$.
For the solved star subclass,
$$
\tau=h,\qquad e=h-1,\qquad |C|=1.
$$
The exact finite formulas require
$$
O\bigl(h\log(h+1)\bigr)
$$
arithmetic operations, independently of the number of winners $m$. The limit formulas and threshold comparisons have the same arithmetic-operation bound.
For an explicit conservative bit bound, put
$$
S_k=L+\log(k+1)+h\log(h+1).
$$
The finite formula algorithm takes
$$
O\bigl(L+h\log(h+1)S_k^3\bigr)
$$
bit operations. For the continuous limit and threshold algorithms, replace $S_k$ by
$$
S=L+h\log(h+1).
$$
Intermediate rational denominators involve input denominators and products of integers bounded by $h$, so their bit lengths are polynomially bounded by $S$. These bounds are polynomial in the continuous input length and require no replica expansion.
Use the finite incentive-compatibility theorem supplied in the question as a premise. Its priority conditions are satisfied: reported outgoing degree is independent of the bid and cannot increase when neighbors are hidden. The prescribed tie orders are independent of reports, and the silence convention matches the finite model. These conditions and the finite theorem appear in Section 3 and Lemma 4 of the [cited paper](https://arxiv.org/pdf/2302.08924v2).
For every finite replica, every tagged buyer, and every permitted joint deviation, including a deviation depending on $k$,
$$
u_k^{\mathrm{dev}}\leq u_k^{\mathrm{truth}}.
$$
For $m=0$, both utilities are zero. Therefore, without assuming any utility limit,
$$
\limsup_k
\bigl(u_k^{\mathrm{dev}}-u_k^{\mathrm{truth}}\bigr)\leq0.
$$
If truthful tagged utility converges to $u$, this additionally gives
$$
\limsup_k u_k^{\mathrm{dev}}\leq u.
$$
Aggregate type convergence does not itself establish convergence of a tagged buyer’s utility.
The remaining general gap is uniqueness of normalized subsequential outcomes for arbitrary templates and menus. The structural facts and welfare bounds above do not close it. Nor does the polynomial algorithm for one-community stars classify any unrestricted threshold problem.
⟨structured verdict parsed — rendered above⟩
Overall assessment: partial, with sound substantive progress. The output establishes the stated results for one-community directed stars, together with general finite structural facts, a welfare bound, and constraints on subsequential limits. It does not settle general replica-limit existence or any unrestricted threshold problem. The prover accurately acknowledges those limitations.
I found no false central step or counterexample to the results actually proved. The major issues below are missing parts of USER_TASK, rather than defects in the star formulas.
The identities
$$
n=hk,\qquad \tau=hd,\qquad |E_k|=k(e+|R|)
$$
are correct, with $d$ denoting the number of positive-share communities in this section. Compatibility ensures that each positive-share community contributes every role to the support.
The normalization by $n$ agrees with the task’s definitions.
The argument is correct. Once an unallocated buyer has at least $\ell$ explored, unallocated buyers preceding it, exploration cannot decrease that count. Selecting a winner decreases the count by at most one while decreasing $\ell$ by exactly one.
The claim remains valid with tied valuations because the prescribed ranking is a fixed total order.
The inclusion
$$
D(A)\subseteq D(A')
$$
for $A\subseteq A'$ is correct when winners and residual supply are fixed. Consequently, the stated expansion map is monotone.
The fixed-point argument correctly accounts for previously expanded buyers: their outgoing neighbors are already explored. Finiteness and exhaustive expansion therefore justify the asserted unique explored set at each selection stage. Fixed winner tie-breaking then determines the run.
The argument is correct, including $m=0$.
For positive residual supply, an empty potential-winner set forces $A=W$. Exhaustive expansion then makes $A$ closed under outgoing edges. Since all seller neighbors are explored and all buyers are seller-reachable, premature termination contradicts $|W|<m\leq n$.
The order-statistic argument is correct. Removing any current potential winner shifts the previous price position to the next price position after the supply decrement. Further exploration cannot lower its valuation.
The bound
$$
0\leq p_i\leq v_i
$$
also follows from membership in the current potential set. No strict-valuation assumption is needed.
The proposition
$$
\sum_i v_i\pi_i\geq \frac{\operatorname{OPT}_k}{h}-V
$$
is supported by the written argument.
The critical steps check as follows:
$$ K(t)-H_{\mathrm{cur}}(t)\leq\ell. $$
$$
N(t)\leq hK(t).
$$
The resulting bound and integration give the displayed proposition.
The zero-supply case is explicitly and correctly separated.
The greedy benchmark argument is valid for the nonnegative valuations and capacities in the task. At density $m/n$, the capacities and supply are multiples of $1/n$, so the equality with normalized finite optimum is justified.
The rounding estimate has the correct constant:
$$
0\leq B_q(\alpha)-\frac{\operatorname{OPT}_k}{n}\leq\frac Vn.
$$
Combining it with the welfare proposition gives the stated error
$$
\frac{(1+1/h)V}{hk}.
$$
Boundedness yields jointly convergent subsequences, and the allocation, payment, supply, and welfare constraints pass to those limits. These conclusions establish subsequential existence, not convergence of the full sequence.
The statement
$$
\frac1h\leq\rho\leq1
$$
is correctly conditional on general existence. It is not presented as an unconditional resolution of $\rho$.
The subclass assumptions are explicit: $h\geq2$, one entry root, edges from that root to every leaf, and one community.
The definition of $g$ correctly includes both strict valuation comparisons and role-order ties. Thus each counted leaf precedes every root buyer.
All branches of the formula for $w_k$ are justified:
$$
gr\leq m-k
$$
correctly characterizes the stage before exhaustion begins.
The additional one in the root-count formula is necessary: the root that first makes this inequality fail has already won before the cascade occurs. The cap at $k$ is correct.
If a leaf is selected, every root has already won or become exhausted and has been expanded. Thus all leaves are explored.
Although leaf priority ties need not select buyers in valuation order, selection eventually allocates exactly the fixed top-$L_k$ leaf set. The clipping formula for $T_{j,k}$ is correct.
The common leaf price is also correct, including exact multiples of $k$ and full leaf allocation.
Before root winner $r+1$, the inequality $gr\leq D$ places the price position below the root block. The condition
$$
jr>D
$$
correctly identifies its leaf valuation, with zero when the position is absent.
The formulas for $N_{j,k}$ correctly count the specified integer intervals. Their endpoints and the special case $j=1$ have the correct offsets.
As a computational cross-check, direct execution of the specified mechanism matched these finite allocation and payment formulas in $56{,}160$ cases covering $2\leq h\leq4$, valuations in $\{0,1,2\}$, every role order, $1\leq k\leq3$, and every feasible integer supply. This supplements, rather than replaces, the written proof.
The finite root formulas imply the displayed limit $x$ in every branch. The allocation formulas follow by continuous clipping and satisfy total mass $q$.
For $s<1$, the finite payment formulas give the stated limits directly.
For $s\geq1$, the normalized interval counts converge to the displayed $\lambda_j$. The endpoint errors are bounded independently of $k$, so they disappear after normalization. The weighted payment formula is justified.
The treatment of integral $y$ is essential and correct.
In the branches where all roots win, the exact leaf count is the stated floor expression. At an integral boundary, the next leaf role supplies the price, or the price is zero at full leaf allocation.
In the partial-root branch, the arithmetic establishing
$$
L_k=jk-1
$$
is correct. It also covers $g=1$: the intermediate quantity is then zero, and the stated floor identity still holds.
When $y=0$, the finite payment bounds ensure that vanishing allocation mass gives vanishing payment mass.
Thus the output establishes all allocation and payment limits for its declared subclass.
With one community, the feasible society set contains only $\alpha=1$. Therefore replacing the infimum defining $\rho$ by the single society’s ratio is legitimate.
The benchmark formula is correct. A positive menu valuation and $q>0$ ensure $F>0$, so the ratio is defined.
The boundary example checks:
$$
x=\frac12,\qquad y=2,\qquad
B_{5/8}=\frac{11}{8},\qquad
\rho=\frac{10}{11}.
$$
Its limiting allocation and payment masses agree with the finite formulas.
The finite simulation operation bound is supported by permanent exhaustion, one-time discovery and expansion, and potential-set trees of size at most $m$. Maintaining the maximum exhausted valuation supports the price query.
The conversion using
$$
hk<\frac{m+1}{q}
$$
is correct. The conservative bit bound is consistent with the required comparisons and counters.
For the star subclass, sorting and evaluating the finite or limiting formulas takes the stated number of arithmetic operations. The denominator and bit-length discussion supports polynomial bit complexity for the continuous threshold algorithms.
The output correctly distinguishes finite-replica simulation from a polynomial algorithm in continuous input size. Its unrestricted simulation bounds do not classify the unrestricted threshold problems.
The invocation is acceptable because USER_TASK expressly supplies finite incentive compatibility as a premise. The cited paper’s priority condition, silent-report convention, and incentive-compatibility statement match the conditions invoked here. [Source, Section 3 and Lemma 4](https://arxiv.org/pdf/2302.08924v2).
The selected priority is independent of bids and cannot increase when neighbors are hidden. The deviation domain in the task is covered by the stated finite premise.
The pointwise finite utility inequality implies the asserted limit-superior inequality, including for deviations depending on $k$. The stronger conclusion is correctly conditional on truthful tagged utility convergence.
The prover correctly avoids inferring tagged-buyer utility convergence from aggregate type convergence.
Severity: major relative to the assigned task.
Boundedness and subsequential constraints do not establish convergence for arbitrary templates and menus.
Required completion: establish full-sequence convergence of every designated allocation and payment coordinate along compatible integers, or provide an admissible failure of convergence. No clarification of the existing subsequence argument alone settles this obligation.
Severity: major relative to the assigned task.
The polynomial formulas apply only to one-community stars. General finite simulation may require replica expansion beyond polynomial continuous input size.
Required completion: after resolving well-definedness, provide a polynomial algorithm or hardness result for each unrestricted threshold problem, with the requested input-size dependence.
Severity: major relative to the assigned task.
The general bound on $\rho$ is conditional, and its exact computation is confined to a singleton society space.
Required completion: justify general well-definedness and classify the unrestricted threshold problem over rational societies satisfying $B_q(\alpha)>0$.
These omissions prevent a complete answer to USER_TASK. They do not invalidate the proved subclass or structural results.
⟨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.