PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Multi-Item Auctions with I.I.D. Values

Boyu Liu, Zhengyang Liu, Zihe Wang

arXiv:2610.11051v1cs.GT

TL;DR

The paper studies revenue-maximizing auctions for additive buyers with independent values from a common finite distribution, subject to DSIC and ex-post IR. It provides an optimal polynomial-time mechanism for two-point values, establishes hardness for general finite supports, and gives exact or approximate algorithms under parameter restrictions.

  • Problem

    For additive buyers with a common finite prior, the paper asks how to optimize revenue under DSIC and ex-post IR, requirements for which Bayesian interim optimization does not directly provide a solution.

    Source: §1 · p. 2

  • Method

    The paper constructs a truthful deterministic auction for two-point values and applies hardness reductions and finite-type symmetry methods to study general priors and parameter-restricted optimization.

    Source: §1.1 · pp. 2–3

  • Results

    Two-point priors admit an optimal polynomial-time mechanism for arbitrary market sizes, while general finite-support revenue is #P-hard in the single-buyer arbitrary-item and two-item arbitrary-buyer cases.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    Bayesian interim feasibility does not ensure DSIC payments, so DSIC optimization requires more than a supply-feasible interim allocation.

    Source: §1 · p. 2

    The PTAS running-time exponent depends on the item count and accuracy, so it gives no polynomial-time guarantee when the item count is unrestricted.

    Source: §6.2 · p. 18

Abstract

from arXiv · show

We study revenue-maximizing multi-item auctions under dominant-strategy incentive compatibility (DSIC) and ex-post individual rationality. Buyers have additive valuations, and all item values are independent draws from a common finite distribution. For every two-point distribution and arbitrary numbers of buyers and items, we give an explicit deterministic mechanism that is optimal among all randomized mechanisms satisfying these requirements, together with a polynomial-time algorithm for computing the optimal expected revenue. For general finite-support distributions, computing the exact optimal revenue is $\#\mathrm P$-hard, both for a single buyer with an arbitrary number of items and for two items with an arbitrary number of buyers. For a single buyer, we also establish hardness of computing an optimal mechanism. Building on prior work, we also obtain exact and approximate algorithms under different parameter restrictions. Exact polynomial-time optimization is possible whenever any two of the buyer count, item count, and support size are fixed. When only the item count is fixed, a polynomial-time approximation scheme constructs a mechanism with expected revenue at least a $1-\varepsilon$ fraction of the optimum for every fixed $0<\varepsilon<1$. All these algorithms satisfy DSIC and ex-post individual rationality.

1 Introduction

The paper asks how a common finite prior affects exact and approximate revenue optimization under DSIC and ex-post IR. It gives an arbitrary-market optimum for two-point values and studies hardness and parameter-restricted algorithms for broader finite priors.

1 Introduction

  • Earlier single-buyer work establishes structured-prior menu and bundling results, while existing hardness results using item-specific marginals do not establish hardness under a common prior.A QPTAS was known for one additive buyer with i.i.d. item values; the paper broadens the study to common finite priors and DSIC.Source: §1 · pp. 1–2, §1.2 · p. 5

1.2 Related work

  • Bayesian reduced-form methods characterize supply-feasible interim allocations, but that feasibility does not guarantee DSIC payments for multidimensional buyers.Prior symmetry algorithms retain conditional incentive constraints, supporting exact algorithms and approximation schemes.Source: §1 · p. 2, §1.2 · p. 5

1 Introduction

  • DSIC optimization cannot directly use the Bayesian interim program: averaging over opponents loses report comparisons required for truthfulness at each fixed opponents’ report.The Bayesian optimum can exceed the DSIC optimum even for two items with i.i.d. two-point values.Source: §1 · p. 2

1.1 Our results and proof ideas

  • For every two-point distribution, a deterministic auction is optimal among randomized DSIC, ex-post IR mechanisms for arbitrary buyer and item counts.The mechanism and its expected revenue are computable exactly in polynomial time.Source: §1.1 · p. 2
  • Exact randomized DSIC, ex-post IR revenue is #P-hard for one buyer with arbitrary items and for two items with arbitrary buyers under a common finite prior.For one buyer, constructing an optimal IC, IR mechanism is also #P-hard.Source: §1.1 · p. 3
  • Exact polynomial-time optimization is possible when any two of buyer count, item count, and support size are fixed; fixing item count alone gives a PTAS for arbitrary buyer counts and support sizes.The PTAS constructs a DSIC, ex-post IR mechanism achieving at least 1 − ε of optimal revenue for each fixed accuracy.Source: §1.1 · pp. 3–4

