-In this paper we present a model of the multiple unit, single item procurement network formation problem in environments with incomplete information (MPNFI). For this we first develop the structure of the procurement network formation problem within Myerson's framework for cooperative games with incomplete information [1]. Using this framework we then investigate the non-emptiness of the incentive compatible core, an extension of the notion of the core for complete information settings based on Myerson's framework, and show that it is indeed non-empty for the class of MPNFI games.
T lowing: We have a buyer who is interested in buying
HE problem that we consider in this paper is the folmultiple 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.
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.
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.
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 vo (origin vertex) and vt (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 ES represent the set of edges owned by agents in S. We also designate FS as the flow in the network between the two special nodes vo and vt using only the edges ES that are owned by agents in S. For any flow FS , we denote the set of owners of the edges that facilitate the flow FS as ψ(FS ). We assume that if multiple units of the item are available to the buyer by using the flow FS , then it costs c(FS ) and the buyer is willing to compensate the edge owners with a value bFS where b is the value that the buyer attaches to a single unit of the item. The surplus from such a transaction is bFS − c(FS ). 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 ri0 ∈ ℜn++1 where ri0,j ∈ {0, 1}, ∀ j ∈ {1, 2, . . . , n} and 0 ri,(n+1) ∈ ℜ+. This implies that when agent i owns the edge j ∈ E then ri0j = 1 and is otherwise 0. Having assumed that there is a one-to-one correspondence between the edges and 0 0 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 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 Ti 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 ti ∈ Ti 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 = TN = ×i∈N Ti 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, ti) where the notation −i denotes N \{i}. Similarly, (t−i, bti) denotes the vector t where t−i = (t1, . . . , ti−1, ti+1, . . . , tn+1) and the ith component ti is changed to bti ∈ Ti. Similarly, T−i = ×j6=iTj , and for any coalition S, a non-empty subset of N , we let TS = ×i∈S Ti so that any tS ∈ TS denotes a combination of types (ti)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 6= ∅}.
Now, for each possible type ti ∈ Ti, we let qi(ti) denote the probability that agent i is of type ti and we assume that there is probability that the agent is of any one of the types in Ti is positive. That is qi(ti) > 0, ∀ ti ∈ Ti. We assume that the agents’ types are independent random variables and hence we can write the following: • q(tS ) = ×i∈S qi(ti), ∀ S ⊆ N, ∀ tS ∈ TS . • q(t−i) = ×j∈N−i qj (tj), ∀ i ∈ N, ∀ t ∈ T . • q(t) = ×j∈N qj(tj ), ∀ 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 ti ∈ Ti are declared by the agents i ∈ S. We call this set of market transactions as the set of possible outcomes XS (tS ), such that XS (tS ) = {(ri)i∈S |ri ∈ ℜn++1 and Pi∈S rij ≤ Pi∈S ri0j, ∀ j ∈ {1, 2, . . . , n, n + 1}}, where ri 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 XS and the set X as the sets that include the outcomes for all possible type declarations tS ∈ TS and all possible coalitions S ∈ C respectively. So, XS = StS∈TS XS (tS ) and X = SS∈C XS .
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 ui(x, t). For any agent i and outcome x, the final outcome vector ri reflects the edges that it currently owns and the money that it has after the transfers have been carried out. That is ri,i can be either 0 or 1 and ri,(n+1) ∈ ℜ.
So, the utility that an agent i = N \{(n + 1)} receives from
outcome x when his type is ti is given by:
ui(x, t) = ri,(n+1) + (ri,i − ri0,i)ti.
(
The payoff that the buying agent (n + 1) gets from an
outcome x, when xvt is the number of units of the item that
he gets, and his type is t(n+1), is given by:
0
u(n+1)(x, t) = xvt t(n+1) + r(n+1),(n+1) − r(n+1),(n+1). (
scenario can now be described by the structure Γ = (X, x∗, (Ti)i∈N , (ui)i∈N , (qi)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. Ti, ui, and qi 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.
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.
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: x∈X
X
q(t−i)[χi(t) + X μ(x|t)ui(x, t)] (
Now, if agent i is of type ti but pretends to be of type tbi
when he reports his type to the mediator who is implementing
the state contingent contract (μ, χ), then his expected utility
is given by:
(
X q(t−i)[χi(t−i, bti) + X μ(x|t−i, bti)ui(x, t)]
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:
Ui(μ, χ|ti) ≥ Ui(μ, χ, bti|ti), ∀ ti ∈ Ti, ∀ bti ∈ Ti, ∀ i ∈ N
(
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 − Pt∈T q(t) Pi∈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 − Pt∈T q(t) Pi∈N χi(t). So we want the following inequality to be satisfied.
X q(t) X χi(t) ≤ 0 t∈T
i∈N
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.
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 (
Ui(μ, χ|ti) ≥ X q(t) X χi(t) ≤ 0 t∈T
Ui(μ, χ, bti|ti), ∀ ti, bti ∈ Ti, ∀ i ∈ N λi(ti) ≥ 0, ∀ ti ∈ Ti, ∀ i ∈ N,
For this linear program we can construct a Lagrangean
function. We let α(bti|ti) be the Lagrange multiplier for the
constraint that says that type ti should not hope to gain
by reporting type tbi 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(μ, χ, λ, α) = X X Ui(μ, χ|ti)
+ X αi(bti|ti)(Ui(μ, χ|ti) − Ui(μ, χ, bti|ti))
(
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 vi(x, t, λ, α) for agent i as follows: vi(x, t, λ, α) =
(λi(ti) + X αi(bti|ti))ui(x, t) 1 qi(ti)
Notice in equation (
Now, we can rewrite the Lagrangean in equation (
L(μ, χ, λ, α) = + −
X q(t) X x∈X μ(x|t) X vi(x, t, λ, α)
i∈N 1 X q(t) X qi(ti) t∈T i∈N X αi(ti|bti) + λi(ti)
χi(t) X
bti∈Ti
αi(bti|ti)
(
So, the linear programming problem given by equation (
X q(t) X t∈T 1 qi(ti) μ(x|t) X vi(x, t, λ, α) + i∈N Xq(t) X χi(t) X αi(bti|ti) + t∈T i∈N bti∈Ti
− X αi(ti|bti) + λi(ti)
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 (
Proposition 4.2: A feasible state contingent contract (μ, χ)
is incentive efficient if and only if there exist vectors λ and α
such that:
(
The blocking procedure that we follow includes a blocking mediator. We assume that the blocking mediator may invite αi(bti|ti) Ui(μ, χ|ti) − Ui(μ, χ, bti|ti) = 0, ∀ ti, bti ∈ Ti, ∀ i ∈ Nd.ifferent coalitions according to some known randomized plan. (16) The plan includes a specification of the probability of any coalition being chosen to implement a specific outcome that μ(x|t) > 0 =⇒ x ∈ argmaxy∈X 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. tttbdvhhhaueeaerfittinatαchbiiotselieevofcsecnfiochccmtaooioresrprenerlentecnssmooprtnooeor-fnennstdmeaχpigrnoiaya(gnxttdiis)tvmlsoaetic.totzkohEeneuqLentuishaniastgectyirec.oanoennEtxnigpdvq(e1eeiuatc5aincto)teoinodcmnsonsumtcurlo(ttae1iirislpr6nielt)tfiissreep,oirssoswmnanhodnsoiriecdntthhdgtiiu(nbnbtaogyg)l saeauliltjbS.hoseoienr,ttiwlnSyveiafatebesaosasuuilbmtlloteehfetSohiruattttocyaojpombeilsneoactxnhkSdei n,b∈gbloamXcseekSddiniaoogtrnociortnhacvelaiiinttrieoraennsskotpoaocninomysaelprislat,einommdnoeunmasttt the incentive constraints of the original linear programming Such a blocking procedure may be characterized as follows: problem. Finally, equation (17) comes from the fact that the For any outcome xS ∈ XS and any type profile tS ∈ TS of the mediator is maximizing the sum of the virtual utilities of all agents in S, we let νS(xS |tS ) represent the probability that the agents when he chooses the state contingent contract. coalition S would be invited to block and implement the jointly feasible outcome xS ∈ XS if the agents in S report a type profile tS . Also, since we allowed the established mediator V. THE EQUITY PRINCIPLE 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 ti of each agent i, we let ξi(ti) be the blocking mediator’s expected sidepayment to agent i if i would be willing to block and report type ti 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:
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 1) ν = (νS )S⊆N , 2) νS(xS |tS ) ≥ 0, ∀ x ∈ XS , ∀ tS ∈ TS , 3) PS⊆N PtS∈TS PxS∈XS νS (xS |tS) ≤ 1, and 4) ξi(ti) ∈ ℜ, ∀ ti ∈ Ti, ∀ 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 xS ∈ XS when its type profile is tS 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 tS ∈ TS and a random outcome xS ∈ XS . • 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 tS then the blocking mediator forms the coalition S and implements the jointly feasible outcome xS . • But if anyone of the agents does not agree to block or if the type profile does not match with tS 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 tS , and the jointly feasible outcome xS that they implement. We let this be described by any function ξb(xS , tS ) such that: P
P
PxS∈XS νS (xS |tS)ξbi(xS , tS ) =
S∋{i} tS\{i}∈TS\{i} ξi(ti)
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.
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 (
tions: We let Vi(ω, t, λ, α) be the transformation of agent i’s
utility allocations in ω into virtual utility in state t, according
to the equation (
1 qi(ti)
X bti∈Ti
X αi(bti|ti))ωi(t) bti∈Ti
αi(ti|bti)ωi(t−i, bti) (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(ti) + Pti∈Ti αi(bti|ti) − Pbti∈Ti αi(ti|bti) = qi(ti), ∀ ti ∈ Tbi, ∀ i ∈ N , 2) PPtN\S∈TN\S q(tN\S ) Pi∈S Vi(ω, t, λ, α) ≥
tN\S∈TN\S q(tN\S ) Pi∈S vi(xS , t, λ, α), ∀ S ⊆
N, ∀ xS ∈ XS , ∀ tS ∈ TS , 3) λi(ti) ≥ 0 and αi(bti|ti) ≥ 0, ∀ ti ∈ Ti, ∀ tbi ∈ Ti, ∀ i ∈ N . q(t−i) X
X νS (xS |tS)(ui(xS , t) − ωi(t)) ≥ 0, ∀ ti ∈ Ti, ∀ i ∈ N. (18) (19) (20) ξi(ti) +
X νS (xS |tS−i, bti)(ui(xS , t) − ωi(t)), ∀ ti ∈ Ti, ∀ tbi ∈ Ti, ∀ i ∈ N. − X X qi(ti)ξi(ti) ≥ 0. 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].
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) + Px∈X μ(x|t)ui(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.
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].
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 ∀ xS ∈ XS , ∀ S ⊆ N 2) PS⊇{i} PxS∈XS θS,xS = 1, ∀ i ∈ N .
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.
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.
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 C(n+1) and C−(n+1) respectively. Now consider the RHS of the balancedness condition given in equation 23:
Equation (26) can be rewritten by taking the summation over all coalitions in Sj,xji ∈ C(n+1) and Sj,xji ∈ C−(n+1). θS,xS ui(xS , t), ∀ t ∈ T, ∀ i ∈ N (26) X
X S∈C(n+1) ,S⊇{i} xS∈XS
X X S∈C−(n+1) ,S⊇{i} xS∈XS ∀ t ∈ T, ∀ i ∈ N θS,xS ui(xS , t) + θS,xS ui(xS , t), 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. 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 kXS k = 1 and the utility of this outcome xS ∈ XS is ui(xS , 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 xb ∈ X and θS,xS = 0 for all other (S,bxS ) 6= (N, x).
b
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 = {S1,x11, S1,x12 , . . . , S1,x1k, S2,x21 , . . . , Sj,xj1 , . . . , Sl,x1m } where an element Sj,xj1 of the set C refers to the fact that coalition Sj ⊆ N forms and implements the outcome xj1 ∈ Xj . Given the above balanced collection C, from the definition of balancedness, we have the following relations. θS,xS ≥ 0, ∀ xS ∈ XS , ∀ S ∈ C
For this balanced collection, consider a partition of the set C into two such that one of them includes all the elements Sj,xji where the buying agent (n + 1) ∈ S and another where the buying agent is not included. We denote these sets as (27) (29) (30) (31) (32)
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 ui(xS , t) = 0, ∀ i ∈ S, S ∈ C−(n+1), ∀ t ∈ T . So, equation (27) can be written as RHS =
X
X
X S∈C(n+1) S⊇{i} xS∈XS (28)
Now, from the condition of the balanced collection of sets, we have:
θS,xS ui(xS , t), ∀ t ∈ T, ∀ i ∈ N θS,xS ≥ 0, ∀ S ∈ C(n+1)
X
X S∈C(n+1) xS∈XS θS,xS = 1
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:
X
X S∈C(n+1) ;S∋i xS∈XS S∈C(n+1) ;S∋i xS∈XS
X X θS,xS = 1, if i = (n + 1) θS,xS ≤ 1, if i 6= (n + 1)
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 (XS )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, xS ).
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.
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.