Best of Both Worlds: Agents with Entitlements (aamas23-00073)

Given rational binary-encoded agent types \(\Theta\) with masses \(\mu_\theta\), entitlements \(\lambda_\theta\) satisfying \(\sum_\theta \mu_\theta\lambda_\theta=1\), additive values \(v_\theta(h)\), tie orders, and homogeneous good classes \(h\in H\) with per-capita supplies \(\sigma_h\), construct a finite-support lottery over integral bundle-population allocations \(z_{\theta,B}\), where \(B\in\mathbb{Z}_{\ge 0}^{H}\), preserving type masses and good supplies, such that type-representative marginals satisfy ex-ante \(\mathrm{WSD\text{-}EF}\) and every positive-mass realization satisfies \(\mathrm{WPROP1}\) and \(\mathrm{WEF}(1,1)\) for every relevant pair of agents.

A society is given by its support: the list \(\Theta\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_\theta\), with \(\sum_\theta\mu_\theta=1\); \(\tau\) is the support size, not the number of possible types. Each type has positive rational entitlement density \(\lambda_\theta\), with \(\sum_\theta\mu_\theta\lambda_\theta=1\).
There are \(m\geq1\) homogeneous good classes \(H\), with positive rational per-capita supplies \(\sigma_h\), and nonnegative rational additive values \(v_\theta(h)\). A supplied common strict order breaks value ties. Let \(L\) be the total binary input length.
A population allocation is a finitely supported nonnegative rational table \(z_{\theta,B}\), where \(B\in\mathbb Z_{\geq0}^{H}\) is an individual bundle and \(z_{\theta,B}\) is its recipient mass, satisfying \(\sum_Bz_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B}z_{\theta,B}B_h=\sigma_h\). Write \(v_\theta(B)=\sum_hB_hv_\theta(h)\).
A lottery consists of finitely many such allocations \(z^r\) with positive rational probabilities \(p_r\) summing to \(1\). Its type-representative marginals are \(x_{\theta h}=\mu_\theta^{-1}\sum_rp_r\sum_Bz^r_{\theta,B}B_h\).
Ex-ante \(\mathrm{WSD\text{-}EF}\) means \(\lambda_\eta\sum_{h:v_\theta(h)\geq v_\theta(k)}x_{\theta h}\geq\lambda_\theta\sum_{h:v_\theta(h)\geq v_\theta(k)}x_{\eta h}\) for every \(\theta,\eta\in\Theta\) and \(k\in H\); tied values share a threshold.
Ex-post \(\mathrm{WPROP1}\) requires every \((\theta,B)\) with \(z^r_{\theta,B}>0\) to satisfy \(v_\theta(B)\geq\lambda_\theta\sum_h\sigma_hv_\theta(h)\), or to satisfy this inequality after adding one copy held elsewhere in society; any supplied class is eligible.
Ex-post \(\mathrm{WEF}(1,1)\) requires, for every two positive-mass groups \((\theta,B),(\eta,C)\) in the same realization, including groups of the same type, either \(C=0\) or some \(h\) with \(C_h>0\) satisfies \(\frac{v_\theta(B)+v_\theta(h)}{\lambda_\theta}\geq\frac{v_\theta(C)-v_\theta(h)}{\lambda_\eta}\); the same copy is transferred from the compared bundle.

Is constructing a lottery satisfying all three guarantees, or determining that none exists, solvable in polynomial time in \(m,\tau,L\), or is this problem NP-hard?

