we-solve (beta)

Econ-110 · economics · computer science · Computational economics

Simple combinatorial bidding

LLM status Open unverified

Statement

Original subject group: Mechanism design and market design

Audit classification: Published research agenda. Roth 2010 §1 and the 2024 auction survey §4.3 supply simplicity agendas. The combined cognitive/communication frontier is editorial; unrestricted real-valued messages make a message-count bound meaningless.

Definitions and precise research target

Model and research target. Let $G$ be $m$ indivisible goods and $n$ bidders have nonnegative monotone values $v_i:2^G\to[0,1]$. Let $\mathcal V$ be a prespecified class of valuation profiles admitting both substitutes and complements, with optimal feasible welfare $\operatorname{OPT}(v)>0$. A bidding interface $I$ allows at most $k$ messages, each encoded in at most $b$ bits, or a separately specified value-query format and has measured decision time $C_i(I)$. Together with allocation and payment rule $M$, it induces a distribution of submitted bids and final allocations $A_i$ for a target bidder population $P$. Define the performance frontier \[ F(k,c)=\sup_{I,M:\sup_{v\in\mathcal V}E_{K_P(\cdot\mid I,M,v)}[C_i(I)]\leq c} \inf_{v\in\mathcal V}\frac{E_P[\sum_i v_i(A_i)]}{\max_{A\text{ feasible}}\sum_i v_i(A_i)}, \] subject to a specified participation and incentive requirement. Declare whether the behavioral response is a rational equilibrium, a calibrated learning model, or an experimentally measured distribution; these interpretations cannot be interchanged. Characterize useful attainable guarantees and complexity costs, design interfaces approaching the frontier, and validate performance under unfamiliar valuations and bidder experience. For strategic guarantees, state the equilibrium concept and exclude arbitrary nonparticipation; for experimental guarantees, quantify sampling uncertainty.

Definitions and maintained assumptions (editorial unless a source definition is named). Feasible allocations are disjoint bundles $A_i\subseteq G$, and $\mathrm{OPT}(v)=\max_A\sum_i v_i(A_i)$. To make $k$ constrain communication, restrict each message to an alphabet of at most $2^b$ symbols (at most $b$ bits), or specify a concrete bundle/value query format with fixed precision. A single arbitrary real message can encode an entire finite valuation table, so raw message count is not a meaningful information bound. Rational values with input bit length $B$, or a value-oracle model, specify computational input. For each $(I,M,v)$, define a behavioral kernel $K_P(\text{bids}\mid I,M,v)$ for the target population. Time expectation must be conditional on valuation profile; use $\sup_{v\in\mathcal V}\mathbb E_{K_P}[C_i]\le c$ for a worst-case frontier. Incentive and participation conditions must be consistent with that kernel. The ratio is defined only for $\mathrm{OPT}(v)>0$. The supremum ranges over implementable interfaces satisfying an announced representation/operation budget.

Variants and assumption changes

  1. Strategic bit budget (editorial). Require dominant-strategy truthfulness and ex-post IR on a specified substitutes or complements domain, with at most $kb$ communicated bits. Seek worst-case welfare guarantees and information lower bounds.
  2. Human interfaces (editorial). Fix a finite set of implementable interfaces and estimate bidding/time kernels experimentally. Compare held-out welfare under identical valuation and population distributions; this empirical frontier cannot automatically inherit rational-equilibrium guarantees.

References and source audit

  1. Roth §1 p.3; Palacios-Huerta et al. §4.3 pp.23–25. Supports the stated research area; exact displayed specification is editorial. https://web.stanford.edu/~alroth/papers/NSF%20Grand%20Challenge.SBE%202020.%20Market%20Design.pdf
  2. Roth §1 p.3; Palacios-Huerta et al. §4.3 pp.23–25. Supports the stated research area; exact displayed specification is editorial. Original LSE fetch failed; full manuscript recovered from Harvard author page. https://parkes.seas.harvard.edu/sites/g/files/omnuum8711/files/parkes/files/palacios-huerta.pdf
  1. Alvin E. Roth. 2010. Market Design: Understanding markets well enough to fix them when they’re broken. §1 Fundamental questions, pp.3–4. https://web.stanford.edu/~alroth/papers/NSF%20Grand%20Challenge.SBE%202020.%20Market%20Design.pdf.
  2. Ignacio Palacios-Huerta; David C. Parkes; Richard Steinberg. 2024. Combinatorial Auctions in Practice. §4.3, printed pp.23–25, Harvard author manuscript; published JEL62(2),517–553 (2024). https://parkes.seas.harvard.edu/sites/g/files/omnuum8711/files/parkes/files/palacios-huerta.pdf. DOI: https://doi.org/10.1257/jel.20221679.

Common conventions: Source mathematical conventions

These conventions apply to each entry unless explicitly replaced.

