I. INTRODUCTION

T HE problem that we consider in this paper is the fol- lowing: We have a buyer who is interested in buying multiple units of a single item. He associates a certain value for each unit of the item. The item goes through many stages of value addition through a linear supply chain. For each stage of value addition, there is at least one supplier. Each supplier has his own cost of value addition in each of the stages that he is present and also has a limited amount of capacity. The buyer's valuation and the suppliers' costs are assumed to be private information. The buyer and the suppliers can enter into a negotiation to finalize an outcome that indicates the number of units that would be produced, the suppliers who would be engaged in the value addition process, and a division of the surplus that accrues from the transaction. In a situation where information is not privately held a division of surplus could be done such that the allocations are in the core of the induced cooperative game. In the incomplete information situation however, this notion of the core needs to be extended appropriately. In doing this there are three basic issues to be considered as to how the agents' information may be used.

1) First, in evaluating whether a coalition can make all its members better off, we must be sure about when the agents' welfare should be evaluated. There are three stages -ex-ante, interim and ex-post, when this evaluation may be carried out. The appropriate stage to evaluate the welfare of agents in the MPNFI problem is the interim stage when each agent has learnt his own private type information but not that of the other agents.

This work was carried out while the first author was a student at the Indian Institute of Science. E-mail: chandrashekar.ts@gmail.com. Narahari Y is with the Department of Computer Science and Automation at the Indian Institute of Science, Bangalore, INDIA. E-mail: hari@csa.iisc.ernet.in 2) Secondly, in defining what a coalition can do, we assume that the agents will use all the information that is available to all its members in deciding upon a blocking plan which leads to the definition of a fine core [2]. 3) Finally, when we assume that agents share information, we must specify whether such communication between agents is verifiable or not. It is natural to see that the private information (valuation and costs) of the agents (buyer and suppliers) is not inherently verifiable and hence incentive constraints need to be incorporated into any analysis of the MPNFI problem. To summarize, the solution concept that we focus upon for the MPNFI problem is the interim, incentive compatible fine core.

A. Interim Incentive Compatible Fine Core

The extension of the core to a cooperative game with incomplete information that we consider for the MPNFI problem is a generalized version of the NTU game involving the method of fictitious transfers of weighted utilities. With incomplete information the role of weighted utility transfers is taken on by virtual utility. Virtual utility is defined by a formula that takes informational incentive constraints into account (see papers by Myerson [3], [4], [5]).

B. Contributions of the paper

Our specific contributions in this paper are twofold and are as follows:

• We believe that this is the first attempt to model the procurement network formation problem as a cooperative game within the context of an incomplete information environment. • We develop the structure of the game based on Myerson's approach [1] and focus on the incentive compatible fine core as a relevant solution concept to be used for this game. Our main result is to show that the incentive compatible fine core of MPNFI game is non-empty.

II. THE MPNFI PROBLEM

For the scenario introduced in Section I, we would expect the buyer and the suppliers to enter into negotiations to find the best way of forming the procurement network. The notion of best here includes (a) an efficiency criterion -selecting a set of suppliers and a quantity to be procured that maximizes the surplus and (b) an equity criterion -sharing the surplus such that the procurement network that is formed remains stable. Clearly the agents would like to negotiate a contract that achieves these objectives. Such a contract would be a state dependent contract. Our problem in this paper is to know whether such a contract exists.

A. Formulation of the MPNFI problem

We let the feasible network for forming the multiple unit single item procurement network be a directed graph G = (V, E) with V as the set of vertices, two special nodes v o (origin vertex) and v t (terminal vertex), and E ⊆ V × V as the set of edges. With each of the edges e ∈ E we associate the numbers c(e), l(e), and u(e). c(e) represents the cost, l(e) the lower bound on the capacity of the edge, and u(e) the upper bound on the capacity of the edge, respectively. Now, assume that each of the edges is owned by an agent i ∈ N where N is a finite set of agents N = {1, . . . , n, n + 1}. The agents {1, 2, . . . , n} own edges in the network and agent (n + 1) is the buyer. That is, we let ψ : E → N such that ψ(e) = i implies that agent i owns (possesses) edge e. We let I(j) and O(j) represent the set of all incoming and outgoing edges at vertex j ∈ V .

We let E S represent the set of edges owned by agents in S. We also designate F S as the flow in the network between the two special nodes v o and v t using only the edges E S that are owned by agents in S. For any flow F S , we denote the set of owners of the edges that facilitate the flow F S as ψ(F S ). We assume that if multiple units of the item are available to the buyer by using the flow F S , then it costs c(F S ) and the buyer is willing to compensate the edge owners with a value bF S where b is the value that the buyer attaches to a single unit of the item. The surplus from such a transaction is bF S − c(F S ). We now follow the structure presented in [5] to model the MPNFI scenario as a cooperative game with incomplete information.