2 Model

The model has multiple buyers with additive values for indivisible items, where all item values are independent draws from a common finite distribution. It compares expected revenue across randomized mechanisms subject to DSIC and ex-post individual rationality.

Buyers and values

  • Buyers have additive values for sets of items, and the seller has one copy of each indivisible item.A buyer's value vector records her value for each item.Source: §2 · p. 6
  • All nm item values are independent draws from a common finite distribution with positive, ordered support values and probabilities.Each buyer's possible value vectors and reports are drawn from the distribution's support across m items.Source: §2 · p. 6

Allocation and payment rules

  • A direct mechanism specifies each buyer's allocation probabilities and expected payment at every report profile.Mechanism randomization is evaluated with the report profile held fixed.Source: §2 · p. 6

Incentives and participation

  • DSIC requires truthful reporting to maximize a buyer's expected utility for every fixed profile of opponents' reports, while ex-post IR requires truthful utility to be nonnegative at every profile.For randomized mechanisms, these conditions concern internal randomness rather than an expectation over opponents' types.Source: §2 · pp. 6–7

Revenue objective

  • The objective is expected revenue over the joint distribution of all buyers' values, optimized over randomized mechanisms satisfying the incentive and participation conditions.The comparison class permits arbitrary finite real payments and is not limited to mechanisms with efficient descriptions.Source: §2 · pp. 6–7

Computational problems

  • The paper distinguishes computing optimal revenue from constructing an optimal mechanism, whose allocation and payment rules must have a finite, efficiently evaluable description.For algorithmic results, the distribution is encoded by rational support values and probabilities; time is measured in n + m + B.Source: §2 · p. 7

3 Optimal Auctions for Two-Point Values

For arbitrary numbers of buyers and items with i.i.d. two-point values, the paper constructs a deterministic auction that is optimal among randomized DSIC, ex-post IR mechanisms. Its revenue bound and conditional bundle offers yield a truthful implementation and exact polynomial-time computation.

3.1 The optimal mechanism

  • For every number of buyers and items, the deterministic auction is optimal among randomized DSIC, ex-post IR mechanisms, and its mechanism and expected revenue are computable in polynomial time.The result applies to rational input.Source: §3.1 · p. 9

3.2 A revenue bound from downward incentive constraints

  • A downward flow weighting incentive constraints yields a revenue upper bound whose all-low-item rent adjustment depends on the recipient’s exclusive high count.The auction’s allocation attains the bound by assigning all-low items using that count.Source: §3.1 · p. 8, §3.2 · p. 10

3.3 Truthful implementation by conditional bundle offers

  • Conditional bundle offers implement the allocation truthfully: with opponents fixed, a buyer’s bundle utility and price reflect her high-value count in items no opponent values highly.The resulting auction is deterministic, feasible, DSIC, and ex-post IR, with nonnegative payments.Source: §3.3 · pp. 11–12

3.4 Computing the mechanism and its revenue

  • The exact revenue algorithm groups items by whether they are all-low, have a sole high reporter, or have multiple high reporters, then aggregates counts with truncated polynomial products.It isolates the maximum exclusive-high count and has a rational bit-complexity analysis.Source: §3.4 · p. 12

4 Hardness with a Single Buyer

For one additive buyer with i.i.d. values from a general finite distribution, the paper proves exact-revenue and optimal-mechanism hardness. Its reduction preserves optimality of a choice between two explicit bundle prices while encoding a counting comparison in every optimum’s lowest-type allocation.

4.1 The computational problem and the main result

  • Exact revenue is #P-hard, and constructing an optimal single-buyer IC, IR mechanism is #P-hard unless FP contains #P, even with unary m and 2m + 2 support points.The hardness applies to rational support points in (0, 1] with positive rational probabilities.Source: §4.1 · p. 12
  • Every constructed instance has two explicit deterministic grand-bundle prices, and the better price is optimal among randomized IC, IR mechanisms.The reduction forces every optimum to allocate the full bundle to the lowest type with the same zero–one probability.Source: §4.1 · pp. 12–13