For finite lists of agents and individually listed goods, a lottery with these three guarantees always exists and is computable in strongly polynomial time ([Hoefer, Schmalhofer, and Varricchio](https://arxiv.org/pdf/2209.03908)).
No result settling the exact support-encoded population problem above was located in the literature search.

Result

The problem is polynomial-time solvable, and a feasible lottery always exists. In fact, one population allocation suffices: its degenerate lottery satisfies all three guarantees.

The construction produces at most \(m+1\) positive-mass bundles per type. The ability to split each type’s population mass is essential to this construction.

1. Continuous consumption

For each type \(\theta\), order the classes by decreasing value, using the supplied strict order to break ties.

Starting at time \(0\), every type continuously consumes its most preferred available class. Its consumption rate per representative is \(\lambda_\theta\), so its aggregate population consumption rate is \(\mu_\theta\lambda_\theta\). When a class is exhausted, the types consuming it switch to their preferred remaining class.

This process has at most \(m\) phases. Because

\(\displaystyle \sum_\theta\mu_\theta\lambda_\theta=1,\)

its total consumption rate is \(1\) until all supply is exhausted. Consequently, its finishing time is

\(\displaystyle S=\sum_h\sigma_h.\)

Let \(d_h\) be the exhaustion time of class \(h\), and let \(x_{\theta h}\) be the amount consumed by a representative of type \(\theta\). These quantities are rational and satisfy

\(\displaystyle \sum_\theta\mu_\theta x_{\theta h}=\sigma_h,\qquad \sum_hx_{\theta h}=\lambda_\theta S.\)

This is the population analogue of the different-speeds eating procedure in [Hoefer, Schmalhofer, and Varricchio](https://arxiv.org/pdf/2209.03908). The rounding and population guarantees below are proved directly.

Ex-ante weighted stochastic-dominance envy-freeness

Fix \(\theta\) and a value threshold \(q=v_\theta(k)\). Write

\(\displaystyle A=\{h:v_\theta(h)\geq q\},\qquad T_A=\max_{h\in A}d_h.\)

At every time before \(T_A\), some class in \(A\) remains available. Every such class is strictly preferred by \(\theta\) to every class outside \(A\). Thus \(\theta\) consumes only classes in \(A\) until \(T_A\), and none thereafter. Hence

\(\displaystyle \sum_{h\in A}x_{\theta h}=\lambda_\theta T_A.\)

All classes in \(A\) are exhausted by \(T_A\), so any other type \(\eta\) consumes at most \(\lambda_\eta T_A\) units from \(A\). Therefore

\(\displaystyle \lambda_\eta\sum_{h\in A}x_{\theta h}\geq\lambda_\theta\sum_{h\in A}x_{\eta h}.\)

These are precisely the required \(\mathrm{WSD\text{-}EF}\) inequalities, including thresholds containing tied values.

We will also use the consequence

\[\displaystyle \sum_{h\in A}x_{\theta h}\geq\lambda_\theta\sum_{h\in A}\sigma_h. \tag{1}\]

Indeed, multiply the preceding inequality by \(\mu_\eta\), sum over \(\eta\), and use both normalization and supply conservation.

2. Rounding each type into finitely many bundles

Fix a type \(\theta\), with ordered classes \(\pi_\theta(1),\ldots,\pi_\theta(m)\). Define cumulative consumption

\(\displaystyle a_{\theta,0}=0,\qquad a_{\theta,j}=\sum_{\ell=1}^j x_{\theta,\pi_\theta(\ell)}.\)

For an offset \(u\in[0,1)\), define an integer bundle by

\[\displaystyle B^\theta_{\pi_\theta(j)}(u)=\lfloor a_{\theta,j}+u\rfloor-\lfloor a_{\theta,j-1}+u\rfloor. \tag{2}\]

The coordinates are nonnegative because the cumulative amounts are nondecreasing. For every preference prefix \(P_{\theta,j}=\{\pi_\theta(1),\ldots,\pi_\theta(j)\}\), telescoping gives

\(\displaystyle \sum_{h\in P_{\theta,j}}B^\theta_h(u)=\lfloor a_{\theta,j}+u\rfloor.\)

In particular,

\[\displaystyle \left\lfloor\sum_{h\in P_{\theta,j}}x_{\theta h}\right\rfloor \leq\sum_{h\in P_{\theta,j}}B^\theta_h(u) \leq\left\lceil\sum_{h\in P_{\theta,j}}x_{\theta h}\right\rceil. \tag{3}\]

Also, \(x_{\theta h}=0\) implies \(B^\theta_h(u)=0\), since the two adjacent cumulative amounts in (2) coincide.

For uniform \(u\), the elementary identity

\(\displaystyle \mathbb E[\lfloor a+u\rfloor]=a\)

holds for every nonnegative real \(a\): writing \(a=n+f\), where \(n\) is integer and \(0\leq f<1\), the floor equals \(n+1\) on an interval of length \(f\) and \(n\) otherwise. Consequently,

\[\displaystyle \mathbb E[B^\theta_h(u)]=x_{\theta h}. \tag{4}\]

The bundle changes only at the interior breakpoints

\(\displaystyle 1-\{a_{\theta,j}\},\)

where \(\{a_{\theta,j}\}\neq0\) denotes the fractional part. There are at most \(m\) such breakpoints, yielding at most \(m+1\) intervals on which the bundle is constant.

For each interval \(I\), choose its rational midpoint \(u_I\), and assign mass \(\mu_\theta|I|\) to \(B^\theta(u_I)\). Merge repeated bundles. All these masses are positive rational numbers.

Perform this construction for every type, obtaining a table \(z\). Its type masses sum to \(\mu_\theta\), and (4) implies

\(\displaystyle \sum_Bz_{\theta,B}B_h=\mu_\theta x_{\theta h}.\)

Thus \(z\) satisfies the exact supplies. Its type-representative marginals are \(x\), so its degenerate lottery is ex-ante \(\mathrm{WSD\text{-}EF}\).

3. A bound for goods exhausted by a given time

For a time \(t\in[0,S]\), define

\(\displaystyle D(t)=\{h:d_h\leq t\}.\)

Lemma. Every bundle \(C\) constructed for type \(\eta\) satisfies

\[\displaystyle \sum_{h\in D(t)}C_h\leq\lceil\lambda_\eta t\rceil. \tag{5}\]

Proof. A type switches classes only when its current class is exhausted. Its positively consumed classes therefore occur in preference order, with strictly increasing exhaustion times.

Consequently, its positively consumed classes belonging to \(D(t)\) form an initial segment of its positively consumed classes. Classes with zero consumption also have zero rounded count. Therefore there is a preference prefix \(P\), possibly empty, such that

\(\displaystyle \sum_{h\in D(t)}C_h=\sum_{h\in P}C_h,\qquad \sum_{h\in D(t)}x_{\eta h}=\sum_{h\in P}x_{\eta h}.\)

The prefix upper bound (3) gives

\(\displaystyle \sum_{h\in D(t)}C_h\leq \left\lceil\sum_{h\in D(t)}x_{\eta h}\right\rceil.\)

All consumption of classes in \(D(t)\) occurred by time \(t\), and the representative’s total consumption by that time is \(\lambda_\eta t\). Thus their total consumption is at most \(\lambda_\eta t\), proving (5). \(\square\)

4. Ex-post weighted transfer envy-freeness

Take any two positive-mass groups \((\theta,B)\) and \((\eta,C)\) in \(z\). The argument allows \(\theta=\eta\).

If \(C=0\), the guarantee holds by definition. Otherwise choose \(g\) with \(C_g>0\) maximizing \(v_\theta(g)\) among classes present in \(C\), and put \(M=v_\theta(g)\).

Fix any value threshold \(q\) of type \(\theta\), and let

\(\displaystyle A=\{h:v_\theta(h)\geq q\},\qquad T_A=\max_{h\in A}d_h.\)

Write \(B_A=\sum_{h\in A}B_h\) and \(C_A=\sum_{h\in A}C_h\).

The set \(A\) is a preference prefix ending at a tie boundary. Section 1 and the lower rounding bound give

\(\displaystyle B_A\geq\lfloor\lambda_\theta T_A\rfloor.\)

Since \(A\subseteq D(T_A)\), lemma (5) gives

\(\displaystyle C_A\leq\lceil\lambda_\eta T_A\rceil.\)

It follows that

\[\displaystyle \frac{B_A+1}{\lambda_\theta}>T_A> \frac{C_A-1}{\lambda_\eta}. \tag{6}\]

If \(q\leq M\), the chosen class \(g\) belongs to \(A\). Therefore (6) is exactly the desired weighted comparison of threshold counts after transferring one copy of \(g\) from \(C\) to \(B\).

If \(q>M\), the bundle \(C\) contains no class in \(A\), and neither does the transferred copy. The corresponding comparison holds because its right-hand side is zero.

Thus every value threshold satisfies

\[\displaystyle \frac{B_A+\mathbf1_{\{g\in A\}}}{\lambda_\theta} \geq \frac{C_A-\mathbf1_{\{g\in A\}}}{\lambda_\eta}. \tag{7}\]

To pass from threshold counts to values, list the distinct values of \(\theta\) as \(q_1>\cdots>q_d\geq0\), and set \(q_{d+1}=0\). For any nonnegative vector \(Y\),

\[\displaystyle v_\theta(Y)= \sum_{j=1}^d(q_j-q_{j+1}) \sum_{h:v_\theta(h)\geq q_j}Y_h. \tag{8}\]

Indeed, a coordinate of value \(q_\ell\) receives coefficient \(\sum_{j=\ell}^d(q_j-q_{j+1})=q_\ell\).

Multiply (7) by these nonnegative value differences and sum. Identity (8) yields

\(\displaystyle \frac{v_\theta(B)+v_\theta(g)}{\lambda_\theta} \geq \frac{v_\theta(C)-v_\theta(g)}{\lambda_\eta}.\)

The same copy of \(g\) is transferred from the compared bundle. This proves ex-post \(\mathrm{WEF}(1,1)\) for every pair of positive-mass groups.

5. Ex-post weighted proportionality up to one copy

First, applying identity (8) to the threshold inequalities (1) gives

\[\displaystyle v_\theta(x_\theta)\geq \lambda_\theta\sum_h\sigma_hv_\theta(h). \tag{9}\]

Now let \(B\) be any constructed bundle for \(\theta\). For every value threshold set \(A\), the lower rounding bound implies

\(\displaystyle B_A\geq\lfloor x_{\theta,A}\rfloor\geq x_{\theta,A}-1.\)

Using (8) again,

\(\displaystyle v_\theta(B)\geq v_\theta(x_\theta)-\sum_{j=1}^d(q_j-q_{j+1}) =v_\theta(x_\theta)-q_1.\)

Choose a supplied class \(g\) of maximum value \(q_1\). Combining this bound with (9) gives

\(\displaystyle v_\theta(B)+v_\theta(g)\geq \lambda_\theta\sum_h\sigma_hv_\theta(h).\)

Every class has positive supply, and the question explicitly makes any supplied class eligible for the added copy. Hence this proves \(\mathrm{WPROP1}\). If the original bundle already meets the target, no addition is needed. If all values are zero, it meets the target automatically.

6. Polynomial running time and output length

Each consumption phase is computed exactly. If the currently chosen class for type \(\theta\) is \(h_\theta\), its aggregate rate on class \(h\) is

\(\displaystyle r_h=\sum_{\theta:h_\theta=h}\mu_\theta\lambda_\theta.\)

For remaining supplies \(s_h\), the next phase duration is

\(\displaystyle \Delta=\min_{h:r_h>0}\frac{s_h}{r_h}.\)

Update the supplies and individual consumptions, remove exhausted classes, and repeat. At least one class is removed per phase, so there are at most \(m\) phases and polynomially many arithmetic operations.

Here is an explicit bound on rational encoding lengths. Let \(D\) be the product of all denominators appearing in the masses, entitlement densities, and supplies. Then \(\log D\leq L\), and \(D\) is a common denominator for these quantities and for every \(\mu_\theta\lambda_\theta\).

Every aggregate class rate is \(c/D\), with integer \(0\leq c\leq D\). Let \(c_j\) be the positive rate numerator of a class attaining the minimum in phase \(j\). By induction, after phase \(j\), the denominators of remaining supplies, accumulated time, and accumulated individual consumptions divide

\(\displaystyle R_j=D^{j+1}\prod_{\ell=1}^j c_\ell.\)

To verify the induction, a remaining supply with denominator dividing \(R_{j-1}\), divided by \(c_j/D\), gives a duration with denominator dividing \(R_{j-1}c_j\). Multiplying this duration by an aggregate rate or an entitlement density introduces at most another factor \(D\). All accumulated quantities therefore have denominators dividing \(R_j\).

Thus these denominators have \(O(mL)\) bits. Supplies and times are bounded by \(S\), and individual consumption is bounded by \(\lambda_\theta S\); their numerators also have polynomially many bits.

Finally, each type requires sorting at most \(m\) rational breakpoints and forming at most \(m+1\) bundles. Bundle coordinates, interval lengths, and recipient masses all have polynomial encoding length. The table contains at most \(\tau(m+1)\) entries, each with \(m\) bundle coordinates.

Therefore the algorithm constructs the required single-realization lottery in polynomial time in \(m,\tau,L\), with polynomial output length.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The construction satisfies all three guarantees under the stated population model, and its running time and output length are polynomial. I found no major or minor issues requiring repair.

• Continuous consumption and feasibility.

Every type consumes at representative rate \(\lambda_\theta>0\). While any supply remains, every type has an available class to consume, so the aggregate consumption rate is
\[ \sum_\theta\mu_\theta\lambda_\theta=1. \]
Consequently, the finishing time is \(S=\sum_h\sigma_h\).

Each phase ends with at least one class exhausting. Simultaneous exhaustion removes multiple classes and does not increase the phase count, so there are at most \(m\) phases.

The stated conservation identities follow directly: aggregate consumption of each class equals its supply, and every representative consumes continuously until time \(S\). All rates, phase durations, exhaustion times, and consumption amounts are rational.

• Ex-ante weighted stochastic-dominance envy-freeness.

For a threshold set \(A=\{h:v_\theta(h)\geq q\}\), every class in \(A\) precedes every class outside \(A\) in type \(\theta\)’s consumption order. Ties within \(A\) do not affect this fact.

Before \(T_A=\max_{h\in A}d_h\), at least one class in \(A\) remains available. After \(T_A\), none does. Therefore
\[ x_{\theta,A}=\lambda_\theta T_A. \]
Any other type \(\eta\) consumes at most \(\lambda_\eta T_A\) units from \(A\), because all its consumption from \(A\) occurs by that time. This establishes every required weighted threshold comparison.

The derivation of inequality (1) is also correct. Multiplying those comparisons by \(\mu_\eta\) and summing uses exactly the two stated identities
\[ \sum_\eta\mu_\eta\lambda_\eta=1, \qquad \sum_\eta\mu_\eta x_{\eta,A}=\sum_{h\in A}\sigma_h. \]

• Rounding and construction of a rational allocation.

Formula (2) produces nonnegative integer coordinates because the cumulative amounts are nondecreasing. Its prefix sums telescope to \(\lfloor a_{\theta,j}+u\rfloor\), giving both bounds in (3), including when a cumulative amount is integral.

The expectation identity is correct for every nonnegative \(a\). Subtracting the expectations of adjacent cumulative floors yields (4).

Only the \(m\) cumulative amounts can introduce interior breakpoints. Coincident breakpoints reduce the number of intervals, and integral cumulative amounts introduce none. Thus there are at most \(m+1\) positive-length intervals per type.

Choosing rational midpoints and weighting their bundles by interval length reproduces the uniform-offset expectations exactly. Values at interval endpoints have measure zero and need not be represented. Merging repeated bundles preserves the masses and consumption totals.

Hence the resulting table is a finitely supported nonnegative rational allocation with the exact type masses and supplies. Its degenerate lottery has precisely the consumption marginals established in step 2.

• The exhaustion-time lemma.

The key assertion about positively consumed classes is valid. A type stays on its chosen class until that class exhausts. Any subsequently positively consumed class must remain available for a positive duration after that switch, so its exhaustion time is strictly later. Classes exhausted simultaneously but never consumed by that type have zero consumption and zero rounded count.

Thus the positively consumed classes in \(D(t)\) form an initial segment of that type’s consumption sequence. They can be represented by a preference prefix after ignoring classes with zero consumption. This justifies applying the prefix rounding bound.

All consumption of classes in \(D(t)\) occurs by time \(t\). Their total representative consumption is therefore at most \(\lambda_\eta t\), establishing (5). Empty prefixes and the endpoints \(t=0,S\) are covered.

• Ex-post weighted transfer envy-freeness.

When \(C\neq0\), a maximizing class \(g\) exists among its finitely many positive coordinates. For each threshold set \(A\), the lower prefix bound for \(B\) and the exhaustion-time lemma for \(C\) give the stated bounds.

The strict inequalities in (6) are correct, including at integral arguments, because
\[ \lfloor y\rfloor+1>y, \qquad \lceil y\rceil-1<y. \]
Positive entitlement densities permit division without changing inequality directions.

If \(q\leq M\), the same chosen class \(g\) lies in \(A\). If \(q>M\), no class present in \(C\) lies in \(A\), so the right-hand threshold count is zero. Consequently, (7) holds for every threshold with a single common transfer choice.

Identity (8) is correct: a coordinate of value \(q_\ell\) belongs exactly to the threshold sets indexed by \(j\geq\ell\), whose coefficients sum to \(q_\ell\). All coefficients are nonnegative. Applying the identity to the transferred bundles proves the required value inequality.

The argument also covers equal types, identical groups, and zero-valued classes. The case \(C=0\) is handled as required by the definition.

• Ex-post weighted proportionality up to one copy.

Applying (8) to (1) correctly establishes (9). The lower rounding bound gives a deficit of at most one unit at every value threshold. Summing with the nonnegative value differences bounds the value deficit by \(q_1\).

A maximum-value class exists because \(m\geq1\), and it has positive supply. The task expressly permits any supplied class as the added copy, so this choice meets the eligibility requirement.

Combining the two bounds proves the required proportionality inequality after adding that copy. Bundles already meeting the target need no addition, and the all-zero valuation case is explicitly covered.

• Polynomial running time and encoding length.

The phase computation uses polynomially many exact arithmetic operations. The denominator argument also supplies the necessary bit-complexity bound.

In defining \(D\), the product includes the denominator of each input mass, entitlement density, and supply. Therefore it is a common denominator for every product \(\mu_\theta\lambda_\theta\), as claimed. Aggregate class rates have integer numerators between zero and \(D\) because their sum is one.

The induction for \(R_j\) is valid. Dividing a remaining supply by \(c_j/D\) introduces at most a factor \(c_j\) into its denominator; subsequent multiplication by a rate or entitlement density introduces at most a factor \(D\). Accumulation preserves divisibility by the stated common denominator.

Since \(c_j\leq D\),
\[ \log R_j\leq(2j+1)\log D, \]
which is \(O(mL)\). The bounds by \(S\) and \(\lambda_\theta S\) also control numerator lengths polynomially.

Computing fractional parts, sorting breakpoints, taking midpoints, forming interval masses, and merging bundles preserve polynomial encoding length. The output has at most \(\tau(m+1)\) entries, each with \(m\) coordinates. A single realization with probability one completes the lottery representation.

The reference to the finite-agent eating procedure is contextual; no external theorem is needed for the submitted argument. No additional clarification or missing lemma is required.

⟨structured verdict parsed — rendered above⟩