KnapsackAuction
structureimported Lean
A knapsack auction with public weights w i and total capacity W. The underlying strategic object is a SingleParameterMechanism I U, where the value type U is a linearly ordered field ([Field U] [LinearOrder U] [IsStrictOrderedRing U]; e.g. ℚ, ℝ): each agent reports a single scalar value in U, receives an allocation level xᵢ ∈ U, and makes a U-valued payment. The pointwise allocation bounds are inherited from SingleParameterMechanism.IsAllocFeasible; the knapsack constraint is recorded separately below.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators in structure KnapsackAuction (I : Type*) (U : Type*) extends SingleParameterMechanism I U
- Defined in
- EconCSLib, `KnapsackAuction`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.KnapsackAuction← KnapsackAuction (EconCSLib/MechanismDesign/Auction/Knapsack.lean:77): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 3
- SingleParameterMechanismA single-parameter mechanism. Each agent
ihas a single private typeθ_i : R(their "value per unit"). The allocation gives each agent… - MechanismWithTransfersA mechanism with monetary transfers. -
I— agents -T— report/type space of each agent -A— allocation space -P— payment space… - SingleParameterMechanism.IsAllocFeasibleAllocation feasibility: each agent's allocation lies in
[0, 1]. RequiresZero R,One R, andLE R(e.g., any linearly ordered field).
- SingleParameterMechanismA single-parameter mechanism. Each agent
- Used by 45
- KnapsackAuction.sizeAgent
i's public weight. - KnapsackAuction.dpSolveList_supportedOnKnapsackAuction.dpSolveList_supportedOn
- KnapsackAuction.binaryToAllocation_fractionalFeasible_of_binaryRespectsCapacityKnapsackAuction.binaryToAllocation_fractionalFeasible_of_binaryRespectsCapacity
- KnapsackAuction.fractionalGreedyAllocationThe greedy fractional knapsack allocation obtained by sorting agents by value-to-weight ratio and then filling capacity in that order.
- KnapsackAuction.feasibleBinaryAllocationsThe finite list of binary allocations satisfying the knapsack constraint.
- KnapsackAuction.welfareMaximizerKnapsackAuction.welfareMaximizer
- KnapsackAuction.binaryRespectsCapacityCapacity feasibility for a binary allocation profile.
- KnapsackAuction.dynamicProgrammingOptimalValueThe social welfare achieved by the dynamic-programming allocation.
- KnapsackAuction.natFractionalGreedyListFractional greedy prefix algorithm on a natural-number remaining capacity: take each whole item if it fits, and otherwise take exactly the…
- KnapsackAuction.welfareMaximizer_geKnapsackAuction.welfareMaximizer_ge
- KnapsackAuction.binaryLoadThe weighted load induced by a binary allocation profile.
- KnapsackAuction.dynamicProgrammingOptimalAllocationThe computable knapsack allocation obtained by running the dynamic program on the full finite agent list.
- KnapsackAuction.welfareMaximizingAllocationRule_isMonotoneKnapsackAuction.welfareMaximizingAllocationRule_isMonotone
- KnapsackAuction.natFractionalGreedyValueWelfare of the ratio-sorted fractional greedy allocation.
- KnapsackAuction.welfareMaximizingAllocationRuleThe welfare-maximizing allocation rule for the knapsack auction, obtained by choosing a feasible binary allocation with maximal social…
- KnapsackAuction.BinaryRespectsCapacity_of_mem_feasibleBinaryAllocationsKnapsackAuction.BinaryRespectsCapacity_of_mem_feasibleBinaryAllocations
- KnapsackAuction.integralGreedyList_supportedOnKnapsackAuction.integralGreedyList_supportedOn
- KnapsackAuction.fractionalGreedyWelfare_ge_zeroOneWelfare_of_optimalIf the ratio-sorted greedy fractional allocation is optimal for the fractional relaxation, then its welfare dominates the welfare of the…
- KnapsackAuction.dpSolveListA computable dynamic-programming solver for finite
0/1knapsack instances. The solver processes the agents in the given list order and… - KnapsackAuction.IsFeasibleFeasibility for a knapsack auction: * each agent's allocation lies in
[0,1]* the weighted allocation satisfies the total capacity bound - KnapsackAuction.NonnegativeWeightsEvery public weight is nonnegative.
- KnapsackAuction.welfareMaximizer_mem_feasibleBinaryAllocationsKnapsackAuction.welfareMaximizer_mem_feasibleBinaryAllocations
- KnapsackAuction.ratioValue-to-weight ratio used by the fractional greedy rule.
- KnapsackAuction.integralGreedyAllocationThe ratio-sorted integral greedy allocation.
- KnapsackAuction.feasibleBinaryAllocations_nonemptyKnapsackAuction.feasibleBinaryAllocations_nonempty
- KnapsackAuction.integralGreedyValueWelfare of the ratio-sorted integral greedy allocation.
- KnapsackAuction.PositiveWeightsEvery public weight is strictly positive.
- KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highestKnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest
- KnapsackAuction.fractionalFeasibleFeasibility of a fractional knapsack allocation: pointwise fractions lie in
[0,1]and the weighted load respects capacity. - KnapsackAuction.welfareMaximizingPaymentRuleThe Myerson payment formula associated with the welfare-maximizing knapsack allocation rule.
- KnapsackAuction.ratioTieKeySorting key for the fractional greedy rule: higher ratio first, ties broken by the ambient linear order on
I. - KnapsackAuction.natFractionalGreedyAllocationThe ratio-sorted fractional greedy allocation on natural-number data.
- KnapsackAuction.fractionalGreedyListGreedy fractional allocation along a fixed list order. If the next item does not fully fit, the algorithm takes exactly the remaining…
- KnapsackAuction.RespectsCapacityThe allocation rule respects the knapsack capacity constraint.
- KnapsackAuction.sortedAgentsByRatioAgents sorted by decreasing value-to-weight ratio, with lexicographic tie-breaking via the ambient order on
I. - KnapsackAuction.natFractionalGreedyList_supportedOnKnapsackAuction.natFractionalGreedyList_supportedOn
- KnapsackAuction.NonnegativeCapacityThe knapsack capacity is nonnegative.
- KnapsackAuction.integralGreedyListThe integral greedy prefix algorithm: process items in a fixed order, take each whole item if it fits, and halt when the first item fails…
- KnapsackAuction.maximalSocialWelfareThe maximal social welfare over the feasible binary allocation space.
- KnapsackAuction.welfareMaximizingMechanismThe canonical welfare-maximizing single-parameter knapsack mechanism, with payments given by the Myerson formula.
- KnapsackAuction.zeroBinaryRespectsCapacityKnapsackAuction.zeroBinaryRespectsCapacity
- KnapsackAuction.capacityThe total capacity bound.
- KnapsackAuction.natAuctionDataThe knapsack-auction data obtained from natural-number weights and capacity, with dummy zero allocation/payment rules. This is only used…
- KnapsackAuction.natFractionalGreedyValue_le_integralGreedyValue_plus_highestKnapsackAuction.natFractionalGreedyValue_le_integralGreedyValue_plus_highest
- KnapsackAuction.exists_welfareMaximizerA welfare-maximizing feasible binary allocation, chosen using
List.argMaxOnon the finite space of feasible0/1allocations.
- KnapsackAuction.sizeAgent
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators in /-- A knapsack auction with public weights `w i` and total capacity `W`. The underlying strategic object is a `SingleParameterMechanism I U`, where the value type `U` is a linearly ordered field (`[Field U] [LinearOrder U] [IsStrictOrderedRing U]`; e.g. `ℚ`, `ℝ`): each agent reports a single scalar value in `U`, receives an allocation level `xᵢ ∈ U`, and makes a `U`-valued payment. The pointwise allocation bounds are inherited from `SingleParameterMechanism.IsAllocFeasible`; the knapsack constraint is recorded separately below. -/ structure KnapsackAuction (I : Type*) (U : Type*) extends SingleParameterMechanism I U where /-- Public weight / size of agent `i` in the knapsack constraint. -/ weight : I → U /-- Total knapsack capacity. -/ totalCapacity : U