Online Contract Design

1 Introduction

Contract theory studies how a principal can incentivize agents to work, when work is costly for the agents and its outcome rewards the principal [Holmstr¨om, 1979; Holmstr¨om, 1982]. The economic tool for aligning incentives is contracts - performance-based payments schemes which the principal commits to. Contract theory is a cornerstone of microeconomics, recognized by the 2016 Nobel prize.

Recently, the rising research area of algorithmic contract theory studies contracts through the computational lens (for early papers see e.g. [Babaioff et al., 2012; D¨utting et al.,

2019], for a survey of the recent flurry of activity see [D¨utting et al., 2024]). Multi-agent settings are of particular computational interest: In such settings, the principal chooses a subset of agents to work for them as a team, and the agents' contracts must disincentivize them from free-riding on the efforts of other team members. Finding the subset of agents is inherently a combinatorial problem, and is tackled by works like [Babaioff et al., 2012; D¨utting et al., 2023a; Deo-Campo Vuong et al., 2024; Castiglioni et al., 2023; Cacciamani et al., 2024; D¨utting et al., 2025a; Alon et al., 2025] and many others. To date, the substantial body of work on multi-agent contracts has focused on the offline setting, in which the set of agents is known in advance, and the principal optimizes globally.

Bringing algorithmic contract theory closer to real-world applications calls for models that capture how interactions unfold over time. In many classic and modern environments, agents arrive sequentially and unpredictably. For example, a manager heading a team occasionally receives an application from a new potential team member; online labor platforms have a dynamic and fluctuating supply of workers; even when the team is to be composed of AI rather than human agents (see e.g. [Wu et al., 2023]), new AI models appear periodically. How should team contracts be designed when the set of potential participants is revealed gradually over time?

Online algorithms provide a classic framework and rich body of techniques for decision-making in settings characterized by sequential and uncertain arrivals [Borodin and ElYaniv, 2005]. In this paper, we marry this framework with contracts, and initiate the study of online contract design.

1.1 Our Contribution: OMACModel

As a first step towards integrating the two fields, we formulate the Online Multi-Agent Contract (OMAC) model (see Section 2). The OMAC model consists of sequential and uncertain agent arrivals that can conclude abruptly. We briefly survey the design of our model, deferring details to Section 2.

Our first design choice is how to approach uncertainty, where two standard approaches are the adversarial (worstcase) approach, and the Bayesian (stochastic) one. We follow the classic work of [Sleator and Tarjan, 1985], which introduces the competitive ratio under adversarial inputs as the gold standard for online algorithms. The competitive ratio measures the relative performance of an online algorithm compared to an optimal offline one (see Section 2 for a definition). The adversarial approach is particularly well-suited for situations with little to no data. 1 It provides the canonical worst-case baseline for contracts under online arrivals. While our focus is adversarial, we view our work as a gateway to future stochastic (or stochastic-adversarial hybrid) approaches to online contracts (see e.g. [Samuel-Cahn, 1984; Kleinberg, 2005; Babaioff et al., 2007; Kleinberg and Weinberg, 2012]).

We obtain our model by combining two fundamental settings: the adversarial online setting with preemption (e.g., [Buchbinder et al., 2015]), and the multi-agent contract setting [D¨utting et al., 2023a]. We now describe these and show how the seemingly unrelated settings blend together naturally.

[Buchbinder et al., 2015] describe an online hiring setting with arbitrarily-arriving agents. 2 The team of agents S must maintain proficiency (as measured by a value function f(S)) at all times, since it is unknown when the arrivals will cease, or when the team will need to take action. For example, this is the case if the team's job is to respond to an emergency, recover from a system crash, or supply a surge in demand [Valentine and Bernstein, 2025].

A central feature of their model is preemption - the principal is allowed to replace an agent who was tentatively accepted as more promising agents arrive. Agent dismissal, however, is final and irrevocable - the main characteristic of online decision-making settings. [Buchbinder et al., 2019] show that preemption is key to circumventing intractability and achieving constant-factor guarantees; there are many other such examples (e.g. [Feldman et al., 2009; Han et al., 2015]). Our model displays the same dichotomy, where preemption is what allows meaningful guarantees to emerge; for an impossibility result without preemption, see our Theorem 5.4.

