acceptodds
Under review as a conference paper at ICLR 2027

StructPay: Joint Workflow and Reward Design for Reliable Agent Services

Abstract

Workflow dependence can make reliable effort expensive, while heterogeneous services can make a common reward inefficient. We introduce StructPay, which jointly selects paid workflow cuts and individualized success bonuses to minimize commitment at a fixed worst-case local-reliability target. For an ordered complementary workflow family, we exactly characterize worst risk over approximate coarse correlated equilibria for every nonnegative reward vector. This yields certified optimization and, in a homogeneous regime, matching bonus-commitment bounds, an interior square-root organizational scale and a constant-factor construction. A specified family exhibits an Ω(n) price of fixed organization. On 300 frozen heterogeneous design instances, StructPay achieves median per-instance commitment savings of 55.5% relative to fully optimized individual rewards on the fixed workflow and 18.1% relative to optimized structure with a common reward. A prespecified 2,700-case continuation shows a strengthening advantage for individualized rewards along the evaluated heterogeneity sequence. In the exact two-agent game, joint design commits 21.4% less while all 16 optimized-contract trajectories across two LLM model families meet the frozen behavioral and reliability targets. Together, these results identify workflow structure and reward allocation as two distinct levers for lowering the commitment required for robust cooperation.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Multi-agent systems, contract theory, incentive design, workflow optimization, coarse correlated equilibrium, LLM agents

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_JbfnOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes StructPay, a framework that jointly optimizes workflow dependencies and individualized agent rewards to achieve multi-agent cooperation at minimum cost. The authors provide theoretical guarantees for worst-case reliability under approximate coarse correlated equilibria (CCE). Experiments on synthetic instances and a two-agent LLM setting demonstrate reduced reward commitment compared with alternative designs.

Critical strengths

The paper addresses an interesting problem of jointly optimizing workflow structures and incentive mechanisms for reliable multi-agent cooperation. It provides a formal characterization of worst-case reliability, along with theoretical bounds and guarantees for the proposed optimization framework.

Critical weaknesses

Limited practical applicability and strong modeling assumptions. While the paper provides theoretical guarantees, the proposed framework assumes prior knowledge of workflow dependencies, individual agent effort costs, and the relationship between effort and task success. It remains unclear how these quantities can be estimated or whether these assumptions hold in realistic LLM-based multi-agent systems, where costs are typically associated with token/API usage rather than success-based incentives. Moreover, the empirical evaluation primarily considers synthetic instances and a simplified two-agent game, leaving the applicability of the proposed framework to real-world agentic workflows insufficiently demonstrated.

Scalability and practical effectiveness. The exact optimization procedure can require exponentially many subproblems, while the empirical evaluation considers relatively small systems. Although the authors provide a more efficient approximation for homogeneous settings, its practical effectiveness is less convincing, as it underperforms some optimized baselines in the additional experiments.

Questions for authors

What are the intended practical use cases of StructPay, and how would the proposed framework be applied to real-world multi-agent systems?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Jbfn (1/3)

Thank you for recognizing the importance of jointly optimizing workflow structures and incentive mechanisms, as well as our formal worst-case reliability characterization and theoretical guarantees. Below, we clarify the intended practical settings, parameter operationalization, and joint reliability across all modeled checks (Q1), and present practical optimization procedures with a polynomial-time lower-bound stage and certified performance on heterogeneous instances up to n=50n=50 services (Q2).

Q1. Intended practical use cases and operationalization

Candidate application scenarios and model-quantity mapping

StructPay is intended for principal-orchestrated multi-agent service pipelines, including candidate scenarios in modular robotics and autonomy (e.g., scene understanding/constraint extraction followed by motion or task planning with independent safety verification), automated software engineering, multi-stage data extraction and scheduling, and cross-vendor service orchestration. These settings share four characteristics: (i) multiple sequential services have identifiable inputs and outputs, (ii) each service's output can be checked locally against a specification, safety rule, or test suite, (iii) individual services have effort-dependent utility costs, which may be informed by observable resource proxies (such as additional token generation, multi-pass verification, tool/search calls, or routing to a stronger model), and (iv) the principal can implement outcome-contingent contractual bonuses or service-level credits and modify workflow dependencies.

In a single-owner script, one user directly pays a combined API bill. In delegated or cross-provider service pipelines, however, token/API expenditure is an operating cost rather than automatically equaling an agent's private opportunity cost. The model quantities therefore play distinct operational roles:

  • Effort costs (cic_i) and success bonuses (bib_i): cic_i represents an agent's incremental utility cost of high effort relative to low effort, while bib_i is an auditable contractual transfer conditional on the sampled local check (not a token/API charge). Benchmarking concrete effort modes (e.g., single-pass generation versus retrieval-augmented generation with iterative verification) on held-out inputs provides observable resource proxies or bounds to inform cic_i. Identifying an agent's actual private opportunity cost may additionally require provider-side information.
  • Workflow dependencies: Dependencies can be identified from execution traces and tested through input-routing interventions.
  • Production-success probabilities: Effort-dependent success rates can be estimated by evaluating each effort mode on held-out tasks under the relevant workflow structure.
  • Verification weights (did_i): These are specified by the principal according to the local audit-sampling design and stage criticality.

