Non-Myopic Negotiators See What's Best

1 Introduction

Consider the following classic problem: a group of agents wishes to divide some jointly earned revenue among themselves in some reasonable manner. The economic literature offers several revenue division methods satisfying some notion of fairness: for example, if the value of agent subsets is given, one can use concepts from coalitional games. If we only know agent utilities, we may use bargaining solutions. However, it is not clear that agents will immediately agree to employing a fair solution concept: if there is no external mediator enforcing the solution, it is reasonable to assume that selfish agents will simply push to obtain as large a share as possible, foregoing any fairness considerations.

The problem here is that greedy agents see their interaction with others as a "one shot" affair; demanding more now does not affect their future welfare (this idea is capture by the famous "tragedy of the commons" problem). However, the greediness assumption seems unreasonable. In many settings, such as budget division in companies or governments, the way revenue is shared at the current round affects welfare in future rounds. For example, the head of a government office desires a high share of the national budget, but, even if one assumes that she only cares about her ministry's success, the success of one ministry depends on the success of others: the ministry of education requires roads, electricity, and health services, all provided by other departments. This means that in iterative settings, non-myopic agents - i.e., selfish agents who care about their long-term welfare, rather than only immediate rewards -must balance their individual welfare against the needs of society as a whole.

This type of tension between individual desires and global utility is common in settings where budgets need to be iteratively shared. One can think of departments in a company that need to share a budget or manpower, agents that need to share the costs of a public project among themselves, or researchers competing for funding with their peers.

Agents are faced with two conflicting agendas. On the one hand, each agent wants to maximize its own revenue; on the other hand, taking up a large share may hurt future profits and result in lower future revenue: even the most incompetent minister would see that investing 100% of the country's budget in a single ministry is detrimental to future growth.

To model this setting, we introduce strategic negotiation games: agents work together for several rounds, generating revenue according to some production function, and use the revenue that they jointly generate in order to maintain their operations (e.g. pay salaries or buy equipment). At each round, each agent proposes a way of dividing the revenue generated at that round, and an aggregate of the proposals is used to divide the revenue.

1.1 Our Contributions

The main message of this work is that non-myopic agents can arrive at socially optimal, equilibrium outcomes without the need for external intervention. In other words, agents may disagree on how revenue should be divided; but, granted that they see the long-termmerit of others' contributions, they will strive to keep others productive. To conclude, non-myopic negotiators can actually agree on an outcome, and that outcome will be socially optimal.

We formally prove this in a class of games called strategic negotiation games. In these settings, agent strategies are revenue sharing proposals, and their utility functions are their total share of the profits for T rounds. However, our results actually hold for other models of negotiation and collaboration (see Section 3.1).

We show that when the production function v is homogeneous of degree k ≥ 1, agents start displaying more collaborative behavior as T grows; that is, the socially optimal revenue division is an eventual equilibrium. However, when v is homogeneous of degree k < 1, this guarantee does not hold: agent strategies do not result in an outcome that is necessarily socially or individually optimal.

Section 6 discusses the implications of our results to functions that model real-world economic interactions, such as CES, Cobb-Douglas and Leontief production functions, as well as to network flow games.

1.2 RelatedWork

Equilibria in strategic negotiation games are somewhat similar to farsighted equilibria discussed by Kilgour [1984] and Li [1992]. There, agents engage in a repeated game, and make strategic outcomes based on how they anticipate others will behave in future rounds. Our work differs in a crucial manner: since agent actions affect future revenue, agents are not playing the same game repeatedly, but rather a different game in each round.

