Incentives for Early Arrival in Cooperative Games (Extended Abstract)

1 Introduction

Consider a frequent scenario, where a group of people form a partnership for a startup [Spender et al., 2017]. They have different abilities or funds to contribute and can cooperate to create values. Sharing the value created is a classic problem studied in the literature on cooperative games [Driessen, 2013; Bilbao, 2012; Shapley, 1953; Von Neumann and Morgenstern, 2007]. Traditional cooperative games distribute the value after the whole coalition is formed. However, in reality, people typically do not all arrive at one point of time; rather, they join sequentially. This creates two issues: first, it is often not realistic to wait until everyone arrives before distributing the value - sometimes, it is not even clear if "everyone" has joined. This requires that values be distributed in an online manner. Second, the time to join can be strategic for a player; for example, a fund may choose the best time to invest in a startup.

∗The full version was first published at AAMAS 2024 [Ge et al., 2024], while Yao Zhang was a Ph.D. student at ShanghaiTech University.

In this work, we propose a theory for online cooperative games that explicitly addresses these issues. Firstly, we require that, after each player joins, an irrevocable distribution of the value created so far should be immediately determined. We formalize a property called online individually rational to guarantee that players' shares be non-negative and nondecreasing as new players join, so that all are willing to participate till the end. Secondly, to gather resources quickly, and to prevent players from waiting indefinitely for each other to join first, we require a share-dividing mechanism to incentivize players to join the game as early as possible. Namely, we require the mechanism to distribute a higher reward to a player when she joins earlier (when the order of the others' arrivals remains fixed). We believe this is a critical property of an online value-sharing mechanism, which has not been discussed in the literature so far.

Incentivizing early arrival is the key property we proposed here, which also has promising applications. For example, considering a group of students working on a hard project which requires different combinations of skills to finish it, the supervisor may want to incentivize the students to join the project as early as possible so that the project can be finished earlier. Again for a startup to quickly get enough funds, they should design a proper reward sharing mechanism to incentivize investors to invest the startup as early as possible.

One may notice that there exist trivial online methods to incentivize early arrivals of players. For example, one may simply always give all the value to the first player in the game. However, such a solution is not fair (e.g., the first player may make no contribution to the value at all). Hence, we use the Shapley value [Shapley, 1953], a well-known and widely accepted classic solution to traditional cooperative game, as a benchmark for fairness [Clippel and Rozen, 2019]. More precisely, we require every player's expected reward over all possible joining orders to be exactly her Shapley value in the game, which is referred to as Shapley-fair in our setting.

Taking everything together, our contributions are summarized as follows.

• We formalize the requirements mentioned above. We check two trivial ideas, including allocating the Shapley Value to the players and allocating the marginal contribution to the players, and show the limitations of them.
• For 0-1 monotone games, we propose a mechanism called Reward First Critical Player (RFC), and show it to be complete. Namely, we analytically characterize the set of games where RFC satisfies all the requirements, and show that any other game does not admit a mechanismwith all the properties.
• We extend the method for 0-1 monotone cooperative games to deal with general games. The key idea is to decompose such a game into 0-1 monotone games in an online fashion. Properties of RFC are then extended to general games.

The remainder of the paper is organized as follows. Section 2 gives the concrete model of the problem we study. We then characterize the solution in 0-1 monotone games and a corollary of impossibility results in Section 3. Furthermore, we extend the solution to general games in Section 4. Finally, we discuss future investigations.

2 The Model

An online cooperative game is given by a triple (N, v, π), where N is a set of players, v : 2N → R+ is a set function, and π ∈ Π(N) is a permutation of N (Π(N) denotes the set of all permutations of N). Players arrive sequentially, in the order given by π. A coalition is a set S ⊆ N of players, who create a value v(S). v(·) is normalized if v(∅) = 0, and is monotone if ∀T ⊆ S ⊆ N, v(S) ≥ v(T). Throughout this work, we consider normalized and monotone games.

