PaperlayerView exact revision on arXiv

Source-linked AI summary

BROCADE: Broker-based Contract Design for the Multi-Agency Model

Yangguang Shi, Ron Lavi, Jie Zhang

arXiv:2610.35291v1cs.GT

TL;DR

Contracts must align principals’ truthful bids with agents’ hidden effort when both determine a shared project’s success. BROCADE separates these sides and characterizes principal incentives; its results range from a constant-factor DSIC guarantee that may violate budget balance to an O(log m) universally DSIC and budget-balanced guarantee independent of n.

  • Problem

    Contract design must incentivize truthful bidding by principals and effort by agents, whose payments and actions jointly affect project success and principal utilities.

    Source: §1 · pp. 2–3

  • Method

    BROCADE introduces a broker to separate principal payments from agent incentives and characterizes DSIC through monotonicity of each principal’s effective allocation.

    Source: §1 · p. 3

  • Results

    A constant-factor DSIC contract may violate BB; with budgets at least the maximum principal value, deterministic DSIC/BB has no finite guarantee and randomized versions face an Ω(n) lower bound, while SATOSH achieves O(log m) independent of n.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The guarantees depend on the benchmark and feasibility constraints: the n-independent randomized guarantee uses one quarter of fixed-price revenue as its agent-selection budget.

    Source: §1 · pp. 3–4

    For the SumV benchmark, achieving any finite approximation guarantee requires violating budget balance.

    Source: §6.2 · p. 19

Abstract

from arXiv · show

We study welfare maximization in a contract model with $m$ principals who privately value a public project's success and $n$ agents whose costly effort is unobservable. Contracts induce truthful dominant strategies for principals and equilibrium effort by agents, maximizing the expected total value of eligible principals. We develop three tools: a broker that separates payments from principals and payments to agents, an extension of Myerson's Lemma characterizing dominant-strategy incentive compatibility (DSIC), and a black-box reduction to budget-constrained single-principal contract design. When the success probability is a strictly monotone XOS function of agents' actions, these tools yield three results. First, a deterministic DSIC contract achieves a constant approximation against a benchmark that qualifies every principal and maximizes success probability using budget $\sum_j v^j$, but may violate budget balance (BB). Second, against benchmarks with budgets at least the largest principal value, deterministic DSIC and BB contracts admit no finite approximation guarantee, even with two agents. Universally DSIC and universally BB randomized contracts have an $\Omega(n)$ approximation lower bound, even for a fixed number of principals. Third, using one quarter of the optimal fixed-price revenue supported by at least two principals as the benchmark budget, we obtain a universally DSIC and universally BB randomized contract with an $O(\log m)$ approximation ratio independent of $n$.

1 Introduction

The paper studies contracts with multiple principals who have private values and multiple agents whose costly effort is hidden, aiming to maximize eligible principals’ expected total value. It develops tools for truthful bidding and agent selection, and shows how budget balance and benchmark choice shape achievable guarantees.

1 Introduction

  • The model combines private principal values and hidden agent effort, with eligibility determining which principals benefit from the common project outcome.The objective is the expected total value of eligible principals; principal payments fund agent incentives, while agent actions determine success probability and affect principal incentives.Source: §1 · pp. 2–3
  • BROCADE inserts a non-strategic broker to separate principal payments from agent incentives, reducing transfer variables from O(mn) to O(m+n).The broker-based and broker-free formulations are equivalent under budget balance.Source: §1 · pp. 3–4
  • The DSIC characterization makes an allocation rule implementable exactly when each principal’s effective allocation, δ_j f(S), is monotone in her bid, with a corresponding payment rule.The effective allocation combines eligibility with the success probability generated by the selected agents.Source: §1 · p. 3
  • A black-box transformation turns a constant-approximation fixed-budget agent-selection algorithm into a budget-scalable selection function whose success probability is non-decreasing as budget rises.This monotonicity supports DSIC on the principals’ side and lets the framework use budget-constrained contract-design algorithms.Source: §1 · pp. 3–4
  • A deterministic DSIC contract achieves a constant approximation against the SumV(v) benchmark, which uses all principals’ total value as the agent budget, but may violate budget balance.The contract is non-excludable, so all principals are eligible to benefit.Source: §1 · p. 3
  • With benchmark budgets at least the largest principal value, deterministic DSIC and budget-balanced contracts have no finite approximation guarantee, while universally DSIC and budget-balanced random contracts incur an Ω(n) lower bound.The randomized lower bound holds even for additive success functions and any fixed number of principals.Source: §1 · p. 3
  • SATOSH is universally DSIC and budget-balanced, achieving an O(log m) approximation independent of n against a benchmark using one quarter of F2(v) as the agent budget.F2(v) is the optimal fixed-price revenue when at least two principals are considered; SATOSH uses one subset’s revenue to set a toll for the other subset.Source: §1 · pp. 3–4
  • The paper addresses a setting with multiple principals and agents who have private types, which the authors say they are unaware of prior papers considering.The related-work discussion describes common agency with hidden actions and incomplete information as still largely open.Source: §1 · p. 4