StructPay takes defensible estimates or bounds for these quantities as design inputs, operating alongside an auditable incentive interface rather than inferring unobservable private costs or assuming that an unincentivized prompt internalizes monetary transfers.

AuthorsOpenReview ↗

Response to Reviewer Jbfn (2/3)

Q1 (continued)

Operational workflow-cut example

A concrete application mapping is constraint extraction (S1S_1) followed by scheduling (S2S_2). Under the dependent route, S2S_2 consumes S1S_1's generated constraint ledger alongside a public request. Under the cut route, S2S_2 is instead granted direct access to the original source requirements and public request without S1S_1's artifact, and its checker validates against public-source constraints, while keeping the task instance, both required deliverables (a constraint ledger and a valid schedule), output schemas, and final reference scorer fixed. The cut fee ρ\rho represents a stipulated principal-side tariff calibrated from a token-cost proxy rather than an independently observed market price. Because this modeled intervention also changes information and checking permissions, preserving the task specification and scorer does not independently establish unchanged production quality. Operationally, a cut is economically meaningful when the principal can obtain the alternative access at a known cost and specify downstream verification independently of the removed upstream artifact. Conceptually, the same cut structure maps to modular autonomy pipelines when a downstream motion- or task-planning module (and its safety checker) is granted direct access to raw map or scene-level constraints rather than relying solely on an upstream agent's intermediate representation. This mapping concerns the staged service-and-verification layer, rather than the continuous low-level control loop.

Joint reliability across all modeled checks

To extend the sampled-local-check guarantee to joint success across all modeled checks, let G={a:there exists i with ai=0}G=\lbrace a:\text{there exists }i\text{ with }a_i=0 \rbrace denote failure of at least one modeled verification item, and let eje_j denote the endpoint of module jj. Under the binary-action model and sampled-local-check payment rule, worst-case all-checks failure over approximate CCEs admits the exact, attainable characterization

sup⁡μ∈CCEε(R,b)Pr⁡μ(G)=min⁡{1,∑jQej},\displaystyle \sup _ {\mu\in\mathrm{CCE} _ {\boldsymbol{\varepsilon}}(R,b)} \Pr _ {\mu}(G) = \min\left\lbrace 1,\sum _ j Q _ {e_j}\right\rbrace,

where QQ is Theorem 1's clipped recurrence reset to zero at each module root. Across the 300 primary instances, Joint achieves median per-instance paired commitment savings of 25.0% and 25.5% against fixed workflow with individual rewards, and 15.9% and 21.1% against optimized workflow with common rewards, at all-checks failure targets of 0.05 and 0.10, respectively (certifying a physical deliverable additionally requires physical failure to be covered by GG under each compared workflow).

Sensitivity to estimation error and extended behavioral checks

  • Parameter uncertainty: Exploiting monotonicity of Theorem 1's risk recurrence on our 300-instance primary panel, direct robust optimization at the upper corner of a 20% simultaneous uncertainty set in effort costs and behavioral tolerances increases median Joint commitment by 14.189% relative to the nominal design. Under 5–20% cost-only uncertainty, Appendix D.3's general transfer bound yields median per-instance commitment ratios of 2.224, 3.226, and 5.039 at 5%, 10%, and 20% uncertainty, respectively, relative to direct endpoint optimization. This conservatism arises because D.3 transfers cost error νi=αci\nu_i=\alpha c_i into the additive tolerance εi+νi\varepsilon_i+\nu_i, whereas direct endpoint optimization replaces cic_i with (1+α)ci(1+\alpha)c_i while retaining εi\varepsilon_i. For production-technology misspecification, Appendix D.3 provides a conditional error-transfer bound under uniform production-error assumptions rather than a numerical sensitivity experiment.
  • Extended behavioral diagnostics: Beyond the original two-agent setting, we conducted 48 additional 64-round proxy-game trajectories covering three-service chains, mixed-model assignments, and forced-low initial play, with the per-agent tolerance εi=0.05\varepsilon_i=0.05 and the expected local-reliability target of 0.90 frozen before model calls. Across contracts that jointly vary structure and bonuses, outcomes are configuration-dependent: Joint attains both criteria in 7/8 forced-low recovery trajectories versus 5/8 for Fixed over free-choice rounds 9–64, while the three-service Qwen condition shows 1/4 for Joint versus 3/4 for Fixed, underscoring the distinction between certifying game-theoretic incentives and empirical LLM compliance.
AuthorsOpenReview ↗

Response to Reviewer Jbfn (3/3)

Q2. Practical scalability and effectiveness beyond the analytical construction

Why the analytical construction is conservative

