acceptodds
Under review as a conference paper at ICLR 2027

Optimally Procuring Homogeneous Goods from Multiple Agents with Private Costs

Abstract

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 units at a cost drawn independently from a known distribution over 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 : it enumerates candidate production profiles across the 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 -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 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 , and in 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 algorithm.

Primary area:
optimization
Keywords:
procurement, data acquisition, contract design, adverse selection, screening, pricing

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gDtVOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies how to set payments for different quantities of homogeneous goods or data to maximize the buyer's expected utility. It gives exact algorithms for general costs, faster algorithms for ordered costs, and treats both adaptive and fixed payment menus.

Critical strengths
  1. The static-menu analysis identifies the key issue: the same type may need to produce different quantities in different rounds. Preserving all best responses and enumerating menus through a tree representation avoids a candidate set that grows exponentially with the number of rounds. (pp. 8–9, Theorem 8)
  2. The paper clearly separates general and ordered costs, with complete arguments for the reductions, minimum-payment recurrence, and dynamic programs. (pp. 4–8)
Critical weaknesses
  1. The static result relies on the buyer choosing a quantity based on the current state whenever the supplier is indifferent. This is exactly what creates the advantage in Example 1: a fixed small price perturbation cannot make the same type uniquely choose two units first and one unit later. The assumption is explicit, but it limits practical applicability. (p. 8)
  2. The general algorithms still enumerate many candidates. Having fewer types than the maximum production level does not by itself make computation practical, and the paper does not explain what problem sizes are manageable. (p. 2; Theorems 4 and 8)
Questions for authors
  1. How sensitive are static menus to errors in costs or implementation? How much of the gain in Example 1 remains when the supplier is no longer exactly indifferent?
  2. What numbers of types, maximum production levels, and horizon lengths can the general algorithms handle in practice? This would help clarify their scope for data procurement.
1 comment
AuthorsOpenReview ↗

On tie-breaking robustness and scalability

Reviewer gDtV:

Thank you for recognizing the technical insight behind the static algorithm, and for raising the questions about robustness and scalability.

Tie-breaking robustness: It is known in item pricing that small perturbations could lead to large losses due to buyers switching to much cheaper items (see Hartline and Koltun (2005), §2 and §5). There is a similar robustness concern in our setting. For example, if we perturb the payments to force a unique best response for each agent, then the optimal principal utility in Example 1 drops from 1.41.4 to at most 11. In particular, the utility of 1.41.4 comes from procuring two units in one round and one unit in the second. If the principal can only repeat a unique best-response production level, the best thing she can do is to collect two units for one or two rounds, both resulting in utility at most 11. She can approach this bound by changing the payment of two units to 1+ε1+\varepsilon. This gives utility 1−ε1-\varepsilon for one round and 1−2ε1-2\varepsilon for two rounds. Thus, even arbitrarily small payment errors can eliminate the 0.40.4 utility gain in this example. We will clarify this sensitivity when discussing the static model.

However, if we remove the strategic advantage that the principal may tie-break differently at different rounds, then we might have a simpler algorithm. Say we force the principal to fix a particular production level for each type beforehand. In this case, we can discard the tree formulation in §6.2. Instead, we may enumerate all production profiles with their cheapest menus, and use a DP to compute the optimal stopping policy for each. This results in a similar (M+1)Kpoly⁡(K,M,T)(M+1)^K \operatorname{poly}(K,M,T) runtime as in the adaptive case. However, such an algorithm exactly fails to reconstruct the optimal utility in Example 1.

Scalability: Under general costs, the exact algorithms are best suited to instances with few cost types KK and a modest range of production levels MM. The adaptive algorithm enumerates (M+1)K(M+1)^K production profiles per DP state, while the static algorithm enumerates at most (K+1)K−1(M+1)K−1(K+1)^{K-1}(M+1)^{K-1} labeled trees. Increasing KK raises the exponent on M+1M+1 in both and the tree-count factor in the static case. For fixed KK, the enumeration grows polynomially in MM, though the degree can still make large MM costly. The horizon TT affects only the O(T2M)O(T^2M) DP state count and leaves both enumeration sizes unchanged. We will clarify these tradeoffs in the paper.

Reviewer_zEFkOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper examines how a principal can design payment menus to procure a homogeneous good from suppliers with privately known production costs. The principal knows the possible cost functions and their distribution, but not the supplier's realized type. The objective is to maximize the principal's expected value of the total quantity procured minus the payments made to suppliers. This paper considers both single-agent and multi-agent settings.

