Theorem 4.1 — optimal equilibrium welfare is NP-hard
ProvedPricingWithTips.theorem_4_1_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 the maximum welfare attainable by a with-tip equilibrium 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_1_np_hard : NPHardMarketPredicate EquilibriumWelfareYes := by sorry end PricingWithTips
Source
Pricing with Tips in Three-Sided Delivery Platforms, arXiv:2507.10872v1, Theorem 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.