1) Agents and their Resources: For simplicity of exposition, we assume here that each agent owns one edge in the network. The analysis however can be extended to scenarios where each agent owns multiple edges. We treat the edges and the money that is owned by agents as resources that are to be traded. Each agent i ∈ N has an initial resource vector r 0 i ∈ ℜ n+1 + where r 0 i,j ∈ {0, 1}, ∀ j ∈ {1, 2, . . . , n} and r 0 i,(n+1) ∈ ℜ + . This implies that when agent i owns the edge j ∈ E then r 0 ij = 1 and is otherwise 0. Having assumed that there is a one-to-one correspondence between the edges and the agents, we have r 0 i,i = 1 and r 0 i,j = 0, ∀ j = i. In addition the (n + 1) th entry in the endowment vector r 0 i indicates the amount of money that agent i has.

2) Type Information of Agents: We now specify the private information (costs and valuations) of the agents through the notion of types as introduced in [6]. For any agent i ∈ N we let T i denote the set of possible types. For the MPNFI problem we assume that the type refers to one of two pieces of information. The type t i ∈ T i for all edge owning agents i ∈ N \{(n + 1)} is a description of the cost that is incurred when an edge is used for an unit amount of flow and for buying agent (n + 1) it describes the valuation for a single unit of the item.

With N = {1, 2, . . ., n, n + 1} as the finite set of agents, we let T = T N = × i∈N T i be the set of all type profiles of all the agents in the game. An information state of the MPNFI scenario is given by t ∈ T and also written as t = (t −i , t i ) where the notation −i denotes N \{i}. Similarly, (t −i , t i ) denotes the vector t where t −i = (t 1 , . . . , t i−1 , t i+1 , . . . , t n+1 ) and the i th component t i is changed to t i ∈ T i . Similarly, T −i = × j =i T j , and for any coalition S, a non-empty subset of N , we let T S = × i∈S T i so that any t S ∈ T S denotes a combination of types (t i ) i∈S . We also let C denote the set of all possible coalitions or non empty subsets of N , that is, C = {S|S ⊆ N, S = ∅}. Now, for each possible type t i ∈ T i , we let q i (t i ) denote the probability that agent i is of type t i and we assume that there is probability that the agent is of any one of the types in T i is positive. That is q i (t i ) > 0, ∀ t i ∈ T i . We assume that the agents' types are independent random variables and hence we can write the following:

• q(t S ) = × i∈S q i (t i ), ∀ S ⊆ N, ∀ t S ∈ T S . • q(t −i ) = × j∈N−i q j (t j ), ∀ i ∈ N, ∀ t ∈ T . • q(t) = × j∈N q j (t j ), ∀ t ∈ T .

3) Outcome Sets: Now, for any subset S ∈ C, which includes the agent (n + 1), we define a set of market transactions. Note that without the buying agent being a part of the coalition, no transaction is possible. The market transaction follows from a surplus maximizing flow computation using the network flow model described earlier in the section. This computation is carried out when the types t i ∈ T i are declared by the agents i ∈ S. We call this set of market transactions as the set of possible outcomes X S (t S ), such that X S (t S ) = {(r i ) i∈S |r i ∈ ℜ n+1 + and i∈S r ij ≤ i∈S r 0 ij , ∀ j ∈ {1, 2, . . . , n, n + 1}}, where r i is the outcome vector of agent i after the transaction is carried out. The outcome set specifies that the reallocation of resources and money is such that there is no infusion of additional resources into the system. We also define the set X S and the set X as the sets that include the outcomes for all possible type declarations t S ∈ T S and all possible coalitions S ∈ C respectively. So, X S = tS ∈TS X S (t S ) and X = S∈C X S .

The reallocation of resources, i.e., the edges and the money, is carried out as follows: Given the set of edges owned by the agents in S, the capacities on these edges, the edge costs declared by them and the valuation declared by the buyer, a surplus maximising network flow computation identifies the set of edges and edge capacities whose ownership is to be transferred to the buying agent. Following this, each edge agent whose edge is transferred to the buying agent is compensated according to the declared cost. The entire surplus, defined as the difference between the buyer's valuation for the entire flow and the cost incurred by the edge agents in maintaining this flow, that results from the transaction is then given to either the buying agent or to one of the agents who plays an active role in providing the surplus maximising flow.

4) Utility Functions: Now, for any outcome x ∈ X and any t ∈ T , we let the utility for an agent i ∈ N be u i (x, t). For any agent i and outcome x, the final outcome vector r i reflects the edges that it currently owns and the money that it has after the transfers have been carried out. That is r i,i can be either 0 or 1 and r i,(n+1) ∈ ℜ.

So, the utility that an agent i = N \{(n + 1)} receives from outcome x when his type is t i is given by:

u i (x, t) = r i,(n+1) + (r i,i − r 0 i,i )t i .(1)

The payoff that the buying agent (n + 1) gets from an outcome x, when x vt is the number of units of the item that he gets, and his type is t (n+1) , is given by:

u (n+1) (x, t) = x vt t (n+1) + r (n+1),(n+1) − r 0 (n+1),(n+1) .

(2) 5) Representation of the MPNFI Game: The MPNFI scenario can now be described by the structure

Γ = (X, x * , (T i ) i∈N , (u i ) i∈N , (q i ) i∈N ).

Here, X refers to the set of all outcomes for all coalitions S ∈ C that could be formed; x * is a default outcome that results when the agents are unable to come to an agreement over the solution. In the context of the MPNFI problem, the default outcome is a null transaction whose utility for all types of all agents is 0. T i , u i , and q i are as defined earlier. This structure Γ of the game is assumed to be known to all agents. In addition we assume that each agent knows his own type before the start of negotiations. We now need to develop a solution to this cooperative game.

III. STATE CONTINGENT CONTRACTS

We assume here that the state contingent contract will be implemented by an external trustworthy mediator who can make side-payments to the agents. A state contingent contract is now defined as follows.

Definition 3.1: A state contingent contract is represented by a pair of functions (µ : T → ∆(X), χ : T → ℜ |N| ) where µ(x|t) represents the probability of choosing the outcome x ∈ X when the agents' types are t and χ(t) denotes the net monetary side-payments that the mediator makes to agent i when the agents' types are t.

If a mediator proposes to implement such a state contingent contract (µ, χ), then the agents must evaluate how they would fare if they agreed to its implementation. This evaluation is carried out by the agents at the interim stage and hence the correct measure of evaluation is conditionally expected utilities, conditioned on their private information.

A. Conditionally Expected Utilities

The conditionally expected utility of agent i if he were to agree to participate in the state contingent contract (µ, χ) proposed by a trustworthy mediator is given by:

U i (µ, χ|t i ) = t−i∈T−i q(t −i )[χ i (t) + x∈X µ(x|t)u i (x, t)] (3)

Now, if agent i is of type t i but pretends to be of type t i when he reports his type to the mediator who is implementing the state contingent contract (µ, χ), then his expected utility is given by:

U i (µ, χ, t i |t i ) = t −i ∈T −i q(t −i )[χ i (t −i , t i ) + x∈X µ(x|t −i , t i )u i (x, t)](4)

B. Incentive Feasible Contracts

If a trustworthy mediator were to implement the state contingent contract (µ, χ) by asking all the agents to reveal their types confidentially to him, then each of the agents would find it in their best interest to report their types honestly if and only if the contract (µ, χ) was incentive compatible. That is, conditionally expected utilities of the agents satisfy the following inequality:

U i (µ, χ|t i ) ≥ U i (µ, χ, t i |t i ), ∀ t i ∈ T i , ∀ t i ∈ T i , ∀ i ∈ N

(5) Since we have assumed that the mediator makes sidepayments to the agents, the expected utility for the mediator from implementing the incentive compatible contract (µ, χ) is − t∈T q(t) i∈N χ i (t). So, if we want a state contingent contract that is implementable, we should then look for one that is (a) incentive compatible and (b) gives the mediator nonnegative utility so that he does not lose from implementing the mechanism.

The utility that the mediator gets from implementing the state contingent contract (µ, χ) is equal to − t∈T q(t) i∈N χ i (t). So we want the following inequality to be satisfied.

t∈T q(t) i∈N χ i (t) ≤ 0(6)

Formally, we call such state contingent contracts as incentive feasible contracts and we define these as follows.

Definition 3.2: We say that a state contingent contract is incentive feasible if and only if it is incentive compatible and yields a non-negative expected payoff to the mediator. That is, it satisfies the inequalities 5 and 6.

In general, we know that there are a number of such incentive feasible state contingent contracts. The mediator's problem is to pick one such state contingent contract to implement. It would therefore be useful if he could be guided by the same criteria of efficiency and equity, but with appropriate extensions, in evaluating the incentive feasible state contingent contract to implement.

IV. THE EFFICIENCY PRINCIPLE

We have seen that in cooperative games with incomplete information, the appropriate object over which negotiations are carried out is the interim incentive compatible state contingent contract. And since conditionally expected utility is the appropriate measure of welfare evaluation of the agents, the mediator would be well placed in selecting a state contingent contract that maximizes the sum of conditionally expected utilities of the agents in the MPNFI game. We call such a contract an incentive-efficient contract. Formally, it is defined as follows: Definition 4.1: A state contingent contract (µ, χ) is weakly incentive-efficient if and only if it is incentive feasible and no other feasible state contingent contract yields higher expected utilities for all types of all agents.

So, we are interested in choosing a state contingent contract (µ, χ) that maximizes the conditionally expected utilities of all agents from among all contracts that obey inequalities ( 5) and (6). It is easy to see that the incentive constraints specified by (5) are convex. So, from convexity of the incentive constraints and linear programming theory, we can say that a feasible state contingent contract ( µ, χ) is incentive efficient if and only if there exists some vector λ = (λ i (t i )) ti∈Ti,i∈N such that λ i (t i ) ≥ 0, ∀ t i ∈ T i , ∀ i ∈ N with at least one strict inequality and ( µ, χ) maximizes i∈N ti∈Ti λ i (t i )U i (µ, χ|t i ) over all feasible state contingent contracts (µ, χ) (See [5]). This is a linear programming problem in (µ, χ).

