Answer: \(R_m=\frac{2}{m+1}\) for every \(m\ge2\).
Theorem 7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor ARP with m different goods, the worst- case efficiency ratio is 2 m+1 for single-minded bidders.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix \(m\) and let \(\mu\) range over rational distributions on a finite catalogue of single-minded types \(t=(S_t,v_t)\). For finite bid profiles \(P_N\) whose empirical type distributions converge to \(\mu\), evaluate ARP and the Pareto optimum using the paper’s convention that demands for bundles of size at least two are treated as bids for all goods; retain exact finite-alias deviations when testing false-name-proofness at each \(N\). What is \(\inf_{\mu,(P_N)}\liminf_{N\to\infty}s_{\mathrm{ARP}}(P_N)/s^*(P_N)\), and is it \(2/(m+1)\)?
Fix \(m\ge2\) indivisible goods \(M\) and a finite catalogue \(T\) of \(K\) single-minded types \(t=(S_t,v_t)\), where \(\varnothing\ne S_t\subseteq M\) and \(v_t\in\mathbb Q_{\ge0}\); utility is quasi-linear, with value \(v_t\) exactly when the allocated bundle contains \(S_t\).
A society \(\mu\) is given by its support: the list of its \(\tau\) positive-mass types with binary-rational masses summing to \(1\); \(\tau\) is the support size, not the number of possible types. Catalogue types outside the support may occur with vanishing frequency. Running times use \(m,\tau,K,L,N\), where \(L\) is the total input bit length.
Let \(P_N\in T^N\) be truthful finite profiles whose empirical frequencies converge coordinatewise to \(\mu\). The catalogue and its values stay fixed along each sequence; goods are neither replicated nor divided. Write \(D_t=S_t\) for singleton demands and \(D_t=M\) otherwise.
ARP treats each report as a bid for \(D_t\). For bidder \(i\), let \(A\) be the highest other grand-bundle bid and \(b_1\ge\cdots\ge b_m\) the highest other singleton bids, ordered by good; missing bids equal \(0\), and equal bids are ordered by a fixed ordering of goods.
The offered grand-bundle price is \(p_i(M)=\max\{A,b_1,2b_2\}\). The first-ranked singleton price is \(\max\{b_1,A/2\}\) if \(A<2b_2\), and \(\max\{b_1,A\}\) otherwise.
Every other singleton price is \(\max\{b_2,A/2\}\) if \(A<2b_1\), and \(\max\{b_1,A\}\) otherwise. Each report receives its effective demand or nothing, maximizing reported value minus its offered price; winners pay that price and losers pay \(0\).
Choose a feasible collection of these maximizing choices with at most two winners, choosing two whenever possible, then one whenever possible; resolve remaining ties by a fixed lexicographic ordering of goods and identifiers.
For the stipulated welfare benchmark, use effective demands in both quantities: \(s_{\mathrm{ARP}}(P_N)\) is the sum of winning values and \(s^*(P_N)=\max\{\sum_{i\in W}v_i:D_i\cap D_j=\varnothing\text{ for distinct }i,j\in W\}\). Require \(s^*(P_N)>0\).
False-name-proofness is tested exactly at each finite profile: replace one bidder's report by any finite collection of single-minded reports, unrestricted by \(T\); compare truthful utility with value for the union of all goods won by those identifiers minus all their payments, using the bidder's original \(S_t\), without withdrawal.
What is \(R_m=\inf_{T,\mu,(P_N)}\liminf_{N\to\infty}s_{\mathrm{ARP}}(P_N)/s^*(P_N)\)? Is \(R_m=2/(m+1)\), or does it differ?
For finite single-minded profiles, ARP is false-name-proof and has exact worst-case welfare ratio \(2/(m+1)\), including the grand-bundle/singleton restriction above. [Verified finite results](https://www.cs.cmu.edu/~conitzer/worstcasefnpAAMAS10.pdf).
No result settling this precise catalogue-convergent asymptotic ratio was located.
\[ R_m=\frac{2}{m+1}. \]
This holds even if every catalogue type has positive mass and every value is strictly positive. The construction below keeps the catalogue fixed along each sequence.
Use the finite-profile guarantee stipulated in the question: for every finite single-minded profile \(P\) with \(s^*(P)>0\), under the specified effective-demand benchmark and allocation rule,
\[
s_{\mathrm{ARP}}(P)\ge \frac{2}{m+1}s^*(P).
\]
This is the supplied finite ARP result; its grand-bundle/singleton restriction and preference for two feasible winners match the present mechanism. [Iwasaki et al., Section 5](https://www.cs.cmu.edu/~conitzer/worstcasefnpAAMAS10.pdf).
Every profile in every admissible sequence satisfies these hypotheses. Therefore,
\[
\liminf_{N\to\infty}
\frac{s_{\mathrm{ARP}}(P_N)}{s^*(P_N)}
\ge \frac{2}{m+1}.
\]
Taking the infimum over catalogues, societies, and sequences gives
\[
R_m\ge \frac{2}{m+1}.
\]
Label the goods \(M=\{g_1,\ldots,g_m\}\). Fix a rational number \(0<\varepsilon<1/2\). Define a catalogue of \(K=m+1\) types:
\[
t_0=(M,2),\qquad
t_1=(\{g_1\},2-\varepsilon),\qquad
t_j=(\{g_j\},1-\varepsilon)\quad(2\le j\le m).
\]
Every value is strictly positive. Moreover, each original demand already equals its effective demand.
Choose a power of two \(Q>m\), and define
\[
\mu(t_0)=\frac{Q-m}{Q},
\qquad
\mu(t_j)=\frac1Q\quad(1\le j\le m).
\]
These are positive binary-rational masses summing to \(1\), so the support size is \(\tau=K=m+1\).
For each \(N\ge1\), let \(P_N\) contain
\[
n_j(N)=\left\lfloor\frac NQ\right\rfloor
\quad(1\le j\le m),
\qquad
n_0(N)=N-m\left\lfloor\frac NQ\right\rfloor
\]
copies of the respective types. Their counts sum to \(N\), and
\[
\frac{n_j(N)}N\longrightarrow\frac1Q,
\qquad
\frac{n_0(N)}N\longrightarrow\frac{Q-m}{Q}.
\]
Thus the empirical frequencies converge coordinatewise to \(\mu\).
Since \(Q>m\), there is at least one grand-bundle bidder for every \(N\); consequently \(s^*(P_N)\ge2>0\). For \(N\ge2Q\), every type has at least two copies.
Fix \(N\ge2Q\). Removing any one bidder leaves at least one copy of every catalogue type. Hence every bidder faces the same highest other bids:
\[
A=2,\qquad b_1=2-\varepsilon,\qquad
b_2=\cdots=b_m=1-\varepsilon.
\]
The first-ranked good is uniquely \(g_1\).
Grand-bundle bidders. Their offered price is
\[
p_i(M)=\max\{2,2-\varepsilon,2-2\varepsilon\}=2.
\]
Thus each grand-bundle bidder is indifferent between winning and receiving nothing: both choices give utility \(0\).
Bidders for \(g_1\). Because
\[
A=2>2(1-\varepsilon)=2b_2,
\]
the first-ranked singleton price is
\[
p_i(\{g_1\})=\max\{2-\varepsilon,2\}=2.
\]
Winning would give utility \(-\varepsilon<0\), so these bidders must lose.
Bidders for \(g_j\), where \(j\ge2\). Because \(\varepsilon<1/2\),
\[
A=2<2(2-\varepsilon)=2b_1.
\]
Their offered singleton price is therefore
\[
p_i(\{g_j\})=\max\{1-\varepsilon,1\}=1.
\]
Again, winning would give utility \(-\varepsilon<0\), so these bidders must lose.
Only grand-bundle bidders can win while making maximizing choices. Two such winners are infeasible, whereas one is feasible. The stipulated rule therefore chooses exactly one grand-bundle winner, independently of the remaining lexicographic tie-breaking. Consequently,
\[
s_{\mathrm{ARP}}(P_N)=2
\qquad(N\ge2Q).
\]
A feasible allocation containing a grand-bundle bidder has welfare at most \(2\). An allocation containing only singleton bidders can take one bidder for each good, achieving
\[
(2-\varepsilon)+(m-1)(1-\varepsilon)
=m+1-m\varepsilon.
\]
No singleton allocation has greater welfare, since each good can be allocated to at most one bidder.
Furthermore,
\[
m+1-m\varepsilon-2
=m-1-m\varepsilon
>m-1-\frac m2
=\frac{m-2}{2}\ge0.
\]
Thus the singleton allocation strictly dominates the grand-bundle allocation, including when \(m=2\). Therefore,
\[
s^*(P_N)=m+1-m\varepsilon
\qquad(N\ge2Q).
\]
The welfare ratio is eventually constant, giving
\[
\liminf_{N\to\infty}
\frac{s_{\mathrm{ARP}}(P_N)}{s^*(P_N)}
=\frac{2}{m+1-m\varepsilon}.
\]
For every fixed rational \(\varepsilon\in(0,1/2)\), this is an admissible sequence with fixed catalogue and values. Hence
\[
R_m\le \frac{2}{m+1-m\varepsilon}.
\]
Taking \(\varepsilon\downarrow0\) through rational values yields
\[
R_m\le\frac{2}{m+1}.
\]
Here \(\varepsilon\) varies between catalogues in the outer infimum, never along an individual profile sequence. Combining this bound with Section 1 proves the claimed equality.
The stipulated finite false-name-proofness theorem applies at every \(P_N\), rather than merely in the limit. For the constructed profiles with \(N\ge2Q\), this can also be checked directly.
Every truthful bidder has utility \(0\). After replacing one bidder by arbitrary finitely many reports, an external grand-bundle bid of \(2\) remains. Thus every winning grand-bundle identifier pays at least \(2\), and every winning singleton identifier pays at least \(1\), directly from the price formulas.
For an original grand-bundle bidder, obtaining all goods requires either a grand-bundle winner or at least two singleton winners. Either possibility costs at least \(2\), its original value.
For an original singleton bidder of value \(v\), an external bid of \(v\) for its desired good remains. Any identifier winning that good as a singleton pays at least \(v\): the first-ranked price is at least \(b_1\), and every other singleton price is at least \(b_2\), which bounds that good’s other bid. Obtaining it through a grand-bundle winner costs at least \(2>v\).
All payments are nonnegative. Hence no such deviation has positive utility, regardless of the values or demands of the false-name reports.
⟨structured verdict parsed — rendered above⟩
The prover establishes \(R_m=2/(m+1)\) for every \(m\ge2\). The construction satisfies the catalogue and convergence requirements, the ARP prices are calculated correctly, and the passage to the outer infimum is valid. No major or minor mathematical issues were found.
The stronger claim—that the same infimum remains attainable arbitrarily closely using full-support societies and strictly positive values—is also established.
The prover states precisely the finite guarantee it uses: every admissible finite profile with positive benchmark welfare satisfies
\(s_{\mathrm{ARP}}(P)\ge [2/(m+1)]s^*(P)\).
This is expressly stipulated in USER_TASK, including the effective-demand benchmark. Consequently, the prover may use it without reproving the finite result. The cited paper’s Section 5 also uses the stated price formulas, converts nonsingleton demands into grand-bundle bids, and prefers two feasible winners. [Iwasaki et al., Section 5](https://www.cs.cmu.edu/~conitzer/worstcasefnpAAMAS10.pdf).
The hypotheses hold at every index of every admissible sequence: profiles are finite and single-minded, and benchmark welfare is required to be positive. Dividing by that positive benchmark, taking the lower limit, and then taking the infimum preserve the lower bound. Thus \(R_m\ge2/(m+1)\) follows.
The construction meets every relevant restriction:
The catalogue and its values remain fixed throughout each individual sequence.
The counts are nonnegative integers and sum exactly to \(N\). The asserted coordinatewise limits follow from \(\lfloor N/Q\rfloor/N\to1/Q\).
There is a grand-bundle bidder at every index: since \(Q>m\),
\(N-m\lfloor N/Q\rfloor\ge N(1-m/Q)>0\).
Because this count is an integer, it is at least one. Hence \(s^*(P_N)\ge2>0\), including the initial profiles.
The replication threshold is also correct. For \(N\ge2Q\), each singleton count is at least two, and the grand-bundle count is at least \(2(Q-m)\ge2\). Removing any one bidder therefore leaves every catalogue type represented.
After that threshold, every bidder faces the stated other-bid maxima:
\(A=2\), \(b_1=2-\varepsilon\), and \(b_2=\cdots=b_m=1-\varepsilon\).
The first-ranked good is uniquely \(g_1\), so ties among the remaining goods do not affect the calculations.
Each price branch is selected correctly:
Thus grand-bundle bidders are indifferent between winning and losing, whereas every singleton bidder strictly prefers losing.
Exactly one grand-bundle winner is feasible; two are infeasible. The prescribed preference for one winner whenever possible therefore yields welfare exactly \(2\). Lexicographic tie-breaking only determines the winner’s identity.
Any allocation containing a grand-bundle bidder has welfare at most \(2\). An allocation consisting of singleton bidders has maximum welfare
\(m+1-m\varepsilon\), because every good has a represented singleton type and at most one bidder can receive each good.
The comparison is correct:
\(m-1-m\varepsilon>(m-2)/2\ge0\).
In particular, for \(m=2\), the strict inequality remains valid because \(\varepsilon<1/2\).
Therefore the claimed benchmark and eventually constant ratio,
\(s^*(P_N)=m+1-m\varepsilon\) and
\(s_{\mathrm{ARP}}(P_N)/s^*(P_N)=2/(m+1-m\varepsilon)\),
are correct. Initial profiles cannot change the lower limit.
For each fixed admissible rational \(\varepsilon\), the construction supplies a separate admissible catalogue, society, and sequence. Accordingly,
\(R_m\le2/(m+1-m\varepsilon)\).
Letting these rational parameters approach zero gives the claimed upper bound. The prover explicitly distinguishes variation between catalogues from variation within a sequence. This resolves the central quantifier concern.
The argument establishes an infimum; it does not need a single constructed catalogue attaining equality.
The supplementary direct verification is valid for its stated range \(N\ge2Q\).
After replacing one original bidder, an external grand-bundle bid of \(2\) remains. Every winning grand-bundle identifier therefore pays at least \(2\). Every singleton price is at least \(A/2\ge1\), whichever branch applies.
For an original grand-bundle bidder, acquiring all goods consequently costs at least its value: either one grand-bundle payment suffices, or acquiring the goods through singleton identifiers requires at least two payments.
For an original singleton bidder, an external bid equal to its original value remains on its desired good. If that good ranks first, its price is at least \(b_1\); otherwise its price is at least \(b_2\), which is at least the other bid on that good. Acquisition through a grand-bundle identifier costs strictly more than its original value.
These bounds cover arbitrary finite false-name collections. Nonnegative payments also cover deviations whose union fails to satisfy the original demand. Thus no deviation produces positive utility, while truthful utility is zero.
For the initial profiles, the prover invokes the finite false-name-proofness result stipulated in the task. The supplementary argument does not claim to cover those indices.
None. No additional mathematical clarification is needed to verify the claimed equality.
The output establishes a welfare-ratio result, without asserting a computational complexity classification; the JSON records that distinction.
⟨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.