In our model, after an online stage consisting of adversarial agent arrivals, tentative accepts, replacements, and irrevocable dismissals as in [Buchbinder et al., 2019], the composition of the team is finalized. Then, since the agents are rational and utility-maximizing, a game is played: the principal designs and offers contracts to the team members, who in turn decide whether to work or not. A working agent incurs a cost and contributes additively to the principal's reward. This is thus an instantiation with additive rewards of the multi-agent (offline) game formulated by [D¨utting et al., 2023a].

As in the formulation of [D¨utting et al., 2023a], the principal offers the agents linear contracts, i.e., a fixed share of the reward eventually generated by the team. The fixed shares should sum up to at most 1 (the entire reward), or to much less in order to reward the principal - this informally connects the setting to the knapsack problem (for a formal connection to knapsack a.k.a. budgeted maximization, see the full version of this paper [Lavi et al., 2026]).

Luckily, the linear contracts can be designed according to a simple elegant formula of [Babaioff et al., 2012], which induces an equilibrium in which all agents on the team are incentivized to work, while minimizing the principal's overall payment (equivalently, maximizing the principal's total utility). Thus, the main algorithmic challenge in OMAC is to maintain a competitive team during the online stage, while taking into account the overall contractual payment once the team is finalized.

1 This can be the case following technological shifts; e.g., there is little data on the next generation of AI agents to arrive, or on how the worker population will evolve in the GenAI era.

2 They use somewhat different language than us, referring to candidate players hired by a soccer team manager.

1.2 Our Contribution: Results and Techniques

Working in the OMAC model, in Section 4 we design a randomized algorithm that achieves a competitive ratio of 1/2 (competitive ratio is the standard approximation measure in online algorithms, see a formal definition in Section 2). We complement our positive result by showing that no deterministic online algorithm achieves a constant competitive ratio. We also establish that randomization allows a competitive ratio of at most 1/2. The impossibilities are established through a direct adversarial construction (see Section 5). Thus, our randomized algorithm achieves a tight, best-possible guarantee, and the case of additive rewards is fully resolved.

Our tight positive result is obtained via a randomized strategy built around balance points, a new structural concept that synchronizes the agents' shares with the principal's utility as arrivals unfold. This technique departs sharply from prior online algorithms, where objectives are always nonnegative and often additive or submodular in the chosen set. In our case, we optimize the principal's incentive-induced utility, which can be negative and non-submodular even when the reward function has additive structure. As a result, existing online algorithms for settings with preemption would fail in our model, as they might output solutions with arbitrarily negative utility. Our approach is explicitly designed to prevent such failures.

To place our approach in context, in the full version of this paper [Lavi et al., 2026] we formalize a connection between our problem and online budgeted maximization (knapsack) with preemption, and show how a known randomized algorithm of [Han et al., 2015] for this problem can be adapted to OMAC. However, this algorithm is based on static thresholds, and achieves a 1/4-competitive ratio for OMAC (as opposed to 1/2 for knapsack). Balance points serve as dynamic thresholds, which are essential for attaining the optimal competitive ratio of 1/2. They thus furnish the novel ingredient that resolves the challenge of OMAC optimally.

The connection to online budgeted maximization also reveals a barrier to going beyond additive rewards, to submodular ones: the problemof onlinemonotone submodular maximization subject to a budget constraint remains open [Rawitz and Ros´en, 2021]. Beyond submodular there are even more barriers: we can construct instances with XOS rewards (a superclass of submodular), where even randomized strategies fail to secure any constant-factor guarantee - thus ruling out the possibility of meaningful performance in this richer domain (see Section 5). Our construction exploits complementarities among the agents, which cause an agent's value and share to crucially depend on the composition of the team, in a way that is inherently unpredictable in an online setting.

Together, our results show a range of online contract design problems, from manageable to intractable. Our resolution of the additive and XOS cases is a first step towards defining the boundary between tractable and hard reward functions in our model of online contracts.

1.3 RelatedWork

