How to Sell a Service with Uncertain Outcomes

Alec Sun; Haifeng Xu; Krishnamurthy Iyer; You Zu

arxiv: 2502.13334 · v1 · submitted 2025-02-18 · 💻 cs.GT

How to Sell a Service with Uncertain Outcomes

Krishnamurthy Iyer , Alec Sun , Haifeng Xu , You Zu This is my paper

Pith reviewed 2026-05-23 02:39 UTC · model grok-4.3

classification 💻 cs.GT

keywords contract designmechanism designservice with uncertain qualitytwo-stage paymentsprofit maximizationapproximation schemesingle-parameter buyers

0 comments

The pith

Sellers maximize profit for uncertain-outcome services only with two-stage contracts combining upfront and usage payments.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper models a seller offering a service with uncertain quality by choosing an action that determines the outcome distribution. Buyers see the realized quality before deciding to pay a usage fee or reject. A menu of contracts with upfront prices and outcome-dependent usage prices is shown to be necessary for maximum profit, unlike single-stage pricing. Computationally, the problem is NP-hard for two buyer types but has an FPTAS for any constant number, and reduces to a single contract when buyer valuations are single-parameter.

Core claim

The central claim is that profit maximization requires a two-stage payment structure in which each contract specifies an action, an upfront price, and usage prices for each possible outcome. The buyer pays the upfront fee upon selecting the contract and then, after observing the outcome, chooses whether to accept it by paying the corresponding usage price or to reject and pay nothing further. This structure is necessary, as the maximum profit cannot be achieved with only upfront prices or only usage prices. For computation, an FPTAS exists when the number of buyer types is constant, and a single contract suffices in the single-parameter case.

What carries the argument

A menu of two-stage contracts, each specifying an action, upfront price, and vector of outcome-dependent usage prices, allowing the buyer to opt out after seeing the realized outcome.

If this is right

Only upfront prices or only usage prices is insufficient to maximize profit.
Computing the exact maximum seller profit is NP-hard even for two buyer types.
A fully-polynomial time approximation scheme exists for the maximum profit when there is a constant number of buyer types.
In the single-parameter setting, seller revenue can be maximized using a menu consisting of a single contract.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the model holds, platforms offering ML training or similar services could increase revenue by implementing post-outcome acceptance options.
The necessity of two-stage pricing may extend to other domains with verifiable but uncertain quality, such as medical treatments or repairs.
Future work could examine settings where the seller cannot commit or where outcomes are not fully observable to the buyer.

Load-bearing premise

The buyer observes the realized outcome quality before choosing to accept or reject the contract.

What would settle it

Finding a setting with two buyer types where the optimal profit using only upfront prices equals that of any two-stage menu would disprove the necessity of the two-stage structure.

read the original abstract

Motivated by the recent popularity of machine learning training services, we introduce a contract design problem in which a provider sells a service that results in an outcome of uncertain quality for the buyer. The seller has a set of actions that lead to different distributions over outcomes. We focus on a setting in which the seller has the ability to commit to an action and the buyer is free to accept or reject the outcome after seeing its realized quality. We propose a two-stage payment scheme where the seller designs a menu of contracts, each of which specifies an action, an upfront price and a vector of outcome-dependent usage prices. Upon selecting a contract, the buyer pays the upfront price, and after observing the realized outcome, the buyer either accepts and pays the corresponding usage price, or rejects and is exempt from further payment. We show that this two-stage payment structure is necessary to maximize profit: only upfront prices or only usage prices is insufficient. We then study the computational complexity of computing a profit-maximizing menu in our model. While computing the exact maximum seller profit is NP-hard even for two buyer types, we derive a fully-polynomial time approximation scheme (FPTAS) for the maximum profit for a constant number of buyer types. Finally, we prove that in the single-parameter setting in which buyers' valuations are parametrized by a single real number that seller revenue can be maximized using a menu consisting of a single contract.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows two-stage payments are required for profit max in this uncertain-service model, gives an FPTAS for constant buyer types, and proves single-contract optimality in the single-parameter case.