Maximize i∈N ti∈Ti λ i (t i )U i (µ, χ|t i ) s.t. U i (µ, χ|t i ) ≥ U i (µ, χ, t i |t i ), ∀ t i , t i ∈ T i , ∀ i ∈ N t∈T q(t) i∈N χ i (t) ≤ 0 λ i (t i ) ≥ 0, ∀ t i ∈ T i , ∀ i ∈ N,(7)

For this linear program we can construct a Lagrangean function. We let α( t i |t i ) be the Lagrange multiplier for the constraint that says that type t i should not hope to gain by reporting type t to the state contingent contract being implemented by the mediator. With this we can write the Lagrangean of the linear programming problem as follows:

L(µ, χ, λ, α) = i∈N ti∈Ti U i (µ, χ|t i ) + ti∈Ti α i ( t i |t i )(U i (µ, χ|t i ) − U i (µ, χ, t i |t i ))(8)

A. The Notion of Virtual Utility

We now introduce an important notion that was first developed by Myerson in [5]. This is the notion of virtual utility which is defined by a formula that takes incentive constraints into account. For any outcome x ∈ X, type profile t ∈ T , and any given vectors λ and α we define the virtual utility v i (x, t, λ, α) for agent i as follows:

v i (x, t, λ, α) = 1 q i (t i )   (λ i (t i ) + ti∈Ti α i ( t i |t i ))u i (x, t) − ti∈Ti α i (t i | t i )u i (x, (t −i , t i )  (9)

Notice in equation ( 9) above that the Lagrange multiplier α i ( t i |t i ) is the dual variable corresponding to the incentive constraint which says an agent i of type t i should not gain by misrepresenting his type as t i . From linear programming theory, we know that this dual variable α i ( t i |t i ) will be nonzero when the corresponding constraint is tight. In the context of the MPNFI problem, if the constraint corresponding to the dual variable α i ( t i |t i ) is non-zero, then we can infer that agent i is tempted to misrepresent his type as t i when his actual type is t i because he gets the same expected utility. From an inspection of equation ( 9), we can conclude that the virtual utility of agent i for an outcome x ∈ X when the type profile is t magnifies the difference between the utilities of his true type t i and the type t i that would tempt him to misrepresent. Now, we can rewrite the Lagrangean in equation ( 8) by using equations ( 3), ( 4) and ( 9) as follows:

L(µ, χ, λ, α) = t∈T q(t) x∈X µ(x|t) i∈N v i (x, t, λ, α) + 1 q i (t i ) t∈T q(t) i∈N χ i (t)   ti∈Ti α i ( t i |t i ) − ti∈Ti α i (t i | t i ) + λ i (t i )  (10)

So, the linear programming problem given by equation ( 7) can be rewritten in terms of virtual utilities as follows:

Max t∈T q(t) x∈X µ(x|t) i∈N v i (x, t, λ, α) + 1 q i (t i )   t∈T q(t) i∈N χ i (t)   ti∈Ti α i ( t i |t i ) + − ti∈Ti α i (t i | t i ) + λ i (t i )    (11) s.t.

t∈T q(t)

i∈N χ i (t) ≤ 0 (12) λ i (t i ) ≥ 0, ∀ t i ∈ T i , ∀ i ∈ N, with at least one strict inequality(13)

B. Incentive Efficient Contracts

From this reformulation of the optimization problem, it is easy to note that the mediator must pick a state contingent contract that maximizes the sum of the virtual utilities of all types of all agents. Now, the Lagrangean in equation ( 10) can be maximized only if the coefficients of χ i (t) are constant over all i and t. Such a constant can be set to 1 without loss of generality. A standard Lagrangean analysis now allows us to record the following proposition: Proposition 4.2: A feasible state contingent contract (µ, χ) is incentive efficient if and only if there exist vectors λ and α such that:

λ i (t i ) ≥ 0 and α i ( t i |t i ) ≥ 0, ∀ t i ∈ T i , ∀ t i ∈ T i , ∀ i ∈ N. (14) λ i (t i ) + ti∈Ti α i ( t i |t i ) − ti∈Ti α i (t i | t i ) = q i (t i ). (15)α i ( t i |t i ) U i (µ, χ|t i ) − U i (µ, χ, t i |t i ) = 0, ∀ t i , t i ∈ T i , ∀ i ∈ N. (16) µ(x|t) > 0 =⇒ x ∈ argmax y∈X i∈N v i (y, t, λ, α), ∀ t ∈ T , ∀ x ∈ X.(17)

Equation ( 14) comes from (a) our choice of the λ vector that is chosen to maximize the expected utilities and (b) the α vector corresponds to Lagrangean multipliers or dual variables corresponding to the incentive constraints, which by definition are non-negative. Equation (15) comes from setting the coefficients of χ i (t) to unity. Equation ( 16) is nothing but the complementary slackness conditions corresponding to the incentive constraints of the original linear programming problem. Finally, equation (17) comes from the fact that the mediator is maximizing the sum of the virtual utilities of all the agents when he chooses the state contingent contract.

V. THE EQUITY PRINCIPLE

In the theory of the core for games with complete information, we are interested in establishing an allocation of surplus that inhibits agents from deviating and joining a coalition that can offer an alternative allocation of surplus which blocks the former. That is, we compare alternative contracts (allocations of surplus) with an established one. In extending this idea to the incomplete information case, we should think in terms of an established mediator who implements a state contingent contract that inhibits agents from deviating to cooperate with another blocking mediator who has a blocking state contingent contract to offer.

In addition, in the complete information case, we allow agents to compare an alternative contract with an established contract with the assumption that any agent who rejects the alternative will still get his allocation as specified by the established contract. For such an assumption to be workable, we then require that if any one agent rejects the alternative then all agents must continue to adhere to the established contract. That is, there can be no blocking without unanimity among all agents that are invited to block. In the incomplete information case, we must recognize the fact that some agents may be willing to block when they are of a certain type and not otherwise. So, an agent who agreed to block but was returned to the original contract would have now learnt new information which he could possibly use profitably in the established contract. So, to maintain the assumption that agents allocations as specified in the established contract are guaranteed, we will have to think about the blocking question being raised after the agents have sent in their type information to the established mediator, but before they are committed to the state contingent contract that is to be implemented. This means that we need to formalize the blocking procedure and the blocking state contingent contacts.

A. Blocking Coalitions and Blocking State Contingent Contracts

The blocking procedure that we follow includes a blocking mediator. We assume that the blocking mediator may invite different coalitions according to some known randomized plan. The plan includes a specification of the probability of any coalition being chosen to implement a specific outcome that is feasible for that coalition. The outcome should of course depend on the information available to the coalition since it is unreasonable to allow blocking by a coalition to depend on information of agents outside the coalition.

So, we assume that a blocking mediator can ask any random subset S about their types and, based on their responses, must either invite all of S to join the blocking coalition to implement a jointly feasible outcome x S ∈ X S or invite no coalition at all.

Such a blocking procedure may be characterized as follows: For any outcome x S ∈ X S and any type profile t S ∈ T S of the agents in S, we let ν S (x S |t S ) represent the probability that coalition S would be invited to block and implement the jointly feasible outcome x S ∈ X S if the agents in S report a type profile t S . Also, since we allowed the established mediator to make side-payments, we must also allow the blocking mediator to make side-payments. We do this by allowing the blocking mediator to specify the expected side-payment for each possible type of each agent. So, for each type t i of each agent i, we let ξ i (t i ) be the blocking mediator's expected sidepayment to agent i if i would be willing to block and report type t i to the blocking mediator. With this we can define a blocking state contingent contract (ν, ξ) as follows:

Definition 5.1: A blocking state contingent contract by a blocking mediator is a pair of vectors (ν, ξ) such that:

1) ν = (ν S ) S⊆N , 2) ν S (x S |t S ) ≥ 0, ∀ x ∈ X S , ∀ t S ∈ T S , 3) S⊆N tS∈TS xS ∈XS ν S (x S |t S ) ≤ 1, and 4) ξ i (t i ) ∈ ℜ, ∀ t i ∈ T i , ∀ i ∈ N .