Dynamic Contracts. Temporal models of contracting have previously been explored by multiple works, all quite different from ours. Several works on dynamic contracts have considered settings where a single agent is engaged with repeatedly. E.g., in [Ezra et al., 2024] the agent chooses actions sequentially, and in [Guruganesh et al., 2024] the principal optimizes the contract against a no-regret learning agent. Other works have focused on learning contracts over time, by interacting over many iterations with agents drawn from the same distribution, or alternatively with a single agent. The principal's goal in the learning process is to adapt the incentives based on past outcomes and thus achieve low regret [Ho et al., 2014; Zhu et al., 2023; Bacchiocchi et al., 2024; Chen et al., 2024; D¨utting et al., 2023b; Guruganesh et al., 2023]. In [Collina et al., 2024], the principal induces a multi-round game by adaptively choosing among k candidates which agent to contract with, again with the goal of no regret. Reinforcement learning approaches have also been considered [Ivanov et al., 2024; Wu et al., 2024; Bollini et al., 2024].

Preemption and Consistency. Online maximization problems with preemption have been studied extensively and under many different names like free dismissal, free disposal, removable, or recourse. A closely related line of work develops consistent algorithms, which bound the recourse under dynamic updates in problems like clustering and covering (e.g., [Lattanzi and Vassilvitskii, 2017; Fichtenberger et al., 2021; Gupta and Levin, 2020; Gupta et al., 2022; Łacki et al., 2021; Bhattachary et al., 2024]). In the terminology of [D¨utting et al., 2025b], our model is 1-consistent, since each new arrival may cause at most one new hire (dismissed agents are never rehired). However, our algorithmic techniques and analysis are quite different as they are closely tied to the challenges of the contracting model. Closer to our model are works on constrained online submodular maximization. As discussed above, budget constraints are still open; the recent work of [Yang and Zheng, 2024] studies cardinality constraints.

2 The OMACModel

We introduce an online contract model, which can be viewed from two perspectives: First, as the online version of the standard multi-agent contract setting [Babaioff et al., 2012; D¨utting et al., 2023a]; second, as the strategic version of the classic online decision problem with preemption [Buchbinder et al., 2015; Chan et al., 2018]. We present our model beginning with its online aspects, then its strategic ones.

Online Multi-Agent Contract (OMAC) Setting. In the OMAC setting, a principal interacts with an unknown set of agents N = [n], revealed sequentially in an arbitrary and unpredictable manner. The principal aims to hire a team-a subset S ⊆ N of agents. The team, once finalized, will be tasked with a project. Crucially, the principal does not know the total number of agents n in advance. I.e., from the principal's point of view, the process may terminate after any iteration. The principal must ensure that at every time step, the quality of the current team is competitive.

W.l.o.g., we call the ith agent to arrive agent i, and let Ni = [i] be the first i agents. At every step i, the principal chooses a tentative team Si, subject to the restriction Si ⊆ Si-1 ∪ {i} (with the convention that S0 = ∅). Note that the team after step i may or may not include the new agent i, and that previously chosen agents in Si-1 can be dismissed. However, any agent not tentatively chosen (i.e., any agent in Ni-1 \ Si-1) cannot be included in Si. Thus, the principal cannot rehire dismissed agents.

The team Sn chosen in step n is final. I.e., after step n is completed, the solution S is set to Sn, and no additional dismissals are allowed.

The above free dismissal assumption is precisely preemption, studied in many previous works on adversarial online algorithms. Since |Si \ Si-1| ≤ 1, it is also 1-consistency, studied e.g. in [D¨utting et al., 2025b] and characteristic of the rapidly growing literature on stable online algorithms (see Section 1.3). Without free dismissal, a hired agent would necessarily remain on the team throughout the arrival of subsequent agents. We do not study this variant since, as shown in Section 5.3, it becomes impossible to guarantee any meaningful performance for the principal through an online strategy.

The Principal's Reward Function. The final team S is delegated a project, whose outcome depends on the team's ensemble. As usual in multi-agent contract settings, this is captured by the reward function f : 2N → R≥0, which is a set function specifying the principal's reward f(S) from the project when carried out by team S. As standard in the literature, we assume that f is normalized (f(∅) = 0), and monotone (f(T) ≤ f(S) whenever T ⊆ S ⊆ N). This reflects that a project yields no reward given an empty team, and that extending a team can only increase the principal's reward. Our focus is on additive set functions f, where f(S) = ∑i∈S f({i}) for all S ⊆ N, meaning each agent's contribution is independent of other agents' contributions. In Section 5 we also consider XOS set functions f, for which there exists a family of additive clauses {w(1) , . . . ,w(m) } such that f(S) = maxℓ∈[m] w(ℓ) (S) for all S ⊆ N. In words, f evaluates each team by the most favorable additive clause.