If a player i arrives earlier than j according to π, we say i ≺π j. Let pπ (i) denote the set of players that arrive (weakly) before i, including i: pπ (i) := {j | j ≺π i} ∪ {i}. For a subset S ⊆ N, v restricted to S, written as v|S, is a set function v|S : 2S → R+ defined as v|S(T ) = v(T ), ∀T ⊆ S; π restricted to S, written as π|S, is the permutation of S defined as i ≺π|S j iff i ≺π j, for all i, j ∈ S.

We look to divide the values in an online fashion as players join; that is, at any point of time, when the set of players that have arrived is S, we should allocate irrevocably to players in S all the value created by S, without the knowledge of v or π beyond the scope of S. We formalize this below.

Definition 1 (Prefix). A coalition S ⊆ N is a prefix of π if S is the set of first |S| players to arrive according to π. This is denoted as S ⊑ π.

Definition 2 (Local Games). For a game (N, v, π) and a prefix S ⊑ π, the local game on S is the game (S, v|S, π|S).

Definition 3. A value-sharing policy ϕ maps a game (N, v, π) to an n-tuple of allocations, so that ϕi(N, v, π) ≥ 0 is player i's share of the value, and ∑i ϕi(N, v, π) = v(N).

An online value-sharing mechanism is given by a valuesharing policy ϕ, so that after the arrival of each prefix S ⊑ π, each player i ∈ S gets a (cumulated) share of ϕi(S, v|S , π|S ).

When the context is clear, we often omit the first argument of a policy ϕ, and simply write ϕi(v, π).

To keep the players from quitting early, we require each player's share to weakly increase as more players arrive:

Definition 4. An online mechanism is online individually rational (OIR) for value function v if for any arrival order π and any T, S ⊑ π with T ⊆ S, we have ϕi(T, v|T , π|T ) ≤ ϕi(S, v|S, π|S) for every player i ∈ T .

To prevent players from strategically delaying their arrivals, we require each player's share of value to be no larger if she chooses to join later than her actual arrival, assuming the other players' order of arrivals is fixed. Formally,

Definition 5. An online mechanism is incentivizing for early arrival (I4EA) if for any player i, ϕi(N, v, π) ≥ ϕi(N, v, π′ ) for all π and π′ such that π|N\{i} = π′ |N\{i} and pπ (i) ⊊ pπ′ (i).

There are trivial mechanisms satisfying OIR and I4EA; consider, e.g., allocating, at any stage, all the current value to the first player. Such a mechanism, however, is easily seen to be unfair. One of the most celebrated notions for fairness in (offline) cooperative games is Shapley value (SV). Intuitively, the Shapley value for a player in an offline games is defined by a mental experiment involving an online game, where players arrive in an order that is uniformly at random; each player's expected marginal contribution in this mental experiment is then her Shapley value. Now for the truly online games that we study, it is natural to require that, in a mechanism considered fair, a player's expected share should equal her Shapley value if the arrival order is uniformly at random. We now formalize this discussion.

Definition 6 (Marginal Contribution). Given a value function v, a player i's marginal contribution (MC) to a coalition S ∋ i is

Definition 7 (Shapley Value, [Shapley, 1953]). Given a value function v, player i's Shapley Value (SV) is

equivalently,

In a monotone game, the MC of any player in any coalition is non-negative; therefore, the SV is also non-negative.

Definition 8 (Shapley-Fair). An online mechanism is Shapley-fair (SF) for a value function v if for each player i ∈ N,

In this work, we aim to design online mechanisms that are OIR, I4EA and SF in games as broad as possible. As a warmup, we discuss two simple mechanisms.

The first one computes the Shapley values for the local game on each prefix S ⊑ π, and allocates these to the players in S. This mechanism is I4EA, because each player's eventual share is her Shapley value, regardless of the arrival order. However, this mechanism is not OIR, as the Shapley value may decrease when new player joins.