Bargaining and negotiation outcomes are well understood (see the overview in [Chevaleyre et al., 2006] or [Weiss, 2013, Chapter 4], as well as the works by Clippel et al. [2008], Kalai and Smorodinsky [1975],and Nash [1950]). Some works (e.g. [Endriss et al., 2006]) consider the effects of negotiation on social welfare, as well as iterated team formation [Dutta et al., 2005; Konishi and Ray, 2003; Shehory and Kraus, 1996]. Cooperative solution concepts such as the Shapley value or the core [Peleg and Sudh¨olter, 2007] propose reasonable payoff divisions that consider the value of subsets of agents. Models of dynamics and bargaining in cooperative games do exist (see the seminal work by Aumann and Maschler [1964], Davis and Maschler [1963], and Harsanyi [1963], or [Lehrer and Scarsini, 2012; Elkind et al., 2013] for a literature review), but these models (as do models of bargaining and negotiation) do not consider the effects of revenue distribution on future welfare.

Our work is also similar to the problem of portfolio selection [Cover, 1991]. One can think of our setting as one where the individual stocks have incentives and would like more money invested in them.

2 Preliminaries

Throughout the paper, boldface letters refer to vectors; the set N is the set of all positive integers (excluding 0), and the set R+ is the set of all non-negative real numbers (including 0). A group of agents N = {1, . . . , n} has an initial resource vector w(0) = (w1(0), . . . , wn(0)) ∈ Rn+, there is some production function v : Rn+ → R+, which, for every x ∈ Rn+ , determines the production level v(x) ∈ R+. We assume that both w(0) and v are known to all agents.

Time is divided into discrete epochs indexed by t. At time t = 1, the total payoff (production value) is v(w(0)), which we denote as V1; agents select an allocation vector x1 from the n - 1 dimensional simplex (x1 ∈ ∆n, where ∆n = {x ∈ Rn+ | ∑ni=1 xi = 1}), and each agent i ∈ N receives an individual share of wi(1) = xi,1V1.

At time 2, the aggregate production is V2 = v(w(1)), agents select x2 ∈ ∆n, and the process repeats.

A contract χ is a sequence (xt)∞t=1 of vectors in ∆n. At every time step t, agent i receives a share of wi(t) = xi,tVt, where Vt = v(w(t - 1)). The revenue that a contract χ generates at time t is denoted Vt(χ), and is computed recursively as described above. Observe that the value Vt(χ) depends only on the first t - 1 payoff divisions; we sometimes write Vt(x1, . . . , xt-1) when this property needs to be emphasized.

We say that a contract is stationary if for all t we have xt = x for some fixed x ∈ ∆n. A stationary contract is then identified with x, rather than the constant sequence (x)∞t=1 .

Given a contract χ = (xt)∞t=1 , the total welfare at time T is simply ∑Tt=1 Vt(χ), and is denoted swT (χ). We say that a contract χ∗ is pointwise optimal at time T if χ∗ maximizes swT (χ) over the space of all possible contracts. We say that χ∗ is universally optimal if χ∗ is optimal at time T for all T.

We assume that agents are not interested in the global social welfare provided by a contract, but rather in their own revenue. Given an agent i ∈ N, the benefit that agent i receives from the contract χ = (xt)∞t=1 at time t is given by xi,tVt(χ); we also write Ui,T (χ) = ∑Tt=1 xi,tVt(χ), to be agent i's utility (or individual revenue) at time T . We mention that other utility functions can be considered, with similar results (see Section 3.1) We say that χ∗ is individually optimal for agent i at time T if χ∗ maximizes Ui,T over the space of all possible contracts. Observe that if v is continuous, then for all T there exists some contract χ∗ that is individually optimal for i at time T.

3 Strategic Negotiation Games

Strategic negotiation games naturally model budget division and negotiation in iterated settings. Each agent starts with an initial endowment of wi(0). Just as in Section 2, at time t, Vt = v(w(t - 1)) is the amount to be divided among the agents. The only difference is in the way that w(t) is computed. First, each agent i ∈ N proposes a sequence of T revenue divisions y1(i), . . . , yT (i) ∈ ∆n. Agents aggregate their proposals by taking an average: xt = ∑ni=1 1n yt(i). 1 At round 1, agents divide V1 = v(w(0)); if they arrive at the aggregate contract x1 ∈ ∆n, the resources for the next round are w(1) = (x1,1V1, . . . , xn,1V1), and V2 = v(w(1)); similarly, the game is repeated on round t + 1 with wi(t) = xi,t(Vt), and Vt+1 = v(w(t)). Agent i's utility is given by Ui,T = ∑Tt=1 wi(t). The value T is referred to as the horizon of the game; agents are said to see T steps ahead.