Agent Costs and Linear Contracts (Shares). Each agent i has a known cost ci ∈ R≥0 for working on the project. Thus, for i to work as part of team S, the principal must pay i. In multi-agent contract settings, this is done by a priori allocating to i (before the project starts) an αi-fraction of the eventual reward from the project. This fraction αi is known as a linear contract [Holmstr¨om and Milgrom, 1987], and is also referred to as i's share [Aharoni et al., 2025]. We write α(S) = ∑i∈S αi for the total share allocated to team S, with the convention that α(∅) = 0.

A defining property of multi-agent contract settings is that once an agent is allocated a fraction of the future reward, this agent might be tempted to shirk, allowing other agents to do the costly work while enjoying a fraction of the reward they generate. This is known in contract design as moral hazard.

The agents' shares (αi)i∈S are designed to overcome moral hazard by making work an equilibrium, while simultaneously ensuring agents are well-compensated and protected in this dynamic setting, mirroring the robust participation incentives of our offline foundation [Babaioff et al., 2012]. When this holds, we say that contract α = (αi)i∈S incentivizes team S. There is a well-known closed formula for shares that incentivize team S, while maximizing the principal's remaining fraction of the project [Babaioff et al., 2012]:

This αi represents the minimal share ensuring incentive compatibility: an agent's gain from effort, αi(f(S)-f(S \{i})), must at least cover their cost ci. When f is additive, αi simplifies to ci/f({i}).

TheDesignProblemandCompetitiveRatio. We can now describe the full setting: Upon arrival of agent i, the principal learns the cost ci, and can evaluate the reward function f on any subset of the arrived agents Ni. Based on this information, the principal must immediately decide whether to hire agent i, without knowledge of future arrivals (but with the ability to revoke earlier choices under free dismissal). When agent i is hired, the principal commits to i's share αi of the eventual reward f(S), where αi is defined in Eq. (1). This guarantees the agent an incentive to work (despite incurring cost ci) if they make it to the final team S. The share αi is parameterized by S until step n, when S is finalized. Once an agent is dismissed, their share is set to zero.

The players' utilities are as follows: The utility of each agent i ∈ S is αif(S) - ci, the utility of any other agent is 0, and the principal's utility depends on the remaining share, and is given by g(S) := (1 - α(S))f(S).

Since the agents' shares (αi)i∈S are determined by S, the principal's design problem boils down to an online algorithm for selecting S such that the principal's utility g(S) is maximized. In online optimization, the performance of an online algorithm is typically evaluated using the competitive ratio (CR), which compares the outcome of the online algorithm to that of an optimal offline algorithm that has complete knowledge of the input sequence in advance.

Formally, an online algorithm ALG has a CR γ ∈ [0, 1] if for every input sequence I, its output satisfies ALG(I) ≥ γ · OPT(I), where OPT(I) denotes the value achieved by the optimal offline solution. When the algorithm is randomized and the adversary is oblivious (i.e., cannot adapt to the random choices), the expected competitive ratio is a random variable defined similarly, requiring that E[ALG(I)] ≥ γ·OPT(I) for all I. In our model, OPT(Ni) = maxSi⊆Ni g(Si) for every i ∈ [n].

3 Toolbox: Balance Points

In this section, we introduce the notion of balance points-a key concept that captures the trade-off between allocating additional shares to agents to incentivize work, and preserving the principal's utility-forming the basis for both the design and analysis of our algorithm in Section 4.

3.1 Agent Quality

We start by defining a quality measure for agents and teams, which captures economic efficiency, namely, the value generated by the hired agents, relative to the total share that must be allocated to them in order to incentivize their work.

Definition 3.1 (Quality). Consider an additive reward function f. For every team S ⊆ N, its quality q(S) is the ratio between the reward it yields, and the total share allocated to the teammembers:

Definition 3.1 applied to a singleton team {i} gives the quality of agent i: qi := f({i}) αi = f 2 ({i}) ci . Using Eq. (2) we can rewrite the principal's utility using the notion of quality:

Notation. We partition the set of all agents N into subsets of uniform quality, ordered from highest to lowest: N = Q1∪ · · ·∪Qp, where for every 1 ≤ x ≤ p, all agents in Qx have the same quality, which is strictly greater than that of any agent in Qy with x < y ≤ p. Each Qx is referred to as a quality group, and we denote its uniform quality by qx ; thus, qx = qi for every agent i ∈ Qx and qx = q(Qx).

