KnapsackAuction.dpSolveList
defimported Lean
A computable dynamic-programming solver for finite 0/1 knapsack instances. The solver processes the agents in the given list order and uses the standard "skip or take" recursion on the remaining capacity. This is the algorithmic counterpart to the abstract welfare-maximizer above, specialized to natural weights, natural capacity, and natural reported values.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open KnapsackAuction in open scoped BigOperators in variable {I : Type*} [Fintype I] [DecidableEq I] in def KnapsackAuction.dpSolveList (w b : I → Nat) : List I → Nat → BinaryAllocation I
- Defined in
- EconCSLib, `KnapsackAuction.dpSolveList`
- 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.dpSolveList← KnapsackAuction.dpSolveList (EconCSLib/MechanismDesign/Auction/Knapsack.lean:570): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 4
- KnapsackAuction.BinaryAllocationA discrete knapsack allocation profile: each agent is either selected or not.
- KnapsackAuction.natBinarySocialWelfareInteger-valued welfare of a binary allocation profile.
- KnapsackAuctionA knapsack auction with public weights
w iand total capacityW. The underlying strategic object is aSingleParameterMechanism I U,… - KnapsackAuction.capacityThe total capacity bound.
- Used by 4
- KnapsackAuction.dpSolveList_supportedOnKnapsackAuction.dpSolveList_supportedOn
- KnapsackAuction.natFractionalGreedyListFractional greedy prefix algorithm on a natural-number remaining capacity: take each whole item if it fits, and otherwise take exactly the…
- KnapsackAuction.dynamicProgrammingOptimalAllocationThe computable knapsack allocation obtained by running the dynamic program on the full finite agent list.
- 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…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open KnapsackAuction in open scoped BigOperators in variable {I : Type*} [Fintype I] [DecidableEq I] in /-- A computable dynamic-programming solver for finite `0/1` knapsack instances. The solver processes the agents in the given list order and uses the standard "skip or take" recursion on the remaining capacity. This is the algorithmic counterpart to the abstract welfare-maximizer above, specialized to natural weights, natural capacity, and natural reported values. -/ def KnapsackAuction.dpSolveList (w b : I → Nat) : List I → Nat → BinaryAllocation I | [], _ => fun _ => false | i :: is, capacity => if w i ≤ capacity then let skip := dpSolveList w b is capacity let takeTail := dpSolveList w b is (capacity - w i) let take := Function.update takeTail i true if natBinarySocialWelfare b take ≥ natBinarySocialWelfare b skip then take else skip else dpSolveList w b is capacity termination_by items _ => items.length