StructPay: Joint Workflow and Reward Design for Reliable Agent Services

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.