A typical application is a seller who wants to sell some items to potential buyers.
The optimal prices depend on the amount that each buyer is willing to pay for each item.
The major research question in PIM design is: what is the sample complexity of the mechanism?
I.e, how many agents it needs to sample in order to attain a reasonable approximation of the optimal welfare?
The results in [1] imply several bounds on the sample-complexity of revenue-maximization of single-item auctions:[2] The situation becomes more complicated when the agents are not i.i.d (each agent's value is drawn from a different regular distribution) and the goods have limited supply.
, which immediately translates to a bound on their generalization error and sample-complexity.
Devanur et al study a market with different item types and unit demand agents.
[5] Chawla et al study PIMs for the makespan minimization problem.
The approximation guarantees of BOM and PIM are in expectation, while those of PFM are in worst-case.