read the letter

The core result is that upfront prices alone or usage prices alone cannot achieve the maximum seller profit; the combination is necessary under the model's commitment and post-outcome rejection setup. They also give an FPTAS for the optimal menu when the number of buyer types is constant and show that a single contract suffices when valuations are single-parameter. These are the actual new pieces relative to standard contract design. The model itself is a reasonable fit for ML training services, and the necessity claim follows directly from the buyer's ability to walk away after seeing realized quality. The computational results are stated cleanly without visible internal contradictions. The main limitation is that everything stays theoretical: no numerical examples or robustness checks beyond the stated assumptions, and the FPTAS applies only for fixed numbers of types, which is typical but restricts immediate applicability. The single-parameter optimality is a nice simplification but rests on the parametrization chosen. This is worth a referee for mechanism-design or algorithmic game theory venues that handle service pricing. The claims are grounded in the model they define, so it clears the bar for review even if revisions will be needed on exposition or extensions.

Referee Report

0 major / 0 minor

Summary. The manuscript introduces a contract design problem for a seller offering a service with stochastic outcomes (e.g., ML training), where the seller commits to an action inducing a distribution over outcomes and the buyer observes the realized outcome before deciding to accept or reject. The authors propose a two-stage menu of contracts, each specifying an action, an upfront price, and a vector of outcome-dependent usage prices. They claim this structure is necessary for profit maximization (neither pure upfront nor pure usage prices suffice), that exact profit maximization is NP-hard even for two buyer types but admits an FPTAS for any constant number of types, and that a single contract is optimal in the single-parameter setting.

Significance. If the proofs are correct, the work contributes structural and algorithmic results to contract theory in stochastic environments. The necessity of the two-stage payment scheme, the FPTAS for constant buyer types, and the single-contract characterization in the single-parameter case are concrete advances. The paper supplies explicit proofs of these claims rather than relying on simulations or fitted parameters.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review and recommendation to accept the manuscript. The summary accurately captures the main results on two-stage contracts, necessity of the payment structure, the FPTAS, and single-contract optimality.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines a novel contract-design model (seller commits to action; buyer observes outcome and accepts/rejects) and derives its three central claims via direct proofs: necessity of the two-stage menu, existence of an FPTAS for constant buyer types, and optimality of a single contract in the single-parameter case. These follow from the stated model without reduction to fitted parameters, self-citations, or ansatzes imported from prior work by the same authors. No equations or claims in the abstract reduce by construction to their inputs; the results are presented as new theorems in a standard but extended mechanism-design setting.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on abstract; model relies on standard mechanism design assumptions not enumerated, plus domain-specific modeling choices for commitment and post-outcome buyer choice.

axioms (2)

domain assumption Seller can commit to an action that determines the distribution over outcomes
Stated as core model feature in abstract.
domain assumption Buyer observes realized outcome quality before deciding to accept or reject
Enables the two-stage payment and rejection option described.

pith-pipeline@v0.9.0 · 5787 in / 1350 out tokens · 37315 ms · 2026-05-23T02:39:02.710362+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Paul D¨ utting, Tim Roughgarden, and Inbal Talgam-Cohen

URL https://arxiv.org/abs/2412.16384. Paul D¨ utting, Tim Roughgarden, and Inbal Talgam-Cohen. Si mple versus optimal contracts. In Proceedings of the 2019 ACM Conference on Economics and Computa tion, EC ’19, page 369–387, New York, NY, USA, 2019. Association for Computing Machiner y. ISBN 9781450367929. doi: 10.1145/3328526.3329591. URL https://doi.org/...

work page doi:10.1145/3328526.3329591 2019
[2]

URL http://www.jstor.org/stable/27857621

