d4-conf-aaai-2015-0421 (d4-conf-aaai-2015-0421)

For a sequence of search instances with fixed τ cohort types \(t_j\), counts \(n_j(N)/N\to\mu_j>0\), type search sets \(A_j^{(N)}\), and common intersection \(D_N=\bigcap_j A_j^{(N)}\), assume \(|D_N|/N\to\infty\) and each \(r_j=\lim_N |A_j^{(N)}|/|D_N|\) exists. Run Mechanism 1 and let \(p_j^{(N)}\) be a type-\(j\) agent's simplified-game win probability. Characterize the limiting type allocation shares \(q_j=\lim_N n_j(N)p_j^{(N)}\) and the limiting expected-total-digs ratio to the simplified-game benchmark; in particular, does \(\limsup_N \mathbb{E}[\#\text{ digs with mechanism}]/\mathbb{E}[\#\text{ digs in benchmark}]\le 1/(2R)\) hold for \(R=\min_j r_j\)?

A society is specified by the support \(t_1,\ldots,t_\tau\) and positive binary-rational masses \(\mu_j\), with \(\sum_j\mu_j=1\); \(\tau\) counts supported types, not possible types.
For each \(N\), there are \(N\) agents on a finite island \(S_N\), with \(n_j(N)\) agents sharing the nonempty search set \(A_j^{(N)}\subseteq S_N\), \(\sum_j n_j(N)=N\), and \(n_j(N)/N\to\mu_j\).
Write \(D_N=\bigcap_j A_j^{(N)}\), \(d_N=|D_N|>0\), and assume \(d_N/N\to\infty\) and \(|A_j^{(N)}|/d_N\to r_j\in[1,\infty)\); put \(R=\min_j r_j\).
In the benchmark, each agent independently chooses a uniform random permutation of her search set; the treasure is independently uniform on \(D_N\). Every agent digs once per period until the first discovery period ends, with simultaneous discoverers tied uniformly. Let \(p_j^{(N)}\) be one type-\(j\) agent's winning probability.
The mechanism independently assigns every location of \(D_N\) to an individual agent with that agent's benchmark winning probability. Agents search only their assignments, one new location per period while any remain, in an arbitrary order chosen without knowledge of the treasure; all digging ends after the discovery period.
Let \(M_N\) and \(B_N\) be the expected total numbers of digs under the mechanism and benchmark, respectively, including every dig in the discovery period. Expectations include treasure and mechanism or benchmark randomness. Any running times should use \(m_N=|S_N|\), \(\tau\), \(N\), and total input bit length \(L_N\).

Do \(q_j=\lim_{N\to\infty}n_j(N)p_j^{(N)}\) and \(\rho=\lim_{N\to\infty}M_N/B_N\) exist for every such sequence and depend only on \((\mu_j,r_j)_{j=1}^{\tau}\)? If so, what are their values and the sharp welfare-ratio guarantee as a function of these data?