Critical strengths
  • For the single-agent setting, this paper presents polynomial-time reductions in both directions between single-agent procurement and revenue-optimal unit-demand item pricing. This shows the strong NP-hardness of the studied problem, even when the principal’s valuation is linear. Authors then propose an exactly optimal algorithm running in (M+1)Kpoly(K,M)(M+1)^K \text{poly}(K,M) and a fast exact algorithm under ordered marginal costs.

  • For multi-agent setting, authors show that offering a common payment menu to multiple agents simultaneously can decrease the principal's optimal expected utility as the number of agents increases, due to overproduction and economies of scale.

  • The authors develop an exact dynamic programming algorithm for sequential procurement with adaptive menus. Each state is reduced to a single-agent procurement problem with a continuation-adjusted valuation function.

  • This paper provides efficient adaptive procurement under ordered costs, and also develops an exact algorithm for sequential procurement with a fixed payment menu.

Critical weaknesses
  • My major concern is on the assumption that agents report all their utility-maximizing production levels and that the principal can select among them. This assumption is particularly important for the static-menu algorithm, where different tied best responses may be selected at different rounds.

  • The adaptive mutl-agent algorithm seems standard to me, in the sense that dynamic programming plus static mechanism optimization oracle is standard.

Questions for authors

I hope the authors can address my major concern on the tie-breaking issue.

2 comments
AuthorsOpenReview ↗

On principal-favorable tie-breaking and the adaptive multi-agent algorithm

Reviewer zEFk:

Thank you for your assessment and for highlighting these two concerns.

Principal-favorable tie-breaking: We recognize that allowing the principal to select among indifferent outcomes is a modeling assumption. Our intent is to carry principal-favorable tie-breaking, a standard notion in item pricing [1, 2], consistently into multi-agent procurement. In item pricing, when a buyer is indifferent between several utility-maximizing items, it is usually assumed that the ties are broken in favor of the seller (there, this translates to a simple rule where the seller selects the highest-price item for highest revenue). Similarly, in single-agent procurement, when several production levels maximize an agent’s utility, the principal selects the production level that maximizes her valuation minus payment. Adaptive multi-agent follows the same tie-breaking rule for each round, because it is fundamentally single-agent problems stacked together. Principal-favorable tie-breaking is straightforward in all these cases.

[1] Chawla, Hartline, and Kleinberg. Algorithmic Pricing via Virtual Valuations. EC 2007, §2, footnote 2.

[2] Chen, Diakonikolas, Paparas, Sun, and Yannakakis. The Complexity of Optimal Multidimensional Pricing. SODA 2014, §2.1.

However, static multi-agent is different. In this case, the principal’s preferred choice among tied production levels can depend on cumulative production and the remaining horizon. This is seen in Example 1 in §6.2, where fixing any single best-response production level across all rounds is suboptimal. Thus, we allow the principal to preserve all agent best responses in each round and select according to her needs. There is no simple rule for principal-favorable tie-breaking in this case. We will clarify this rationale when introducing this assumption.

Adaptive multi-agent: The adaptive multi-agent algorithm reduces each state to a single-agent procurement problem with a continuation-adjusted valuation. This allows our single-agent algorithms, including the ordered-cost one, to apply directly. We do not intend to present the Bellman decomposition itself as the main technical innovation. The more substantial ones include the ordered-cost algorithm in §4.2 and the tree-based static multi-agent algorithm in §6.2. Unlike the adaptive setting, the static setting requires a different construction that preserves multiple best responses. We will make this distinction clearer.

Thank you for the detailed response and clarifications. While I still consider the tie-breaking assumption a limitation, I find the overall contributions interesting and will maintain my positive assessment.

Reviewer_WTduOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

ABSTRACT

"Procuring data for machine learning" -> explain this for what purpose; motivate the procurement of data

"vary with the quantity supplied." -> what is the quantity here?

"homogeneous goods" -> a seller also has homogeneous copies?

"payment menus " -> what are menus? What is the production level here?

What is the transition to the next sentence about "each agent" ... are agents providers here? Why is M the same for each agent? Why is the cost over K types only? I wonder how realistic this assumption is

"wishes to maximize her expected value less payments." -> minus; maximize her value by doing what? you need to state this more explicitly

"We first study the single-agent setting" -> why can't you do a reduction from a knapsack variant where the obj is value minus cost?

"We then give an exact algorithm" -> with running time? "candidate production " > what is this? you can just explain this in plain english I think you should explain poly(K,M)

"an ordering condition on the types’ cost curves" -> what is the meaning of this?

"In the multi-agent setting, posting ..." -> this sentence doesn't make sense; they are not producing anything (so why over production?), high startup costs? economy of scale? It has nothing to do with economies of scale; then don't do posting one menu, then why do you have to use it to motivate the sequential model?