4.2 Two tied prices and the cost of departing from them

  • At a two-point prior where two bundle prices tie, retained incentive-constraint slack measures the revenue loss from departing from the original optimal family.The proof uses nonnegative summands in this loss bound.Source: §4.2 · pp. 13–14

4.3 Stability under a small perturbation

  • Under a sufficiently small perturbation, the gain from new types cannot offset the old revenue loss, and every optimum agrees with a comparison menu at all vertices.When the old loss is zero, allocations and payments at every vertex agree with that menu.Source: §4.3 · p. 14

4.4 How the perturbation reveals the count

  • Rare intermediate values encode a counting comparison through the revenue difference between endpoint prices; stability then forces the corresponding zero–one allocation choice at the lowest type.A paired-marker lemma converts the common alphabet into a subset-count encoding.Source: §4.4 · p. 15

5 Revenue Hardness with Two Items

For two items, exact revenue computation is #P-hard even with a common i.i.d. marginal and only K types per buyer. The reduction extracts conditional-menu capacity from revenue, builds a supply-constrained optimum encoding a counting statistic, and realizes its menus using a common prior.

5 Revenue Hardness with Two Items

  • Computing OPT(F; n, 2) is #P-hard under deterministic polynomial-time Turing reductions, even for unary n and an explicitly listed rational distribution on (0, 1].The reduction uses rational-threshold revenue queries; a sufficiently precise additive approximation would compute every #P function in polynomial time.Source: §5 · p. 15

5.1 Reading conditional-menu capacities from revenue

  • Polynomially many rational revenue comparisons recover the total capacity of revenue-tight menus within any 0 < e ≤ 1.A rare high value exposes a buyer’s maximum allocation through information rent, with a matching offer controlling the finite error.Source: §5.1 · p. 16

5.2 A supply optimum containing the encoded statistic

  • The supply-constrained capacity optimum is constructed to contain a positive-part expectation whose encoding recovers an exact-sum probability.The construction separates a baseline from a correction that arises when opponents share the same orientation.Source: §5.2 · p. 16, §5.3 · p. 17

5.3 Realizing every equality menu with a common prior

  • A rational scalar prior on 2J + 3 positive values makes the equality menus exactly the capacity cone Cκ, with their allocations and payments uniquely determined.Together, realizing the entire truthful menu family, evaluating its supply-constrained capacity, and extracting that capacity from revenue yield the reduction.Source: §5.3 · p. 17

6 Exact and Approximate Algorithms

For general finite rational priors, the section gives exact algorithms when any two of buyer count, item count, and support size are fixed, and a PTAS when item count alone is fixed. The appendix proves the two-point auction’s revenue bound, truthfulness, attainment, and polynomial-time evaluation.

6 Exact and Approximate Algorithms

  • The section’s algorithms for general finite rational priors complement the preceding hardness results by restricting buyer count, item count, or support size.The full finite-type linear program is one component of the fixed-item PTAS.Source: §6 · p. 17

6.1 Exact optimization under fixed parameters

  • Fixing any two of n, m, and K permits polynomial-time computation of both OPT(F; n, m) and an optimal randomized DSIC, ex-post IR mechanism.The mechanism’s marginal allocations and expected payments are exactly evaluable at any report profile.Source: §6.1 · p. 18

6.2 A PTAS for every fixed number of items

  • For every fixed 0 < ε < 1, fixing m yields a polynomial-time DSIC, ex-post IR mechanism with revenue at least (1 − ε) OPT(F; n, m), even when n and K are unrestricted.The algorithm uses separate single-item optimal auctions with many buyers and exact optimization otherwise.Source: §6.2 · p. 18

A.1 The conditional flow bound

  • A downward flow on the Boolean lattice combines weighted incentive constraints and lowest-type individual rationality into a lower bound on expected utility.Averaging the conditional bound over opponents and summing buyers yields the itemwise virtual-value revenue bound.Source: §A.1 · p. 22

A.2 The chosen flow and sale thresholds

  • The chosen flow and sale thresholds make the pointwise virtual-value bound attain the stated revenue upper bound when its tightness conditions hold.For all-low items, a larger exclusive high count raises virtual value; items with high reporters have highest virtual value b.Source: §A.2 · p. 23