For finite societies, the independent-assignment mechanism preserves benchmark winning probabilities and never increases expected total digs. Its verified welfare guarantee already yields \(\limsup_{N\to\infty}M_N/B_N\le 1/(2R)\) in the stated regime ([full version](https://bowaggoner.com/papers/2015/fair-information-sharing-for-treasure-hunting--2015--chen%2Cnissim%2Cwaggoner.pdf)).
No result characterizing these cohort allocation limits and the exact limiting welfare ratio was located in the searches.

Result. Both limits exist and depend only on the stated data. Define
\[ \lambda=\sum_{j=1}^{\tau}\frac{\mu_j}{r_j}. \]
Then
\[ \boxed{q_j=\frac{\mu_j/r_j}{\lambda}}, \qquad \boxed{\rho=\frac{\lambda}{2} =\frac12\sum_{j=1}^{\tau}\frac{\mu_j}{r_j}}. \]
Thus the sharp guarantee using all the data is the exact limiting ratio \(\lambda/2\). In particular,
\[ \rho\leq \frac{1}{2R}, \]
with equality exactly when every \(r_j=R\), since every \(\mu_j\) is positive.

The proof below is self-contained.

1. Benchmark discovery times. Write \(a_{j,N}=|A_j^{(N)}|\) and \(h_N=d_N/N\). By assumption, \(h_N\to\infty\). Since \(n_j(N)/N\to\mu_j>0\), every cohort is nonempty for all sufficiently large \(N\); throughout the limiting argument we restrict to those \(N\).

Conditional on any treasure location \(z\in D_N\), its position in one type-\(j\) agent’s random permutation is uniform on \(\{1,\ldots,a_{j,N}\}\). These positions are independent across agents. Their joint distribution does not depend on \(z\), so they remain independent after averaging over the treasure.

Let \(T_{j,N}\) be the minimum position among type-\(j\) agents, and let \(T_N=\min_jT_{j,N}\) be the benchmark discovery period. Put \(\alpha_j=\mu_j/r_j\), so \(\lambda=\sum_j\alpha_j>0\).

For each fixed \(x\geq0\), eventually \(\lfloor h_Nx\rfloor<a_{j,N}\), and
\[ \Pr(T_{j,N}/h_N>x) =\left(1-\frac{\lfloor h_Nx\rfloor}{a_{j,N}}\right)^{n_j(N)}. \]
Indeed, \(a_{j,N}/h_N=N(a_{j,N}/d_N)\to\infty\). Moreover,
\[ n_j(N)\frac{\lfloor h_Nx\rfloor}{a_{j,N}}\longrightarrow\alpha_jx, \qquad n_j(N)\left(\frac{\lfloor h_Nx\rfloor}{a_{j,N}}\right)^2\longrightarrow0. \]
The first convergence follows from \(n_j(N)/N\to\mu_j\) and \(a_{j,N}/d_N\to r_j\); the second follows because the fraction is \(O(1/N)\) and \(n_j(N)\leq N\). Applying \(\log(1-u)=-u+O(u^2)\) therefore gives
\[ \Pr(T_{j,N}/h_N>x)\longrightarrow e^{-\alpha_jx}. \]

Different cohorts use disjoint collections of independent permutations, so their minima are independent. Consequently,
\[ (T_{1,N}/h_N,\ldots,T_{\tau,N}/h_N) \ \xrightarrow{\mathrm d}\ (X_1,\ldots,X_\tau), \]
where the \(X_j\) are independent exponential random variables with rates \(\alpha_j\). This joint convergence follows from the product of the marginal distribution functions, whose limiting product is continuous.

2. Cohort winning probabilities. By symmetry among agents of the same type,
\[ Q_{j,N}:=n_j(N)p_j^{(N)} \]
is exactly the probability that the selected winner belongs to cohort \(j\).

If \(T_{j,N}<T_{k,N}\) for all \(k\ne j\), cohort \(j\) certainly wins. Conversely, cohort \(j\) can win only if \(T_{j,N}\leq T_{k,N}\) for all \(k\ne j\). Thus
\[ \Pr(T_{j,N}<T_{k,N}\text{ for every }k\ne j) \leq Q_{j,N} \leq \Pr(T_{j,N}\leq T_{k,N}\text{ for every }k\ne j). \]
Both comparison events have boundaries contained in coordinate-equality hyperplanes. The limiting independent exponential variables have zero probability on these hyperplanes. The joint convergence established above therefore makes both bounds converge to the same value:
\[ \Pr(X_j<X_k\text{ for every }k\ne j) =\int_0^\infty \alpha_j e^{-\alpha_jx} \prod_{k\ne j}e^{-\alpha_kx}\,dx =\frac{\alpha_j}{\lambda}. \]
The sandwich proves \(q_j=\alpha_j/\lambda\), including the effect of simultaneous discoveries. For \(\tau=1\), the comparison conditions are vacuous and the same conclusion holds.

This also describes actual cohort allocation shares. If \(C_{j,N}\) counts locations assigned to cohort \(j\), independent assignment gives
\[ C_{j,N}\sim\operatorname{Binomial}(d_N,Q_{j,N}). \]
Hence \(\mathbb E[C_{j,N}/d_N]=Q_{j,N}\) and \(\operatorname{Var}(C_{j,N}/d_N)\leq1/(4d_N)\), so \(C_{j,N}/d_N\to q_j\) in probability.

3. Expected benchmark digs. Every agent can dig through period \(T_N\): the treasure belongs to every search set, and \(T_N\leq\min_j a_{j,N}\). Counting all digs in the discovery period therefore gives
\[ B_N=N\,\mathbb E[T_N]. \]

We must justify convergence of the expectation, not merely convergence in distribution. Define
\[ H_N=\sum_j\frac{n_j(N)}{a_{j,N}}. \]
Then
\[ h_NH_N =\sum_j\frac{n_j(N)/N}{a_{j,N}/d_N} \longrightarrow\lambda. \]
For integers \(0\leq t\leq\min_j a_{j,N}\), independence gives
\[ \Pr(T_N>t)=\prod_j(1-t/a_{j,N})^{n_j(N)} \leq e^{-H_Nt}. \]
For larger \(t\), the probability is zero, so the inequality remains valid.

Consequently, for every \(x\geq0\),
\[ \Pr(T_N/h_N>x) \leq e^{H_N}e^{-(h_NH_N)x}. \]
Because \(H_N\to0\) and \(h_NH_N\to\lambda>0\), this is eventually bounded by the integrable function \(e\,e^{-\lambda x/2}\). The pointwise limit of the tail probability is \(e^{-\lambda x}\), by the independent exponential limits. Dominated convergence applied to the tail integral now yields
\[ \frac{\mathbb E[T_N]}{h_N} =\int_0^\infty\Pr(T_N/h_N>x)\,dx \longrightarrow\frac1\lambda. \]
Therefore
\[ \boxed{\frac{B_N}{d_N}\longrightarrow\frac1\lambda}. \]

4. An exact mechanism-cost identity. Fix \(N\), and condition on a realized assignment and its treasure-independent search orders. Write \(d=d_N\), and let \(K_i\) be the number of locations assigned to individual agent \(i\), so \(\sum_iK_i=d\).

The treasure remains uniform among these \(d\) locations. If it has rank \(k\) in agent \(i\)’s assignment, discovery occurs in period \(k\), and agent \(\ell\) makes exactly \(\min(K_\ell,k)\) digs. This counts every dig made during that period. Thus the conditional expected total is
\[ \frac1d\sum_{i=1}^N\sum_{k=1}^{K_i} \sum_{\ell=1}^N\min(K_\ell,k). \]

For nonnegative integers \(a,b\), define \(F(a,b)=\sum_{k=1}^a\min(b,k)\). If \(a\geq b\), direct summation gives
\[ F(a,b)=ab-\frac{b(b-1)}2, \qquad F(b,a)=\frac{b(b+1)}2. \]
Interchanging \(a,b\) handles the other case, proving
\[ F(a,b)+F(b,a)=ab+\min(a,b). \]
Symmetrizing the conditional expectation therefore gives the exact identity
\[ \mathbb E[\text{total mechanism digs}\mid\text{assignment and orders}] =\frac d2+\frac1{2d}\sum_{i,\ell=1}^N\min(K_i,K_\ell). \]

The diagonal terms sum to \(d\), while
\[ \sum_{i,\ell}\min(K_i,K_\ell) \leq\sum_{i,\ell}K_i=Nd. \]
Averaging over assignments and orders yields
\[ \frac{d_N+1}{2}\leq M_N\leq\frac{d_N+N}{2}. \]
Since \(N/d_N\to0\),
\[ \boxed{\frac{M_N}{d_N}\longrightarrow\frac12}. \]
This conclusion holds for any treasure-independent partition into \(N\) assignments; its leading term does not require assumptions about assignment-size concentration.

For the specified mechanism, winning probabilities are preserved exactly: the only agent who can discover a location is its owner, and each possible treasure location is assigned to individual agent \(i\) with probability \(p_i^{(N)}\).

5. Ratio and sharpness. Combining the two cost limits gives
\[ \frac{M_N}{B_N} =\frac{M_N/d_N}{B_N/d_N} \longrightarrow\frac{\lambda}{2}. \]
Because \(r_j\geq R\) and \(\sum_j\mu_j=1\),
\[ \lambda=\sum_j\frac{\mu_j}{r_j}\leq\frac1R. \]
Positivity of every \(\mu_j\) makes equality equivalent to \(r_j=R\) for every \(j\).

The bound based only on \(R\) is attainable. For any fixed \(\tau\geq2\), take a common set \(D_N\) of size \(N^2\) and pairwise disjoint additional sets \(E_{j,N}\), disjoint from \(D_N\), each of size \(\lfloor(R-1)N^2\rfloor+1\). Set \(A_j^{(N)}=D_N\cup E_{j,N}\), and choose integer cohort counts whose fractions converge to the prescribed masses. Then the intersection is exactly \(D_N\), all size ratios converge to \(R\), and the proved formula gives \(\rho=1/(2R)\). When \(\tau=1\), necessarily \(D_N=A_1^{(N)}\), so \(R=r_1=1\), and again equality holds.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct and resolves the requested limits and sharp welfare guarantee. I found no major or minor mathematical issues.

1. Assumptions and benchmark discovery times

The proof correctly restricts the limiting argument to sufficiently large \(N\), when every cohort is nonempty because \(n_j(N)/N\to\mu_j>0\).

The definitions \(h_N=d_N/N\) and \(\alpha_j=\mu_j/r_j\) satisfy \(h_N\to\infty\) and \(\alpha_j>0\). In particular, \(\lambda=\sum_j\alpha_j\) is finite and strictly positive.

Conditional on any treasure location in \(D_N\), its permutation positions are independent and uniform on the respective search sets. The conditional joint distribution is identical for every treasure location, so averaging over the treasure preserves independence. This justification is essential and is supplied correctly.

The survival formula
\[ \Pr(T_{j,N}/h_N>x) =\left(1-\frac{\lfloor h_Nx\rfloor}{a_{j,N}}\right)^{n_j(N)} \]
has the correct integer rounding, including \(x=0\). For every fixed finite \(x\), its stated range condition eventually holds because \(a_{j,N}/h_N=N(a_{j,N}/d_N)\to\infty\).

Both estimates needed for the logarithmic expansion are correct:
\[ n_j(N)\frac{\lfloor h_Nx\rfloor}{a_{j,N}}\to\alpha_jx, \qquad n_j(N)\left(\frac{\lfloor h_Nx\rfloor}{a_{j,N}}\right)^2\to0. \]
Thus the exponential marginal limits follow. Independence across cohorts and continuity of the limiting joint distribution justify the asserted joint convergence.

2. Cohort winning probabilities and allocation shares

Within-cohort symmetry correctly identifies \(Q_{j,N}=n_j(N)p_j^{(N)}\) as the probability that cohort \(j\) supplies the selected winner.

The strict-minimum and weak-minimum bounds are valid regardless of how many simultaneous discoverers belong to a cohort. Their event boundaries lie in coordinate-equality hyperplanes, which have zero probability under the independent continuous limiting distributions. The standard continuity-set consequence of convergence in distribution therefore applies with its hypotheses verified.

The integral for the limiting strict-minimum probability evaluates correctly to \(\alpha_j/\lambda\). Consequently,
\[ q_j=\frac{\mu_j/r_j}{\sum_k\mu_k/r_k}. \]
The proof explicitly handles the vacuous comparisons when \(\tau=1\).

The additional allocation-share assertion is also valid: independent location assignments make \(C_{j,N}\) binomial with parameters \(d_N\) and \(Q_{j,N}\). The stated variance bound tends to zero because \(d_N\to\infty\), establishing the claimed convergence in probability.

3. Expected benchmark digs

The identity \(B_N=N\mathbb E[T_N]\) is justified. For the sufficiently large \(N\) under consideration, every search set has an agent, and discovery occurs no later than the size of the smallest search set. Hence every agent makes a dig in every period through discovery, including the discovery period.

The calculation \(h_NH_N\to\lambda\) is correct. Since \(h_N\to\infty\), it also implies \(H_N\to0\).

The survival bound uses independence and \(1-u\leq e^{-u}\) within the stated range. Beyond the smallest search-set size, the survival probability is zero. Applying the bound at \(\lfloor h_Nx\rfloor\) gives the displayed factor \(e^{H_N}\) correctly.

The eventual dominating function \(e\,e^{-\lambda x/2}\) is integrable on the nonnegative real line. The pointwise survival limit is \(e^{-\lambda x}\), so dominated convergence legitimately applies to the tail-integral representation of expectation. This establishes
\[ \frac{B_N}{d_N}\to\frac1\lambda. \]
There is no unsupported interchange of a limit and expectation.

4. Exact mechanism-cost identity

Conditioning on assignments and treasure-independent search orders leaves the treasure uniform on the \(d_N\) assigned locations. If its assigned rank is \(k\), each agent \(\ell\) makes exactly \(\min(K_\ell,k)\) digs. The conditional expectation therefore correctly includes all discovery-period digs.

The arithmetic identities for \(F(a,b)\) are correct, including zero assignment sizes:
\[ F(a,b)+F(b,a)=ab+\min(a,b). \]
Symmetrizing the double sum consequently gives exactly
\[ \frac d2+\frac1{2d}\sum_{i,\ell}\min(K_i,K_\ell). \]
Both bounds on the remaining sum are valid: its diagonal contributes \(d\), and its full value is at most \(Nd\). Thus
\[ \frac{d_N+1}{2}\leq M_N\leq\frac{d_N+N}{2}. \]
Since \(N/d_N\to0\), these bounds prove \(M_N/d_N\to1/2\).

The exact preservation of individual winning probabilities is also correctly explained: each treasure location has one owner, and that owner eventually discovers it. Averaging its ownership probability gives the benchmark probability.

5. Ratio, equality, and sharpness

The denominator limit \(1/\lambda\) is strictly positive, so division of the two cost limits is justified:
\[ \rho=\frac{\lambda}{2} =\frac12\sum_j\frac{\mu_j}{r_j}. \]
This establishes existence and dependence only on the prescribed data.

The bound \(\lambda\leq1/R\) follows from \(r_j\geq R\). Because all masses are positive, equality holds exactly when every \(r_j=R\).

The sharpness construction satisfies the required assumptions. For \(\tau\geq2\), the disjoint additional sets ensure that the intersection is exactly \(D_N\), while their stated sizes give search-set ratios tending to \(R\), including when \(R=1\). The choice \(d_N=N^2\) ensures \(d_N/N\to\infty\). The separate treatment of \(\tau=1\) correctly recognizes that only \(R=r_1=1\) is feasible.

No running-time claim is made, so the task’s requirements for expressing running times do not create an omission.

Feedback

No repair or additional clarification is needed. The proof establishes the exact asymptotic welfare ratio; it does not make a computational-complexity classification.

⟨structured verdict parsed — rendered above⟩