Exact risk evaluation for any specified contract takes O(n)O(n) arithmetic operations via Theorem 1's clipped recurrence, whereas unrestricted heterogeneous design remains combinatorial. In Appendix F (Tables 5–6), the "Joint algorithm" row evaluated Theorem 5's closed-form formula (Eq. 13), which assigns analytical margins yi=mj(c+ε/δ)y_i=m_j(c+\varepsilon/\delta) without numerical refinement to establish a worst-case constant-factor bound (80/380/3). Because this analytical margin can be conservative (for instance, at reliability target 0.8 in Table 5, it achieves worst-case risk 0.08125 when 0.20 is permitted), it commits more than numerically optimized baselines.

To bridge theory and practical computation, we evaluated two practical design procedures that return checked feasible contracts alongside independently verifiable bounds.

1. Homogeneous instances: Balanced Scan + Reward Polishing (BS+P)

BS scans balanced partitions across module counts using exact common-bonus bisection to obtain checked feasible incumbents. Reward Polishing refines bonuses only on the BS-selected partition under a positive-margin convex restriction (ϕend≤1\phi _ {\mathrm{end}}\leq1). This restriction excludes unpaid suffixes, nonpositive margins, and contracts relying on clipping an untruncated recurrence value above one, while terminal equality ϕend=1\phi _ {\mathrm{end}}=1 remains admissible. Polishing is accepted only when the candidate passes exact feasibility checks and strictly reduces commitment, and the checked BS incumbent is retained otherwise. Polishing improved 146/240 cases and retained the BS fallback in 94/240, so every returned contract remains feasible and has commitment no greater than its BS incumbent.

On all 240 scheduled homogeneous instances, the exhaustive oracle encloses OPT∈[L,U]\mathrm{OPT}\in[L,U]. Here, C/UC/U measures the returned commitment relative to the oracle's feasible witness, whereas C/LC/L is a certified upper bound on its ratio to the global optimum:

Homogeneous BS+P (240 cases)Result
Median feasible/oracle-witness ratio (C/UC/U)1.000000
Worst certified optimality-ratio upper bound (C/LC/L)1.011201
Feasible returned contracts240/240

2. Heterogeneous instances: Segmentation DP up to n=50n=50

For heterogeneous instances with positive costs, positive normalized verification weights, positive tolerances, nonnegative cut fees, and 0<δ<min⁡idi0<\delta<\min_i d_i, we developed a segmentation dynamic program whose lower-bound stage computes segment costs and a global Bellman lower bound in O(n3)O(n^3) arithmetic operations and O(n2)O(n^2) storage. These complexity bounds apply specifically to the lower-bound stage, while scalar searches and candidate convex refinements are additional steps in the full method. The procedure backtracks at most one candidate partition per module count for individual-reward refinement, acting as a certified candidate-family heuristic rather than unrestricted global optimization, and retains an exactly checked common-bonus fallback.

  • Accuracy on the 300 primary heterogeneous cases (n∈{6,8,10,12}n\in\lbrace 6,8,10,12 \rbrace), measured against the exhaustive oracle interval [Lold,Uold][L _ {\mathrm{old}},U _ {\mathrm{old}}]:
Heterogeneous DP (300 primary cases)Result
Median feasible/oracle-witness ratio (C/UoldC/U _ {\mathrm{old}})1.000000
Worst certified optimality-ratio upper bound (C/LoldC/L _ {\mathrm{old}})1.086891
Returned contracts with checked feasibility certificates300/300
  • Scalability across n=20,30,50n=20,30,50 (225 extended heterogeneous cases): Evaluating all 75 cost/weight/tolerance patterns at each of n∈{20,30,50}n\in\lbrace 20,30,50 \rbrace returns checked feasible contracts in all 225 cases. At n=50n=50 (75 cases), median and maximum total method runtimes, including scalar searches and candidate convex refinements, are 0.883 s and 2.604 s, respectively. The median and worst ratios of feasible commitment to the DP lower bound are 1.102488 and 1.324001. These extended-grid ratios use the relaxed DP lower bound rather than an exhaustive oracle interval, so the primary and extended ratios have different denominators and should not be pooled as a single approximation ratio.

Taken together, StructPay targets principal-governed multi-agent and modular autonomy workflows with locally auditable outputs, measurable effort modes, and restructurable dependencies. Although unrestricted heterogeneous optimization is combinatorial, exact risk evaluation takes O(n)O(n) arithmetic operations, and our BS+P and segmentation DP procedures return checked feasible contracts with certified bounds—matching exhaustive oracle witnesses at the median on the homogeneous and primary heterogeneous panels, and scaling to n=50n=50 heterogeneous services in seconds against the DP lower bound.

Thank you for addressing my concerns regarding practicality. I maintain my recommendation for acceptance. However, as this aspect falls outside my area of expertise, I defer to the AC for the final judgment.

Reviewer_L4wNOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