In definition (5.1) above, the blocking state contingent contract is a pair of vectors where the probability of any coalition S being picked to implement an outcome x S ∈ X S when its type profile is t S is always non-negative; and the probability of any such coalition being chosen by the blocking mediator is never greater than unity. With this definition of a blocking state contingent contract, we can now specify the blocking procedure.

1) The Blocking Procedure: We can describe the blocking procedure with this series of steps:

• First, according to the probability distribution specified by ν = (ν S ) S⊆N , the blocking mediator chooses a random coalition S ⊆ N , a random profile of types t S ∈ T S and a random outcome x S ∈ X S . • The mediator then asks each of the agents in S whether he is willing to block and, if so, what his type is.

• If the agents in S all agree to block and their type profiles coincide exactly with t S then the blocking mediator forms the coalition S and implements the jointly feasible outcome x S . • But if anyone of the agents does not agree to block or if the type profile does not match with t S then he asks all the agents in S to continue with the state contingent contract from the established mediator. • Now, when the blocking coalition does form, the planned monetary side-payments from the blocking mediator to the agents could depend on the blocking coalition S, the type profile t S , and the jointly feasible outcome x S that they implement. We let this be described by any function ξ(x S , t S ) such that:

S∋{i} t S\{i} ∈T S\{i} xS ∈XS ν S (x S |t S ) ξ i (x S , t S ) = ξ i (t i )