ISSN 00030996. URL http://www.jstor.org/stable/27857621. Hayne E. Leland and Robert A. Meyer. Monopoly pricing struct ures with imperfect discrimina- tion. The Bell Journal of Economics , 7(2):449–462, 1976. ISSN 0361915X, 23263032. URL http://www.jstor.org/stable/3003266. Yingkai Li. Selling Data to an Agent with Endogenous Informa tion. In Proceedings o...

work page doi:10.1145/3490486.3538360 1976
[3]

( 2), we can assume that 0 < µ 1 ≤ · · · ≤ µT ≤ 1

By Eq. ( 2), we can assume that 0 < µ 1 ≤ · · · ≤ µT ≤ 1

work page
[4]

There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 T , ∀q ∈ Q

We construct the following problem instance: • Let Q = [ T ]. There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 T , ∀q ∈ Q. • Valuations are given by vt q = { T∑t i=1 µi if q = t 0 if q ̸= t. The utility of buyer type t satisﬁes U (t; Ct) ≤ 1 T · T∑t i=1 µi = 1 ∑t i=1 µi , 22 so R ≤ ∑ t∈ [T ] µt · 1∑t i=1 µi . The upper b...

work page
[5]

Suppose that the contract Ct = (at, wt, xt) yields proﬁt rt := wt − c(at) + ∑ q∈ Q pat q xt q ·1 [ vt q ≥ xt q ] from type t and assume without loss of generality that r1 ≥ r2 ≥ · · · ≥ rT . Claim. For every t ∈ [T ] we can construct a modiﬁed menu with only upfront prices that achieves a proﬁt of at least ( t∑ i=1 µi ) ·rt. 23 Proof. To construct such a ...

work page
[6]

We also show that the lower and upper bounds are both tight

satisﬁes Hµ ∈ [HT , T ) where HT = ∑ t∈ [T ] 1 t is the T -th harmonic number. We also show that the lower and upper bounds are both tight. We ﬁrst show that the lower bound is achievable and the upper b ound is achievable in the limit. The lower bound is achieved by setting µ1 = · · ·= µT = 1 T . The upper bound can be achieved in the limit by setting µt...

work page
[7]

There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 2 , ∀q ∈ [2]

To show that R Rusage ≥ 3 2 , we construct the following problem instance: • Let T = 2, µ1 = µ2 = 1 2 , and Q = {1, 2}. There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 2 , ∀q ∈ [2]. • Valuations are given by v1 = ( 1, 1 2 ) and v2 = (1 2 , 1 ) . Note that V (t; a) = 3 4 , so R ≤ 3 4 . The upper bound on R can be achieve...

work page
[8]

The utility of contract Ct for type u is U (u; Ct) := − wt + ∑ q pat q ·max { 0, vu q − xt q } = − wt + ∑ q:vuq ≥ xt q pat q ( vu q − xt q )

Consider a IC menu of the form Ct = ( at, wt, xt). The utility of contract Ct for type u is U (u; Ct) := − wt + ∑ q pat q ·max { 0, vu q − xt q } = − wt + ∑ q:vuq ≥ xt q pat q ( vu q − xt q ) . 26 The revenue from type t is wt + ∑ q∈ St pat q xt q, recalling that St := { q : vt q ≥ xt q } is the set of outcomes that type t accepts. Consider replacing Ct w...

work page
[9]

This process stops when one buyer’s surplus is 0

Note that increasing both upfront prices w1 and w2 at the same rate increases proﬁt while preserving IC since each buyers’ utility for eac h contract decreases at the same rate. This process stops when one buyer’s surplus is 0. Hence any pr oﬁt-maximizing menu must have no buyer surplus for at least one type. To ﬁnish the proof of the l emma, we split int...

work page
[10]

For two states s and s′ that diﬀer in only one component i = ( t, t′) by a constant ε > 0, we have πindirect(s′) ≥ πindirect(s) − ε

It suﬃces to prove the following: Claim. For two states s and s′ that diﬀer in only one component i = ( t, t′) by a constant ε > 0, we have πindirect(s′) ≥ πindirect(s) − ε. Furthermore, if s′ i ≥ si then πindirect(s′) ≥ πindirect(s). Proof. We consider four cases: Case 1: s′ is derived from s by an increase of ε in a component of the form (t, t′) for t ∈...

work page
[11]

Fixing the function u, we claim that the service provider’s optimization problem can be solved by linear programming

The key idea to enumerate over all possible functions u : [T ] → { 0} ∪ [T ], of which there are ( T +1) T , a constant because we assume the number of types T is a constant. Fixing the function u, we claim that the service provider’s optimization problem can be solved by linear programming. Indeed, ﬁxing u the proﬁt is linear in the upfront prices ( wt) ...

work page
[12]

Since t ≥ u, we conclude V t αt ≥ V u αu and also wt ≥ wu from Eq

The IC constraints can be rewritten as U (t, t) ≥ U (t, u) ⇐ ⇒ V t − wt ≥ V (t, u) − wu = αt αu ·V u − wu ⇐ ⇒ wt − wu ≤ αt (V t αt − V u αu ) Combined with the IC constraint U (u; u) ≥ U (u, t) ⇐ ⇒ wt − wu ≥ αu (V t αt − V u αu ) , we have αu (V t αt − V u αu ) ≤ wt − wu ≤ αt (V t αt − V u αu ) , (9) hence ( αt − αu) (V t αt − V u αu ) ≥ 0. Since t ≥ u, w...

work page

[1] [1]

Paul D¨ utting, Tim Roughgarden, and Inbal Talgam-Cohen

URL https://arxiv.org/abs/2412.16384. Paul D¨ utting, Tim Roughgarden, and Inbal Talgam-Cohen. Si mple versus optimal contracts. In Proceedings of the 2019 ACM Conference on Economics and Computa tion, EC ’19, page 369–387, New York, NY, USA, 2019. Association for Computing Machiner y. ISBN 9781450367929. doi: 10.1145/3328526.3329591. URL https://doi.org/...

work page doi:10.1145/3328526.3329591 2019

[2] [2]

URL http://www.jstor.org/stable/27857621

ISSN 00030996. URL http://www.jstor.org/stable/27857621. Hayne E. Leland and Robert A. Meyer. Monopoly pricing struct ures with imperfect discrimina- tion. The Bell Journal of Economics , 7(2):449–462, 1976. ISSN 0361915X, 23263032. URL http://www.jstor.org/stable/3003266. Yingkai Li. Selling Data to an Agent with Endogenous Informa tion. In Proceedings o...

work page doi:10.1145/3490486.3538360 1976

[3] [3]

( 2), we can assume that 0 < µ 1 ≤ · · · ≤ µT ≤ 1

By Eq. ( 2), we can assume that 0 < µ 1 ≤ · · · ≤ µT ≤ 1

work page

[4] [4]

There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 T , ∀q ∈ Q

We construct the following problem instance: • Let Q = [ T ]. There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 T , ∀q ∈ Q. • Valuations are given by vt q = { T∑t i=1 µi if q = t 0 if q ̸= t. The utility of buyer type t satisﬁes U (t; Ct) ≤ 1 T · T∑t i=1 µi = 1 ∑t i=1 µi , 22 so R ≤ ∑ t∈ [T ] µt · 1∑t i=1 µi . The upper b...

work page

[5] [5]

Suppose that the contract Ct = (at, wt, xt) yields proﬁt rt := wt − c(at) + ∑ q∈ Q pat q xt q ·1 [ vt q ≥ xt q ] from type t and assume without loss of generality that r1 ≥ r2 ≥ · · · ≥ rT . Claim. For every t ∈ [T ] we can construct a modiﬁed menu with only upfront prices that achieves a proﬁt of at least ( t∑ i=1 µi ) ·rt. 23 Proof. To construct such a ...

work page

[6] [6]

We also show that the lower and upper bounds are both tight

satisﬁes Hµ ∈ [HT , T ) where HT = ∑ t∈ [T ] 1 t is the T -th harmonic number. We also show that the lower and upper bounds are both tight. We ﬁrst show that the lower bound is achievable and the upper b ound is achievable in the limit. The lower bound is achieved by setting µ1 = · · ·= µT = 1 T . The upper bound can be achieved in the limit by setting µt...

work page

[7] [7]

There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 2 , ∀q ∈ [2]

To show that R Rusage ≥ 3 2 , we construct the following problem instance: • Let T = 2, µ1 = µ2 = 1 2 , and Q = {1, 2}. There is a single action a with cost c(a) = 0 and transition probabilities pa q = 1 2 , ∀q ∈ [2]. • Valuations are given by v1 = ( 1, 1 2 ) and v2 = (1 2 , 1 ) . Note that V (t; a) = 3 4 , so R ≤ 3 4 . The upper bound on R can be achieve...

work page

[8] [8]

The utility of contract Ct for type u is U (u; Ct) := − wt + ∑ q pat q ·max { 0, vu q − xt q } = − wt + ∑ q:vuq ≥ xt q pat q ( vu q − xt q )

Consider a IC menu of the form Ct = ( at, wt, xt). The utility of contract Ct for type u is U (u; Ct) := − wt + ∑ q pat q ·max { 0, vu q − xt q } = − wt + ∑ q:vuq ≥ xt q pat q ( vu q − xt q ) . 26 The revenue from type t is wt + ∑ q∈ St pat q xt q, recalling that St := { q : vt q ≥ xt q } is the set of outcomes that type t accepts. Consider replacing Ct w...

work page

[9] [9]

This process stops when one buyer’s surplus is 0

Note that increasing both upfront prices w1 and w2 at the same rate increases proﬁt while preserving IC since each buyers’ utility for eac h contract decreases at the same rate. This process stops when one buyer’s surplus is 0. Hence any pr oﬁt-maximizing menu must have no buyer surplus for at least one type. To ﬁnish the proof of the l emma, we split int...

work page

[10] [10]

For two states s and s′ that diﬀer in only one component i = ( t, t′) by a constant ε > 0, we have πindirect(s′) ≥ πindirect(s) − ε

It suﬃces to prove the following: Claim. For two states s and s′ that diﬀer in only one component i = ( t, t′) by a constant ε > 0, we have πindirect(s′) ≥ πindirect(s) − ε. Furthermore, if s′ i ≥ si then πindirect(s′) ≥ πindirect(s). Proof. We consider four cases: Case 1: s′ is derived from s by an increase of ε in a component of the form (t, t′) for t ∈...

work page

[11] [11]

Fixing the function u, we claim that the service provider’s optimization problem can be solved by linear programming

The key idea to enumerate over all possible functions u : [T ] → { 0} ∪ [T ], of which there are ( T +1) T , a constant because we assume the number of types T is a constant. Fixing the function u, we claim that the service provider’s optimization problem can be solved by linear programming. Indeed, ﬁxing u the proﬁt is linear in the upfront prices ( wt) ...

work page

[12] [12]

Since t ≥ u, we conclude V t αt ≥ V u αu and also wt ≥ wu from Eq

The IC constraints can be rewritten as U (t, t) ≥ U (t, u) ⇐ ⇒ V t − wt ≥ V (t, u) − wu = αt αu ·V u − wu ⇐ ⇒ wt − wu ≤ αt (V t αt − V u αu ) Combined with the IC constraint U (u; u) ≥ U (u, t) ⇐ ⇒ wt − wu ≥ αu (V t αt − V u αu ) , we have αu (V t αt − V u αu ) ≤ wt − wu ≤ αt (V t αt − V u αu ) , (9) hence ( αt − αu) (V t αt − V u αu ) ≥ 0. Since t ≥ u, w...

work page