Answer: The lottery optimization is exactly polynomial-time solvable. Proportional-supply MVM is DSIC and feasible, but its eventual welfare guarantee fails: an instance with both values strictly greater than \(1\) has limiting gap \(1/16\).
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor arbitrary value distribution with sup- port [1, U], for arbitrary finite U > 1: MVM is DSIC and feasible; for arbitrary ǫ > 0, ∃n ∈Z+ such that if there are at least n agents and a residual claimant for type-B goods, expected welfare under MVM is within ǫ of the expected wel- fare of optimal allocation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite value-type set \(T\), values \(v_t\in[1,U]\), rational masses \(\mu_t\) summing to one, and per-capita type-A supply \(\rho\in(0,1)\), compute a type-based lottery \((q_t,p_t)_{t\in T}\) maximizing \(\sum_t\mu_t v_t q_t\), subject to \(\sum_t\mu_t q_t\le\rho\), \(q_t+p_t\le1\), and DSIC constraints \(v_tq_t+p_t\ge v_tq_s+p_s\) for all \(t,s\). Determine whether an MVM-style rule can attain the efficient welfare within additive \(\varepsilon\) as finite populations grow with proportions converging to \(\mu\).
A society is given by its support: the list of the \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Values \(v_t\in[1,U]\), the finite bound \(U>1\), and supply \(\rho\in(0,1)\) are binary rationals. Let \(L\) be total input bit length and \(m=2\) the number of good types.
Agents are risk neutral and consume at most one good: utility is \(v_t\) for type A, \(1\) for type B, and \(0\) for nothing. Type B is plentiful and has a residual claimant; evaluate only type-A welfare, per capita.
A type-based lottery specifies \(q_t,p_t\ge0\), with \(q_t+p_t\le1\), \(\sum_t\mu_tq_t\le\rho\), and DSIC inequalities \(v_tq_t+p_t\ge v_tq_s+p_s\) for every \(t,s\in T\); reports are restricted to \(T\).
Let \(W_{\mathrm{IC}}\) be the maximum of \(W(q)=\sum_t\mu_tv_tq_t\) under these constraints, and let \(W_{\mathrm{eff}}=\max\{\sum_t\mu_tv_tx_t:0\le x_t\le1,\ \sum_t\mu_tx_t\le\rho\}\), the benchmark without incentive constraints.
For finite populations, take values in \(T\), counts \(n_t\) satisfying \(n_t/n\to\mu_t\), and \(k_n=\lfloor\rho n\rfloor\) type-A goods. Put \(C=\lceil U\rceil\) and \(h_n=Ck_n\). Break bid ties using uniformly random priorities drawn independently of reports.
Define the proportional-supply MVM rule as follows: when \(0<h_n<n\), the highest \(h_n\) bidders each receive probabilities \(q_i=1/C\), \(p_i=1-b_{(h_n+1)}/C\), where \(b_{(j)}\) is the \(j\)th-highest bid; all others receive \((q_i,p_i)=(0,1)\).
When \(h_n\ge n\), everyone receives \((q_i,p_i)=(k_n/n,1-k_n/n)\); when \(k_n=0\), everyone receives \((0,1)\). Let \(W_n=n^{-1}\sum_i v_iq_i\) at truthful reports, averaging over tie-breaking.
For rational \(\varepsilon>0\), can a feasible DSIC lottery with welfare at least \(W_{\mathrm{IC}}-\varepsilon\) be computed in time polynomial in \(m,\tau,L,1/\varepsilon\), or is this approximation problem NP-hard?
Does the defined proportional-supply MVM rule remain DSIC and feasible and satisfy \(W_n\ge W_{\mathrm{eff}}-\varepsilon\) eventually for every such population sequence and every \(\varepsilon>0\), or can this guarantee fail?
Known discrete result: with one type-A good, a residual claimant, and i.i.d. values supported on \([1,U]\) for finite \(U>1\), MVM is DSIC and feasible and approaches efficient expected welfare within every additive \(\varepsilon>0\) as population size grows. [Source](https://ifaamas.org/Proceedings/aamas2014/aamas/p1313.pdf)
No result settling this proportional-supply, finite-support version was located.
The lottery optimization problem is polynomial-time solvable exactly, and therefore admits the requested additive approximation.
The proportional-supply MVM rule is DSIC and feasible, but its claimed asymptotic welfare guarantee fails, even with two supported values strictly greater than \(1\).
Use one pair of variables \((q_t,p_t)\) for each supported type \(t\in T\). Consider the linear program
\(\displaystyle \max \sum_{t\in T}\mu_t v_t q_t\)
subject to
\(\displaystyle q_t\ge 0,\qquad p_t\ge 0,\qquad q_t+p_t\le 1\quad(t\in T),\)
\(\displaystyle \sum_{t\in T}\mu_tq_t\le\rho,\)
and
\(\displaystyle v_tq_t+p_t-v_tq_s-p_s\ge 0\quad(t,s\in T).\)
These are exactly the feasibility and DSIC constraints in the question. Thus the optimal objective value is \(W_{\mathrm{IC}}\).
There are \(2\tau\) variables and at most \(\tau^2+3\tau+1\) inequalities. All coefficients are rational. In particular, forming each objective coefficient \(\mu_tv_t\) requires only rational multiplication, and its encoding length is bounded by a polynomial in \(L\). The entire explicitly constructed linear program therefore has encoding length polynomial in \(\tau\) and \(L\).
The feasible set is nonempty: take \(q_t=0\) and \(p_t=1\) for every \(t\). It is closed and contained in \([0,1]^{2\tau}\), hence compact. Consequently an optimum exists.
We apply the standard rational linear-programming theorem: a linear program with rational coefficients can be solved in time polynomial in its numbers of variables and constraints and its total binary encoding length, returning an exact rational optimal solution when an optimum exists. All these hypotheses hold here. The returned probabilities have polynomial encoding length; this also follows from the determinant bounds for basic feasible solutions after clearing denominators.
Hence an optimal feasible DSIC lottery can be computed in time \(\operatorname{poly}(\tau,L)\). Its welfare is \(W_{\mathrm{IC}}\), so it satisfies the requested bound for every \(\varepsilon>0\). Since \(m=2\), this is in particular polynomial in \(m,\tau,L,1/\varepsilon\).
The explicit support matters: only the supplied \(\tau\) types and their \(\tau^2\) ordered report pairs are required.
Fix a population size \(n\), write \(k=k_n\) and \(h=Ck\), and consider admissible bids in \(T\). Every such bid belongs to \([1,U]\), and \(U\le C\).
Let \(b=b_{(h+1)}\). Each selected agent receives
\(\displaystyle q_i=\frac1C,\qquad p_i=1-\frac bC.\)
Because \(1\le b\le U\le C\),
\(\displaystyle q_i\ge0,\qquad p_i\ge0,\qquad q_i+p_i=1+\frac{1-b}{C}\le1.\)
Each unselected agent receives \((0,1)\), which also satisfies the individual constraints. Aggregate type-A allocation is
\(\displaystyle \sum_iq_i=\frac hC=k.\)
These marginal probabilities admit an implementation that respects supply in every realization. Choose uniformly a subset of \(k\) agents among the \(h\) selected agents, and give them type-A goods. Each selected agent then receives type A with probability \(k/h=1/C\).
Conditional on not receiving type A, give a selected agent type B with probability
\(\displaystyle \frac{p_i}{1-q_i}=\frac{C-b}{C-1}.\)
Here \(C\ge2\), and the displayed probability lies in \([0,1]\) because \(1\le b\le C\). Give every unselected agent type B. This realizes the prescribed marginals without giving any agent more than one good.
If \(h\ge n\), choose uniformly a subset of \(k\) agents from the whole population, give them type A, and give all others type B. This realizes \((k/n,1-k/n)\). Since \(\rho<1\), we have \(0\le k<n\).
If \(k=0\), give everyone type B.
Thus the rule is feasible in every case.
The cases \(h\ge n\) and \(k=0\) are DSIC because allocations do not depend on reports.
Suppose \(0<h<n\). Fix an agent \(i\), every other agent’s bid, and a realization of all tie-breaking priorities. Let \(a_i\) be the numerical bid of the \(h\)-th-ranked opponent. This is defined because \(h\le n-1\).
If agent \(i\) is selected, then the \((h+1)\)-st-ranked bid in the full population equals \(a_i\). Indeed, removing a selected agent from the first \(h+1\) positions leaves precisely the first \(h\) opponents. Thus every report that selects \(i\) gives the same lottery
\(\displaystyle \left(\frac1C,1-\frac{a_i}{C}\right).\)
For true value \(v_i\), its expected utility is
\(\displaystyle 1+\frac{v_i-a_i}{C}.\)
Every report that leaves \(i\) unselected gives utility \(1\).
There are three cases:
Truthful reporting therefore maximizes expected utility for every fixed realization of priorities and every fixed vector of opponents’ reports. Since priorities are independent of reports, averaging these inequalities over priorities preserves them. This proves DSIC for the risk-neutral agents specified in the question.
Consider two types, denoted \(\ell\) and \(H\), with
\(\displaystyle U=2,\qquad C=2,\qquad \rho=\frac14,\qquad \mu_H=\frac14,\qquad \mu_\ell=\frac34,\)
and values
\(\displaystyle v_H=2,\qquad v_\ell=a,\)
where \(a\) is any binary rational satisfying \(1\le a<2\).
Every feasible benchmark allocation satisfies
\(\displaystyle \sum_t\mu_tv_tx_t\le2\sum_t\mu_tx_t\le2\rho=\frac12.\)
Taking \(x_H=1\) and \(x_\ell=0\) attains this bound. Hence
\(\displaystyle W_{\mathrm{eff}}=\frac12.\)
For every \(n\), choose counts
\(\displaystyle n_H=\left\lfloor\frac n4\right\rfloor,\qquad n_\ell=n-n_H.\)
Then \(n_H/n\to1/4\) and \(n_\ell/n\to3/4\), as required. Moreover,
\(\displaystyle k_n=\left\lfloor\frac n4\right\rfloor=n_H.\)
For \(n\ge4\), we have \(0<h_n=2k_n<n\). At truthful reports, the selected agents consist of all \(k_n\) high-value agents and exactly \(k_n\) low-value agents. Each receives type A with probability \(1/2\). Consequently,
\(\displaystyle W_n=\frac1n\left(\frac{2k_n}{2}+\frac{ak_n}{2}\right)=\frac{(2+a)k_n}{2n}\le\frac{2+a}{8}.\)
Tie-breaking does not affect this expression, because all low-value agents have identical value. Taking the limit gives
\(\displaystyle \lim_{n\to\infty}W_n=\frac{2+a}{8},\qquad W_{\mathrm{eff}}-\lim_{n\to\infty}W_n=\frac{2-a}{8}>0.\)
For example, take \(a=3/2\), so both supported values are strictly greater than \(1\). Then
\(\displaystyle W_n\le\frac7{16}<\frac{15}{32}=W_{\mathrm{eff}}-\frac1{32}\qquad(n\ge4).\)
Thus the requested eventual guarantee fails for \(\varepsilon=1/32\).
The same construction with \(a=1\) has an additional property. Set
\(\displaystyle (q_H,p_H)=(1,0),\qquad(q_\ell,p_\ell)=(0,1).\)
This uses exactly \(\mu_H=\rho\) units of type-A supply. The low type obtains utility \(1\) from either report, while the high type obtains utility \(2\) truthfully and \(1\) by reporting low. Therefore this lottery is feasible and DSIC, with welfare \(1/2\). It follows that
\(\displaystyle W_{\mathrm{IC}}=W_{\mathrm{eff}}=\frac12,\)
whereas proportional-supply MVM has limiting welfare \(3/8\).
So its failure can persist even when incentive constraints impose no loss relative to the efficient benchmark.
The cited [Mechanism 4 and Theorem 5](https://ifaamas.org/Proceedings/aamas2014/aamas/p1313.pdf) concern one type-A good. Once the population exceeds \(C\), that mechanism selects a fixed number \(C\) of agents.
In the proportional-supply rule, the number selected is \(Ck_n\), with \(Ck_n/n\to C\rho>0\). The counterexample shows directly that this change can force a positive fraction of type-A allocation onto lower-value agents. It therefore does not contradict the cited single-good theorem.
⟨structured verdict parsed — rendered above⟩
The prover resolves both questions correctly. The explicitly supported lottery optimization is exactly solvable in polynomial time. The proportional-supply MVM rule is feasible and DSIC, but the stated eventual welfare guarantee fails.
No major or minor mathematical issues were found. No additional clarification is needed.
Consequently, the returned lottery achieves \(W_{\mathrm{IC}}\), which satisfies every requested additive approximation bound. With \(m=2\), the claimed running-time classification follows.
For \(0<h<n\), admissible reports ensure \(1\le b\le U\le C\). The selected agents’ probabilities therefore satisfy
\[
q_i\ge0,\qquad p_i\ge0,\qquad q_i+p_i=1+\frac{1-b}{C}\le1.
\]
Unselected agents’ probabilities also satisfy the individual constraints, and aggregate type-A probability is exactly \(h/C=k\).
The implementation described by the prover is valid: a uniform subset of \(k\) selected agents gives each selected agent type-A probability \(k/h=1/C\). Since \(U>1\), one has \(C\ge2\), so the conditional type-B probability
\[
\frac{C-b}{C-1}
\]
is defined and belongs to \([0,1]\). It gives the prescribed type-B marginal without assigning two goods to any agent. Type-B supply imposes no further constraint.
For \(h\ge n\), the uniform subset implementation gives the stated marginals and uses exactly \(k\) type-A goods. The inequality \(k<n\) follows from \(\rho<1\). The \(k=0\) branch is also feasible. These branches cover all cases, including \(h=n\).
The report-independent branches are DSIC.
For \(0<h<n\), the opponent threshold \(a_i\) exists because \(h\le n-1\). With priorities fixed, removing a selected agent from the first \(h+1\) positions leaves the highest-ranked \(h\) opponents. Thus every report selecting that agent gives the same numerical threshold \(a_i\), including when bids tie.
The selected and unselected expected utilities are correctly computed as
\[
1+\frac{v_i-a_i}{C}
\qquad\text{and}\qquad
1.
\]
The three cases \(v_i>a_i\), \(v_i<a_i\), and \(v_i=a_i\) exhaust all possibilities. Truthful reporting selects the agent in the first case, leaves the agent unselected in the second, and gives an indifferent outcome in the third.
These inequalities hold for every fixed vector of opponents’ reports and fixed priorities. Report independence of the priorities permits averaging while preserving the inequalities. This establishes precisely the expected-utility DSIC property appropriate for the task’s risk-neutral agents.
All parameters of the counterexample meet the input restrictions. The concrete choice \(a=3/2\) gives two positive-mass supported values strictly greater than \(1\).
The efficient benchmark calculation is correct: the supply constraint and maximum value \(2\) give an upper bound \(1/2\), attained by assigning type A to the entire high type.
The counts satisfy the required limiting proportions and \(n_H=k_n\). For every \(n\ge4\),
\[
0<2k_n<n.
\]
There are exactly \(k_n\) high-value selected agents and \(k_n\) low-value selected agents. The welfare calculation therefore correctly yields
\[
W_n=\frac{(2+a)k_n}{2n}\le\frac{2+a}{8}.
\]
Tie-breaking cannot change this value because the tied low-value agents have identical values.
The limit and gap are correct:
\[
\lim_{n\to\infty}W_n=\frac{2+a}{8},
\qquad
W_{\mathrm{eff}}-\lim_{n\to\infty}W_n=\frac{2-a}{8}>0.
\]
For \(a=3/2\), the gap is \(1/16\), and
\[
W_n\le\frac7{16}<\frac{15}{32}
=W_{\mathrm{eff}}-\frac1{32}
\]
for every \(n\ge4\). This disproves the universal eventual guarantee.
The additional \(a=1\) example is also valid: the proposed lottery satisfies feasibility and both nontrivial DSIC inequalities, attains \(W_{\mathrm{eff}}=1/2\), and establishes \(W_{\mathrm{IC}}=W_{\mathrm{eff}}\). Its stated MVM limit \(3/8\) is correct.
The source comparison is accurate. [Mechanism 4 and Theorem 5](https://ifaamas.org/Proceedings/aamas2014/aamas/p1313.pdf) concern a single type-A good; when \(n>C\), the mechanism selects \(C\) agents. The proportional-supply rule instead selects \(Ck_n\) agents. The prover does not apply the single-good theorem to the new setting, so no unverified theorem extension enters the argument.
⟨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.