StructPay jointly optimizes paid dependency cuts and individualized success bonuses in an ordered complementary service game, minimizing committed bonuses plus cut fees at a prescribed worst-case local-reliability target. The paper derives an exact linear-time worst-risk recurrence over approximate coarse correlated equilibria, homogeneous commitment bounds and organizational-scale laws, and a constant-factor construction. An exhaustive certified optimizer is compared with optimized reward-only and common-reward alternatives on controlled heterogeneous grids. A two-service LLM game provides limited behavioral compatibility evidence under frozen targets.

Critical strengths
  1. The exact worst-case characterization is a substantial and well-structured theoretical contribution. The prefix upper bound is paired with an explicit attaining CCE, including nonpositive margins and saturation (Theorem 1; Appendix B). The commitment bounds and organizational-scale results compare achievable designs against arbitrary reward vectors rather than assuming balanced partitions are optimal (Theorem 3; Corollary 4; Appendix D).

  2. The controlled comparisons use strong optimized baselines and independently check numerical bounds rather than equating solver success with optimality (Sections 4 and 6; Appendices E, G, and H). The 300-case primary panel and the heterogeneity continuation distinguish the value of structure from individualized rewards, include cut fees, and clearly separate deterministic grid summaries from population estimates. The post-hoc reallocation diagnostic also usefully quantifies how much of the common-reward gap is reward allocation versus residual structural coupling.

Critical weaknesses
  1. The applicability to reliable agent services depends on strong technology assumptions that the experiments do not validate. A paid cut is assumed to remove a predecessor requirement while preserving deliverable quality and all other production parameters, with public known costs/weights/tolerances. The guarantee concerns a randomly selected local check; the whole-task coverage bound can be weak when minimum verification weight is small (Section 3; Appendix B.1). The paper acknowledges this scope, but an operational example is still needed to show when actual restructuring has the modeled isolation property and what the reliability certificate means for a complete service.

  2. The LLM evidence is narrow relative to the service framing. All optimized trajectories in the two-agent experiment choose HH throughout; after the cut both agents have dominant high effort, and on the fixed chain upstream effort is dominant (Section 6.3; Appendix I). This is valid compatibility evidence for the specified game, but does not test robust behavior under longer dependencies, heterogeneous agents, or actual costly task execution. Proxy credits are not API expenditure. The theoretical result should remain the main basis for the contribution rather than treating this experiment as validation of practical workflow reliability.

Questions for authors
  1. Can the authors give a concrete existing workflow example in which a cut's cost and isolation property are independently justified, and explain how the local-check target translates into whole-deliverable reliability? If this is outside the current evidence, please sharpen the practical claims accordingly.

  2. How sensitive is the optimized design to errors in estimated effort costs, tolerances, and production technology? Appendix D.3 gives a uniform-error transfer argument; evaluating its resulting conservatism on the existing cases would clarify its operational usefulness.

  3. Can the behavioral claim be stress-tested within the present framework using longer or heterogeneous games, or perturbed initial play, while keeping the tolerance frozen before calls? This would test the bridge beyond persistent HH behavior in the exact two-agent game.

4 comments
AuthorsOpenReview ↗

Response to Reviewer L4wN (1/3)

Thank you for recognizing the value of our exact risk characterization and controlled comparisons. Stimulated by your questions, we derived an exact characterization for all-modeled-checks reliability, quantified design robustness under parameter uncertainty against Appendix D.3, and conducted 48 behavioral stress-test trajectories across multi-service, mixed-model, and perturbed-start settings.

Q1. All-modeled-checks reliability and operational workflow cuts

Exact all-checks reliability characterization and 300-instance redesign. Within our binary-action model and sampled-local-check payment rule, we can move directly from sampled local checks to joint success across all modeled checks. Let G={a:there exists i with ai=0}G = \lbrace a : \text{there exists } i \text{ with } a_i = 0 \rbrace denote failure of at least one modeled verification item, and let eje_j denote the endpoint of module jj. Worst-case all-checks failure over approximate CCEs admits the exact, attainable characterization:

sup⁡μ∈CCEε(R,b)Pr⁡μ(G)=min⁡{1,∑jQej},\displaystyle \sup _ {\mu \in \mathrm{CCE} _ {\boldsymbol{\varepsilon}}(R,b)} \Pr _ {\mu}(G) = \min\left\lbrace 1, \sum _ j Q _ {e_j}\right\rbrace,

