Fair and Truthful Giveaway Lotteries

The strongest positive case is a faithful high-multiplicity version of the paper’s main result, Theorem 1. The paper contains no NP-hardness, W[1]-hardness, or similar hardness anchor, so this cannot honestly be presented as a case where discrete hardness dissolves. Its computational anchor is the polynomial mechanism itself.

Consider a large public-event lottery with \(N\) family groups and capacity \(C_N=N\kappa\), where family sizes come from a fixed finite set \(K\), such as \(K=\{1,\ldots,6\}\). There are \(N\mu_k\) families of size \(k\), with \(N\gg |K|\). This could be a large venue, festival, or high-capacity attraction. The relevant type is exactly a family size \(k\): in the paper, families of the same size are indistinguishable to the mechanism, and no other individual attribute matters. Mass \(\mu_k\) is the fraction of family groups of type \(k\), not the fraction of individuals; individual mass \(k\mu_k\) is recovered when needed.

A continuous lottery chooses a measurable mass of whole families. Its aggregate outcome is \(z=(z_k)_{k\in K}\), where \(z_k\) is the mass of size-\(k\) families admitted, subject to \(0\le z_k\le\mu_k\) and \(\sum_k k z_k\le\kappa\). Thus the feasible aggregate set is \(Z(\mu,\kappa)=\{z:\ 0\le z_k\le\mu_k,\ \sum_k k z_k\le\kappa\}\). Every family remains all-or-nothing in every realization; only the population of families is nonatomic. A random rotation within each type class implements any desired admission rate without splitting a family.

For a lottery \(P\) over feasible aggregate outcomes, the admission probability of type \(k\) is \(q_k(P)=\mathbb E_P[z_k]/\mu_k\), and utilization is \(u(P)=\mathbb E_P[\sum_k k z_k]/\kappa\). Leximin means lexicographically maximizing the type-specific admission probabilities, with the type masses providing the multiplicities inherited from the finite model.

My lead continuous problem is Continuous IPMAX-GaL:

Given rational \(\mu\), rational \(\kappa\), and finite \(K\), output an exactly encoded lottery \(P\) over \(Z(\mu,\kappa)\) that is leximin-optimal, Pareto-optimal, envy-free, hybrid adjunctive group-strategyproof, and achieves utilization at least one half of the unrestricted optimum. A deviation is the direct measure-valued analogue of the paper’s Definitions 2.1–2.3: a positive-mass coalition may split or merge its families, and under hybrid adjunctive deviations may add uninterested people only to reported groups containing coalition members. The deviation is unsuccessful if it does not strictly improve the admission probability of almost every coalition member.

This is recognizably the authors’ problem. It retains the same capacity constraint, the same group indivisibility, the same lottery outcome, the same fairness objective, and the same manipulation model. The only change is replacing repeated family units by their type masses. It is not merely fractional allocation of a divisible good.

The anchor is Theorem 1, proved in this paper: “Algorithm IPMAX is hybrid adjunctive group strategyproof … produces a solution that is leximin optimal, and approximates the utilization to at least a \(1/2\) factor.” The continuous problem should be in Class A. The max-min step becomes the finite LP \(\max \eta\) subject to \(\bar z_k\ge\mu_k\eta\), \(0\le\bar z_k\le\mu_k\), and \(\sum_k k\bar z_k\le\kappa\). Iterated leximin optimization has at most \(|K|\) stages. The relevant dual pricing problem is a fractional knapsack problem, hence polynomial in \(|K|\) and the input bit length. The substantive remaining proof is lifting IPMAX’s descending-family-size strategyproofness argument from finite lists to positive-mass reports; that looks like a genuine technical extension, not a change of question.

A useful secondary anchor is Proposition 7, also proved here. It says that any egalitarian-welfare-optimal, leximin-optimal, or envy-free mechanism has worst-case utilization ratio at most \(1/2\). Its continuous counterpart is the Fluid Leximin Utilization Frontier: given \((\mu,\kappa)\), compute a leximin-optimal lottery maximizing utilization among all leximin-optimal lotteries, and determine the worst-case ratio to unrestricted utilization. Here I would expect Class A and, in the fluid model, ratio \(1\), not \(1/2\). Indeed, unrestricted utilization is \(\min\{1,(\sum_k k\mu_k)/\kappa\}\). If a leximin solution left capacity unused while some type had \(q_k<1\), increasing that type’s admission rate would lexicographically improve it. Hence a leximin solution can fill all available capacity whenever total demand exceeds capacity. The paper’s \(1/2\) example depends on finite group indivisibility at the scale of the resource; that obstruction disappears when many repeated groups make aggregate mass continuous, even though each individual family remains indivisible.

This mirror covers Theorem 1 and the fairness-utilization boundary in Proposition 7. It does not claim to mirror every impossibility result in the paper. In particular, whether Proposition 4’s incompatibility between leximin and strong group strategyproofness survives when deviations must have positive mass is a further question, as is whether the \(1/2\) bound reappears when family sizes or capacities scale so that individual groups remain macroscopic.

The weakest point is precisely that fluidization may remove the paper’s most vivid phenomenon: with a ten-person capacity, one family can be a substantial part of the resource, whereas in the proposed regime each family is negligible. If the intended application is intrinsically a small lottery with capacity fixed at \(10\), this mirror is weak or degenerate. It is convincing only for a genuinely high-multiplicity regime—many repeated family types and capacity scaling with the number of groups. Under that interpretation, however, it is a faithful computational mirror and gives a clean Class A problem with a meaningful explanation of why the finite \(1/2\) barrier need not survive.