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.