where QQ is the clipped recurrence in Theorem 1, reset to zero at each module root.

  • Proof and LP verification: Each module's terminal value QejQ _ {e_j} bounds its module failure probability, giving the capped union upper bound. Conversely, coupling Theorem 1's module prefix witnesses via consecutive arcs on a unit circle attains the maximum union probability while preserving all unilateral-deviation constraints (cross-module terms cancel in payoff differences, covering zero tolerances, nonpositive margins, and saturation). We also numerically verified this analytical proof against 448 complete-profile CCE linear programs enumerating all action profiles and fixed-deviation constraints (maximum objective/primal discrepancy 2.22×10−162.22 \times 10^{-16}; these LP checks serve as numerical verification rather than a substitute for the analytical proof).
  • Certified savings under all-checks targets: We redesigned all 300 heterogeneous primary instances at two all-checks failure targets (0.05 and 0.10, yielding 600 instance-target conditions and 1,800 certified contracts). All three methods use the same all-checks failure target within each paired instance, while retaining the original costs, verification weights, tolerances, and cut fee, as well as the sampled-local-check payment rule (strictly positive tolerances and targets below 1 preserve the convex reduction throughout):
All-checks failure targetJoint saving vs. fixed workflow + individual rewardsJoint saving vs. optimized workflow + common reward
0.0524.996%15.907%
0.1025.508%21.069%

(Entries report median paired savings, 1−Cjoint/Cbaseline1 - C _ {\text{joint}} / C _ {\text{baseline}}, across the 300 instances.) Whereas Table 1's 55.5% median saving reflects sampled local-check reliability, joint workflow–reward design retains approximately 25% median savings under the stricter requirement that every modeled check succeeds simultaneously.

Operational workflow-cut mapping and scope. Concretely, consider a two-stage pipeline of constraint extraction (S1S_1) followed by scheduling (S2S_2), where S2S_2 normally relies on S1S_1's generated constraint ledger. A workflow cut grants S2S_2 and its verifier direct access to the original source requirements and public request rather than routing solely through S1S_1's intermediate ledger, removing the modeled predecessor failure dependency at a stipulated principal-side tariff ρ\rho calibrated from a token-cost proxy while retaining both tasks. Operationalizing this certificate on a deployed system requires verifying two domain conditions: (i) that the restructuring genuinely isolates S2S_2's check while preserving required production and verification semantics, and (ii) that physical deliverable failure is contained in GG across every compared workflow (as unmodeled production or checker errors lie outside the game-theoretic certificate).

AuthorsOpenReview ↗

Response to Reviewer L4wN (2/3)

Q2. Parameter uncertainty and evaluating Appendix D.3

Exact robustness on rectangular uncertainty sets. Because Theorem 1's clipped recurrence is nondecreasing in effort costs cc and tolerances ε\boldsymbol{\varepsilon}, optimizing directly at the upper corner (c+,ε+)(c^+, \boldsymbol{\varepsilon}^+) provides an exact robust certificate for any specified rectangular uncertainty set, conditional on the true parameters lying inside that set. Evaluating 5%, 10%, and 20% uncertainty across all 300 primary instances (δ=0.01\delta = 0.01) shows moderate commitment premiums over the nominal design:

Relative uncertaintyCost onlyTolerance onlyCost + tolerance
5%1.883%1.639%3.584%
10%3.742%3.244%7.124%
20%7.471%6.406%14.189%

At 20% simultaneous cost and tolerance uncertainty, the median paired commitment premium is 14.189%.

Quantifying the conservatism of Appendix D.3. Comparing Appendix D.3's general transfer bound against direct optimization at the exact uncertainty-set endpoint under cost-only uncertainty (νi=αci\nu_i = \alpha c_i, κ=0\kappa = 0) clarifies their relative conservatism:

Cost uncertainty α\alpha5%10%20%
Median D.3 / exact-endpoint commitment2.2243.2265.039

Each entry is the median over 300 paired Joint commitments of the per-instance ratio UiD.3/UiendpointU_i^{D.3}/U_i^{\mathrm{endpoint}}, not a ratio of cohort medians.

This difference reflects how D.3 transfers cost uncertainty into the behavioral tolerance. For binary linear costs and relative cost uncertainty α\alpha, the cost-deviation term is νi=αci\nu_i = \alpha c_i, giving εi′=εi+αci\varepsilon_i' = \varepsilon_i + \alpha c_i. With κ=0\kappa = 0, the transfer bound adds this term directly to the tolerance, whereas direct endpoint optimization retains εi\varepsilon_i and replaces cic_i with (1+α)ci(1 + \alpha)c_i. On our primary benchmark, mean effort cost is approximately 1 while mean tolerance is approximately 0.01, so a 5–20% cost perturbation increases the effective tolerance in D.3 to approximately 6–21 times its nominal scale, explaining the observed gap.

For production-technology misspecification, Appendix D.3 assumes a uniform production-success error bound κ\kappa across profiles and a cost-deviation error bound νi\nu_i across unilateral deviations, enlarging the estimated-game tolerance to εi′=εi+2biκ+νi\varepsilon_i' = \varepsilon_i + 2 b_i \kappa + \nu_i with an additional κ\kappa in the local-risk bound. Protection against production misspecification remains conditional on these uniform-error assumptions, while checker errors or cut-induced quality shifts require separate domain validation.

AuthorsOpenReview ↗

Response to Reviewer L4wN (3/3)

Q3. Behavioral stress tests beyond persistent HH play

