Optimally Procuring Homogeneous Goods from Multiple Agents with Private Costs

Procuring data for machine learning often requires compensating providers whose costs are privately known and vary with the quantity supplied. Motivated by this, we study how a principal procures homogeneous goods (i.e. her value depends only on the total amount procured) using payment menus that specify compensation for each production level. Each agent produces at most $M$ units at a cost drawn independently from a known distribution over $K$ types. The principal wishes to maximize her expected value less payments. We first study the single-agent setting, establishing NP-hardness via a reduction from revenue-optimal unit-demand pricing. We then give an exact algorithm running in time $(M+1{)}^K\text{poly}(K,M)$: it enumerates candidate production profiles across the $K$ types and solves a linear program for the optimal menu inducing each. Under an ordering condition on the types' cost curves (satisfied by linear costs as a special case), we obtain an exact $\text{poly}(K,M)$-time algorithm. In the multi-agent setting, posting one menu to all agents simultaneously fails: to avoid overproducing, the principal must equally distribute the task among agents; each agent suffers from high startup costs due to economy of scale. We therefore study a sequential model in which agents arrive over $T$ rounds and the principal's value depends on their total production. With adaptive menus, where the principal may revise the menu on each round, an exact dynamic program over single-agent subproblems runs in time $(M+1{)}^K\text{poly}(K,M,T)$, and in $\text{poly}(K,M,T)$ time under the ordering condition. With static menus, where the principal commits to a fixed menu but may close the market at any round, a tree representation of candidate menus yields a $(K+1{)}^{K-1}(M+1{)}^{K-1}\text{poly}(K,M,T)$ algorithm.