Models and identification. A primitive model $m$ specifies all probability laws, feasible choices, information, equilibrium and measurement rules used by its target. The admissible class $\mathcal M$ is fixed independently of outcomes. If $P_O(m)$ is its observable probability law and $\tau(m)$ the target, its identified set at observable law $P$ is \[ \mathcal I_\tau(P)=\{\tau(m):m\in\mathcal M,\ P_O(m)=P\}. \] Point identification means that this set is a singleton. An empty set signals incompatibility of data and assumptions. Coordinate bounds need not describe the joint set. Bounds are sharp only if every retained target is attainable or arbitrarily approachable by compatible models. Finite bounds require explicit restrictions on unobserved quantities; unrestricted confounding, hidden wealth, extrapolation or arbitrary equilibrium selection can yield uninformative sets.

Causal interventions. A potential outcome $Y_i(p)$ is the outcome under a complete policy regime $p$, including timing, financing, information and market spillovers. The target population and units are fixed before treatment. With interference, use the complete assignment vector or a justified exposure mapping; individual no-interference notation alone cannot identify an economy-wide intervention. A difference of mean potential outcomes does not require the cross-world joint distribution. Conditioning on post-treatment migration, survival, enrollment or employment changes the estimand and needs separate justification.

Statistical statements. An estimator, confidence set, forecast or test specifies a sampling law, model class and loss/coverage criterion. Uniform $(1-\alpha)$-coverage means $\inf_{m\in\mathcal M}\Pr_m\{\tau(m)\in C_n\}\geq1-\alpha$, or an explicitly asymptotic version. The whole parameter space trivially has coverage, so informativeness requires a stated width, risk or power objective. A forecasting improvement is relative to a named benchmark, information set and evaluation population.

Equilibrium and optimization. An equilibrium comprises feasible plans, optimality, beliefs where needed, budget constraints and all market/resource clearing. The primitives or a stated benchmark define each correspondence $\mathcal E(p;m)$. Nonemptiness is assumed or proved, never inferred just from compact policy sets. A selected-equilibrium target uses a declared selection rule; a robust target quantifies over all permitted equilibria. Use suprema or infima unless attainment is established. An $\varepsilon$-optimal policy is feasible and within $\varepsilon$ of the finite optimum value. Report an empty feasible set separately.

Welfare and accounting. Normative utility, interpersonal normalization, social weights, numeraire, discounting and the use of public receipts are primitives. Behavioral utility need not coincide with the welfare criterion. Household welfare includes ownership income and rents once; adding profits again to compensating variation generally double-counts them. A monetary equivalent is defined by an explicit transfer and price convention, with monotonicity and range conditions. Average effects, mechanism contributions, transfers and welfare losses are different targets. Infinite sums require convergence and dynamic feasible plans require terminal or no-Ponzi conditions.

Source versions. A working-paper date, revision date and journal publication year are distinguished. A DOI for a journal version is not automatically the DOI of an earlier manuscript. Locators refer to the stated version and printed pages where specified. A metadata-only check does not verify a claim about a full-text conclusion. Every entry's source subsection narrows the provenance claim accordingly.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-110-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-110

Communication, complements, and covering menus

Problem ID: D44-108. Status: Unresolved. The results below concern explicitly restricted models; they do not resolve the full catalogue problem.

A precise restricted frontier

The original question asks how communication and cognitive limits constrain welfare in combinatorial bidding, under declared incentives and behavioral responses. We solve a restricted deterministic communication problem with one privately informed complement bidder and one public additive bidder. It already exhibits an exponential menu requirement in some regimes. We do not identify a human decision-time frontier or cover general valuations.

Let $G$ have $m$ goods, $1\le r\le t\le m$, and $0<c<1/m$. Bidder 1 privately knows $S\subseteq G$ with $|S|=r$ and values a bundle $A$ by \[ v_S(A)={\mathbf 1}\{S\subseteq A\}. \] Bidder 2 has the publicly known additive value $v_2(A)=c|A|$. All values lie in $[0,1]$. Both have quasilinear utility and outside allocation/payment zero. Feasible allocations are disjoint. Define \[ W_*=1+c(m-r),\qquad W_t=1+c(m-t),\qquad N=\binom mr. \] The efficient allocation gives $S$ to bidder 1 and $G\setminus S$ to bidder 2, so its welfare is $W_*$ for every type. Communication is one-way and deterministic: bidder 1 selects one of at most $L$ messages and the mechanism implements a fixed allocation and transfers for each message. A deterministic prescribed response must satisfy dominant-strategy optimality. For the lower bound we even allow an arbitrary deterministic response, making the impossibility stronger.

Counting and implementation

Theorem (Matching communication bounds up to a logarithmic covering factor): Any deterministic $L$-message mechanism whose prescribed outcome has welfare at least $W_t$ for every $r$-set $S$ must satisfy \[ L\ge\frac{\binom mr}{\binom tr}. \] Conversely, there exists an individually rational posted-menu mechanism with truthful utility-maximizing selection, worst-case welfare at least $W_t$, and \[ L\le\left\lceil\frac{\binom mr}{\binom tr}(1+\log N)\right\rceil. \] It communicates a menu index using $\lceil\log_2(L+1)\rceil$ bits, including the outside option. The additive bidder needs no message. Thus the necessary and sufficient numbers of messages differ by at most a factor of order $1+\log N$.
Proof: Consider any message used by at least one type and let $A$ be its allocation to bidder 1. If some type mapped to this message has $S\not\subseteq A$, its welfare is at most $cm<1\le W_t$, a contradiction. Thus $A$ contains every $S$ using the message. Even if all remaining goods go to bidder 2, welfare is at most $1+c(m-|A|)$. The promised bound implies $|A|\le t$. A message can therefore serve at most $\binom tr$ of the $N$ possible types. Covering all types proves the lower bound; transfers cannot change welfare in this calculation.