We executed 48 fresh 64-round trajectories with pre-frozen thresholds (ε=0.05\varepsilon = 0.05, expected local reliability ≥0.90\ge 0.90) spanning three-service chains, mixed-model pairs, and forced low-effort starts (four trajectories per condition). Each cell reports the number of trajectories satisfying the regret-tolerance criterion; the counts for regret, expected local reliability, and their conjunction happen to coincide in every condition:

Stress testFixed contractJoint contractEvaluation window
Three services, DeepSeek3/43/4Rounds 1–64
Three services, Qwen3/41/4Rounds 1–64
Mixed: DeepSeek / Qwen3/42/4Rounds 1–64
Mixed: Qwen / DeepSeek2/42/4Rounds 1–64
Forced-low start, DeepSeek2/43/4Rounds 9–64
Forced-low start, Qwen3/44/4Rounds 9–64

In mixed games, model order denotes Agent 1 / Agent 2. In forced-low tests, all agents were required to play low effort during rounds 1–8 with the intervention disclosed; over the full 64-round horizon, those eight forced-low rounds mechanically cap expected local reliability at 56/64=0.875<0.9056/64 = 0.875 < 0.90, yielding 0/8 full-horizon passes for both contracts, so recovery is evaluated over the free-choice window, rounds 9–64.

Behavioral takeaways and theoretical meaning:

  • Post-perturbation recovery window: In these recovery-window tests (rounds 9–64), Joint attains both criteria in 7/8 trajectories, compared with 5/8 for Fixed. All 12 passing trajectories return to HH immediately at round 9, indicating immediate behavioral recovery rather than gradual within-window adaptation.
  • Stage-game dominance vs. LLM execution in longer games: In three-service Qwen runs, trajectories lock into zero-switch profiles (HHH ×\times 3, HHL ×\times 1 under Fixed; LHH ×\times 3, HHH ×\times 1 under Joint). Notably, Joint Agent 1 has a strictly dominant high-effort payoff margin of approximately 0.5850.585 regardless of downstream actions, yet plays L throughout three runs. Because Fixed and Joint simultaneously vary structure and bonus magnitudes over four-trajectory cohorts, these contrasts are descriptive rather than isolating a causal effect of structure or bonus level alone: they reinforce our core distinction between certifying game-theoretic incentives (Theorem 1) and empirical model compliance, which is non-uniform across architectures and game lengths.

Taken together, these results strengthen our theoretical foundation with an exact all-checks reliability characterization and a quantitative parameter-uncertainty analysis, while using controlled stress tests to characterize post-perturbation recovery and model-level compliance alongside the certified incentive design.

Dear Reviewer,

We sincerely apologize for the additional message and appreciate your time and consideration, especially during this busy review period.

We would be grateful for your thoughts on whether our responses have adequately addressed the concerns raised in your review.

If any concerns remain or if any part of our response requires further clarification, we would be truly grateful for your guidance and would be more than happy to provide additional explanations.

Thank you again for your valuable feedback and for taking the time to engage with our work. We sincerely appreciate your consideration.

Sincerely, The Authors

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

StructPay jointly optimizes workflow cuts and individual success bonuses in an ordered team-production model. The objective is to minimize bonus commitment and restructuring fees subject to a local-check reliability requirement under every approximate coarse correlated equilibrium, abbreviated as CCE. Theorem 1 gives an exact, attainable recurrence for worst-case failure risk that can be evaluated in linear time for a fixed contract. The paper uses this result for certified optimization and derives matching-order commitment bounds and a constant-factor construction under homogeneous assumptions. It also identifies an interior square-root law for module count and a family whose cost ratio between fixed and jointly optimized workflows grows at least linearly with the number of services. The reported evaluation includes 300 heterogeneous instances, a 2,700-entry heterogeneity continuation, and a two-agent experiment using two LLM families. The experimental savings measure commitment in the specified game, and reliability measures the success of a sampled local check.

Critical strengths
  1. I recognize the value of Theorem 1. It covers arbitrary nonnegative bonuses and heterogeneous deviation tolerances, including zero bonuses and saturation. The attaining CCE constructed in Appendix B establishes tightness simultaneously across local checks. This gives an exact reliability constraint for contract design under correlated play.

  2. I consider the commitment bounds in Theorem 3 informative. Under the stated homogeneous assumptions, the lower bound covers all feasible individual bonus vectors, while the upper bound has an explicit construction. Together with the cut fee, these bounds explain the tradeoff between reward commitment and module count. The fixed-workflow comparator in Table 1 also optimizes individual rewards, so the reported structural gains are measured against a baseline that permits asymmetric payments.