A.3 Conditional transactions and DSIC

  • The threshold auction’s conditional transactions satisfy DSIC and ex-post IR, with nonnegative payments and feasible deterministic allocations.The proof compares truthful utility with deviations that induce either per-item trades or a discounted bundle.Source: §A.3 · p. 24

A.4 Attainment of the revenue bound

  • The auction attains the revenue bound by allocating items at their highest positive virtual value and retaining them when every virtual value is nonpositive.Its construction is deterministic and has nonnegative payments.Source: §A.4 · pp. 24–25

A.5 Exact computation of the mechanism and revenue

  • The mechanism and revenue can be evaluated in polynomial time by computing category-count probabilities with truncated polynomial multiplication.The resulting thresholds and payments have the same computational bound.Source: §A.5 · p. 25

A.6 Breakpoints and the high-value regime

For fixed p, a, and m, optimal revenue as the high value b varies is continuous, convex, and piecewise linear, with a bounded set of breakpoints. The appendix also gives a large-b auction rule, boundary cases, a paired-marker counting encoding, and technical revenue-loss identities.

A.6 Breakpoints and the high-value regime

  • For fixed p, a, and m, and n ≥ 2, optimal revenue as a function of b > a is continuous, convex, and piecewise linear, with at most m(m + 1)/2 breakpoints independent of n.Source: §A.6 · p. 26
  • For b ≥ bU, selling each item at b is optimal; for bL ≤ b < bU, a unique active buyer reporting at least m − 1 high values can receive the bundle at (m − 1)b + a.The rule otherwise sells each non-all-low item for b.Source: §A.6 · pp. 26–27

A.7 Boundary cases

  • The boundary cases include a single buyer’s bundle threshold and the one-item optimal revenue max{a, qb}.For one buyer and one item, either price gives the same revenue at equality.Source: §A.7 · p. 27

B Paired-Marker Encoding

  • Paired markers force one draw from each input pair, so the probability of the encoded target sum recovers the subset-counting quantity.The encoding has polynomial length in the number of input integers and their encoding length.Source: B Paired-Marker Encoding · p. 28

C.1 Normalization and the revenue-loss identity

  • Normalizing the lowest type’s utility to zero yields a revenue-loss identity whose nonnegative terms compare mechanisms with the constructed family Mz.The displayed edge constraints suffice for this identity, while feasibility still requires the full set of IC constraints.Source: §C.1 · pp. 28–29

C.2 Pointwise allocation and payment estimates

The technical estimates bound how far a normalized IC, IR mechanism’s vertex allocations, utilities, and payments can deviate from the constructed family. They support a perturbation argument showing that added types with sufficiently small probability cannot compensate for the base revenue loss.

C.2 Pointwise allocation and payment estimates

  • When δ = 0, the allocation and payment bounds vanish, and every vertex outcome agrees with Mz.The pointwise estimates bound nonempty-vertex allocation shortfalls and utility slacks in terms of δ.Source: §C.2 · pp. 29–30

C.3 Stability under a small perturbation

  • Adding sufficiently low-probability types cannot offset the base revenue loss; at an optimum, δ = 0 and vertex outcomes agree with Mz.The proof compares revenue on old vertices using two-sided bounds and controls the new types separately.Source: §C.3 · p. 31

C.4 Encoding a count in the winning price

The construction encodes a count threshold in a buyer’s bundle-price comparison. A half-integer offset keeps the comparison nonzero, while stability forces every optimum to make the corresponding lowest-type allocation choice.

C.4 Encoding a count in the winning price

  • Conditional on all m values being intermediate, the indices are independent and uniform, and t is the fraction of tuples whose increments reach the threshold.The event has unconditional probability η^m; fewer than m intermediate increments always sum to less than 1.Source: §C.4 · p. 32
  • Within the family Mz, choosing the reciprocal price using the known θ places the price comparison halfway between counts k and k + 1, making the slope nonzero.Stability forces δ = 0, so every optimum agrees at the vertices with a revenue-maximizing Mz.Source: §C.4 · pp. 32–33
  • The endpoint revenues are ma and ma + Pη^m(t − θ), so the optimal revenue is their maximum.The slope’s sign selects which endpoint-price menu is optimal.Source: §C.4 · p. 33

C.5 Verification of the rational perturbation

The perturbation creates a rational common marginal whose intermediate values separate sums below and above the target. The subsequent encoding and bit-length arguments make the count-recovery construction a polynomial-time reduction, including after scaling values into (0, 1].