For the upper bound, draw independently $L$ uniformly random $t$-subsets of $G$. A fixed $r$-set is contained in a draw with probability \[ p=\frac{\binom{m-r}{t-r}}{\binom mt}=\frac{\binom tr}{\binom mr}. \] Its probability of remaining uncovered is $(1-p)^L\le e^{-pL}$. The union bound makes the probability that any type remains uncovered at most $Ne^{-pL}<1$ for the stated $L$. A covering family $\mathcal T$ of that size consequently exists. Repeated members may be removed. This is a finite existence proof; exhaustive enumeration can construct one, without a polynomial-time claim.

For each $T\in\mathcal T$, offer bidder 1 the bundle $T$ at price $ct$ and give the complement to bidder 2. Pass the payment $ct$ to bidder 2. A bidder whose true demand is $S$ obtains $1-ct>0$ from any covering menu entry, obtains $-ct<0$ from any noncovering entry, and obtains zero from nonparticipation. Every utility-maximizing response therefore selects a cover, giving welfare exactly $W_t$. Bidder 1 is individually rational. Bidder 2 receives value $c(m-t)$ and cash $ct$, totaling its full-endowment value $cm$, so it accepts voluntarily. Transfers balance. Selecting a maximizer is dominant because the second valuation is public and no other strategic report affects the menu. ∎

The theorem can be stated as a direct mechanism by fixing a deterministic rule selecting a covering $T(S)$. Truthful reporting gives maximal attainable utility; a false report cannot give greater utility, even if it selects a different covering set. The mechanism is truthful, though truth-telling need not be a unique best response. Every best response still attains the welfare guarantee.

Corollary (Bit cost and the exact-efficiency endpoint): If at most $B=kb$ bits may be sent in the stated one-way model, attaining welfare ratio $W_t/W_*$ requires \[ B\ge\log_2\binom mr-\log_2\binom tr. \] For $t=r$, exact efficiency requires $L\ge\binom mr$ and is attainable with exactly that many active menu entries. If $r\le t$ then \[ \frac{\binom mr}{\binom tr} =\prod_{j=0}^{r-1}\frac{m-j}{t-j}\ge(m/t)^r. \] In particular, for $r$ proportional to $m$ and $t\le\zeta m$ with fixed $\zeta<1$, the number of required messages grows exponentially with $m$.
Proof: There are at most $2^B$ messages. Apply the theorem. At $t=r$ the family of all $r$-sets is an exact covering menu, and no set of size at most $r$ covers two distinct types. The product identity is factorial cancellation. Each factor is at least $m/t$ since $t\le m$. ∎

The lower bound concerns menu cardinality. Its logarithm is a bit bound, so exponential menu size does not by itself imply exponentially many bits. Conflating these quantities would reverse the intended interpretation of simplicity.

A concrete welfare tradeoff

Take $c=\gamma/m$ for fixed $0<\gamma<1$, $r=\alpha m$, and $t=\zeta m$ when these are integers. The posted menu guarantees \[ \frac{1+\gamma(1-\zeta)}{1+\gamma(1-\alpha)} \] and requires at least $(1/\zeta)^{\alpha m}$ messages in the deterministic model. Giving the grand bundle to bidder 1 always attains $1/[1+\gamma(1-\alpha)]$ with a single active message. The cost of preserving surplus for the additive bidder can therefore be quantified without assuming that complementary values can be communicated through independent item bids.

The interface has a simple operational implementation once a cover family is fixed: display its members and their common price; a bidder can inspect all $L$ sets, test containment using at most $mL$ elementary membership comparisons, and submit an index. This is an upper bound on an explicit computational procedure, not a prediction of human time. Construction of a smallest covering family is also a separate combinatorial problem; the probabilistic upper bound is not an efficient optimization algorithm for it.

Boundaries of the result

Randomized allocation, randomized communication, interactive queries, multiple informed complement bidders, and uncertainty about the additive valuation are absent. The deterministic counting proof does not automatically apply when a type can receive its desired set only with high probability; then a distributional or randomized communication lower bound is needed.

For a behavioral application, the rational response kernel in the theorem would need replacement by a measured menu-selection kernel. Selection failures, experience, display order, and search costs can then reduce the computed welfare guarantee. No experimental estimates have been supplied here. The exact covering-menu calculation supplies a benchmark against which such evidence could be compared, while the original population-specific frontier remains unresolved.

References

Completion Estimate

25%

Go to contribution →