Critical weaknesses
  1. I see limited evidence for the incremental benefit of jointly selecting structure and rewards. Appendix G shows that individual reward reoptimization on the structure selected under a common bonus reduces the median ratio to the joint optimum from 1.221 to 1.029. Thus, much of the 18.1% saving in Table 1 is recoverable without revisiting the structure. Savings still exceed 10% in 77 of 300 cases, but the reported diagnostic concerns selected partitions. Figure 6 leaves tied alternatives unresolved in H2. I cannot determine how much of the remaining gap persists under favorable tie selection, which matters when attributing the gains to joint design.

  2. I find the empirical basis for choosing the behavioral tolerance before contract design limited. Equation 3 measures deviation gains in utility units, which depend on the bonuses and workflow. Appendix I reports zero regret and uninterrupted HH play in all 16 optimized-contract trajectories, while several under-incentivized controls exceed the prescribed tolerance. These results do not establish how to select a tolerance for a new contract before observing behavior. Since that choice affects both the reliability constraint and the required commitment, the evidence leaves an unresolved calibration problem in applying the mechanism to LLM agents.

Questions for authors
  1. I want to know how many primary instances have multiple partitions that are optimal under a common bonus. Where ties occur, what gap remains after individual bonuses are reoptimized on every tied partition and the cheapest result is selected? How do the median ratio of 1.029 and the count of 77 instances with savings above 10% change?

  2. How the tolerance would be selected before optimizing a contract? Do the additional behavioral diagnostics mentioned in Section 7 test a calibration rule across changes in bonuses or structure? If observed regret exceeds the prescribed tolerance, how would the rule change the selected contract and its commitment?

3 comments
AuthorsOpenReview ↗

Response to Reviewer uGBb (1/2)

Thank you for the careful review and for recognizing the value of Theorem 1's exact risk characterization and Theorem 3's commitment bounds. Your questions help us distinguish the benefit of individualized rewards from the additional value of joint workflow–reward design, and clarify how behavioral tolerances enter practical contract selection.

Q1. Exact ties and the residual value of joint design

We examined all 204,000 ordered partitions across the 300 primary instances, using exact risk-function identities and rational exclusion certificates. For every partition tied for the common-bonus optimum, we reoptimized individual bonuses and retained the cheapest resulting sequential contract.

  • How often do ties occur? 14/300 instances have exact ties (11 two-way, one three-way, and two four-way); the other 286/300 have unique common-bonus optima.
  • What changes under favorable tie-breaking? Stage-2 commitment decreases in 4/14 tied instances and is unchanged in the other ten. The median sequential/joint commitment ratio changes from 1.029 to 1.026805, with a certified numerical enclosure of [1.02680434, 1.02680615]. Certified savings above 10% remain 77/300, and strictly suboptimal sequential solutions change from 205/300 to 204/300.

We also gave the sequential comparator additional flexibility: Stage 1 could retain structures within 0.1% or 1.0% of the common-bonus optimum before Stage 2 selected the lowest-cost individualized-reward contract.

Stage-1 allowanceInstances with multiple eligible structuresMedian sequential/joint ratioStrictly suboptimalCertified saving >10%
Exact ties14/3001.026805204/30077/300
Within 0.1%37/3001.026805204/30075/300
Within 1.0%151/3001.017404187/30057/300

Exact ties were resolved using risk-function identities and rational exclusion certificates, rather than overlapping numerical optimizer intervals. The near-optimal comparisons use certified membership bounds, with no unresolved membership cases on this grid.

The H2 continuation further characterizes the residual structural benefit under heterogeneity. Among 2,196 unique inputs, 99 have exact ties. With favorable tie selection, strict residual structural losses decrease from 986 to 965 of the original 2,700 indexed entries; allowing 0.1% first-stage slack further reduces this to 939. The pooled median ratio remains one. At the endpoints, the fraction with certified residual structural loss increases from 5.6% at λ=0\lambda = 0 to 55.0% at λ=1\lambda = 1. Repeated indexed endpoints are not independent inputs.

These results sharpen the attribution of Table 1's 18.1% median saving over common-bonus design: individualized rewards account for most of that median improvement, while simultaneous optimization provides an additional, heterogeneous structural benefit. For example, on primary instance h230, the unique common-bonus-optimal structure (11,1) costs 1220.04 after individual reward re-optimization, whereas joint design selects (4,4,2,2) at 849.93, a 30.3% saving. Across the primary panel, 77/300 instances still exhibit certified savings above 10% after exact tie-breaking.

Theorem 1 supports certified reliability evaluation for both sequential and joint contracts. The additional role of joint optimization is to certify minimum commitment over the full space of structures and individualized rewards, rather than over the structure already selected in Stage 1.

AuthorsOpenReview ↗

Response to Reviewer uGBb (2/2)

Q2. Selecting tolerance before design and responding to exceedances

(1) Pre-design choice. As an empirical pre-design heuristic, one can observe nonnegative external regret r^k,i+\hat{r}^+ _ {k,i} across a pilot set of contracts C\mathcal{C}, freeze a conservative factor

η=2max⁡(k,i)∈Cr^k,i+ci\displaystyle \eta = 2 \max _ {(k,i)\in\mathcal{C}} \frac{\hat{r}^+ _ {k,i}}{c_i}