Since f is additive, each agent i has a fixed value αi that can be determined upon arrival. Consequently, an agent's quality and associated quality group remain unchanged throughout the process.

Consider a hired set of agents S ⊆ N. For every 1 ≤ x ≤ p, let Sx := S ∩ ⋃1≤y≤x Qy be the subset of S consisting of agents from the first x quality groups, with S0 := ∅.

Let ¯ S denote the ordering of agents in S in decreasing order of quality. In case of ties in quality, agents with smaller shares appear earlier in the ordering. Let ¯N denote the entire set of agents, ordered in this way. For every i ∈ [n], let ¯Ni = ( ¯N)i denote the agents in ¯N appearing up to agent i, including i itself. Now we can define ¯ Si := S ∩ ¯Ni. In words, these are the agents in ¯ S that are ordered before agent i. 3

3.2 Balance Point Definition

Intuitively, a balance point is defined per quality group Qx and per team S (which determines the set Sx-1 of higherquality agents who are allocated shares). It quantifies the maximum additional share that can be allocated to agents of quality Qx before the principal's utility begins to decline. Once the balance point is exceeded by the allocated shares, adding more agents from Qx or from lower-quality groups can only decrease the principal's utility. Therefore, identifying and maintaining allocations near the balance point is key to achieving optimal utility when selecting agents in an online manner.

Definition 3.2 (Balance point). Given a hired set of agents S ⊆ N and a quality group Qx, the balance point b(S, x) ∈

3 For example, if the agents arrive in increasing order of quality, and S = N, then ¯ Sn = {n} since all other agents succeed agent n in the ordering.

(0, 1) of Qx relative to S is a share satisfying the following property. For any two subsets S′ , S′′ ⊆ Qx such that ∣∣α(Sx-1 ∪ S′ ) - b(S, x)∣∣ ≤ ∣∣α(Sx-1 ∪ S′′ ) - b(S, x)∣∣, it holds that

Figure 1 illustrates this definition geometrically. In Lemma 3.4 we show that such a balance point exists for every quality group and every set of hired agents.

To better understand the idea of balance points, consider a fixed quality group, Qx. Similarly to Eq. (3), we can use the additivity of f to write the principal's utility as

Suppose that the agents hired from other quality groups S \ Qx are fixed. As the principal allocates more shares to agents in Qx, the utility may increase at first but is guaranteed to decline eventually. Indeed, by the monotonicity of f, hiring additional agents fromQx (increasing α(S∩Qx)) increases the reward f(S∩Qx) = α(S∩Qx)qx contributed by this quality group, thereby increasing the total reward. At the same time, the principal's share of the reward 1-α(S\Qx)-α(S∩Qx) is reduced. Thus, the marginal effect of hiring agents in Qx on g(S) follows a concave trajectory as a function of α(S∩Qx), forming a downward-opening parabola with the balance point marking its peak-see Figure 1.

3.3 Characterizing Balance Points

We now give an alternative characterization of balance points using an auxiliary agent: a hypothetical agent of quality qx , whose share is set according to Eq. (1) by setting a corresponding cost. The auxiliary agent whose share maximizes utility relative to Sx-1 yields the balance point b(S, x).

Observation 3.3. Let r be an auxiliary agent with qr = qx such that g(Sx-1 ∪ {r}) ≥ g(Sx-1 ∪ {v}) for any other auxiliary agent v with qv = qx . Then, α(Sx-1 ∪ {r}) = b(S, x).

The concept of auxiliary agent gives a simple and intuitive way to derive the balance point of each quality group, as it represents the optimal share allocation to agents of a given quality. This allows us to express b(S, x) using a concise algebraic formula.

Lemma 3.4. For every hired set of agents S ⊆ N and quality group Qx,

Corollary 3.5. For every S ⊆ N, the balance point of the first quality group is b(S, 1) = 1/2.

3.4 Comparing Hired Agent Sets

We use balance points to compare sets of hired agents based on the total utility they generate for the principal. Specifically, if a set allocates shares more effectively across quality groups while staying within its balance points, its total utility is guaranteed to be higher.