"an exact dynamic program over single-agent" -> what problem does it solve? Do you solve each t independently? I am not clear

"may close the market at any round," -> what does this mean? T is given as input right?

Are these like exact algorithms?

1 INTRODUCTION

"In many applications of interest," -> for these applications, can you provide specific use cases?

"The same structure appears well beyond data ..." -> what structure are you referring to?

"her" -> how is her the right word for data center? accelerators are not homogeneous

"person-hours " -> ???

"She " -> i would be gender neutral

what is the meaning of "a menu of payments"?

"Each agent then best responds" -> this sounds more like equilibrium computation

"producing the quantity that maximizes her payment less her costs" -> minus; producing doesn't mean that the principal will buy it right? this implies you have no budget constraint; so then you need to make procurement decisions

"This setting poses three distinct challenges. " -> no it doesn't; you didn't show anything challenges so this setting doesn't show any challenges to begin with; you are making the challenges here artificially yourself

"the distribution from which agents’ costs" -> why is this realistic? why is this a challenge? "a payment sufficient to induce production" -> what is the connection of this sentence to your argument? what is the meaning of while higher payments erode her utility?

"payments offered at different quantities must be chosen jointly" -> jointly as in you offer the same prices to each agent?

"Third, the menu may depend only on the quantity an agent supplies, " -> i am confused what is the agents reporting? in general you payment computations are based on the input of bids from others which depend on the sellers

1.1 SUMMARY OF OUR CONTRIBUTIONS

there is no transition to here

"anonymous payment menu" -> you didn't define anonymous or payment menu; why does it have to be anonymous?

why a known distribution over K? how do you motivate that? Why do you cap them at M? why does it have to be discrete?

"the agent best responds by maximizing ..." -> ok so where are the purchasing decisions? "with ties resolved in the principal’s favor" -> why? it should be in the best interest of the agent

Where is the procurement decision here? This should be explained explicitly, so the whole point of the principal is to buy something

"In Alzheimer’s data ..." -> provide citations in these examples

"We first give polynomial-time reductions ..." -> so the two problems are the same or not?

"This reduction transfers" -> transfers?

"However, as we are interested in the large " -> however as in? what is the novelty of this algorithm? it is just enumeration

what is marginal cost here?

spectacularly???? -> this doesn't sound like the right word

2 SINGLE-AGENT PROBLEM SETTING

"A principal wishes to incentivize " -> dont need to say incentivize; incentivize means something else in procurement

This organization is so strange; usually people just present the general setting together and you have two separate settings; this looks like two papers combined together

"The agent belongs to one of K types," -> you said they have one of the ci function instead of belongs to K types this needs to be consistent

so what does the agents decide?

"chooses a production level which maximizes her utility" > this doesn't mean that the items will be purchased right ?

what is the meaning of mi(\pi) in ()? it hasn't been defined yet

3 HARDNESS RESULTS AND CONNECTION TO ITEM PRICING

so Theorem 1 says both problem is the same; what is new here?

4 EXACT ALGORITHMS FOR A SINGLE AGENT

What are exact algorithms for unit-demand item pricing?

4.1 AN EXACT ALGORITHM FOR GENERAL COST CURVES

What is the connection to the Bellman equation?

5 MULTI-AGENT PROBLEM SETTING

"With concave costs, however, this fails. " => fails as in what? what don't you try other approaches instead of the squential models

Critical strengths
  • The paper considers an interesting model
  • The paper provides theoretical results
Critical weaknesses
  • There are many places in which they don't read like normal English
  • The paper lacks motivations for the considered problems and settings
  • The technical/modeling novelty is rather limited and restricted to DP-based and enumeration algorithms with high complexity.
Questions for authors

N/A

5 comments
AuthorsOpenReview ↗

Some clarifications on the procurement model and real-world motivation

Reviewer WTdu:

Thank you for the detailed feedback. We will revise the presentation to make the model easier to follow. In particular, we will make sure that main quantities are clearly defined when they first appear, clarify what the principal and the agents know when they make their decisions, and explain the timing of menu posting, production, and payment.

Some quick clarifications:

Abstract: We intend to give a high-level overview of our paper here. Many details of concern can be found in the paper’s corresponding sections.

“Producing doesn't mean that the principal will buy it right?”: We assume that the principal must commit to buying the quantity selected under the posted menu at the posted payment.

