FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 1 On the Incentive Compatible Core of a Procurement Network Formation Game with Incomplete Information Chandrashekar T S, Narahari Y Abstract—In this paper we present a model of the multiple 2) Secondly, in defining what a coalition can do, we assume unit, single item procurement network formation problem in that the agents will use all the information that is environments with incomplete information (MPNFI). For this we available to all its members in deciding upon a blocking first develop the structure of the procurement network formation problem within Myerson’s framework for cooperative games plan which leads to the definition of a fine core [2]. with incomplete information [1]. Using this framework we then 3) Finally, when we assume that agents share information, investigate the non-emptiness of the incentive compatible core, we must specify whether such communication between an extension of the notion of the core for complete information agents is verifiable or not. It is natural to see that the settings based on Myerson’s framework, and show that it is private information (valuation and costs) of the agents indeed non-empty for the class of MPNFI games. (buyer and suppliers) is not inherently verifiable and Index Terms—Cooperative Games, Incomplete Information, hence incentive constraints need to be incorporated into Procurement Networks any analysis of the MPNFI problem. To summarize, the solution concept that we focus upon for I. I NTRODUCTION the MPNFI problem is the interim, incentive compatible fine core. 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 A. Interim Incentive Compatible Fine Core for each unit of the item. The item goes through many stages The extension of the core to a cooperative game with incom- of value addition through a linear supply chain. For each stage plete information that we consider for the MPNFI problem is of value addition, there is at least one supplier. Each supplier a generalized version of the NTU game involving the method has his own cost of value addition in each of the stages that of fictitious transfers of weighted utilities. With incomplete he is present and also has a limited amount of capacity. The information the role of weighted utility transfers is taken on by buyer’s valuation and the suppliers’ costs are assumed to be virtual utility. Virtual utility is defined by a formula that takes private information. The buyer and the suppliers can enter into informational incentive constraints into account (see papers by a negotiation to finalize an outcome that indicates the number Myerson [3], [4], [5]). of units that would be produced, the suppliers who would be engaged in the value addition process, and a division of B. Contributions of the paper the surplus that accrues from the transaction. In a situation where information is not privately held a division of surplus Our specific contributions in this paper are twofold and are could be done such that the allocations are in the core of as follows: the induced cooperative game. In the incomplete information • We believe that this is the first attempt to model the situation however, this notion of the core needs to be extended procurement network formation problem as a cooperative appropriately. In doing this there are three basic issues to be game within the context of an incomplete information considered as to how the agents’ information may be used. environment. • We develop the structure of the game based on Myerson’s 1) First, in evaluating whether a coalition can make all its members better off, we must be sure about when approach [1] and focus on the incentive compatible fine the agents’ welfare should be evaluated. There are core as a relevant solution concept to be used for this three stages - ex-ante, interim and ex-post, when this game. Our main result is to show that the incentive compatible fine core of MPNFI game is non-empty. 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 II. T HE MPNFI P ROBLEM private type information but not that of the other agents. For the scenario introduced in Section I, we would expect the buyer and the suppliers to enter into negotiations to find This work was carried out while the first author was a student at the Indian the best way of forming the procurement network. The notion 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 best here includes (a) an efficiency criterion - selecting a of Science, Bangalore, INDIA. E-mail: hari@csa.iisc.ernet.in set of suppliers and a quantity to be procured that maximizes FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 2 the surplus and (b) an equity criterion - sharing the surplus With N = {1, 2, . . ., n, n + 1} as the finite set of agents, such that the procurement network that is formed remains we let T = TN = ×i∈N Ti be the set of all type profiles of all stable. Clearly the agents would like to negotiate a contract the agents in the game. An information state of the MPNFI that achieves these objectives. Such a contract would be a scenario is given by t ∈ T and also written as t = (t−i , ti ) state dependent contract. Our problem in this paper is to know where the notation −i denotes N \{i}. Similarly, (t−i , b ti ) whether such a contract exists. denotes the vector t where t−i = (t1 , . . . , ti−1 , ti+1 , . . . , tn+1 ) and the ith component ti is changed to b ti ∈ Ti . Similarly, A. Formulation of the MPNFI problem T−i = ×j6=i Tj , and for any coalition S, a non-empty subset We let the feasible network for forming the multiple unit of N , we let TS = ×i∈S Ti so that any tS ∈ TS denotes a single item procurement network be a directed graph G = combination of types (ti )i∈S . We also let C denote the set of (V, E) with V as the set of vertices, two special nodes vo all possible coalitions or non empty subsets of N , that is, C (origin vertex) and vt (terminal vertex), and E ⊆ V × V as = {S|S ⊆ N, S 6= ∅}. the set of edges. With each of the edges e ∈ E we associate the Now, for each possible type ti ∈ Ti , we let qi (ti ) denote numbers c(e), l(e), and u(e). c(e) represents the cost, l(e) the the probability that agent i is of type ti and we assume that lower bound on the capacity of the edge, and u(e) the upper there is probability that the agent is of any one of the types in bound on the capacity of the edge, respectively. Now, assume Ti is positive. That is qi (ti ) > 0, ∀ ti ∈ Ti . We assume that that each of the edges is owned by an agent i ∈ N where N the agents’ types are independent random variables and hence is a finite set of agents N = {1, . . . , n, n + 1}. The agents we can write the following: {1, 2, . . . , n} own edges in the network and agent (n + 1) is • q(tS ) = ×i∈S qi (ti ), ∀ S ⊆ N, ∀ tS ∈ TS . the buyer. That is, we let ψ : E → N such that ψ(e) = i • q(t−i ) = ×j∈N−i qj (tj ), ∀ i ∈ N, ∀ t ∈ T . implies that agent i owns (possesses) edge e. We let I(j) and • q(t) = ×j∈N qj (tj ), ∀ t ∈ T . O(j) represent the set of all incoming and outgoing edges at vertex j ∈ V . 3) Outcome Sets: Now, for any subset S ∈ C, which We let ES represent the set of edges owned by agents in S. includes the agent (n + 1), we define a set of market transac- We also designate FS as the flow in the network between the tions. Note that without the buying agent being a part of the two special nodes vo and vt using only the edges ES that are coalition, no transaction is possible. The market transaction owned by agents in S. For any flow FS , we denote the set of follows from a surplus maximizing flow computation using owners of the edges that facilitate the flow FS as ψ(FS ). We the network flow model described earlier in the section. assume that if multiple units of the item are available to the This computation is carried out when the types ti ∈ Ti buyer by using the flow FS , then it costs c(FS ) and the buyer is are declared by the agents i ∈ S. We call this set of willing to compensate the edge owners with a value bFS where market transactions as the set of possible outcomes n+1 P XS (tS ), b is the value that the buyer attaches to a single unit of the such P that XS (t S ) = {(r i )i∈S |r i ∈ ℜ + and i∈S rij ≤ 0 item. The surplus from such a transaction is bFS − c(FS ). We i∈S r ij , ∀ j ∈ {1, 2, . . . , n, n + 1}}, where ri is the now follow the structure presented in [5] to model the MPNFI outcome vector of agent i after the transaction is carried out. scenario as a cooperative game with incomplete information. The outcome set specifies that the reallocation of resources and 1) Agents and their Resources: For simplicity of exposi- money is such that there is no infusion of additional resources tion, we assume here that each agent owns one edge in the into the system. We also define the set XS and the set X as the network. The analysis however can be extended to scenarios sets that include the outcomes for all possible type declarations where each agent owns multiple edges. We treat the edges and tS ∈ TS S and all possible coalitions S S ∈ C respectively. So, the money that is owned by agents as resources that are to XS = tS ∈TS XS (tS ) and X = S∈C XS . be traded. Each agent i ∈ N has an initial resource vector The reallocation of resources, i.e., the edges and the money, ri0 ∈ ℜn+1 + 0 where ri,j ∈ {0, 1}, ∀ j ∈ {1, 2, . . . , n} and is carried out as follows: Given the set of edges owned by 0 the agents in S, the capacities on these edges, the edge costs ri,(n+1) ∈ ℜ+ . This implies that when agent i owns the edge 0 declared by them and the valuation declared by the buyer, j ∈ E then rij = 1 and is otherwise 0. Having assumed that there is a one-to-one correspondence between the edges and a surplus maximising network flow computation identifies 0 0 the set of edges and edge capacities whose ownership is the agents, we have ri,i = 1 and ri,j = 0, ∀ j 6= i. In addition the (n + 1)th entry in the endowment vector ri0 indicates the to be transferred to the buying agent. Following this, each amount of money that agent i has. edge agent whose edge is transferred to the buying agent 2) Type Information of Agents: We now specify the private is compensated according to the declared cost. The entire information (costs and valuations) of the agents through the surplus, defined as the difference between the buyer’s valuation notion of types as introduced in [6]. For any agent i ∈ N for the entire flow and the cost incurred by the edge agents in we let Ti denote the set of possible types. For the MPNFI maintaining this flow, that results from the transaction is then problem we assume that the type refers to one of two pieces given to either the buying agent or to one of the agents who of information. The type ti ∈ Ti for all edge owning agents plays an active role in providing the surplus maximising flow. i ∈ N \{(n + 1)} is a description of the cost that is incurred 4) Utility Functions: Now, for any outcome x ∈ X and when an edge is used for an unit amount of flow and for any t ∈ T , we let the utility for an agent i ∈ N be ui (x, t). buying agent (n + 1) it describes the valuation for a single For any agent i and outcome x, the final outcome vector ri unit of the item. reflects the edges that it currently owns and the money that it FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 3 has after the transfers have been carried out. That is ri,i can be either 0 or 1 and ri,(n+1) ∈ ℜ. X X Ui (µ, χ, b ti |ti) = q(t−i )[χi(t−i , b ti ) + µ(x|t−i , b ti)ui (x, t)] So, the utility that an agent i = N \{(n + 1)} receives from t−i ∈T−i x∈X outcome x when his type is ti is given by: (4) 0 ui (x, t) = ri,(n+1) + (ri,i − ri,i )ti . (1) B. Incentive Feasible Contracts The payoff that the buying agent (n + 1) gets from an If a trustworthy mediator were to implement the state outcome x, when xvt is the number of units of the item that contingent contract (µ, χ) by asking all the agents to reveal he gets, and his type is t(n+1) , is given by: their types confidentially to him, then each of the agents would find it in their best interest to report their types honestly if 0 and only if the contract (µ, χ) was incentive compatible. That u(n+1) (x, t) = xvt t(n+1) + r(n+1),(n+1) − r(n+1),(n+1) . (2) is, conditionally expected utilities of the agents satisfy the 5) Representation of the MPNFI Game: The MPNFI following inequality: scenario can now be described by the structure Γ = (X, x∗ , (Ti )i∈N , (ui )i∈N , (qi )i∈N ). Ui (µ, χ|ti ) ≥ Ui (µ, χ, b ti |ti ), ∀ ti ∈ Ti , ∀ b ti ∈ Ti , ∀ i ∈ N Here, X refers to the set of all outcomes for all coalitions (5) S ∈ C that could be formed; x∗ is a default outcome that Since we have assumed that the mediator makes side- results when the agents are unable to come to an agreement payments to the agents, the expected utility for the mediator over the solution. In the context of the MPNFI problem, the from P implementing P the incentive compatible contract (µ, χ) is default outcome is a null transaction whose utility for all types − t∈T q(t) i∈N χi (t). So, if we want a state contingent of all agents is 0. Ti , ui , and qi are as defined earlier. This contract that is implementable, we should then look for one structure Γ of the game is assumed to be known to all agents. that is (a) incentive compatible and (b) gives the mediator non- In addition we assume that each agent knows his own type negative utility so that he does not lose from implementing the before the start of negotiations. We now need to develop a mechanism. solution to this cooperative game. The utility that the mediator gets from implement- III. S TATE C ONTINGENT C ONTRACTS ingP the state P contingent contract (µ, χ) is equal to − t∈T q(t) i∈N χi (t). So we want the following inequality We assume here that the state contingent contract will be to be satisfied. implemented by an external trustworthy mediator who can X X make side-payments to the agents. A state contingent contract q(t) χi (t) ≤ 0 (6) is now defined as follows. t∈T i∈N Definition 3.1: A state contingent contract is represented by Formally, we call such state contingent contracts as incen- a pair of functions (µ : T → ∆(X), χ : T → ℜ|N| ) where tive feasible contracts and we define these as follows. µ(x|t) represents the probability of choosing the outcome Definition 3.2: We say that a state contingent contract is x ∈ X when the agents’ types are t and χ(t) denotes the incentive feasible if and only if it is incentive compatible and net monetary side-payments that the mediator makes to agent yields a non-negative expected payoff to the mediator. That is, i when the agents’ types are t. it satisfies the inequalities 5 and 6. If a mediator proposes to implement such a state contingent In general, we know that there are a number of such contract (µ, χ), then the agents must evaluate how they would incentive feasible state contingent contracts. The mediator’s fare if they agreed to its implementation. This evaluation problem is to pick one such state contingent contract to im- is carried out by the agents at the interim stage and hence plement. It would therefore be useful if he could be guided by the correct measure of evaluation is conditionally expected the same criteria of efficiency and equity, but with appropriate utilities, conditioned on their private information. extensions, in evaluating the incentive feasible state contingent contract to implement. A. Conditionally Expected Utilities The conditionally expected utility of agent i if he were IV. T HE E FFICIENCY P RINCIPLE to agree to participate in the state contingent contract (µ, χ) We have seen that in cooperative games with incomplete proposed by a trustworthy mediator is given by: information, the appropriate object over which negotiations are carried out is the interim incentive compatible state con- X X tingent contract. And since conditionally expected utility is the Ui (µ, χ|ti ) = q(t−i )[χi (t) + µ(x|t)ui (x, t)] (3) appropriate measure of welfare evaluation of the agents, the t−i ∈T−i x∈X mediator would be well placed in selecting a state contingent Now, if agent i is of type ti but pretends to be of type tbi contract that maximizes the sum of conditionally expected when he reports his type to the mediator who is implementing utilities of the agents in the MPNFI game. We call such a the state contingent contract (µ, χ), then his expected utility contract an incentive-efficient contract. Formally, it is defined is given by: as follows: FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 4 Definition 4.1: A state contingent contract (µ, χ) is weakly by misrepresenting his type as b ti . From linear programming incentive-efficient if and only if it is incentive feasible and no theory, we know that this dual variable αi (b ti |ti ) will be non- other feasible state contingent contract yields higher expected zero when the corresponding constraint is tight. In the context utilities for all types of all agents. of the MPNFI problem, if the constraint corresponding to the So, we are interested in choosing a state contingent contract dual variable αi (b ti |ti ) is non-zero, then we can infer that agent (µ, χ) that maximizes the conditionally expected utilities of all i is tempted to misrepresent his type as b ti when his actual agents from among all contracts that obey inequalities (5) and type is ti because he gets the same expected utility. From an (6). It is easy to see that the incentive constraints specified by inspection of equation (9), we can conclude that the virtual (5) are convex. So, from convexity of the incentive constraints utility of agent i for an outcome x ∈ X when the type profile and linear programming theory, we can say that a feasible state is t magnifies the difference between the utilities of his true contingent contract (b b) is incentive efficient if and only µ, χ type ti and the type b ti that would tempt him to misrepresent. if there exists some vector λ = (λi (ti ))ti ∈Ti ,i∈N such that Now, we can rewrite the Lagrangean in equation (8) by λi (ti ) ≥ 0, ∀ ti ∈ Ti , ∀ i ∈ PN withP at least one strict inequal- using equations (3), (4) and (9) as follows: ity and (b b) maximizes i∈N ti ∈Ti λi (ti )Ui (µ, χ|ti) over µ, χ all feasible state contingent contracts (µ, χ) (See [5]). This is X X X a linear programming problem in (µ, χ). L(µ, χ, λ, α) = q(t) µ(x|t) vi (x, t, λ, α) t∈T x∈X i∈N  P P 1 X X X Maximize i∈N ti ∈Ti λi (ti )Ui (µ, χ|ti ) + q(t) χi (t)  αi (b ti |ti ) qi (ti ) s.t. t∈T i∈N bt ∈T  i i Ui (µ, χ|ti ) ≥ Ui (µ, χ, b ti |ti ), ∀ ti , b ti ∈ Ti , ∀ i ∈ N X X X q(t) χi (t) ≤ 0 − ti ) + λi (ti ) αi (ti |b (10) t∈T i∈N bti ∈Ti λi (ti ) ≥ 0, ∀ ti ∈ Ti , ∀ i ∈ N, So, the linear programming problem given by equation (7) (7) can be rewritten in terms of virtual utilities as follows: For this linear program we can construct a Lagrangean X X X function. We let α(bti |ti ) be the Lagrange multiplier for the Max q(t) µ(x|t) vi (x, t, λ, α) + constraint that says that type ti should not hope to gain t∈T x∈X i∈N   by reporting type bti to the state contingent contract being implemented by the mediator. With this we can write the 1 X X X q(t) χi (t)  αi (b ti |ti ) + Lagrangean of the linear programming problem as follows: qi (ti ) t∈T i∈N bti ∈Ti  X X X L(µ, χ, λ, α) = Ui (µ, χ|ti ) − ti ) + λi (ti ) αi (ti |b (11) i∈N ti ∈Ti bti∈Ti X + αi (b ti |ti )(Ui (µ, χ|ti ) − Ui (µ, χ, b ti |ti )) (8) s.t. bti ∈Ti X X q(t) χi (t) ≤ 0 (12) A. The Notion of Virtual Utility t∈T i∈N We now introduce an important notion that was first devel- oped by Myerson in [5]. This is the notion of virtual utility λi (ti ) ≥ 0, ∀ ti ∈ Ti , ∀ i ∈ N, with at least one strict inequality which is defined by a formula that takes incentive constraints (13) into account. For any outcome x ∈ X, type profile t ∈ T , and any given vectors λ and α we define the virtual utility vi (x, t, λ, α) for agent i as follows: B. Incentive Efficient Contracts From this reformulation of the optimization problem, it is  X easy to note that the mediator must pick a state contingent 1  contract that maximizes the sum of the virtual utilities of all vi (x, t, λ, α) = (λi (ti ) + αi (b ti |ti ))ui (x, t) qi (ti ) types of all agents. Now, the Lagrangean in equation (10) can bti∈Ti  be maximized only if the coefficients of χi (t) are constant X over all i and t. Such a constant can be set to 1 without loss − αi (ti |b ti ) ti )ui (x, (t−i , b (9) of generality. A standard Lagrangean analysis now allows us bti∈Ti to record the following proposition: Notice in equation (9) above that the Lagrange multiplier Proposition 4.2: A feasible state contingent contract (µ, χ) αi (b ti |ti ) is the dual variable corresponding to the incentive is incentive efficient if and only if there exist vectors λ and α constraint which says an agent i of type ti should not gain such that: FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 5 the state contingent contract that is to be implemented. This means that we need to formalize the blocking procedure and λi (ti ) ≥ 0 and αi (b ti |ti ) ≥ 0, ∀ ti ∈ Ti , ∀ b ti ∈ Ti , ∀ i ∈ N. the blocking state contingent contacts. (14) X X A. Blocking Coalitions and Blocking State Contingent Con- λi (ti ) + αi (b ti |ti ) − αi (ti |b ti ) = qi (ti ). (15) tracts b ti ∈Ti bti∈Ti The blocking procedure that we follow includes a blocking   mediator. We assume that the blocking mediator may invite αi (b ti |ti ) Ui (µ, χ|ti ) − Ui (µ, χ, b ti |ti ) = 0, ∀ ti , b ti ∈ Ti , ∀ i ∈ N. different coalitions according to some known randomized plan. (16) The plan includes a specification of the probability of any X coalition being chosen to implement a specific outcome that µ(x|t) > 0 =⇒ x ∈ argmaxy∈X vi (y, t, λ, α), ∀ t ∈ T , ∀ x ∈ X. is feasible for that coalition. The outcome should of course i∈N depend on the information available to the coalition since it (17) is unreasonable to allow blocking by a coalition to depend on Equation (14) comes from (a) our choice of the λ vector information of agents outside the coalition. that is chosen to maximize the expected utilities and (b) So, we assume that a blocking mediator can ask any random the α vector corresponds to Lagrangean multipliers or dual subset S about their types and, based on their responses, must variables corresponding to the incentive constraints, which by either invite all of S to join the blocking coalition to implement definition are non-negative. Equation (15) comes from setting a jointly feasible outcome xS ∈ XS or invite no coalition at the coefficients of χi (t) to unity. Equation (16) is nothing all. but the complementary slackness conditions corresponding to Such a blocking procedure may be characterized as follows: the incentive constraints of the original linear programming For any outcome xS ∈ XS and any type profile tS ∈ TS of the problem. Finally, equation (17) comes from the fact that the agents in S, we let νS (xS |tS ) represent the probability that mediator is maximizing the sum of the virtual utilities of all coalition S would be invited to block and implement the jointly the agents when he chooses the state contingent contract. feasible outcome xS ∈ XS if the agents in S report a type profile tS . Also, since we allowed the established mediator V. T HE E QUITY P RINCIPLE to make side-payments, we must also allow the blocking In the theory of the core for games with complete informa- mediator to make side-payments. We do this by allowing the tion, we are interested in establishing an allocation of surplus blocking mediator to specify the expected side-payment for that inhibits agents from deviating and joining a coalition that each possible type of each agent. So, for each type ti of each can offer an alternative allocation of surplus which blocks the agent i, we let ξi (ti ) be the blocking mediator’s expected side- former. That is, we compare alternative contracts (allocations payment to agent i if i would be willing to block and report of surplus) with an established one. In extending this idea to type ti to the blocking mediator. With this we can define a the incomplete information case, we should think in terms of blocking state contingent contract (ν, ξ) as follows: an established mediator who implements a state contingent Definition 5.1: A blocking state contingent contract by a contract that inhibits agents from deviating to cooperate with blocking mediator is a pair of vectors (ν, ξ) such that: another blocking mediator who has a blocking state contingent 1) ν = (νS )S⊆N , contract to offer. 2) νP S (xS |tP S ) ≥ 0, ∀Px ∈ XS , ∀ tS ∈ TS , In addition, in the complete information case, we allow 3) S⊆N tS ∈TS xS ∈XS νS (xS |tS ) ≤ 1, and agents to compare an alternative contract with an established 4) ξi (ti ) ∈ ℜ, ∀ ti ∈ Ti , ∀ i ∈ N . contract with the assumption that any agent who rejects the alternative will still get his allocation as specified by the In definition (5.1) above, the blocking state contingent established contract. For such an assumption to be workable, contract is a pair of vectors where the probability of any we then require that if any one agent rejects the alternative coalition S being picked to implement an outcome xS ∈ XS then all agents must continue to adhere to the established when its type profile is tS is always non-negative; and the contract. That is, there can be no blocking without unanimity probability of any such coalition being chosen by the blocking among all agents that are invited to block. In the incomplete mediator is never greater than unity. With this definition of a information case, we must recognize the fact that some agents blocking state contingent contract, we can now specify the may be willing to block when they are of a certain type blocking procedure. and not otherwise. So, an agent who agreed to block but 1) The Blocking Procedure: We can describe the blocking was returned to the original contract would have now learnt procedure with this series of steps: new information which he could possibly use profitably in • First, according to the probability distribution specified by the established contract. So, to maintain the assumption that ν = (νS )S⊆N , the blocking mediator chooses a random agents allocations as specified in the established contract are coalition S ⊆ N , a random profile of types tS ∈ TS and guaranteed, we will have to think about the blocking question a random outcome xS ∈ XS . being raised after the agents have sent in their type information • The mediator then asks each of the agents in S whether to the established mediator, but before they are committed to he is willing to block and, if so, what his type is. FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 6 • If the agents in S all agree to block and their type profiles such contracts next. coincide exactly with tS then the blocking mediator forms the coalition S and implements the jointly feasible B. Inhibitive State Contingent Contracts and Allocations outcome xS . Recall from our discussion on the efficiency criterion in • But if anyone of the agents does not agree to block or selecting a state contingent contract by an established medi- if the type profile does not match with tS then he asks ator, we were able to define an optimization problem whose all the agents in S to continue with the state contingent objective was to maximize the sum of virtual utilities of all contract from the established mediator. the agents. That is, in selecting a state contingent contract to • Now, when the blocking coalition does form, the planned implement, the mediator would have to assume that the agents monetary side-payments from the blocking mediator to were behaving in a manner to maximize their virtual utilities the agents could depend on the blocking coalition S, and not their actual utilities. So, in order to operationalize the the type profile tS , and the jointly feasible outcome xS equity criteria in the selection of a contract, we would have that they implement. We let this be described by any b S , tS ) such that: to carry out the comparisons between contracts offered by an function ξ(x established mediator and a blocking mediator in virtual utility P P P terms. b S∋{i} tS\{i} ∈TS\{i} xS ∈XS νS (xS |tS )ξi (xS , tS ) = Recall now our utility allocation vector ω = (ωi (t))i∈N,t∈T . ξi (ti ) Such a utility allocation vector is said to be inhibitive if and Now that we have formalized the notions of a blocking only if there does not exist any blocking state contingent state contingent contract and the blocking procedure, to opera- contract (ν, ψ) that is tenable against it. Since the Lagrangean tionalize the idea of equity in selecting an implementable state function (11) that we are maximizing is specified in terms of contingent contract we would need to compare the utilities that virtual utilities, we would need to make these comparisons such blocking state contingent contracts provide to agents in between the utility allocation vector ω and those from a a blocking vis-a-vis the utilities that they derive by continuing blocking state contingent contract in virtual utility terms. to remain in the state contingent contract that an established 1) A Virtual Utility Transformation of Inhibitive Alloca- mediator seeks to implement. We do this next. tions: We let Vi (ω, t, λ, α) be the transformation of agent i’s 2) Tenable Blocking State Contingent Contracts: For the utility allocations in ω into virtual utility in state t, according purpose of comparing the welfare that agents get by either to the equation (9) with parameters λ and α. We therefore going along with a blocking mediator or staying with an have the following relation: 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 1  X decided to join a blocking mediator. Let ω = (ωi (t))i∈N,t∈T Vi (ω, t, λ, α) = (λi (ti ) + ti |ti ))ωi (t) αi (b qi (ti ) be a vector of such utility allocations. Given this vector of bti ∈Ti   utility allocations, any blocking state contingent contract that 1 X a blocking mediator proposes must be such that it gives the − αi (ti |b ti ) (21) ti )ωi (t−i , b agents more than what they can get in the established plan. We qi (ti ) bti ∈Ti call such a state contingent contract a tenable state contingent With this relation in place, we can now redefine an inhibitive contract and define it formally below: Definition 5.2: A blocking state contingent contract (ν, ξ) is allocation vector in terms of its virtual utilities. That is, we tenable against an established state contingent contract (µ, χ) say that the utility allocation vector ω coming from a state which gives utility allocations ω = (ωi (t))t∈T ,i∈N if and only contingent contract (µ, χ) is inhibitive if and only if there if it satisfies the conditions in equations 18 to 20: exist parameters λ and α such that, for any coalition S, the Equation (18) states the fact that agents in a blocking sum of virtual utilities that the members of S can expect coalition must not lose when they deviate from the established with any outcome that is feasible for them, given all their mediator; equation (19) is simply the incentive compatibility information, is not more than the virtual-utility transformation condition that says that agents must find it beneficial to report of what they expect from the inhibitive utility allocation vector their true types to the blocking mediator when they have ω. We record this as a theorem below. deviated from the established mediator; finally equation (20) theorem 5.3: An allocation vector ω from a state contingent simply says that the blocking mediator must get a non-negative contract (µ, χ) offered for implementation by an established payoff from forming a blocking coalition and implementing mediator is inhibitive if and only if there exist vectors λ and the blocking contract. α such that: P P b b With this definition of a blocking state contingent contract, 1) λi (ti ) + bti∈Ti αi (ti |ti ) − bti ∈Ti αi (ti |ti ) = we can now sharpen our focus on isolating those contracts that qPi (ti ), ∀ ti ∈ Ti , ∀ i ∈ PN, are both efficient and equitable that an established mediator 2) q(tN\S ) i∈S Vi (ω, t, λ, α) ≥ PtN\S ∈TN\S P can hope to implement. Such contracts can be said to be tN\S ∈TN\S q(t N\S ) i∈S vi (xS , t, λ, α), ∀ S ⊆ inhibitive since they inhibit agents from cooperating with N, ∀ xS ∈ XS , ∀ tS ∈ TS , a blocking mediator and forming a blocking coalition that 3) λi (ti ) ≥ 0 and αi (b ti |ti ) ≥ 0, ∀ ti ∈ Ti , ∀ b ti ∈ Ti , ∀ i ∈ implements a blocking state contingent contract. We define N. FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 7 X X X ξi (ti ) + q(t−i ) νS (xS |tS )(ui (xS , t) − ωi (t)) ≥ 0, ∀ ti ∈ Ti , ∀ i ∈ N. (18) t−i ∈T−i S⊇{i} xs ∈XS X X X ξi (ti ) + q(t−i ) νS (xS |tS )(ui (xS , t) − ωi (t)) t−i ∈T−i S⊇{i} xs ∈XS X X X ≥ ξi (b ti ) + q(t−i ) νS (xS |tS−i , b ti )(ui (xS , t) − ωi (t)), ∀ ti ∈ Ti , ∀ b ti ∈ Ti , ∀ i ∈ N. (19) t−i ∈T−i S⊇{i} xs ∈XS X X − qi (ti )ξi (ti ) ≥ 0. (20) i∈N ti ∈Ti Proof: The proof for this theorem is along the lines of the 1) The Incentive Compatible Fine Core: proof in Theorem 1 in [1] and hence is omitted here. Definition 6.2: A utility allocation vector ω is said to be The theorem basically says that the utility allocation vector in the incentive compatible fine core if and only if ω is is inhibitive if and only if there exist parameters λ and α such inhibitive and achievable by some feasible state contingent that, for any coalition S, the sum of all virtual utilities that contract (µ, χ). the members of S can expect is not more than the sum of the In general, we have seen in the case of complete information virtual utility transformations of what they can expect from games that (a) the non-emptiness of the core is not guaranteed the ω given all their type information. and (b) to show non-emptiness of the core a balancedness With this understanding of inhibitive allocations, we are condition should be satisfied. Our main result is to show that ready to define the notion of the core as extended to coop- the incentive compatible fine core of the MPNFI game is non- erative games with incomplete information. empty. To show this we use the extension of the balancedness condition to incomplete information settings as introduced in VI. T HE I NTERIM I NCENTIVE C OMPATIBLE F INE C ORE OF [1]. THE MPNFI G AME 2) Balancedness and Balancing Weights: Recall from our preliminary discussion on the core for the Definition 6.3: We let a vector of weights θ = MPNFI game in Section I that we assumed the mediator can (θS,xS )xS ∈XS ,S⊆N be a balanced collection of weights if and make severance payments to agents who deviate from the only if the following conditions are satisfied: established mediator to a blocking mediator. This assumption 1) θPS,xS ≥ P0 ∀ xS ∈ XS , ∀ S ⊆ N at first glance may seem surprising because such severance 2) S⊇{i} xS ∈XS θS,xS = 1, ∀ i ∈ N . payments in the complete information case can never be 3) Balanced Games: beneficial. But in the incomplete information case they are Definition 6.4: We say that a game is balanced if for serve an essential technical purpose in deriving the proof of any balanced collection of weights θ = (θS,xS )xS ∈XS ,S⊆N , existence of the core [1]. there is some randomized strategy σ ∈ ∆(X) such that the following condition is satisfied. A. Balancedness and Balanced Games For now, we let ǫi (t) denote the severance payment that X X X agent i would get from the established mediator if he joined σ(x)ui (x, t) = θS,xS ui (xS , t), a blocking coalition after the type profile t was reported to x∈X S⊇{i} xS ∈XS the established mediator. We can now define the notion of an ∀ t ∈ T, ∀ i ∈ N. (22) utility allocation vector that is achievable by a state contingent Myerson [1] has shown that if the game is balanced then the contract (µ, χ). core is non-empty. We record this as a theorem below which Definition 6.1: A utility allocation vector ω = we use to show the non-emptiness of the incentive compatible (ωi (t))t∈T ,i∈N is achievable by a state contingent contract fine core of the MPNFI game. (µ, χ) if and only if (µ, χ) is feasible (as defined in Definition theorem 6.5: If a cooperative game with incomplete infor- 3.2) and there exists a promised vector of severance payments mation is balanced then the incentive compatible fine core is ǫ = (ǫi (t))t∈T ,i∈N such that: non-empty. 1) ǫi (t) ≥ 0, and P 2) ωi (t) = χi (t) + x∈X µ(x|t)ui (x, t) − ǫi (t), ∀ t ∈ T, ∀ i ∈ N . B. Non-Emptiness of the Incentive Compatible Fine Core of It is easy to see that ωi (t) is the residual stake that an the MPNFI Game agent i has in the established plan which he stands to lose if theorem 6.6: The incentive compatible fine core of the he deviates to blocking coalition in state t. With this, we are MPNFI game is non-empty. ready to define the interim incentive compatible fine core of Proof: To show that this theorem holds, we simply need to the MPNFI game and then examine its non-emptiness. show that the MPNFI game is balanced. That is, we need FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 8 to show that there is some randomization over the set of C(n+1) and C−(n+1) respectively. Now consider the RHS of outcomes (σ ∈ ∆(X)) such that the condition given by the balancedness condition given in equation 23: equation (23) is satisfied for any balanced collection of weights θ = (θS,xS )xS ∈XS ,S⊆N , for the class of MPNFI games. X X RHS = θS,xS ui (xS , t), ∀ t ∈ T, ∀ i ∈ N (26) S⊇{i} xS ∈XS X X X σ(x)ui (x, t) = θS,xS ui (xS , t), Equation (26) can be rewritten by taking the summation x∈X S⊇{i} xS ∈XS over all coalitions in Sj,xji ∈ C(n+1) and Sj,xji ∈ C−(n+1). ∀ t ∈ T, ∀ i ∈ N (23) X X To show this we first consider two special cases of the RHS = θS,xS ui (xS , t) + balanced collection of weights θ = (θS,xS )xS ∈XS ,S⊆N . S∈C(n+1) ,S⊇{i} xS ∈XS X X Case 1: Consider the collection of singleton subsets of N . θS,xS ui (xS , t), With such a collection of subsets of N , it is easy to see S∈C−(n+1) ,S⊇{i} xS ∈XS that the only outcome possible for each subset is the no-trade ∀ t ∈ T, ∀ i ∈ N (27) outcome and we know that the utility that an agent gets from From the structure of the MPNFI problem, it is clear that the no-trade outcome is zero. So, for any agent i ∈ N and the only outcome possible for any coalition S that does not for any singleton coalition S = {i}, the set of outcomes is a contain the buying agent is the no-trade outcome. The utility singleton kXS k = 1 and the utility of this outcome xS ∈ XS of the no-trade outcome is zero for all agents in a coalition S is ui (xS , t) = 0, ∀ t ∈ T . Such a collection of subsets can that does not contain the buying agent (n+1). This means that be a balanced collection if we associate the weights θ{i} = 1. in equation (27) above, we have ui (xS , t) = 0, ∀ i ∈ S, S ∈ Notice that we have dropped the subscript associated with the C−(n+1), ∀ t ∈ T . So, equation (27) can be written as outcome since the the set of outcomes is a singleton. With this set of balancing weights and utilities associated with the X X X outcomes, it is easy to see that the LHS of equation (23) is RHS = θS,xS ui (xS , t), ∀ t ∈ T, ∀ i ∈ N always zero. S∈C(n+1) S⊇{i} xS ∈XS Now, looking at the RHS of equation (23), it is clear that we (28) can always pick a randomization σ over the set of outcomes Now, from the condition of the balanced collection of sets, X such that the probability associated with the outcome which we have: gives no agent any of the surplus is always 1. Such an outcome can be trivially constructed by giving all the surplus to the θS,xS ≥ 0, ∀ S ∈ C(n+1) (29) mediator. So, the RHS of (23) is also zero and we have a X X randomization over the set of outcomes such that the condition θS,xS = 1 (30) in equation (23) is satisfied. S∈C(n+1) xS ∈XS Case 2: We now consider a balancing vector θ such that Equation (29) follows from equation (24). Equation (30) θN,b x = 1 for some x b ∈ X and θS,xS = 0 for all other follows from the fact that the C(n+1) contains all those sets (S, xS ) 6= (N, x b). which include the buying agent (n + 1) and sum of the This can be easily proved and hence for reasons of con- weights associated with these sets and their outcomes must sevring space is omitted. sum to unity given the fact that we are considering a balanced collection of weights. The General Case: We now consider the case of an arbitrarily This immediately implies the following: balanced collection, say C = {S1,x11 , S1,x12 , . . . , S1,x1k , S2,x21 , . . . , Sj,xj1 , . . . , Sl,x1m } X X where an element Sj,xj1 of the set C refers to the fact that θS,xS = 1, if i = (n + 1) (31) S∈C(n+1) ;S∋i xS ∈XS coalition Sj ⊆ N forms and implements the outcome xj1 ∈ Xj . Given the above balanced collection C, from the X X definition of balancedness, we have the following relations. θS,xS ≤ 1, if i 6= (n + 1) (32) S∈C(n+1) ;S∋i xS ∈XS θS,xS ≥ 0, ∀ xS ∈ XS , ∀ S ∈ C (24) 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 pos- X X sible outcomes (XS )S∈C(n+1) . Since any outcome that can θS,xS = 1, ∀ i ∈ N. (25) be achieved by a coalition S ⊂ N where S ∋ {(n + 1)} S∋{i};S∈C xS ∈XS can also be achieved by the grand coalition N , we can For this balanced collection, consider a partition of the set construct a randomization σ over the set of outcomes X such C into two such that one of them includes all the elements that the randomization simply assigns the same weight as Sj,xji where the buying agent (n + 1) ∈ S and another where the corresponding balancing weight to a particular outcome the buying agent is not included. We denote these sets as (S, xS ). FORMAL APPROACHES TO MULTI-AGENT SYSTEMS, 2009 9 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 non- empty incentive compatible fine core. VII. D ISCUSSION AND C ONCLUSION 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 com- patible 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. R EFERENCES [1] R.B. Myerson, “Virtual utility and the core for games with incomplete information”, Tech. Rep., Department of Economics, University of Chicago, Chicago, IL, 2005. [2] R. Wilson, “Information, efficiency and the core of an economy”, Econometrica, vol. 46, no. 4, pp. 807–816, July 1978. [3] R.B. Myerson and M.A. Satterthwaite, “Efficient mechanisms for bilateral trading”, Journal of Economic Theory, vol. 28, pp. 265–283, 1983. [4] R.B. Myerson, “Two-person bargaining problems with incomplete information”, Econometrica, vol. 52, pp. 461–487, 1984. [5] R.B. Myerson, “Cooperative games with incomplete information”, International Journal of Game Theory, vol. 13, pp. 69–96, 1984. [6] J.C Harsanyi, “Games with incomplete information played by Bayesian players”, Management Science, vol. 14, no. 7, pp. 486–502, March 1968. [7] A.M. Kwasnica, “Bayesian implementable efficient and core alloca- tions”, 2000, Pennsylvania State University. Working Paper. [8] F. Forges, E. Minelli, and R. Vohra, “Incentives and the core of an exchange economy: A survey”, Journal of Mathematical Economics, vol. 38, pp. 1–41, 2002. [9] D. Lee and O. Volij, “The core of economies with asymmetric infor- mation: An axiomatic approach”, Journal of Mathematical Economics, vol. 38, pp. 43–63, 2002. [10] T. Ichiishi and A. Yamazaki, “Interim core concepts for a Bayesian pure exchange economy”, Journal of Mathematical Economics, vol. 40, pp. 347–370, 2004. [11] G. de Clippel, “Values for cooperative games with incomplete informa- tion: An eloquent example”, Games and Economic Behavior, vol. 53, pp. 73–82, 2005.