Lemma 3.6. Let S, S′ ⊆ N be two sets of hired agents. Suppose that for every quality group Qx, 1 ≤ x ≤ p, the shares satisfy α(S ∩ Qx) ≤ α(S′ ∩ Qx) and α(Sx ) ≤ α((S ′ )x ) ≤ b(S′ , x), then it holds that g(S) ≤ g(S ′ ).

The statement of the above lemma naturally extends to the case where we introduce an auxiliary agent r that maximizes the contribution of a given quality group, assuming the agents in all preceding quality groups are fixed.

Lemma 3.7. Let S, S′ ⊆ N be two sets of hired agents and 1 ≤ y ≤ p. Suppose that for every quality group Qx, 1 ≤ x ≤ y, the shares satisfy α(S ∩ Qy) ≤ α(S ′ ∩ Qy) and α(Sy ) ≤ α((S ′ )y ) ≤ b(S′ , y). Then g(S) ≤ g((S ′ )y ∪ {r}), where r is the auxiliary agent that maximizes utility over the fixed (S′ )y .

4 Positive Result: Randomized Algorithm

In this section, we present our randomized algorithm for OMAC. We start with two deterministic algorithms representing complementary approaches to OMAC with an additive reward function. Our final algorithm is a randomized combination of these strategies.

Algorithm BP (Balance Point) hires agents with the highest possible utility while ensuring no group exceeds its balance points. When comparing two agents of equal quality, BP prefers the one with the smaller share. To achieve this, it runs BP-STEP (Algorithm 1) upon each agent's arrival.

AlgorithmMAX selects the best agent from all arrivals by running MAX-STEP upon each agent's arrival. It is formally described in Algorithm 2. For simplicity, we initialize with a dummy agent 0, having α0 = 0, indicating no agents have been hired yet.

We define the randomized algorithm ALG-OMAC (Algorithm 3) as follows: With equal probability (i.e., uniformly at random), run either BP or MAX throughout the entire arrival process. The following illustrates the executions of BP and MAX on a short arrival sequence.

Example 4.1. Let N = {A,B,C,D} with αA = 0.05 and f({A}) = 0.15, αB = 0.25 and f({B}) = 1.00, αC = 0.16 and f({C}) = 0.80, αD = 0.35 and f({D}) = 1.75. By

Algorithm 1 BP-STEP

Input: A previously hired group of agents S, and an arriving agent j.

• 1: S′ ←S ∪ {j}
• 2: Sort the agents in S′ in decreasing order of quality, breaking ties by non-decreasing order of shares.
• 3: Let ¯ S′ = {i1, . . . , is} be the sorted list.
• 4: Set S ← ∅
• 5: for k = 1 to s do
• 6: Let x be such that ik ∈ Qx
• 7: if α(S ∪ {ik}) < b(S, x) then
• 8: S ← S ∪ {ik}
• 9: end if
• 10: end for
• 11: return S

Algorithm 2 MAX-STEP

Input: A previously hired agent i, and an arriving agent j. 1: return argmax{g({i}), g({j})}

evaluating agent qualities, qi = f({i})/αi, we have three quality groups: Q1 (q1 = 5) contains C and D, Q2 (q2 = 4) contains B, and Q3 (q3 = 3) contains A.

We briefly trace the execution of Algorithm BP upon each arrival.

Arrival of A: The tentative team is S = {A}. As αA ≤ 0.5 = b(∅, 3), BP tentatively hires A.

Arrival of B: The sorted quality order is B,A. BP keeps B as αB ≤ 0.5. For A, the dynamic threshold drops to b({B}, 3) ≈ 0.458; since α({B,A}) = 0.30 ≤ 0.458, A is kept, and S = {B, A}.

Arrival of C: The order is C,B,A. C is kept as αC ≤ 0.5. For B, b({C}, 2) = 0.5 + 0.5(1 - 54 )0.16 = 0.48, and since α({C,B}) = 0.41 ≤ 0.48, B is kept. For A, the threshold is b({C,B}, 3) = 0.405. The total share satisfies α({C, B}) = 0.41 > 0.405; therefore, A is irrevocably dismissed, and S = {C, B}.

Arrival of D: The order within Q1 is {C,D}. C is evaluated first and kept. For D, the threshold is b({C}, 1) = 0.5. Since α({C,D}) = 0.51 > 0.5, D is rejected. B evaluates safely against C as before.