Now that we have formalized the notions of a blocking state contingent contract and the blocking procedure, to operationalize the idea of equity in selecting an implementable state contingent contract we would need to compare the utilities that such blocking state contingent contracts provide to agents in a blocking vis-a-vis the utilities that they derive by continuing to remain in the state contingent contract that an established mediator seeks to implement. We do this next.

2) Tenable Blocking State Contingent Contracts: For the purpose of comparing the welfare that agents get by either going along with a blocking mediator or staying with an established mediator, we let ω i (t) denote the utility allocation from a state contingent contract of the established mediator that an agent i would lose when the type profile was t and he decided to join a blocking mediator. Let ω = (ω i (t)) i∈N,t∈T be a vector of such utility allocations. Given this vector of utility allocations, any blocking state contingent contract that a blocking mediator proposes must be such that it gives the agents more than what they can get in the established plan. We call such a state contingent contract a tenable state contingent contract and define it formally below: Definition 5.2: A blocking state contingent contract (ν, ξ) is tenable against an established state contingent contract (µ, χ) which gives utility allocations ω = (ω i (t)) t∈T ,i∈N if and only if it satisfies the conditions in equations 18 to 20: Equation ( 18) states the fact that agents in a blocking coalition must not lose when they deviate from the established mediator; equation ( 19) is simply the incentive compatibility condition that says that agents must find it beneficial to report their true types to the blocking mediator when they have deviated from the established mediator; finally equation (20) simply says that the blocking mediator must get a non-negative payoff from forming a blocking coalition and implementing the blocking contract.

With this definition of a blocking state contingent contract, we can now sharpen our focus on isolating those contracts that are both efficient and equitable that an established mediator can hope to implement. Such contracts can be said to be inhibitive since they inhibit agents from cooperating with a blocking mediator and forming a blocking coalition that implements a blocking state contingent contract. We define such contracts next.

B. Inhibitive State Contingent Contracts and Allocations

Recall from our discussion on the efficiency criterion in selecting a state contingent contract by an established mediator, we were able to define an optimization problem whose objective was to maximize the sum of virtual utilities of all the agents. That is, in selecting a state contingent contract to implement, the mediator would have to assume that the agents were behaving in a manner to maximize their virtual utilities and not their actual utilities. So, in order to operationalize the equity criteria in the selection of a contract, we would have to carry out the comparisons between contracts offered by an established mediator and a blocking mediator in virtual utility terms.

Recall now our utility allocation vector ω = (ω i (t)) i∈N,t∈T . Such a utility allocation vector is said to be inhibitive if and only if there does not exist any blocking state contingent contract (ν, ψ) that is tenable against it. Since the Lagrangean function (11) that we are maximizing is specified in terms of virtual utilities, we would need to make these comparisons between the utility allocation vector ω and those from a blocking state contingent contract in virtual utility terms.

1) A Virtual Utility Transformation of Inhibitive Allocations: We let V i (ω, t, λ, α) be the transformation of agent i's utility allocations in ω into virtual utility in state t, according to the equation ( 9) with parameters λ and α. We therefore have the following relation:

V i (ω, t, λ, α) = 1 q i (t i )   (λ i (t i ) + ti∈Ti α i ( t i |t i ))ω i (t)   − 1 q i (t i )   ti∈Ti α i (t i | t i )ω i (t −i , t i )  (21)

With this relation in place, we can now redefine an inhibitive allocation vector in terms of its virtual utilities. That is, we say that the utility allocation vector ω coming from a state contingent contract (µ, χ) is inhibitive if and only if there exist parameters λ and α such that, for any coalition S, the sum of virtual utilities that the members of S can expect with any outcome that is feasible for them, given all their information, is not more than the virtual-utility transformation of what they expect from the inhibitive utility allocation vector ω. We record this as a theorem below. theorem 5.3: An allocation vector ω from a state contingent contract (µ, χ) offered for implementation by an established mediator is inhibitive if and only if there exist vectors λ and α such that:

1)

λ i (t i ) + ti∈Ti α i ( t i |t i ) − ti∈Ti α i (t i | t i ) = q i (t i ), ∀ t i ∈ T i , ∀ i ∈ N , 2) t N\S ∈T N\S q(t N\S ) i∈S V i (ω, t, λ, α) ≥ t N\S ∈T N\S q(t N\S ) i∈S v i (x S , t, λ, α), ∀ S ⊆ N, ∀ x S ∈ X S , ∀ t S ∈ T S , 3) λ i (t i ) ≥ 0 and α i ( t i |t i ) ≥ 0, ∀ t i ∈ T i , ∀ t i ∈ T i , ∀ i ∈ N . ξ i (t i ) + t−i∈T−i q(t −i ) S⊇{i} xs∈XS ν S (x S |t S )(u i (x S , t) − ω i (t)) ≥ 0, ∀ t i ∈ T i , ∀ i ∈ N.(18)ξ i (t i ) + t−i∈T−i q(t −i ) S⊇{i} xs∈XS ν S (x S |t S )(u i (x S , t) − ω i (t)) ≥ ξ i ( t i ) + t−i∈T−i q(t −i ) S⊇{i} xs∈XS ν S (x S |t S−i , t i )(u i (x S , t) − ω i (t)), ∀ t i ∈ T i , ∀ t i ∈ T i , ∀ i ∈ N. (19) − i∈N ti∈Ti q i (t i )ξ i (t i ) ≥ 0. (20)