The second simple mechanism awards each player, at her arrival, her MC to the existing coalition, and gives out no more share to this player in the future. This mechanism is obviously OIR and SF, but it is I4EA only when the game is submodular. We call this mechanism the Distributing Marginal Contribution (DMC) and propose the following theorem.

Theorem 1. DMC is I4EA if and only if the value function v is submodular. 1

3 0-1 valuedMonotone Games

In this section, we focus on valuation functions that take value only 0 or 1. Even for such simple functions, it is not a priori clear whether every function admits a mechanism that is OIR, I4EA and SF. A corollary of this section answers this question in the negative. The main technical contribution in this section is a mechanism, Rewarding The First Critical Player (RFC, Definition 10), which we show to be complete for 0-1 valuation functions, in the sense that for any 0-1 valued v that admits an OIR, I4EA and SF mechanism, RFC also satisfies these properties (Theorem 3). We also analytically characterize all such valuation functions (Theorem 4). In Section 4, we discuss extensions to general valuation functions.

3.1 The RFCMechanism

When v takes values only 0 or 1 and is monotone, for any arrival order π, there is at most one player whose arrival makes the current coalition's value jump from 0 to 1. We call this player the marginal player of (N, v, π). Note that the DMC mechanism allocates all the value to the marginal player. The RFCmechanism, in contrast, considers players that are indispensable in creating the positive value, and allocates the value to the first such player. Such indispensable players are called critical. Formally,

Definition 9. Given a 0-1 valued v, for any S with v(S) = 1, define S∗ := {j ∈ S | MC(j, v, S) = 1}. For a 0-1 valued v and arrival order π, let i be the marginal player; the set of critical players is

Recall that pπ (i) is the coalition formed after i's arrival. In plain language, a player is critical if she is in pπ (i) and if her removal makes the coalition's value drop to 0. By definition, the marginal player must be critical, but the set of critical players may include others. In the DMC mechanism, a critical player arriving earlier than the marginal player does not get allocated anything but may choose to delay her arrival to become the marginal player herself; this destroys incentive for early arrival. The RFC mechanism redresses this by awarding to the earliest among the critical players. Crucially, the set of critical players is fully determined by v|pπ (i) and π|pπ (i) .

1 A value function v is submodular if for every S, T ⊆ N with T ⊆ S and every i ∈ N \ S, we have v(T ∪ {i}) - v(T) ≥ v(S ∪ {i}) - v(S). v is supermodular if this inequality goes the other way for all such S, T and i.

Definition 10 (RFC). The Rewarding The First Critical Player (RFC) mechanism is defined by the following valuesharing policy: for any prefix S ⊑ π with v(S) = 1, and player i ∈ S,

For prefix S with v(S) = 0, no player gets allocated anything.

Theorem 2. For all 0-1 valued, monotone v, RFC is OIR and SF.

Example 1. Consider N = {A,B,C} and v = [v(A), v(B), v(C), v(AB), v(AC), v(BC), v(ABC)] = [0, 0, 0, 0, 1, 1, 1], the marginal player and the critical players are listed in the 2nd column and 3rd column of Table ??. In the 4th column, we list the receivers of the values determined by RFC. In this game, RFC is not I4EA as we have v(C) = 0 and {A,B,C}∗ = {C}. More specifically, in order [A,C,B], C is the marginal player but not the unique critical player when she joins, so the value would be allocated to A. However, in order [A,B,C], C is both the marginal player and the unique critical player when she joins, so she would get the value.

3.2 Completeness of RFC

The RFC mechanism was motivated to redress an incentive issue in the DMC mechanism. Perhaps surprisingly, we show that RFC not only outperforms DMC in the sense that it is I4EA for broader 0-1 valued games, but it is the best among all mechanisms for such valuation functions: whenever a 0-1 valued v admits an OIR, SF and I4EA mechanism, RFC is such a mechanism as well (Theorem 3). We then precisely characterize all such valuation functions(Theorem 4). Figure 1 illustrates the corresponding categorization of 0-1 valuation functions.