2 Preliminaries

The multi-agency model combines principals’ private values and agents’ hidden, costly effort in a shared project whose success probability depends on the agents who exert effort. The contract must incentivize effort and truthful bidding while maximizing eligible principals’ expected value.

Model

  • Each principal privately values project success, while agents choose whether to exert costly effort and their actions are hidden.Agent costs are publicly known and strictly positive for exerting effort; the project’s success probability depends on the subset exerting effort.Source: §2 · pp. 4–5

Contracts

  • Contracts make success-contingent transfers from principals to agents and choose which principals are eligible to benefit from success.An excluded principal receives no value and makes no payment.Source: §2 · p. 5

Success function

  • The success function is assumed to be strictly monotone and XOS, with oracle access used for contract-design algorithms.The paper considers value and demand oracles for the succinctly represented function.Source: §2 · p. 6

Objective and incentives

  • The design objective is to maximize the expected total value of eligible principals using a DSIC contract.Eligible values generalize success-probability maximization in single-principal contract design.Source: §2 · p. 6

Approximation benchmarks

  • The benchmark upper-bounds eligible value under a transfer budget R(v), using all principals’ values and the best success probability achievable with that budget.The paper also considers F2(v), the optimal fixed-price revenue supported by at least two principals.Source: §2 · p. 7

3 Broker-based Contract

BROCADE inserts a non-strategic broker between principals and agents, reducing the contract’s decision variables while separating collected payments from agent incentives. The broker-based and broker-free formulations are utility-wise equivalent, and the broker representation can preserve DSIC and budget balance.

3 Broker-based Contract

  • BROCADE uses a non-strategic broker to collect principal payments and redistribute them to agents, reducing decision variables from O(mn) to O(m + n).The broker’s transfers depend on bids because it cannot observe agents’ actions.Source: §3 · p. 7
  • The broker-based protocol specifies principal-to-broker and broker-to-agent transfers, followed by bids, agent responses, and success-contingent payments.The broker collects from principals and pays agents if the project succeeds.Source: §3 · p. 7

3.1 Equivalence between broker-free and broker-based contracts

  • Every broker-free transfer function has a budget-balanced broker-based counterpart with equivalent utilities, and the converse also holds.The reverse construction uses fractional bin packing to distribute broker payments among principal-agent pairs.Source: §3.1 · pp. 8–9
  • The equivalence lets contract design use a budget-balanced broker representation without changing the underlying problem; DSIC broker-free contracts can be represented as DSIC and budget-balanced broker-based contracts.This representation supports formulating the design objective using broker-based contracts.Source: §3.1 · pp. 8–9

4 Incentive Compatibility and Monotone Allocation Rules

The section characterizes truthful implementation through monotonicity of each principal’s effective allocation, which combines eligibility with the project’s success probability. It supplies a corresponding payment rule and accounts for agent incentives and budget balance in constructing contracts.

Agent incentives and budget balance

  • Agents receive minimum success-contingent payments sufficient to make the target set an equilibrium; any surplus can be redistributed to ensure exact budget balance.The surplus payment preserves the success probability and principal utilities.Source: §4 · p. 9

Allocation and payments

  • The allocation rule chooses principal eligibility and a target agent set, while the payment rule specifies principal transfers to the broker.The effective allocation for a principal is eligibility multiplied by the success probability induced by the selected agents.Source: §4 · pp. 9–10

Incentive compatibility

  • An allocation rule is DSIC-implementable if and only if it is monotone in each principal’s bid, with a corresponding payment rule.The relevant allocation incorporates the public project’s shared success probability, so the characterization extends the standard Myerson approach.Source: §4 · p. 10
  • The monotonicity condition is necessary for DSIC because truthful bidding must dominate misreports, and the constructed payments implement a monotone allocation.The proof also establishes nonnegative transfers and individual rationality for the payment construction.Source: §4 · pp. 10–11

5 Budget-Scalable Selection

The section constructs a budget-scalable selection function: the chosen agents’ success probability does not decrease as the available budget rises. A tagged-partition method turns a black-box approximation into such a selection rule with a constant approximation guarantee.

5 Budget-Scalable Selection

  • Budget scalability requires the selected set’s success probability to be non-decreasing with budget, a property used to obtain DSIC contracts.The paper transforms a black-box constant-approximation algorithm into an O(1)-approximate budget-scalable selection function.Source: §5 · pp. 12–13
  • The optimal budgeted success-probability selection is computationally infeasible in general, since it includes the NP-hard knapsack problem even for additive functions.An available constant-approximation algorithm cannot be used directly because its budget scalability is unknown.Source: §5 · pp. 12–13