Proof: The proof for this theorem is along the lines of the proof in Theorem 1 in [1] and hence is omitted here.

The theorem basically says that the utility allocation vector is inhibitive if and only if there exist parameters λ and α such that, for any coalition S, the sum of all virtual utilities that the members of S can expect is not more than the sum of the virtual utility transformations of what they can expect from the ω given all their type information.

With this understanding of inhibitive allocations, we are ready to define the notion of the core as extended to cooperative games with incomplete information.

VI. THE INTERIM INCENTIVE COMPATIBLE FINE CORE OF

THE MPNFI GAME Recall from our preliminary discussion on the core for the MPNFI game in Section I that we assumed the mediator can make severance payments to agents who deviate from the established mediator to a blocking mediator. This assumption at first glance may seem surprising because such severance payments in the complete information case can never be beneficial. But in the incomplete information case they are serve an essential technical purpose in deriving the proof of existence of the core [1].

A. Balancedness and Balanced Games

For now, we let ǫ i (t) denote the severance payment that agent i would get from the established mediator if he joined a blocking coalition after the type profile t was reported to the established mediator. We can now define the notion of an utility allocation vector that is achievable by a state contingent contract (µ, χ). Definition 6.1: A utility allocation vector ω = (ω i (t)) t∈T ,i∈N is achievable by a state contingent contract (µ, χ) if and only if (µ, χ) is feasible (as defined in Definition 3.2) and there exists a promised vector of severance payments ǫ = (ǫ i (t)) t∈T ,i∈N such that:

1) ǫ i (t) ≥ 0, and 2)

ω i (t) = χ i (t) + x∈X µ(x|t)u i (x, t) − ǫ i (t), ∀ t ∈ T, ∀ i ∈ N .

It is easy to see that ω i (t) is the residual stake that an agent i has in the established plan which he stands to lose if he deviates to blocking coalition in state t. With this, we are ready to define the interim incentive compatible fine core of the MPNFI game and then examine its non-emptiness.

1) The Incentive Compatible Fine Core: Definition 6.2: A utility allocation vector ω is said to be in the incentive compatible fine core if and only if ω is inhibitive and achievable by some feasible state contingent contract (µ, χ).

In general, we have seen in the case of complete information games that (a) the non-emptiness of the core is not guaranteed and (b) to show non-emptiness of the core a balancedness condition should be satisfied. Our main result is to show that the incentive compatible fine core of the MPNFI game is nonempty. To show this we use the extension of the balancedness condition to incomplete information settings as introduced in [1].

2) Balancedness and Balancing Weights: Definition 6.3: We let a vector of weights θ = (θ S,xS ) xS ∈XS ,S⊆N be a balanced collection of weights if and only if the following conditions are satisfied:

1) θ S,xS ≥ 0 ∀ x S ∈ X S , ∀ S ⊆ N 2) S⊇{i} xS ∈XS θ S,xS = 1, ∀ i ∈ N .

3) Balanced Games: Definition 6.4: We say that a game is balanced if for any balanced collection of weights θ = (θ S,xS ) xS ∈XS ,S⊆N , there is some randomized strategy σ ∈ ∆(X) such that the following condition is satisfied.

x∈X σ(x)u i (x, t) = S⊇{i} xS ∈XS θ S,xS u i (x S , t), ∀ t ∈ T, ∀ i ∈ N.(22)

Myerson [1] has shown that if the game is balanced then the core is non-empty. We record this as a theorem below which we use to show the non-emptiness of the incentive compatible fine core of the MPNFI game. theorem 6.5: If a cooperative game with incomplete information is balanced then the incentive compatible fine core is non-empty.

B. Non-Emptiness of the Incentive Compatible Fine Core of the MPNFI Game theorem 6.6: The incentive compatible fine core of the MPNFI game is non-empty. Proof: To show that this theorem holds, we simply need to show that the MPNFI game is balanced. That is, we need to show that there is some randomization over the set of outcomes (σ ∈ ∆(X)) such that the condition given by equation ( 23) is satisfied for any balanced collection of weights θ = (θ S,xS ) xS ∈XS ,S⊆N , for the class of MPNFI games.

x∈X σ(x)u i (x, t) = S⊇{i} xS ∈XS θ S,xS u i (x S , t), ∀ t ∈ T, ∀ i ∈ N(23)

