Answer: Every society in the product family satisfies \(R_\infty\le (k-1)/(1+(k-2)\mu)\le 1/\mu\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe average-case approximation ratio of Random Priority, when agents' preferences are independent and identically distributed random variables, is upper bounded by the constant $1/ \mu$, where $\mu$ is the expectation of these random variables.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(k\) item classes and a finite support \(\{(v_t,\rho_t)\}_{t=1}^{\tau}\), where \(v_t\in[0,1]^k\), \(\rho_t\in\mathbb{Q}_{>0}\), and \(\sum_t\rho_t=1\), with per-capita supply \(1/k\) of each class, compute the ratio of optimal welfare to Random Priority welfare in the fluid limit of replicas with \(K\rho_t\) agents of type \(t\) and \(K/k\) indivisible copies of each class. For the product-type family where the first two coordinates are fixed at \(1\) and \(0\), and the remaining coordinates are independent draws from a finite-support rational distribution \(D\) on \([0,1]\) with mean \(\mu>0\), does this limiting ratio always satisfy \(R_\infty\le 1/\mu\)?
A society is given by its support: the list of \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. There are \(m=k\ge2\) item classes, each with supply \(1/k\), and types \(v_t\in(\mathbb Q\cap[0,1])^k\) with masses \(\rho_t>0\) summing to \(1\). Let \(L\) be the total input bit length; state any running times in \(m,\tau,L\) and any additional parameters.
Each agent receives exactly one item. A mass allocation \(x_{tj}\ge0\) satisfies \(\sum_jx_{tj}=\rho_t\) and \(\sum_tx_{tj}=1/k\); its welfare is \(\sum_{t,j}v_{tj}x_{tj}\). Let \(W_{\mathrm{OPT}}\) be the maximum feasible welfare.
For each integer \(K\) making every \(K\rho_t\) and \(K/k\) integral, form a replica with \(K\rho_t\) agents of type \(t\) and \(K/k\) copies of each class. Random Priority chooses a uniformly random agent ordering; each agent takes a highest-valued available class, breaking value ties by increasing class index.
Let \(W_{\mathrm{RP}}=\lim_{K\to\infty}K^{-1}\mathbb E[SW_{\mathrm{RP},K}]\), along these admissible integers, with expectation over the ordering, and define \(R_\infty=W_{\mathrm{OPT}}/W_{\mathrm{RP}}\).
In the product family, the society is exactly the law of \((1,0,Z_3,\ldots,Z_k)\), where the \(Z_j\) are independent with common finite-support distribution \(D\) on \(\mathbb Q\cap[0,1]\), having positive rational probabilities and mean \(\mu>0\). Endpoint atoms and point-mass distributions are allowed.
Does every society in this product family satisfy \(R_\infty\le1/\mu\), or is there a member with \(R_\infty>1/\mu\)?
For discrete assignments with one preset value \(1\) and one preset value \(0\) per agent and all remaining entries independent draws from a common distribution of mean \(\mu\), the established average-case approximation guarantee is asymptotically \(1/\mu\). [Gao–Zhang](https://www.ijcai.org/proceedings/2019/0041.pdf)
Random Priority assignments in replica markets with strict rankings converge to the continuum Probabilistic Serial assignment; fixed tie-breaking supplies such rankings here. This establishes an allocation limit, rather than the product-family welfare bound above. [Che–Kojima](https://www.columbia.edu/~yc2271/files/papers/psrp33-EMA.pdf)
Every society in the stated product family satisfies \(R_\infty\le 1/\mu\). In fact, the following stronger bounds hold:
\(W_{\mathrm{RP}}\ge \dfrac{1+(k-2)\mu}{k}\),
\(R_\infty\le \dfrac{k-1}{1+(k-2)\mu}\le \dfrac1\mu\).
The proof accommodates endpoint atoms, point-mass distributions, and the prescribed tie-breaking rule.
Refine each type’s preferences into a strict ranking by decreasing value, breaking ties by increasing class index. Random Priority depends only on these refined rankings.
We use the replica-convergence theorem: with finitely many classes and strict preference types, fixed proportions of preference types, and class supplies growing proportionally, the Random Priority assignment converges to the continuum Probabilistic Serial assignment. This is [Che–Kojima, Theorem 2](https://www.columbia.edu/~yc2271/files/papers/psrp33-EMA.pdf).
Its hypotheses hold here. Let \(K_0\) be the least common multiple of \(k\) and the reduced denominators of all masses. The admissible integers are exactly \(K=nK_0\), and their markets are replicas of one fixed finite market. There are finitely many refined rankings, their proportions are constant, and each class has \(K/k\) copies. Every class is acceptable: in the theorem’s formulation, place the outside option below all classes.
Write \(p_{tj}^{(K)}\) for the probability that a type-\(t\) agent receives class \(j\), and \(p_{tj}^{\mathrm{PS}}\) for its continuum PS share. Types sharing a refined ranking receive the same assignment probabilities, even if their cardinal values differ. Thus the theorem gives \(p_{tj}^{(K)}\to p_{tj}^{\mathrm{PS}}\) for every \(t,j\). Consequently,
\(\displaystyle \frac1K\mathbb E[SW_{\mathrm{RP},K}]=\sum_{t,j}\rho_t v_{tj}p_{tj}^{(K)}\longrightarrow \sum_{t,j}\rho_t v_{tj}p_{tj}^{\mathrm{PS}}=:W_{\mathrm{PS}}.\)
The interchange with the sum is valid because it is finite. Hence \(W_{\mathrm{RP}}=W_{\mathrm{PS}}\).
In this continuum PS process, every agent eats its highest-ranked available class at speed one throughout the time interval \([0,1]\). Therefore, at every time before completion, each type contributes its original mass to the consumption rates. Earlier consumption does not remove types from the population.
The total consumption rate is one whenever some supply remains. Since total supply is one, consumption finishes at time one. Every class is exhausted: otherwise the total amount consumed would be less than one.
Let \(S\subseteq\{1,\ldots,k\}\) be any nonempty, fixed set of available classes. For a valuation vector \(V=(1,0,Z_3,\ldots,Z_k)\), let \(c_S(V)\) denote the class chosen from \(S\), using the prescribed tie-breaking.
For each random class \(j\in S\cap\{3,\ldots,k\}\), define
\(a_j(S)=\mathbb P(c_S(V)=j)\),
\(b_j(S)=\mathbb E[Z_j\,\mathbf 1_{\{c_S(V)=j\}}]\).
We prove \(b_j(S)\ge\mu a_j(S)\).
For a support value \(z\) of \(D\), set
\(q_j(z)=\mathbb P(c_S(V)=j\mid Z_j=z)\).
Fix all coordinates other than \(Z_j\). If class \(j\) is chosen at value \(z\), increasing its value preserves that choice. This holds at ties because the tie-breaking order is fixed. Independence ensures that the distribution of the other coordinates does not change when conditioning on \(Z_j=z\). Thus \(q_j\) is nondecreasing on the support of \(D\).
Let \(Z,Z'\) be independent draws from \(D\). Monotonicity gives
\((Z-Z')(q_j(Z)-q_j(Z'))\ge0\)
for every pair of support values. Expanding its expectation and using independence yields
\(\displaystyle 0\le \frac12\mathbb E[(Z-Z')(q_j(Z)-q_j(Z'))]=\mathbb E[Zq_j(Z)]-\mathbb E[Z]\mathbb E[q_j(Z)].\)
By conditioning on \(Z_j\),
\(\mathbb E[Zq_j(Z)]=b_j(S)\), \(\mathbb E[q_j(Z)]=a_j(S)\), and \(\mathbb E[Z]=\mu\).
This proves the lemma. It requires neither a density nor positive variance.
Partition the PS process into stages during which the available set is constant. There are at most \(k\) stages, because each stage ends by exhausting at least one class.
Let stage \(\ell\) have available set \(S_\ell\) and duration \(\Delta_\ell\). Throughout that stage, the consumption rate of random class \(j\) is \(a_j(S_\ell)\), and its welfare rate is \(b_j(S_\ell)\). These expectations use the original product law, since every type continues eating throughout the process.
Take both rates to be zero when \(j\notin S_\ell\). Since class \(j\) is exhausted and has supply \(1/k\),
\(\displaystyle \sum_\ell\Delta_\ell a_j(S_\ell)=\frac1k.\)
The selection lemma therefore implies that its total welfare contribution satisfies
\(\displaystyle \sum_\ell\Delta_\ell b_j(S_\ell)\ge \mu\sum_\ell\Delta_\ell a_j(S_\ell)=\frac{\mu}{k}.\)
Class \(1\) contributes exactly \(1/k\), because its value is always one and its entire supply is consumed. Class \(2\) contributes zero. Summing over the \(k-2\) random classes gives
\(\displaystyle W_{\mathrm{RP}}=W_{\mathrm{PS}}\ge\frac1k+\frac{(k-2)\mu}{k}=\frac{1+(k-2)\mu}{k}.\)
For any feasible allocation, class \(2\) contributes zero, and each other class contributes at most its supply, because all values are at most one. Hence
\(W_{\mathrm{OPT}}\le\dfrac{k-1}{k}.\)
The denominator \(W_{\mathrm{RP}}\) is positive by the established lower bound. Combining the bounds,
\(\displaystyle R_\infty\le\frac{k-1}{1+(k-2)\mu}.\)
Finally, \(0<\mu\le1\), so
\(1+(k-2)\mu-\mu(k-1)=1-\mu\ge0.\)
This proves \(R_\infty\le1/\mu\). Indeed, the stronger bound is strictly below \(1/\mu\) whenever \(\mu<1\). For \(k=2\), both mechanisms have welfare \(1/2\), so \(R_\infty=1\).
The continuum assignment can be computed directly from the explicit list of \(\tau\) types. At each stage, scan the rankings to find each type’s preferred available class, sum its mass into that class’s consumption rate, and advance to the next exhaustion.
With \(m=k\), this uses \(O(m^2\tau)\) rational arithmetic operations. Its bit complexity is polynomial in \(m,\tau,L\): using a common denominator for the input masses, consumption rates have \(O(L)\)-bit representations, and over at most \(m\) stages the residual supplies and stage durations have \(O(mL)\)-bit representations. This computation does not enumerate absent types or replicate agents.
⟨structured verdict parsed — rendered above⟩
The output resolves the product-family question correctly. The selection lemma is valid, its application to Probabilistic Serial preserves the original product distribution, and the cited replica-convergence theorem applies. No major or minor mathematical issues were found.
The argument covers every finite-support distribution specified in the task, including endpoint atoms and point masses. It proves the stronger bound
\(R_\infty\le (k-1)/(1+(k-2)\mu)\), which implies the requested bound for all \(0<\mu\le1\).
The proof uses the exact product law of the society, rather than a sample drawn from that law. This matches the task.
Refining preferences by decreasing value and then increasing class index reproduces the prescribed choices exactly. Ranking-equivalent agents have identical assignment probabilities under Random Priority, even when their cardinal values differ.
The description of admissible integers is correct: integrality of all type counts requires divisibility by every reduced mass denominator, and integrality of class supplies requires divisibility by \(k\). Hence they are precisely the multiples of \(K_0\).
The cited theorem is correctly identified. Che–Kojima’s Theorem 2 gives convergence of Random Priority assignments to continuum PS assignments for a fixed finite set of classes with equal growing quotas and convergent preference-type counts per quota. Here the quota is \(q=K/k\), and the count of any refined ranking divided by \(q\) is constant. Placing the outside option last makes every class acceptable. The paper’s normalization of one unit per class and the output’s normalization of total supply one differ by uniform scaling of supplies and population, which preserves assignment shares. Thus its hypotheses are satisfied. [Che–Kojima, model and Theorem 2](https://www.columbia.edu/~yc2271/files/papers/psrp33-EMA.pdf)
The normalized expected-welfare identity is also correct. There are exactly \(K\rho_t\) agents of type \(t\), so division by \(K\) yields the stated finite sum. Coordinatewise convergence permits passing the limit through that sum. Consequently, \(W_{\mathrm{RP}}=W_{\mathrm{PS}}\).
The output correctly distinguishes PS consumption from sequential removal of agents: every type continues consuming at speed one until time one, so its contribution to consumption rates remains its original mass.
While any class remains available, all agents have an acceptable choice and aggregate consumption speed is one. Total supply is one, so the process finishes at time one and consumes every class completely. This justifies the later class-by-class supply identities.
For fixed available set \(S\) and fixed other coordinates, increasing \(Z_j\) cannot turn a choice of class \(j\) into a choice of another class. The fixed tie-breaking order preserves this monotonicity, including at endpoint values and ties.
Independence is used in the correct place: conditioning on \(Z_j=z\) leaves the distribution of all other coordinates unchanged. Therefore the conditional choice probability \(q_j(z)\) is nondecreasing.
The covariance calculation is correct. Independence and identical distribution of \(Z,Z'\) give
\(\frac12\mathbb E[(Z-Z')(q_j(Z)-q_j(Z'))]=\mathbb E[Zq_j(Z)]-\mathbb E[Z]\mathbb E[q_j(Z)]\).
Its left side is nonnegative by monotonicity. The conditioning identities then establish \(b_j(S)\ge\mu a_j(S)\).
No positive variance or density assumption is needed. In particular, the calculation remains valid for point masses and for classes whose selection probability is zero.
Within a stage, the available set is fixed and each type’s choice is fixed. Since all types continue consuming, the rates are exactly the expectations under the original product law.
The available sets are deterministic features of the continuum process. Applying the lemma to each such set therefore does not condition the population distribution on a random selection event.
Each positive-duration stage exhausts at least one class, so there are at most \(k\) stages. Simultaneous exhaustion only reduces this number. Because random class \(j\) is fully consumed,
\(\sum_\ell\Delta_\ell a_j(S_\ell)=1/k\).
Multiplication of the stagewise lemma by nonnegative durations and summation correctly gives a welfare contribution of at least \(\mu/k\) for each random class.
Class \(1\) contributes exactly \(1/k\), and class \(2\) contributes zero. Thus the claimed lower bound on \(W_{\mathrm{RP}}\) follows.
The upper bound \(W_{\mathrm{OPT}}\le(k-1)/k\) follows directly from the column-supply constraints: class \(2\) has value zero, and each other class has value at most one.
The RP lower bound is positive, so division is legitimate. The final comparison is algebraically correct:
\(1+(k-2)\mu-\mu(k-1)=1-\mu\ge0\).
For \(\mu<1\), the stronger upper bound is strictly below \(1/\mu\). This is a statement about the upper bound, and does not assert equality for the actual ratio.
The stated \(k=2\) case is correct: every allocation has welfare \(1/2\), hence the ratio is one. The proof also handles \(\mu=1\).
The stage algorithm operates on the supplied \(\tau\) types and never requires enumeration of absent valuation vectors or individual replica agents.
Scanning at most \(m\) classes for each type at each of at most \(m\) stages gives the claimed \(O(m^2\tau)\) rational-arithmetic operation bound. Ranking preparation fits within this bound.
The bit-size claim is consistent with the updates described. A common denominator for input masses has \(O(L)\) bits, and every consumption rate is a subset sum of those masses. Each stage can enlarge a common denominator for residual supplies by a factor with \(O(L)\) bits; over at most \(m\) stages, \(O(mL)\)-bit representations suffice. Zero-rate classes simply cannot be the next exhaustion while their residual supply is positive.
Accordingly, the explicit algorithm establishes polynomial-time computation of the continuum PS assignment. It does not claim a polynomial bound in a succinct product encoding, or a running time independent of the explicitly supplied support size.
No repair or additional clarification is required.
⟨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.