Theorem 4.2 — optimal welfare is NP-hard
ProvedPricingWithTips.theorem_4_2_np_hardcomputational-complexitymarket-design
For three-sided delivery markets with equally many buyers, stores, and couriers, every buyer-store valuation equal to one, and delivery costs in {0,1}, deciding whether maximum feasible-allocation welfare equals the common cardinality is NP-hard under polynomial-time many-one reductions.
Preamble
import Definitions.Def_PricingWithTips_NPHardness
Formal statement
namespace PricingWithTips theorem theorem_4_2_np_hard : NPHardMarketPredicate WelfareYes := by sorry end PricingWithTips
Source
Pricing with Tips in Three-Sided Delivery Platforms, arXiv:2507.10872v1, Theorem 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.