5.1 Tagged partition-based selection

  • TPS builds an increasing sequence of budget thresholds, each paired with a feasible agent-set tag, and selects among affordable tags.The final tag contains all agents; the same tagged partition is used across bid profiles.Source: §5.1 · pp. 13–14
  • A tagged partition with jump ratio r yields an r-approximate, budget-scalable selection function.TPS satisfies the budget constraint at every budget and chooses the best affordable tag.Source: §5.1 · p. 14

5.2 Computing the Tagged partition

  • TaggedPartition constructs the thresholds and tags in polynomial time using value-oracle and α-demand-oracle access, with a jump ratio bounded by a constant depending on α.The resulting partition length is polynomially bounded.Source: §5.2 · p. 16
  • The black-box construction converts an r-approximation for budgeted success maximization into a budget-scalable (129 · r)-approximate selection function.With the cited constant-approximation algorithm, TPS gives an O(1)-approximate budget-scalable selection function.Source: §5.2 · p. 16

6 Deterministic Contracts: Positive and Negative Results

Section 6 presents a deterministic DSIC contract with a constant approximation against the SumV benchmark, then shows that deterministic DSIC and budget balance cannot guarantee any finite approximation against budgets at least as large as the largest principal value.

6.1 A Non-excludable Deterministic Contract

  • NEED is a non-excludable deterministic DSIC contract with a constant approximation against OPT(·, SumV), but it may violate budget balance.Its agent-selection budget is SumV(v), while principal payments can total less than the budget used for agent incentives.Source: §6 · p. 16, §6.1 · p. 19, §6.2 · p. 19
  • NEED separates the agent-selection budget from principal payments and computes payments using a breakpoint oracle in O(K) queries and operations.The stated bound is K = O(n + log(Bmax/Bmin)); the approximation guarantee additionally assumes an efficiently computable, coordinatewise nondecreasing budget function with an efficient breakpoint oracle.Source: §6.1 · pp. 17–18

6.2 Impossibility Results for Deterministic Contracts

  • No deterministic DSIC and budget-balanced contract has a finite approximation guarantee for any revenue function R(v) ≥ max_j vj, even with two agents and additive success probabilities.The guarantee fails on at least one of two value profiles, which may depend on the contract.Source: §6.2 · pp. 19–20

7 The Sampling Toll Sharing Contract

Section 7 develops and analyzes SATOSH, a randomized contract for multiple principals and agents, covering randomized contract equivalence and monotonicity, its universal DSIC and budget-balance properties, and its approximation guarantee under an F2-based benchmark. It also establishes an Ω(n) lower bound under stronger benchmarks and presents SATOSH’s Oα(log m) guarantee under the stated weaker benchmark.

7.1 Definitions and Extensions

  • Universally DSIC and universally BB random contracts can be converted to broker-based random contracts with the same eligible values, and random allocations are implementable by universally DSIC contracts exactly when universally monotone.Applying the deterministic payment rule to each realization of a universally monotone allocation gives a universally DSIC contract.Source: §7.1 · pp. 20–21
  • Universally DSIC and universally BB random contracts have a worst-case approximation ratio of Ω(n), even for fixed m, when the benchmark budget is at least the largest principal value.The lower bound holds for n ≥ 2 and an additive success probability function.Source: §7.1 · pp. 21–22
  • With benchmark budget F2_1/4(v), SATOSH is universally DSIC and universally BB and achieves an O_α(log m) approximation independent of n for m ≥ 2.F2_1/4(v) is one quarter of the optimal fixed-price revenue supported by at least two principals; the benchmark is zero for m = 1.Source: §7.1 · p. 22

7.2 Algorithm Description

  • SATOSH samples principals into two groups, uses optimal fixed-price revenue to set a toll, and shares that toll among selected principals; its contract is universally budget balanced.The algorithm uses a random partition, and each selected principal pays an equal share of the toll.Source: §7.2 · pp. 22–24

7.3 Analysis of the DSIC Property of SATOSH

  • For each fixed coin realization, SATOSH’s allocation is universally monotone and its payment rule agrees with the payment characterization used to establish DSIC.The payment agreement holds when effective allocation is positive and in expected payment for all bid profiles.Source: §7.3 · p. 25
  • SATOSH’s random contract is universally DSIC because Algorithm 3 induces the same expected payments and utilities as a DSIC normalized payment rule, including at zero effective allocation.The payment-rule comparison applies for each fixed partition.Source: §7.3 · p. 26

7.4 Approximation Analysis

  • The approximation analysis bounds eligible-principal values relative to SumV and uses a lower bound on the probability that the extracted toll reaches a threshold tied to F2(b).Lemma 7.20’s logarithmic ratio cannot be obtained directly from the conventional SumV(b)/F(b) bound because SATOSH’s random eligibility may exclude principals counted by maxk k · πk(b).Source: §7.4 · pp. 26–27
Loading 2610.35291v1…