C.5 Verification of the rational perturbation

  • The constructed marginal has exactly N + 2 positive rational support points, and its intermediate increments separate sums below the target from sums reaching it by at least γ.The endpoint probabilities and new intermediate mass give ∥F − F0∥1 = 2η.Source: §C.5 · pp. 33–34

C.6 The source count and valid queries

  • The paired-marker encoding makes Z_R − Z_{R+1} count exactly the tuples of sum R, with r! ordered tuples per solution subset.Binary search uses O(m log N) queries, and the half-integer threshold makes each query satisfy the proposition’s promise.Source: §C.6 · pp. 34–35

C.7 Encoding length and computational consequences

  • The construction has polynomial encoding length and takes polynomial time; scaling values and payments by a + 1 preserves feasibility, IC, IR, and optimal allocations.The scaled marginal has 2m + 2 rational support points in (0, 1], and optimal revenue is divided by a + 1.Source: §C.7 · p. 35

C.8 Completing the two computational reductions

The construction turns exact optimal-revenue queries into recovery of the encoded source count and establishes the claimed single-buyer hardness results. It also shows that an always-correct, expected-polynomial-time exact sampler for an optimum would yield zero-error expected polynomial-time algorithms for every #P function.

C.8 Completing the two computational reductions

  • Two exact revenue queries, followed by undoing the scaling, recover the source count; the constructed instances also have two grand-bundle prices that are optimal among randomized mechanisms.The reduction uses binary search and polynomial-length constructions.Source: §C.8 · p. 36

C.9 Exact sampling

  • An always-correct optimal-mechanism constructor with exact allocation sampling and uniform expected polynomial running time would give every #P function a zero-error expected polynomial-time algorithm.The forced lowest-type allocation bit can be read from one exact sample.Source: §C.9 · p. 36, §C.8 · p. 36

D.1 Completing the revenue-hardness reduction

  • Rounding the recovered estimates to the nearest integer yields each cardinality count N_k, whose sum is the source count.The count error is at most 1/(16s!) < 1/2.Source: §D.1 · p. 37
  • The two-item reduction uses polynomial-bit parameters and a polynomial number of revenue comparisons, with scaling preserving the common i.i.d. prior and values in (0, 1].The construction supports the stated polynomial-time Turing reduction with unary buyer count.Source: §D.1 · p. 37

D.2 Revenue extraction

Revenue extraction bounds the value of two-item mechanisms through the maximal allocation probabilities of their conditional menus. The capacity optimization constructs a feasible table attaining the capacity bound used in that extraction.

D.2 Revenue extraction

  • For every conditional menu, revenue is at most γ times the sum of its two capacities; a zero-gap mechanism attains the resulting bound σY_n.Replacing positive-gap vertices by the zero menu decreases allocations while preserving DSIC and IR.Source: §D.2 · p. 38
  • A finite high-value atom lets the base-mechanism objective approximate revenue, with the stated error bound CH/H.The construction augments menus with deterministic offers when exactly one buyer reports a type containing H.Source: §D.2 · pp. 38–39

D.3 The capacity optimum

  • The capacity optimum is attained by a feasible table formed by correcting residual capacities into the cone Cκ while preserving supply constraints.The construction leaves other capacities unchanged and uses reflected replacements for all-X and all-Y opponents.Source: §D.3 · pp. 39–40
  • The expected total capacity of the constructed optimum is given by (5.7), as established from the mean residual matrix and summed over buyers and orientations.The table’s capacities satisfy the cone correction relation w*_k = G(U_k(w*)).Source: §D.3 · pp. 40–41

D.4 The common-prior construction

This section develops the common-prior construction, giving a menu and dual certificate for its revenue bound and characterizing menus that attain equality. It also describes exit-report inversion, encoding and recovery of integers and geometric weights, and the use of separate single-item optimal auctions when there are sufficiently many buyers.

D.4 The common-prior construction

  • A nonnegative combination of IC and IR constraints is tight at the displayed menus; symmetry equates the positive-coefficient sums, identifying OPT(F; 1, 2) = 2γ.The probabilities are Pr(Z) = p², Pr(X0) = Pr(Y0) = pq0, and Pr(Xj) = Pr(Yj) = pr0(θ/2)^j for j ≥ 1.Source: §D.4 · pp. 42, 45
  • Every equality menu has capacities in Cκ and matches the constructed menu at every supported type; no equality menu exists outside Cκ.The characterization includes boundary capacities and zero-capacity cases.Source: §D.4 · p. 46