The final team selected by BP is {C, B}, obtaining the utility g({C, B}) = 1.062. Simultaneously, Algorithm MAX selects {D}, the team yielding the highest utility from a single agent. Hence, the utility of MAX is g({D}) = 1.1375.

The optimal offline team for this instance is OPT = {D,A}, yielding g({D,A}) = 1.14. Notably, this optimal subset violates the balance point conditions. By adhering strictly to these thresholds, BP guarantees a secure utility against adversarial worst-cases, while MAX captures heavy-

Algorithm 3 ALG-OMAC

Input: An instance of OMAC.

1: With probability 1/2, run BP; with probability 1/2, run MAX.

hitting individual agents.

We now formally analyze ALG-OMAC.

Theorem 4.2. Given an instance I of OMAC, it holds that OPT(I) ≤ g(BP(I)) + g(MAX(I)).

Corollary 4.3. The expected CR of ALG-OMAC is ≥ 1/2.

Proof. By the definition of ALG-OMAC, its expected utility is given by 1 2 (g(BP(I)) + g(MAX(I))). Therefore, by Theorem 4.2, the competitive ratio of the algorithm is ≥ 1/2.

We proceed to formally analyze the algorithm. Let S1 and S2 denote the groups of agents hired by BP and MAX, respectively, given the arrival sequence N. Let ¯ S∗ = {1∗ , . . . , k∗ } denote an optimal solution of size k = |S∗ |, where agents are sorted in decreasing order of quality, with agents of the same quality ordered in non-decreasing order of shares.

Let t ∈ Qz be the first agent that satisfies at least one of these two properties:

• α( ¯Nt) ≥ b(N, z) and αt ≤ 1/2;
• t = k∗ .

In other words, t is defined as the first agent in the ordering Nt who, when hired together with all preceding agents, crosses their corresponding balance point and whose share size is at most 1/2-or, alternatively, as the last agent in ¯ S∗ , whichever occurs earlier. Denote by t′ the agent that immediately precedes t in the ordering.

We note that containment (between two subsets S, S′ ⊆ N) is a special case of Lemma 3.6. Hence, using Lemma 4.4 and the fact that ¯ S∗ t′ ⊆ ¯Nt′ , we have

Proof of Theorem 4.2: We distinguish between two cases. Assume first that t is the last agent in S∗ . By definition, S∗ = ¯ S∗ t′ ∪ {t}, and by the sub-additivity of g, we have

By inequality (5), g( ¯ S∗ t′) ≤ g(S1 ), and from the maximality of the single agent selected by algorithm MAX, we have g({t}) ≤ g(S 2 ). Therefore,

If t is not last in S∗ then it must hold that αt ≤ 1/2. We know that S∗z-1 ⊆ N z-1 , which allows us to apply Lemma 3.7. Consequently, g(S∗ ) ≤ g(N z-1 ∪ {r}), where r denotes the auxiliary agent corresponding to N z . By subadditivity of g, we have that g(S∗ ) ≤ g(N z-1 )+g({r}). Furthermore, using Lemma 3.6, we have N z-1 ⊆ ¯Nt′ , implying that g(N z-1 ) ≤ g( ¯Nt′ ). Thus, g(S∗ ) ≤ g( ¯Nt′ ) + g({r}).

Now, observe that in this case, agent t crosses its balance point over ¯Nt′ , i.e., α( ¯Nt) ≥ b(N, z). As a result, we have by Corollary 3.5

and hence αt ≥ αr.

Since αr ≤ αt ≤ 1/2, g({r}) ≤ g({t}). Moreover, as t ∈ N is not an auxiliary agent (unlike r), MAX ensures that g({t}) ≤ g(S 2 ). Therefore, g({r}) ≤ g(S 2 ).

Finally, from inequality (5), we also have g( ¯Nt′ ) ≤ g(S1 ). Combining these bounds, we conclude that

5 Negative Results

5.1 Additive Rewards

We identify two fundamental limitations in the additive case, both arising from the same adversarial scenario: the arrival of an agent demanding a large share. Such an agent can either cause the principal to lose all project value, or block the recruitment of more effective agents. Consequently, deterministic strategies might perform arbitrarily poorly.

Theorem 5.1. The CR of any deterministic algorithm for OMAC can be arbitrarily small.