Theorem 3. For any 0-1 valued monotone v, if there exists a mechanism satisfying OIR, SF and I4EA, then RFC is such a mechanism.

Theorem 4. For any 0-1 valued monotone v, RFC is not I4EA if and only if there exists i such that v({i}) = 0 and ∃S, S∗ = {i}. (Recall the definition of S∗ from Definition 9.)

Corollary 1. RFC is OIR, SF and I4EA on submodular and supermodular 0-1 valued monotone games.

4 Extension to General Valuation Functions

In this section, we propose an extension of RFC for general valuation functions. We give a procedure (Algorithm 1) that decomposes any monotone valuation function into a weighted sum of 0-1 monotone valuation functions. Importantly, this decomposition is done in an online fashion as players arrive. An RFC is then run, simultaneously, on each 0-1 valued component, and each player's share is the weighted sum of her shares from the decomposed 0-1 games.

4.1 GM-Decomposition

We firstly introduce the decomposing process in the mechanism, which is called the greedy monotone decomposition (GM) and formalized in Algorithm 1. GM gives a nonnegative linear combination of a monotone game as v = ∑k ckgk where {gk} are the 0-1 game components and {ck} are the coefficients. We denote D(v) = {(gk, ck)} as the set of component-coefficient pairs which determines a decomposition. In each iteration, we greedily split a scaled 0-1 valued monotone set function from the current set function until it becomes zero. An example for this decomposition is

It is proved that GM has the following properties, which is the reason why we choose it for extending the RFC: (1) the GM provides a positive linear combination of a set function; (2) the component functions are monotone; (3) a game is decomposed consistently in both global and local games.

4.2 The Extended RFC

Now we propose the extended RFC mechanism based on GM. The mechanism firstly does GM-decomposition on input set function v. Then it calculates the value in each 0-1 valued

Algorithm 1 Greedy Monotone Decomposition (GM) Input: monotone v. Output: a decomposition D(v). 1: Let D be an empty list. 2: Let v1 be a copy of v. 3: while max(vk) > 0 do 4: S ← argminT⊆N,v(T)>0vk(T) 5: ck ← vk(S) 6: Let gk be a set function. 7: for T ⊆ N do 8: if vk(T) > 0 then 9: gk(T ) ← 1 10: else if vk(T) = 0 then 11: gk(T ) ← 0 12: end if 13: end for 14: vk+1 ← vk - ckgk 15: Put (gk, ck) into D. 16: k ← k +1 17: end while 18: return D.

monotone games by RFC and accumulates them with coefficients to be the value in v. The properties of RFC are maintained through this process.

Definition 11. The extended rewarding first critical player mechanism (eRFC) is defined by

where ϕRFC i is the value-sharing policy of RFC and D(·) is the GM-decomposition.

Theorem 5. eRFC is SF and OIR. Moreover, it is I4EA for monotone v if for every gk in D(v), RFC is I4EA on gk.

5 FutureWork

Several promising research directions emerge from this study. For 0-1 valued monotone games, a fundamental challenge lies in systematically characterizing the complete set of mechanisms that satisfy all properties on all solvable games. The more general valued monotone games presents two open problems: first, establishing necessary and sufficient conditions for game solvability remains unresolved; second, the decomposition framework proposed cannot always be used to solve the general valued games. [Zhao, 2025] further demonstrated the I4EA property is worth investigating in many other settings such as cost-sharing [Zhang et al., 2025], marketing, data collection and venture capital finance.

Acknowledgements

This work was partially supported by Science and Technology Commission of Shanghai Municipality (No. 23010503000), and Shanghai Frontiers Science Center of Human-centered Artificial Intelligence (ShangHAI).