D.5 Exit reports and binomial inversion

  • Binomial inversion removes the exit class by grouping capacity variables according to the number of non-exit opponents, while preserving the fixed capacity region and allocation maps.The objective counts a buyer’s capacity even when her own report is exit, yielding a factor of n/(k + 1) in the grouped formula.Source: §D.5 · pp. 46–47

D.6 Encoding and precision

  • The encoding chooses integer offsets so the subset equation forces |A| = k and then reduces to the target-sum condition; paired indices give probability ratio 1/R.The encoding specifies B = s + 1, C = 1 + sAmax + T0, and M = 1 + s(C + Amax) + T0.Source: §D.6 · p. 47
  • The markers, targets, slopes, distributions, and revenue queries have polynomial encoding length, with no multibuyer-polytope denominator bound required.The extraction step uses a single-buyer polytope of dimension 3K^2 + 2.Source: §D.6 · p. 48
  • Revenue comparisons approximated at normalized high-atom precision ϵ = σe/(4H) keep extraction error below e, preserving inversion and integer recovery.The passage states that this precision has polynomial bit length.Source: §D.6 · p. 48

E Supporting Details for the Fixed-Item PTAS

  • When there are sufficiently many buyers, Section 6.2 uses separate single-item optimal auctions and records a competition bound and exact revenue calculation for a finite rational case.The supplied passage ends before specifying the rational object or the bound and calculation.Source: E Supporting Details for the… · p. 48

E.1 Proof of the approximation guarantee

The approximation proof combines separate Myerson auctions with an exact full-program fallback, and establishes the bounds and computation needed for this guarantee. The following subsections make the competition bound explicit and prove the exact-algorithm runtime through symmetry reductions.

E.2 Competition and exact separate revenue

  • The competition bound allows irregular distributions and atoms, and its Bayesian benchmark contains the DSIC benchmark; the proof also makes its integer bound explicit and computes Sn.The separate-auction calculation uses the ironed virtual-value distribution; fixed buyer priority resolves tied ironed scores.Source: §E.1 · p. 48, §E.2 · p. 49

E.1 Proof of the approximation guarantee

  • When n ≥ 100m/ε^2, separate Myerson auctions give bounds Sn and (1 + ε)Sn; otherwise the full program computes OPT exactly.The fallback has runtime KO(m(n+1)) poly(n, m, K, B).Source: §E.1 · pp. 48–49

F Proofs for the Exact Algorithms

  • Symmetry reductions for fixed buyer/support and item/support counts retain every fixed-opponent incentive constraint, supporting the exact-algorithm runtime bound.The resulting bounds include min{KO(m(n+1)), (m + 1)O(Kn+1), (n + 1)O(Km)} poly(n, m, K, B).Source: F Proofs for the Exact Algorithms · p. 49

F.1 Full and symmetry-reduced linear programs

The full and symmetry-reduced linear programs encode allocation, payment, and incentive constraints over type histograms. Symmetry yields polynomial-time exact optimization under parameter restrictions while retaining all deviations.

Full and symmetry-reduced linear programs

  • Adding the lowest type’s utility to every payment in a conditional menu preserves DSIC and IR and weakly increases revenue.The lowest type minimizes utility, and the reverse deviation followed by IR supports the payment adjustment.Source: §F.1 · p. 49
  • For fixed n and K, the item-symmetric LP represents every deviation through joint histograms, retaining simultaneous increases and decreases of reported values.The number of histograms is polynomial in m when n and K are fixed.Source: §F.1 · pp. 49–50
  • For fixed m and K, the buyer-symmetric LP uses type histograms and imposes full DSIC constraints for each reported-type deviation.The dot products use the true type on both sides of the incentive inequality.Source: §F.1 · p. 50
  • Exact rational LP optimization computes the optimum and an optimal solution within min{KO(m(n+1)), (m + 1)O(Kn+1), (n + 1)O(Km)} poly(n, m, K, B) time.The allocation-payment LP is compact for fixed n and m, and its outcome table can be evaluated by sampling recipients independently per item.Source: §F.1 · pp. 49, 51
Loading 2610.11051v1…