To show this we first consider two special cases of the balanced collection of weights θ = (θ S,xS ) xS∈XS ,S⊆N .

Case 1: Consider the collection of singleton subsets of N . With such a collection of subsets of N , it is easy to see that the only outcome possible for each subset is the no-trade outcome and we know that the utility that an agent gets from the no-trade outcome is zero. So, for any agent i ∈ N and for any singleton coalition S = {i}, the set of outcomes is a singleton X S = 1 and the utility of this outcome x S ∈ X S is u i (x S , t) = 0, ∀ t ∈ T . Such a collection of subsets can be a balanced collection if we associate the weights θ {i} = 1. Notice that we have dropped the subscript associated with the outcome since the the set of outcomes is a singleton. With this set of balancing weights and utilities associated with the outcomes, it is easy to see that the LHS of equation ( 23) is always zero. Now, looking at the RHS of equation ( 23), it is clear that we can always pick a randomization σ over the set of outcomes X such that the probability associated with the outcome which gives no agent any of the surplus is always 1. Such an outcome can be trivially constructed by giving all the surplus to the mediator. So, the RHS of ( 23) is also zero and we have a randomization over the set of outcomes such that the condition in equation ( 23) is satisfied.

Case 2: We now consider a balancing vector θ such that θ N, x = 1 for some x ∈ X and θ S,xS = 0 for all other (S, x S ) = (N, x).

This can be easily proved and hence for reasons of consevring space is omitted.

The General Case: We now consider the case of an arbitrarily balanced collection, say C = {S 1,x11 , S 1,x12 , . . . , S 1,x1k , S 2,x21 , . . . , S j,xj1 , . . . , S l,x1m } where an element S j,xj1 of the set C refers to the fact that coalition S j ⊆ N forms and implements the outcome x j1 ∈ X j . Given the above balanced collection C, from the definition of balancedness, we have the following relations.

θ S,xS ≥ 0, ∀ x S ∈ X S , ∀ S ∈ C (24) S∋{i};S∈C xS∈XS θ S,xS = 1, ∀ i ∈ N.(25)

For this balanced collection, consider a partition of the set C into two such that one of them includes all the elements S j,xji where the buying agent (n + 1) ∈ S and another where the buying agent is not included. We denote these sets as From the structure of the MPNFI problem, it is clear that the only outcome possible for any coalition S that does not contain the buying agent is the no-trade outcome. The utility of the no-trade outcome is zero for all agents in a coalition S that does not contain the buying agent (n+1). This means that in equation ( 27) above, we have u i (x S , t) = 0, ∀ i ∈ S, S ∈ C −(n+1) , ∀ t ∈ T . So, equation ( 27 Equation (29) follows from equation (24). Equation (30) follows from the fact that the C (n+1) contains all those sets which include the buying agent (n + 1) and sum of the weights associated with these sets and their outcomes must sum to unity given the fact that we are considering a balanced collection of weights.

This immediately implies the following:

S∈C (n+1) ;S∋i xS ∈XS θ S,xS = 1, if i = (n + 1)(31)S∈C (n+1) ;S∋i xS ∈XS θ S,xS ≤ 1, if i = (n + 1)(32)

So, the vector of balancing weights (θ S,xS ) xS ∈XS ,S∈C (n+1) is akin to a probability distribution over the set of all possible outcomes (X S ) S∈C (n+1) . Since any outcome that can be achieved by a coalition S ⊂ N where S ∋ {(n + 1)} can also be achieved by the grand coalition N , we can construct a randomization σ over the set of outcomes X such that the randomization simply assigns the same weight as the corresponding balancing weight to a particular outcome (S, x S ).

With this, it is clear that given an arbitrary set of balancing weights, a randomization over the set of outcomes X is always possible such that the condition in Equation (23) always holds. This proves that the MPNFI game is balanced. And from Theorem 6.5 we can infer that the MPNFI game has a nonempty incentive compatible fine core.

VII. DISCUSSION AND CONCLUSION

In studying the procurement network formation problem when informational asymmetries exist, we have borrowed the conceptual apparatus from the stream of literature that extends the core to incomplete information settings [7], [8], [9], [10], [11]. Our result on the non-emptiness of the interim incentive compatible fine core of the multiple unit, single item procurement network formation problem shows clearly that a mediator, possibly a web based market maker can always come up with a mechanism to form the procurement network. The mechanism here is simply an implementation of the state contingent contract. However, before we can operationalize this there are several open issues that need to be addressed.

1) Our result on the non-emptiness of the incentive compatible fine core is a non-constructive existence result. We still need to develop an algorithmic procedure to identify a state contingent contract that is in the core of the game.

2) The interim incentive compatible core is an axiomatic exogenously imposed solution concept. If agents were to engage in endogenous non-cooperative play to agree upon a state contingent contract, then designing an extensive form game to reconcile the endogenous and exogenous viewpoints is an interesting question. Such games have been designed for the complete information setting, but we are not aware of any literature in the incomplete information context.