Answer: \(\alpha=2/3\), guaranteed by an algorithm polynomial in \(m,\tau,L\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet (n1, n2) = (2, 1), and suppose that α is the best possible ap- proximation ratio for the maximin share. Then 2/3 ≤α ≤3/4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given indivisible goods \(G\), two groups, a distribution \(\mu\) over exactly two complete additive-utility types in group \(1\) and one type in group \(2\), and rational positive masses, define \(M_\theta=\max_{G=B_1\dot\cup B_2}\min\{u_\theta(B_1),u_\theta(B_2)\}\). Compute or approximate the maximum \(\lambda(\mu)=\max_{G_1\dot\cup G_2=G}\min_{\mu_{i,\theta}>0}u_\theta(G_i)/M_\theta\), in particular deciding whether \(\lambda(\mu)\ge 2/3\).
Let \(G\) consist of \(m\) indivisible goods. There are two groups: group \(1\) has exactly two additive utility types and group \(2\) exactly one. Each type specifies a nonnegative binary-rational value for every good; assume its two-bundle maximin share is positive.
A society is given by its support: the list of the \(\tau\) group–type pairs with positive mass, each mass a binary rational, with masses summing to \(1\). Here \(\tau=3\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
An allocation is a complete partition \(G=G_1\dot\cup G_2\); every member of group \(i\) evaluates the entire bundle \(G_i\). Goods and group bundles cannot be divided among types.
For each supported type \(\theta\), define \(M_\theta=\max_{G=B_1\dot\cup B_2}\min\{u_\theta(B_1),u_\theta(B_2)\}\), and define \(\lambda(\mu)=\max_{G=G_1\dot\cup G_2}\min_{(i,\theta)\in\operatorname{supp}(\mu)}u_\theta(G_i)/M_\theta\).
What is the sharp universal maximin-share approximation factor \(\alpha\) such that every such society admits an allocation with \(u_\theta(G_i)\ge\alpha M_\theta\) for every supported \((i,\theta)\), and can that factor be guaranteed by an algorithm polynomial in \(m,\tau,L\)?
For discrete groups of sizes \((2,1)\), a polynomial-time algorithm guarantees \(2/3\), while some instances admit no factor exceeding \(3/4\). [Source](https://arxiv.org/pdf/1706.09869)
These bounds also apply to the stated mass model: its objective depends only on the three supported group–type pairs. In particular, deciding whether \(\lambda(\mu)\ge2/3\) is already settled affirmatively.
The sharp universal factor is \(\alpha=2/3\), and it can be guaranteed in time polynomial in \(m,\tau,L\).
The following four-good instance improves the stated upper bound from \(3/4\) to \(2/3\).
Let \(G=\{g_1,g_2,g_3,g_4\}\), with valuations
| Supported type | \(g_1\) | \(g_2\) | \(g_3\) | \(g_4\) | Mass |
|---|---:|---:|---:|---:|---:|
| Group \(1\), type \(a\) | \(3\) | \(1\) | \(1\) | \(1\) | \(1/4\) |
| Group \(1\), type \(b\) | \(1\) | \(3\) | \(1\) | \(1\) | \(1/4\) |
| Group \(2\), type \(c\) | \(2\) | \(2\) | \(1\) | \(1\) | \(1/2\) |
All values and masses are nonnegative binary rationals, all three masses are positive, and they sum to \(1\).
Maximin shares. Each type values the whole set at \(6\), so its two-bundle maximin share is at most \(3\). The following partitions give both bundles value \(3\) to the indicated type:
Consequently, \(M_a=M_b=M_c=3\).
Impossibility above \(2/3\). Write \(S=G_1\), so \(G_2=G\setminus S\). We prove that some supported type receives utility at most \(2\).
If \(u_a(S)\le 2\) or \(u_b(S)\le 2\), this already holds. Otherwise, both utilities exceed \(2\). There are three exhaustive cases:
Since every maximin share equals \(3\), no allocation achieves a factor exceeding \(2/3\). Conversely, \(G_1=\{g_1,g_2\}\), \(G_2=\{g_3,g_4\}\) gives utilities \((4,4,2)\), so this instance has \(\lambda(\mu)=2/3\).
The given discrete theorem guarantees a \(2/3\)-MMS allocation for nonnegative additive valuations with group sizes \((2,1)\). Its maximin shares use two bundles, exactly as here. Representing each supported pair by one agent therefore preserves every constraint and the objective; positive masses impose no additional conditions. [Suksompong, Theorem 1](https://arxiv.org/pdf/1706.09869).
The cited algorithm normalizes utilities by their totals, handles goods worth at least \(1/3\), and then uses greedy round robin. It requires no exact maximin-share computation. A scanning implementation uses \(O(\tau m^2)\) comparisons and rational arithmetic operations. Totals and normalized values have bit length polynomial in \(L\), so these operations take polynomial bit time.
Thus the universal guarantee and the counterexample match: \(\alpha=2/3\), with a polynomial-time algorithm attaining it.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned question correctly. The counterexample establishes the sharp upper bound, and the cited theorem supplies the matching universal guarantee and polynomial-time algorithm. No major or minor mathematical issues were found.
The instance has exactly two supported types in group \(1\) and one in group \(2\). All valuations are positive integers, hence valid nonnegative binary rationals.
The masses \(1/4,1/4,1/2\) are positive binary rationals summing to \(1\). Thus the support size is exactly \(\tau=3\).
The subsequent maximin-share calculation establishes that every supported type has positive maximin share, as required.
The utility totals are correctly calculated:
\[ u_a(G)=u_b(G)=u_c(G)=6. \]
For every two-bundle partition, the smaller bundle value is at most half the total. Therefore each maximin share is at most \(3\).
All three displayed partitions attain this bound:
Consequently, the conclusion \(M_a=M_b=M_c=3\) is correct.
The proof correctly considers an arbitrary complete allocation by writing \(S=G_1\) and \(G_2=G\setminus S\).
If either \(u_a(S)\le 2\) or \(u_b(S)\le 2\), a supported type already receives at most \(2\). Otherwise, the three listed cases are exhaustive:
Hence every allocation gives some supported type utility at most \(2\), establishing \(\lambda(\mu)\le 2/3\).
The displayed allocation has utilities \((4,4,2)\), so its minimum normalized utility is exactly \(2/3\). Therefore the claim \(\lambda(\mu)=2/3\) for this instance is fully verified.
The cited theorem applies to two groups containing respectively two agents and one agent, with nonnegative additive valuations and maximin shares defined using two bundles. It establishes a universal \(2/3\) guarantee through a constructive algorithm. These are precisely the relevant hypotheses here. [Suksompong, Theorem 1 and its proof](https://arxiv.org/pdf/1706.09869)
Representing each supported group–type pair by one agent preserves the allocation constraints: the two representatives in group \(1\) evaluate the same group bundle, and the representative in group \(2\) evaluates its complement. Their maximin shares also remain unchanged.
The masses do not enter any utility constraint or the minimum defining \(\lambda(\mu)\). Their magnitudes therefore introduce no discrepancy in this reduction.
The algorithm description agrees with the cited construction: total-value normalization, handling goods meeting the normalized \(1/3\) threshold, and greedy round robin. It does not require exact maximin-share computation. [Theorem 1’s constructive proof](https://arxiv.org/pdf/1706.09869)
The claimed \(O(\tau m^2)\) bound is a valid conservative bound for scanning implementations. Positive maximin shares ensure positive utility totals, so normalization is defined. Summation and normalization of the input rationals produce numbers of polynomial bit length, and the required comparisons and arithmetic consequently take polynomial bit time.
The matching lower and upper bounds establish the sharp universal factor \(\alpha=2/3\), with an algorithm polynomial in \(m,\tau,L\). No additional clarification or repair is needed.
⟨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.