In this setting, agents can only gain by proposing that they receive 100% of the revenue at time T (in particular, if T = 1 demanding 100% of the revenue is a dominant strategy); however, in Section 5, we show that for a large enough value of T, the contracts that agents propose at earlier rounds are close to optimal (i.e., nearly maximize social welfare).

1 One can assume more complex aggregation functions rather than a simple average. Our results hold whenever the aggregation function f is continuous, and satisfies a notion of unanimity (i.e., if all agents propose x, the aggregate outputs x).

In the static variant of this game, agents propose a single contract y(i) to be used in all T rounds. We refer to this case as a strategic negotiation game with static contracts.

Before we proceed with our formal results, let us demonstrate what happens when agents' behavior is greedy.

Example 3.1. Suppose that we have two agents, and a production function v(x, y) = αx2 y3 , where α = ( 53 )3 · ( 52 )2 . 2 We assume that agents' starting resources are w1(0) = 25 , w2(0) = 35 . If agents' utilities are just their revenue at time t, then their proposals will be (1, 0) and (0, 1), respectively, arriving at the contract ( 12 , 12 ). If agents choose to divide revenue equally, the resulting payoffs decay rapidly (at t = 3, agent 1's revenue is 12 · α31 2155 ); however, the socially optimal contract ( 25 , 35 ) offers them a constant revenue at each round. Thus, adopting the optimal contract results in strictly higher revenue in the long run.

Example 3.1 demonstrates the issue with the greedy behavior: if agents are non-myopic, their proposals result in higher revenue both for them and for the group as a whole. In Section 5, we formally explain this intuition.

Before we proceed, let us recall that an ε-Nash equilibrium of a game is a strategy profile where no agent can gain more than ε by changing its action. Thus, in the strategic negotiation setting, agent i is not interested in changing his proposed share if doing so will not increase his utility by more than ε. We mention that similar results hold for other solution concepts (see Section 3.1). Since we want to capture the effects of the horizon T on the equilibria, it will be useful to think of some vectors as eventual consensus points.

Definition 3.2 (Eventual Consensus Point). Given N, w(0) ∈ Rn+ and v : R+ → R, a point x∗ ∈ ∆n is an eventual consensus point of 〈N,w(0), v〉 at time t if for every ε > 0 there is some T0 such that for all T > T0, if all agents see T steps ahead, there is an ε-Nash equilibrium of the resulting negotiation game where all agents propose x∗ at time t.

In other words, x∗ is a consensus point if sufficiently farsighted agents will jointly agree to propose it at time t. When we are limited to static contracts, agents must essentially agree on a single revenue division to be used in the next T rounds. The following definition captures an eventual agreement on the contract to propose.

Definition 3.3 (Eventual Static Equilibrium). A point x∗ ∈ ∆n is an eventual static equilibrium of 〈N,w(0), v〉 if for every ε > 0 there is some T0 such that for all T > T0, if all agents see T steps ahead, then all agents proposing x∗ is a symmetric ε-Nash equilibrium of the resulting strategic negotiation game under static contracts.

3.1 Model Variants

Our results still hold if Ui,T is only the payoff at time T, rather than the total payoff up to time T .

Strategic negotiation is only one example of a strategic interaction where non-myopic behavior leads to desirable outcomes. Similar results hold in other strategic settings, and with other solution concepts. For example, one can employ the ε-Strong Nash equilibrium.

2 We have chosen v to be a Cobb-Douglas production function; this is not a coincidence, as we will show in Section 5

Our model does not use discounted returns: future revenue is seen as equally important as current revenue; however, we can easily incorporate discount factors, with similar results. In general, agent welfare is far more affected by the structure of the production function than by discounted returns.

To conclude, non-myopic behavior is a widely applicable paradigm, that leads agents to behave in a desirable manner, without the need for external intervention.

4 Optimal Contracts: First Observations

Finding a socially optimal contract at time T amounts to solving the following problem:

We say that f : Rn → R is monotone increasing if for every w,w′ ∈ Rn such that w′ ≤ w (i.e. w′i ≤ wi for all i), f(w′ ) ≤ f(w). We first show that if v is monotone increasing, one can find an optimal solution to Equation (1) using a greedy procedure. Given a non-negative constant C, let us write ∆n(C) = {w ∈ Rn+ | ∑ni=1 wi = C}; in particular, ∆n equals ∆n(1).

Proposition 4.1. Let opt(V ) be the value of Equation (1) when V1 = V ; if v is monotone increasing, then opt(V ) is monotone increasing in V .

As an immediate corollary of Proposition 4.1 (proof omitted), we have that in order to find an optimal contract at time T , one must find a point w1 ∈ argmaxw∈∆n(V1)v(w); then, a point w2 ∈ argmaxw∈∆n(V2)v(w) and so on. In other words, greedily maximizing the revenue at every time step will result in a universally optimal contract. From a computational point of view, finding universally optimal contracts is relatively straightforward when v is monotone, assuming that maximizing v over ∆n(V ) can be done in polynomial time for any V .

When v is homogeneous, finding an optimal contract is even easier. A function f : Rn+ → R+ is homogeneous of degree k, or k-homogeneous, if for all α ≥ 0 and all w ∈ Rn+, v(αw) = αk v(w). We now make an important observation (proof omitted): if v is homogeneous of degree k, then there exists a stationary socially optimal contract.

Proposition 4.2. If v is monotone and homogeneous of degree k, then the set of universally optimal stationary contracts is the set of global maxima of v over ∆n.

Another useful property of homogeneity is as follows: if v is homogeneous, we get a closed formula for utility under a contract χ = (xt)∞t=1 .

and an even simpler formula for stationary contracts:

Applying Equation (2), the individual utility of agent i at time T is thus ∑Tt=1 xi,tV kt-1 1 ∏t-1 h=1 v(xh)kt-1-h , and for a stationary contract, it is xi (∑Tt=1 V kt-1 1 v(x)∑t-2 h=0 kh ) .

5 Optimal Contracts are Eventual Equilibria and Consensus Points

Using the closed formulas for individual agent utility, we now present the main result of this paper: when agents are sufficiently far-sighted, socially optimal contracts are eventual equilibria of strategic negotiation games.

In order to have a robust model of cooperation and individual incentives, we wish to capture some notion of complementarity among agents. If agents are actually better off without allocating resources to some agents, then there is little reason to collaborate with them. This notion is captured via the idea of mutual dependency.

Definition 5.1. A function v : Rn → R satisfies mutual dependency if for all x ∈ ∆n, if xi = 0 for some i ∈ N, then v(x) = 0.

Mutual dependency is an important aspect of negotiating optimal contracts; if mutual dependency does not hold, then there are some agents who need not contribute to the group effort, and are somewhat expendable. In other words, suppose that x∗ is an optimal stationary contract for v and that x∗i = 0; then the set N \ {i} can argue that agent i should receive no share of the profits, as there exist optimal contracts that do not require any of his resources (in terms of a company, i would be a department that is completely redundant).

Remark 5.2. Mutual dependency is a sufficient - not necessary - condition for our results to hold. Many weaker forms of complementarities will suffice: we really require that all maxima (for agents as a whole and as individuals) occur in the interior of ∆n. In fact, in Section 6, we show that our results apply to CES production functions, for which the mutual dependency does not hold.

Model assumptions to guarantee interior solutions have been used in other settings (e.g. [Kelly et al., 1998; Kelly and Voice, 2005]); weaker versions of our results do hold in the case where maxima occur on the boundary of ∆n. Briefly, if there are global maxima on the boundary of ∆n, then in the limit, agents who receive a positive share of the profits will want to have these maxima as the negotiation outcome. That said, it is unclear what strategies can achieve this outcome.

In what follows we assume that the function v satisfies mutual dependency, and that there are some points in ∆n for which v assumes strictly positive values.

We begin with a basic question regarding properties of optimal versus individually optimal stationary contracts. Given an optimal (or pointwise optimal) contract x∗ ∈ ∆n, is it possible that x∗ is also individually optimal for some i ∈ N? As Lemma 5.3 shows (proof omitted), if v is continuously differentiable, this is not possible.

Lemma 5.3. Suppose that v is continuously differentiable, and define F : Rn → R with F ∈ {Vt, swt} (where t is a fixed time period); Given some x∗ that is a global maximum of F in the interior of ∆n, then x∗ does not maximize individual utility for any i ∈ N at time t.

Lemma 5.3 implies that there always exist stationary contracts that are better for individuals than optimal stationary contracts. In particular, an optimal contract is never a symmetric equilibrium of the strategic negotiation game. The proof of Lemma 5.3 is simple, but we wish to stress its importance. For an individual agent, this lemma presents a rather unfortunate state of affairs: any contract that is socially optimal is necessarily individually sub-optimal. This means that social welfare and individual gains are always at odds. Can we, under certain conditions, mitigate this effect? In what follows, we show that socially optimal contracts can be eventual consensus points, and eventual equilibria of strategic negotiation games.

Before we proceed, let us recall the following property of homogeneous functions.

Proposition 5.4. Let f : Rn → R be a k-homogeneous, differentiable function, then the point x∗ is a critical point of f in the interior ∆n if and only if ∂f ∂xi (x∗ ) = ∂f ∂xj (x∗ ) for all i, j ∈ N; in that case, ∂f

Using the formulas for individual utility derived from Equations (2) and (3), we obtain the following result.

Lemma 5.5. Let χ∗T = (x∗t )∞t=1 be an individually optimal contract for agent i at time T, then for any q ≤ T and any j, j ′ ∈ N such that j, j ′ ̸= i, ∂v ∂xj,q (x∗q ) = ∂v ∂xj′,q (x∗q ); moreover,

Proof. First, if χ∗T is an individually optimal contract at time T, then in particular, (x∗1 , . . . , x∗t ) is a critical point of Ui,T (χ∗T ) subject to the constraint that x∗t ∈ ∆n for all 1 ≤ t ≤ T . Translating this to Lagrange multipliers, we have a function

that equals Ui,T (x1, . . . , xT ) + ∑Tt=1 λt(1 - ∑nj=1 xj,t). Since (x∗1 , . . . , x∗T ) are a critical point of Ui,T subject to their constraints, we get that for any 1 ≤ q ≤ T and any j ̸= i,

Now,

which, by the closed-form formula for Vt, equals

which we simplify to ∂v ∂xj,q (x∗q ) 1 kq v(x∗q ) ∑Tt=q x∗i,tktVt(χ∗T ). Note that v(x∗q ) > 0 since χ∗T is individually optimal for i at time T, and in particular, i always chooses a point where positive profit is made, due to mutual dependency. Since ∂Ui,T ∂xj,q (x∗1 , . . . , x∗T ) = ∂Ui,T ∂xj′,q (x∗1 , . . . , x∗T ) for all j, j ′ ̸= i, we get that ∂v ∂xj,q (x∗q ) = ∂v ∂xj′,q (x∗q ) for all j, j ′ ̸= i and for all q ≤ T . Similarly, we take the derivative of Ui,T with respect to xi,q to obtain

which equals

which implies that for all j ̸= i,

Lemma 5.5 implies that if χ∗T = (x∗t )∞t=1 is an individually optimal contract for i ∈ N at time T, then every point x∗q is "nearly" a critical point of v: the partial derivatives of v at x∗q are all equal, except that of agent i. However, when fixing a time q and taking the horizon T to infinity, one can ensure that x∗q approaches a critical point of v over ∆n.

First, let us observe a simple property of individually optimal contracts.

Lemma 5.6. Suppose that v is k homogeneous. Let χ∗T = (x∗t )∞t=1 be an individually optimal contract for agent i at time T, and let x∗ be an optimal stationary contract, then x∗i,t ≥ x∗i for all t.

Proof. Assume otherwise, then at time t agent i receives a share of x∗i,t v(x∗t Vt-1(χ∗T )). Under x∗ , agent i could receive at time t x∗i v(x∗Vt-1(χ∗T )), which is strictly greater than what he receives at time t under χ∗T . Moreover, since x∗ maximizes v over ∆n, it also maximizes v over ∆n(Vt-1(χ∗T )); i.e., choosing x∗ will strictly improve welfare for i at time t, and weakly improve his welfare at every subsequent round.

Since Lemma 5.6 holds for any individually optimal contract, we get as a corollary that there is some constant c > 0 such that x∗i,t > c for all individually optimal contracts and for all t ∈ N. Given a contract χ = (xt)∞t=1 , agent i receives a weakly increasing share at every round if for all t,

Theorem 5.7. Suppose that we are given a sequence of contracts (χ∗T )∞T=1 such that χ∗T is individually optimal for agent i at time T for all T. Moreover, suppose that i receives a weakly increasing share under χ∗T for all T .

If v is continuously differentiable and homogeneous of degree k ≥ 1, then for any q ∈ N, if (xq(T))∞T=1 converges, then limT→∞xq(T) is a critical point of v over ∆n. However, if k < 1, then the limit is never a critical point.

Proof. The case k < 1 is omitted due to space constraints.

We show that when k ≥ 1, we do have convergence to a critical point. According to Lemma 5.5,

for all j, j ′ ̸= i. Now, it remains to show that

Under the above assumptions, this indeed holds. All we need to show is that

Letting x∗ ∈ argmaxx∈∆n v(x) be some optimal stationary contract, we recall that according to Lemma 5.6, xi,q(T) ≥ x∗i , and that x∗i > 0 according to the mutual dependency property. Therefore

Since v is homogeneous of degree k ≥ 1, we have that ∑T -q t=0 kt goes to infinity is T grows, thus

According to Proposition 5.4, this implies that the limit of the sequence (xq(T))∞T=1 is a critical point of v over ∆n.

If v has a unique critical point in the interior of ∆n (e.g., if v is a strictly concave function), then we can obtain a stronger claim.

Corollary 5.8. Let (χ∗T = (xt(T))∞t=1 )∞T=1 be a sequence satisfying the conditions stated in Theorem 5.7; suppose that v is continuously differentiable, concave and homogeneous of degree k ≥ 1; then for any q, limT→∞ xq(T ) exists and is an optimal contract for v.

Corollary 5.8 implies the following claim

Theorem 5.9. If v is continuously differentiable, homogeneous of degree k ≥ 1, and has a unique maximum x∗ over ∆n, then for every fixed q ∈ N, x∗ is an eventual consensus point of 〈N,w(0), v〉 for all t ≤ q.

Simply put, Theorem 5.9 states that as the horizon increases, agents can agree on sharing according to the optimal contract on early rounds; however, there is no such guarantee for later rounds.

In strategic negotiation games with static contracts, we can show an even stronger result: if we assume that the socially optimal contract x∗ can secure non-vanishing revenue to every one of the agents - i.e. that limT→∞Ui,T (x∗ ) = ∞ for all i ∈ N - then x∗ is an eventual consensus point for all t.

Theorem 5.10. Suppose that v is homogeneous of degree k ≥ 1 and has a unique maximum x∗ over ∆n; if agents have non-vanishing revenue under x∗ , then x∗ is an eventual static equilibrium of 〈N, w(0), v〉.

Theorems 5.9 and 5.10 do not hold if we drop the unique maximum assumption. Let x∗ , y∗ ∈ ∆n be two different maxima of v in ∆n. There exist i, j ∈ ∆n such that x∗i > x∗j and y∗ i < y∗ j . Under x∗ , agent j will do much better, and similarly, under y∗ , agent i will do much better. In this case, our results imply that for every i ∈ N, there is a socially optimal contract that is "nearly" individually optimal for i.

Theorems 5.9 and 5.10 rely on v being continuously differentiable; we can, prove similar claims for functions that are are uniform limits of continuously differentiable functions. Such functions are not mere pathologies, but arise in some of the applications we describe later, in Section 6. This is stated in Theorem 5.11 (proof omitted).

Theorem 5.11. If v is the uniform limit of continuously differentiable functions that are homogeneous of degree k ≥ 1, and v has a unique maximum x∗ over ∆n, then for any fixed q ∈ N x∗ is an eventual consensus point for all t ≤ q. Moreover, x∗ is an eventual static equilibrium of 〈N,w(0), v〉 under static contracts.

6 Applications

In this section we analyze certain classes of functions to which our results apply. In first set of examples, we explore common production functions used in the economic literature. The first three functions we study have inherent agent parameters, a1, . . . , an. We also write a = ∑ni=1 ai.

We first look at CES production functions (Constant Elasticity of Substitution); for two agents, constant elasticity of substitution captures the idea that an increase in the good of one agent would cause a constant reduction in the amount of good required by the other, in order to produce the same

amount of revenue. Let vr(x) be c · ( 1n ∑ni=1 ( xi ai )r) 1 r , where c and a1, . . . , an are positive constants, and r ̸= 0. When r < 1, vr is concave and homogeneous of degree 1. We observe that in general, CES production functions do not satisfy the mutual dependency property. For example v(x, y) = (√x + √y)2 is a CES production which satisfies v(1, 0) = v(0, 1) = 1. However, when r < 1, CES production functions are homogeneous of degree 1, and have a unique maximum over ∆n, and individual players' maxima occur in interior points (when the horizon T is more than 1).

A Cobb-Douglas production function is a function of the form vc(x) = c ∏ni=1 xai i . Cobb-Douglas production functions also capture some notion of substitutability among agents; the variable exponents strongly determine the payment to agent i under an optimal contract. Indeed, we observe that a Cobb-Douglas production function is a-homogeneous: vc(λx) = c ∏ni=1 (λxi)ai = λa vc(x). It is well-known in the economic literature that the maximum of vc over ∆n is unique, and equals ( a1 a , . . . , an a ), with the shares directly proportional to the weights ai. Moreover, the Cobb-Douglas production function is concave.

Next, consider the function vℓ(x) = cmini∈N{ xi ai }, known as a Leontief production function, where c and (ai)i∈N are all strictly positive constants. If agent production is determined by Leontief functions, their goods are entirely unsubstitutable. For example, in order to produce lemonade (priced at $2/cup), one needs 4 cups of lemon juice (priced at $0.1/cup), 1 cup of sugar (priced at $0.02/cup) and half a cup of mint (priced at $0.5/cup). A Leontief production function capturing the revenue that agents can produce given that they invest x, y, z dollars in lemon juice, sugar and mint, respectively, is

The function vℓ is 1-homogeneous. However, since vℓ is not differentiable, Theorem 5.7 does not apply here. However, limr→-∞vr(x) = vℓ(x); moreover, vℓ has a unique maximum over ∆n (x∗i = ai a for all i ∈ N), and is the uniform limit of functions satisfying the conditions of Theorem 5.11 (CES production functions with r < 1); thus, Theorem 5.11 applies to Leontief functions.

Finally, suppose we are given a directed, weighted graph Γ = 〈V, E〉, with a source-terminal node pair s, t ∈ V , where the edge set E (with E = {e1, . . . , en) and the weight of the edge ei ∈ E is a positive integer wi. Given a vector x ∈ Rn , the maximum flow function vΓ(x) is the maximum flow from s to t that can be achieved on Γ when the weight of the i-th edge is given by xiwi. The edge ei uses the amount of money it has, xi, to purchase capacity, which is multiplied by the factor wi. Given x ∈ Rn+, we write Γ(x) to be the graph Γ with capacities wixi; thus Γ(1n ) = Γ, and we indeed assume that w(0) = 1n . This means that vΓ(x) equals the maximum flow through Γ(x). This is a straightforward generalization of network flow games [Peleg and Sudh¨olter, 2007].

The first observation we make is that vΓ is homogeneous of degree 1: changing all edge capacities by a factor of λ results in a change of λ to the maximum flow. Interestingly, we can also show that the maximum flow function is the uniform limit of 1-homogeneous, concave, differentiable functions. However, it is only when vΓ has a unique maximum (i.e., a unique maximum flow in Γ) that our results hold.

Theorem 6.1. the maximum flow function vΓ is the uniform limit of 1-homogeneous, concave, differentiable functions.

Proof. Let us write Γ = 〈V,E〉, where E = {e1, . . . , en} is the set of directed edges in Γ. We let wi be the capacity of the edge ei. Let C(Γ) be the set of (s, t) cuts of Γ. Given a cut C ∈ C(Γ), we can write C as a vector wC in Rn , with wi,C = wi for all ei ∈ C, and wi,C = 0 otherwise. We let MΓ be an |C(Γ)| × n matrix whose rows are the vectors wC. This means that vΓ(x) can be rewritten as vΓ(x) = minC∈C(Γ) wC · x. Now, given a vector y in R|C| , we let fr(y) be a CES production function, i.e. fr(y) = c (∑|C| j=1 1 |C| yr i ) 1 r (here, a1 = · · · = a|C| = 1). We write vΓ,r : Rn → R to be vΓ,r(x) = fr(MΓx), and observe that limr→-∞vΓ,r(x) = vΓ(x) with uniform convergence.

We note that all vΓ,r are homogeneous of degree 1, differentiable in the interior of ∆n, and when r < 1, are strictly concave. This concludes the proof.

To conclude, if v is a

• (a) CES production function with parameter r < 1 or
• (b) Cobb-Douglas production function with a ≥ 1 or
• (c) Leontief function or
• (d) network flow function (Γ has a unique maximum flow), and x∗ is a global maximum of v over ∆n, then for any fixed

q ∈ N, x∗ is an eventual consensus point of 〈N,w(0), v〉 at time t ≤ q. Moreover, x∗ is an eventual static equilibrium of 〈N, w(0), v〉 under static contracts.

7 Conclusions and FutureWork

In this paper, we propose a new paradigm: selfish agents that care about their long-term revenue can achieve good outcomes without the help of an outside mediator. This approach can be naturally applied to any strategic setting that can be expressed as a function v : Rn → R. This includes, for example, cooperative games such as matching games, market exchange games, weighted voting games, and weighted graph games.

Not all of these settings induce homogeneous production functions, but we hope that when restricted to classes of games, structural properties of the game can be utilized in order to obtain some interesting results. We expect that in settings where homogeneity does not hold, individuals tend to be less collaborative.

We assume that at every round, agents "reinvest" all of the money towards future production. While this is a realistic assumption in some settings (e.g. government offices or company departments), one could relax this assumption by allowing agents to keep a certain fraction of their revenue at each round. If this share is fixed, our results easily hold. Complicated behavior may arise when agents are allowed to choose how much to invest in the group production and how much to keep for themselves.

Finally, one can naturally extend our model to uncertain environments. A noisy production function would be more realistic; moreover, due to the fact that notions such as mutual dependency may only hold in expectation. In this case, some agents may be paid at a round even if they do not contribute, since they may be useful in future iterations.

Acknowledgments: Part of this work was done while Yair Zick was affiliated with Nanyang Technological University, funded by the A*STAR (SINGA) scholarship.