before optimizing the new contract, and prescribe the cost-normalized tolerance εi=ηci\varepsilon_i = \eta c_i.

Because the public effort cost cic_i is independent of the bonuses bib_i being optimized, εi\varepsilon_i is fixed prior to optimization without circular dependence on the solution. By contrast, under a stake-scaled rule εi=ηbidi\varepsilon_i=\eta b_i d_i with 0<η<10<\eta<1, any module root with positive incentive margin (bidi>cib_i d_i>c_i) has recurrence value

Qi=min⁡(1,ηbidibidi−ci)≥η,\displaystyle Q_i=\min\left(1,\frac{\eta b_i d_i}{b_i d_i-c_i}\right)\geq\eta,

which imposes a nonvanishing lower bound on the root's recurrence value even as the bonus increases. Cost normalization avoids this particular bonus-dependent floor. The transfer of a calibration factor to an unseen contract nevertheless remains an empirical behavioral question, rather than a guarantee implied by Theorem 1.

(2) Behavioral diagnostics and tolerance selection. The behavioral diagnostics in Section 7 and Appendix I examine whether agents' observed play is compatible with the prescribed regret and local-reliability criteria. In E6, all 16 optimized-contract trajectories satisfy both prespecified thresholds. Together with the additional checks across incentive settings retained in our research archive, these results provide behavioral evidence for the tested contracts and incentive settings.

The cost-normalized rule in (1) provides a complementary pre-design specification: it fixes the tolerance before optimizing a new contract, after which the resulting contract can be evaluated on fresh play. The diagnostics inform behavioral compatibility under the tested settings; they should not be read as a universal guarantee for arbitrary unseen contracts.

Analytically, in our two-agent fully separated setting (ci=1c_i=1, di=1/2d_i=1/2, δ=0.1\delta=0.1, and bi>2b_i>2), 64-round empirical regret satisfies

r^i=(bi2−1)Ni,L64.\displaystyle \hat{r} _ i=\left(\frac{b_i}{2}-1\right)\frac{N _ {i,L}}{64}.

Because the joint optimizer sets the split-structure margin to bi2−1=εδ\frac{b_i}{2}-1=\frac{\varepsilon}{\delta}, satisfying r^i≤ε\hat{r} _ i\leq\varepsilon in this setting requires Ni,L64≤δ\frac{N _ {i,L}}{64}\leq\delta, i.e., at most 10% low-effort actions for any prescribed ε>0\varepsilon>0. Thus, enlarging ε\varepsilon raises the optimized bonuses to strengthen stage-game incentives, while the required action-level compliance rate remains unchanged in this particular game. This illustrates why the behavior of agents under the newly selected contract should be checked directly.

(3) If regret exceeds the chosen tolerance. Let r^i\hat{r} _ i be each agent's measured nonnegative external regret and set ε~i=max⁡(εi,r^i)\widetilde{\varepsilon} _ i=\max(\varepsilon_i,\hat{r} _ i). The empirical play distribution then belongs to the corresponding ε~\widetilde{\varepsilon}-CCE set, so Theorem 1 provides an exact reassessment of the existing contract's worst-case local-check risk, R(R,b,ε~)\mathcal{R}(R,b,\widetilde{\varepsilon}). If this exceeds δ\delta, the original tolerance-based certificate is insufficient for the observed behavior; provided the updated problem is feasible, the existing optimizer can re-solve the contract-design problem using ε~\widetilde{\varepsilon} to obtain an updated structure, bonus vector, and commitment. The revised contract would then require fresh behavioral validation.

The commitment and structural consequences of widening ε\varepsilon can be quantified directly. In the two-service example (ci=1c_i=1, di=0.5d_i=0.5, δ=0.1\delta=0.1, and cut fee ρ=0.25\rho=0.25), increasing ε\varepsilon from 0.05 to 0.1 raises Fixed Chain and Joint commitments from 7.949 and 6.25 to 11 and 8.25, respectively; joint design still selects the cut structure. This quantifies how a more conservative behavioral assumption changes commitment and structure, without implying that re-optimization alone guarantees compliant LLM behavior.

Together, these points provide a concrete pre-design heuristic and show how the exact risk characterization and existing optimizer quantify the reliability, structural, and commitment consequences of tolerance adjustments, while keeping Theorem 1's conditional CCE-risk guarantee distinct from forecasting LLM behavior across unseen contracts.

Dear Reviewer,

We sincerely apologize for the additional message and appreciate your time and consideration, especially during this busy review period.

We would be grateful for your thoughts on whether our responses have adequately addressed the concerns raised in your review.

If any concerns remain or if any part of our response requires further clarification, we would be truly grateful for your guidance and would be more than happy to provide additional explanations.

Thank you again for your valuable feedback and for taking the time to engage with our work. We sincerely appreciate your consideration.

Sincerely, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.