Furthermore, even randomized algorithms cannot fully avoid the trade-off induced by such an agent: no randomized algorithm can achieve a competitive ratio better than 1/2 (our randomized algorithm in Section 4 matches this bound).

Theorem 5.2. No (randomized) algorithm for OMAC can achieve a CR > 1/2.

Proof sketch. Let ε ∈ (0, 1) be a small value, n = ε2 /2 + 1 and N = {1, . . . , n} such that α1 = 1 - ε2 , q1 = ε and αi = ε2 , qi = ε2 for every 2 ≤ i ≤ n.

Given a (possibly randomized) algorithm, let X be an indicator random variable for hiring agent 1 upon arrival. For any small agent i ∈ N \ 1, let Ti ⊆ Ni \ 1 be the random set of small agents hired by the algorithm among the first i arrivals, conditioned on hiring agent 1, with ti = |Ti|.

Then every randomized algorithm belongs to one of the following types:

1. ALG1 is the class of algorithms for which the corresponding indicator variable X satisfies Pr(X) ≤ 1/2.
2. For all i ∈ N \ {1}, let ALGi be the class of algorithms for which Pr(X) > 1/2. In addition, i is the first index such that E[ti] > 1, meaning that for every 1 ≤ j < i, we have E[tj ] ≤ 1.
3. ALGn+1 denotes the class of algorithms for which Pr(X) > 1/2, and E[ti] ≤ 1 for all 1 ≤ i ≤ n.

Consider one of the classes ALGi for 1 ≤ i ≤ n+1. We claim that by setting k = min{i, n}, the utility of every algorithm in this class on the input prefix Nk can be made arbitrarily small compared to the optimal solution. In [Lavi et al., 2026], we prove this claim separately for each class.

5.2 XOS Rewards

We study OMAC with an XOS reward function f and show that, even under free dismissal, no (possibly randomized) algorithm can achieve a constant competitive ratio. This impossibility stems from the adversary's ability to nullify an agent's marginal contribution as new agents arrive. As in real economic settings, the principal lacks foresight into future interactions, making reliable long-term decisions impossible.

Theorem 5.3. For OMAC with an XOS reward function f, the CR of any algorithm can be arbitrarily small.

Proof sketch. We apply Yao's min-max principle using a distribution D over m sequential groups of n indistinguishable agents. Each group contains exactly one "good" agent and n - 1 "bad" agents, where the class of each agent cannot be revealed for the principal upon arrival. Within any group, agent i provides zero marginal contribution in their team S, leading to αi = ∞ and g(S) = -∞ if multiple agents are hired. Thus, productive collaboration occurs exclusively between good agents from different groups.

Ex ante, ALG hires the good agent with probability only 1/n. Failure to identify a good agent precludes synergy with future arrivals, forcing a dilemma between retaining a likely bad hire or swapping for another uncertain candidate. While the optimal offline solution pairs all m good agents, the algorithm's expected utility remains suppressed by the low success rate per group. As both n and m increase, the expected competitive ratio goes to zero.

In [Lavi et al., 2026], we give an example and clarify the construction of the distribution D along with the behavior of algorithms in this setting.

5.3 Without Preemption

To complete the picture, we show that dismiss-free OMAC admits no algorithm with a competitive ratio (CR) bounded away from zero. This impossibility holds even under the assumption of uniform agent quality (see Definition 3.1). The impossibility follows by taking n →∞ in the next theorem:

Theorem 5.4. Consider OMAC with uniform agent quality q and at most n arriving agents. The CR γ of any algorithm ALG satisfies γ = O(1/n).

We give a formal proof in [Lavi et al., 2026].

6 FutureWork

We initiate the study of online team formation with rational team members who must be incentivized by contracts. We completely resolve the case of additive rewards by developing the technique of balance points. We highlight a gap in the literature - online algorithms for budgeted submodular maximization. A first step towards bridging this gap can be online maximization of weighted matroid rank functions subject to a budget constraint. Our work focuses on establishing the adversarial baseline; a natural direction for future work is to explore stochastic refinements - from secretary models to prophet inequalities - to achieve stronger performance guarantees under random arrival patterns.

Acknowledgments

We gratefully acknowledge feedback from anonymous reviewers that led to this improved version of our work. This work was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 101077862, project ALGOCONTRACT), by the Israel Science Foundation (grant No. 3331/24), by the NSF-BSF (grant No. 2021680), and by a Google Research Scholar Award.