=Paper=
{{Paper
|id=Vol-494/paper-24
|storemode=property
|title=On the Incentive Compatible Core of a Procurement Network Game with Incomplete Information
|pdfUrl=https://ceur-ws.org/Vol-494/famaspaper6.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/SubramanyamN09
}}
==On the Incentive Compatible Core of a Procurement Network Game with Incomplete Information==
https://ceur-ws.org/Vol-494/famaspaper6.pdf
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.