“[I] am confused what [are] the agents reporting”: This is not an auction setting. Our problem setting has the following steps: 1. the principal posts a payment menu; 2. an agent type is drawn; 3. this agent reports her utility-maximizing production levels; 4. the principal chooses a tie-breaking production level; 5. the production and payments are realized. This is very similar to item pricing, which has the following steps: 1. the seller posts a pricing of items; 2. a buyer type is drawn; 3. the buyer chooses a utility-maximizing item, with ties resolved in favor of the highest-priced item; 4. the purchase happens.

“anonymous payment menu”: “Anonymous” means that the same payment menu is presented to all agent types without discrimination. “Payment menu” is simply a function mapping an agent’s production levels to the monetary reward she gets. These are standard terms in the item pricing literature.

“Theorem 1 says both problem[s] [are] the same; what is new here?”: The significance of Theorem 1 is to make a connection between our problem and a well-studied problem. The proof is straightforward, but recognizing the connection is not trivial. The Hartline–Koltun approximation scheme transferred in Corollary 3 has exponential dependence on MM, making it costly when the production range is large (see “Implications for computation” at the end of §3). Thus, our goal is to find algorithms without exponential dependence on MM.

“this looks like two papers combined together”: solving the single-agent problem is a prerequisite for understanding the multi-agent problem, and many of our techniques carry over. For example, in §6.1, the adaptive multi-agent algorithm uses single-agent algorithms (both the general enumeration algorithm and the ordered-cost improved algorithm) at each state.

Real-world motivation and the regime K≪MK\ll M:

Starting in the introduction, we cite applications of data collection in clinical studies, market research, ecological monitoring, and spectrum monitoring. It also gives examples beyond data collection, such as procuring accelerators of a specified model, hours of a specified service, or doses of a specified vaccine. We will clarify what makes units comparable (homogeneous) in each example.

We elaborate this motivation in the Alzheimer’s imaging example in §1.1. A study sponsor can post a common payment menu specifying how much it will pay a clinic for each quantity of eligible scans. When the study treats eligible scans as comparable, the sponsor’s valuation can depend on the total number collected, thus we say the data is homogeneous. Each clinic chooses an integer production quantity up to a common bound MM (representing hard resource constraints, see §2 “Model”) based on its private collection costs. To model variation in collection costs, the sponsor might group clinics by scanner and staffing characteristics, assign a representative cost curve to each group, and use a prior over the KK groups. This can give a small number of modeled cost types even when clinics can supply many different quantities. The model allows arbitrary KK and MM, and the example illustrates why K≪MK\ll M is a regime of interest. We will cite Weiner et al. (2017) alongside the imaging example and make this modeling connection clearer.

AuthorsOpenReview ↗

Technical contributions beyond DP and enumeration

Novelty beyond DP and enumeration:

Multi-agent modeling novelty (why sequential arrivals): Finding a way to deal with the tension in the multi-agent setting is a key contribution of this work. We first show that allowing agents to arrive simultaneously is problematic. In §5 and Appendix E, Example 2 shows that even the optimal common menu offered simultaneously can yield lower expected utility with two suppliers than with one. The principal must honor the menu for every supplier, which can lead to excess production or repeated setup costs. An alternative could involve conditioning each supplier’s payment on what other suppliers produce. However, this can create coordination problems, as discussed in §5, footnote 1. Our solution is the sequential model, which allows the principal to stop before the next arrival within the TT-round horizon and, in the adaptive case, update future menus based on cumulative production.

Reduction to item pricing: The reduction in Theorem 1 makes a connection to the item pricing literature. The proof is straightforward but coming up with the connection is not trivial.

Applying the idea of single-crossing/Spence-Mirrlees condition: In §4.2, the ordered-cost condition makes local incentive constraints suffice to capture all incentive constraints. Cheapest payments derived from local constraints then give a separable virtual-cost objective. This allows for optimization over monotone profiles in O(KM)O(KM) arithmetic operations without enumerating them. This improvement can be further applied to the adaptive multi-agent case when the costs are ordered.

A novel tree formulation to preserve all best responses: In §6.2, we encounter a challenge: enumerating production profiles can miss the optimum because the principal may prefer different tied production levels for the same type at different states, as Example 1 shows. A standard profile enumeration + DP algorithm, like the one we used for adaptive multi-agent, thus fails. Instead, we prove that any static menu can be replaced by one that preserves all of its best responses at weakly lower payments on those responses. We then show that the replacement menu is determined by a tree of tight constraints. Thus, enumerating all such trees is sufficient to capture the optimum.

The paper should use standard language for academic writing and requires significant revisions to address these concerns and improve readability for human readers. Having said that, it requires another round of reviews.

BTW, "Novelty beyond DP and enumeration:" is not copied and pasted correctly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.