Stochastic Packing-Market Planning Dan Golovin In traditional mechanism design problems, the mechanism receives its inputs from various strategic players, and must select an outcome and payment scheme with the goal of providing the proper incentives to the selfish players to achieve an optimal outcome, for various objective functions. A well-studied special case of this problem is to design mechanisms for combinatorial auctions to maximize social welfare. We consider a variant of this problem in which there is probabilistic demand and participants associate some cost with participating (e.g., by waiting until their demand is sampled and then attending the auction, they incur some opportunity cost). We call this the Stochastic Packing-Market Planning problem (SPMP), which is a stochastic generalization of the Maximum k-Set Packing problem. We provide an approximation algorithm and mechanism for SPMP, and also give a linear programming based approximation for the expected weight of a maximum set packing in a random subhypergraph of a fixed hypergraph G, using techniques which may be of independent interest.