# On the Structure of Cooperative and Competitive Solutions for a Generalized Assignment Game

Authors: R. Pablo Arribillaga; Jordi Massó; Alejandro Neme
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We study cooperative and competitive solutions for a many-to-many generalization of Shapley and Shubik’s (1971) assignment game. We consider the Core, three other notions of group stability, and two alternative definitions of competitive equilibrium. We show that (i) each group stable set is closely related to the Core of certain games defined using a proper notion of blocking and (ii) each group stable set contains the set of payoff vectors associated with the two definitions of competitive equilibrium. We also show that all six solutions maintain a strictly nested structure. Moreover, each solution can be identified with a set of matrices of (discriminated) prices which indicate how gains from trade are distributed among buyers and sellers. In all cases such matrices arise as solutions of a system of linear inequalities. Hence, all six solutions have the same properties from a structural and computational point of view.


---

## Body

## 1. Introduction

Gale and Shapley [1] introduce ordinal two-sided matching models to study assignment problems between two disjoint sets of agents. In the marriage model, where matchings are one-to-one, each agent has to be matched to at most an agent on the opposite set. It is assumed that each agent has strict ordinal preferences over the set of agents that he does not belong to plus the prospect of remaining unmatched. These models are ordinal and money does not play any role; in particular, money cannot be used to compensate an agent in the case he has to be matched to an agent at the bottom of the agent’s preference list. Ordinal models have been enormously useful and extensively used in economics to study situations where the assignment problem has only one issue: who is matched to whom.1 In these models and given a preference profile (a preference for each agent), a matching is stable if it is individually rational (no agent is assigned to a partner that is worse than to remain unmatched) and pairwise stable (there is no pair of agents that are not matched to each other but they would prefer to be so rather than to be matched to the partner proposed by the matching, or to one of them if the agent is a college). Gale and Shapley [1] show that, for every preference profile, the set of stable matchings is nonempty and it coincides with the Core of the associated cooperative game with nontransferable utility (and hence, coalitions with two or more agents from the same set of agents do not have additional blocking power).2However, there are many assignment problems (solved by markets) where money plays a significant role, for instance, through salaries or prices. Hence, in those cases agents’ preferences may be cardinal. But then, to describe a solution of the problem (in particular, to unsure its stability) it is not sufficient to specify the matching between the two sides of the market because it is also required to describe how each pair of assigned agents shares the gains of being matched to each other. Shapley and Shubik [2] propose the assignment game as an appropriated tool to study one-to-one matching problems with money (i.e., with transferable utility). The prototypical and most simple example of an assignment game is a market with sellers and buyers in which each seller owns one indivisible unit of a good and each buyer wants to buy at most one unit of one good. This setting differs from the marriage model of Gale and Shapley [1] by the fact that there exists money used as a means of exchange. In addition money is also used to determine buyers’ valuations (or maximal willingness to pay) of each unit of the available goods and sellers’ reservation prices (or minimal amounts at which they are willing to sell the unit of the good they own). Shapley and Shubik [2] show that the assignment game has, among others, the following properties. (i) There exists at least one competitive equilibrium price vector, with a price for each of the goods and an assignment between buyers and sellers such that, at those prices, each buyer is assigned to the seller that owns the good (namely, the buyer buys the unit of the good that the seller has and pays its price) that gives him the maximal net valuation (the difference between his valuation and the price of the good). (ii) The set of competitive equilibrium payoffs coincides with the Core of the cooperative game with transferable utility induced by the assignment game. (iii) The Core coincides with the set of individually rational and pairwise stable payoff vectors. In this model, a solution is not only an assignment (who buys to whom, or equivalently, who sells to whom) but it is also a description of how each assigned pair of agents splits the gains generated by their trade.3Sotomayor [3–8], Camiña [9], Milgrom [10], Fagebaume et al. [11], Jaume et al. [12], and Massó and Neme [13] are some of the papers that extend the one-to-one Shapley and Shubik [2] assignment game by allowing that buyers can buy different goods and/or that sellers can own and sell units of different goods to different buyers. Most of those papers show that some of the properties of the one-to-one model also hold for the generalized versions. In addition, most of the previously cited papers propose and study cooperative solution concepts that are natural in the many-to-one or many-to-many contexts. The Core is the most studied solution concept. Given a payoff vector and an associated assignment (the payoffs are obtained after distributing among players the net gains generated from each trade specified by the assignment) a coalition Core-blocks the payoff vector if all its agents, by breaking all their trades with all agents outside the coalition, may improve upon their payoffs by reorganizing new trades, performed only among themselves. The Core is the set of payoff vectors that are not Core-blocked by any coalition.However, in this setting there are other alternative notions of group stability. They differ on the type of transactions that agents in a blocking coalition are allowed to perform with agents outside. That is, the notions depend on how sale contracts have been specified and, hence, on how they can be broken. The Core concept assumes that agents in a blocking coalition can only trade among themselves, without being able to keep any trade with agents outside the blocking coalition; thus, when a coalition of agents Core-blocks a proposed payoff vector, they have to break all contracts with agents outside the coalition. In the group stability notion defined in Massó and Neme [13] it is assumed that sale contracts are unit-by-unit. A trade of a unit of a good between a buyer and a seller is performed independently of the other traded units of the same good as well as of the traded units of the other goods. An agent of a blocking coalition can reduce (but not increase) the trade, with members outside the coalition, of a given good in the number of units that he wishes, but without being forced for this reason to reduce neither the number of traded units of the same good nor the number of units of the other goods. In this paper we consider the other two alternative notions of group stability. They are more appropriated for those cases where sale contracts are written good-by-good or globally. In the good-by-good case, the sale contract between a buyer and a seller includes all traded units of only one good, and it is independent of their trade on the other goods. Thus, when an agent belongs to a blocking coalition and the other does not, either they keep the trade of all units of the good specified in the sale contract or they completely eliminate the trade of this good. In the global case, the sale contract between a buyer and a seller includes all trades on all goods and, thus, when an agent belongs to a blocking coalition and the other does not, either they keep all trades or they have to be eliminated altogether.Jaume et al. [12], when defining competitive equilibrium for this generalized assignment game, consider that given a price vector (a price for each of the goods) agents demand and supply those units of the goods that maximize their total payoff without taking into account the aggregate feasibility constraints. The supply or demand of each agent only depends on the price vector and hisindividual feasibility constraints. The fact that, at a given price vector, all supply and demand plans are mutually compatible is an equilibrium question, rather than a restriction on the individual maximization problems. On the other hand, the competitive equilibrium notion studied by Sotomayor [6–8] in related models assumes that individual demands and supplies have to be feasible for the market. Namely, when obtaining their optimal demands and supplies, it is assumed that agents cannot demand or supply more than the available amounts present in the market.The most important results of this paper are the following. First, we show that each one of the sets of payoffs corresponding to the three group stability notions can be directly identified with the union of Cores of particular cooperative games with transferable utility, where the blocking power of coalitions is inherited from the corresponding nature of the sale contracts between buyers and sellers (unit-by-unit, good-by-good, or global). Second and using this identification, we show that the three notions of group stability are supported by a Cartesian product structure between a given set ofmatrices of pricesand the set of optimal assignments; all payoff vectors in any of the sets corresponding to the three group stability notions are fully identified by a set of matrices of prices; all payoff vectors in any of the sets corresponding to the three group stability notions are completely identified with the solutions of a system of bounded linear inequalities. Third, we show that each of the two competitive equilibrium notions can be directly identified with the union of Cores of certain cooperative games with transferable utility. This result allows us to obtain for the two competitive equilibrium concepts the same conclusions that we have already obtained for the three group stability notions. Hence, cooperative as well as competitive solutions have all the same properties from a structural and computational point of view. Furthermore, all studied solutions maintain a strictly nested relationship.In short, the paper contributes to the study of markets with indivisible goods. In particular, it shows that the two competitive equilibrium notions are immune with respect to the secession of subgroups of agents. It also identifies some structural properties that hold for competitive equilibrium solutions as well as for different notions of group stability.The paper is organized as follows. In the next section we present the model introduced in Jaume et al. [12]. In Section 3 we define three notions of group stability and study the equivalence of each of these notions with the Cores of their corresponding cooperative games with transferable utility. We show that the three group stability sets of payoffs have a Cartesian product structure and that they can be identified as the solutions of a system of linear inequalities. In Section 4 we perform a similar analysis for the two notions of competitive equilibria. In Section 5 we compare the three notions of group stability with the two notions of competitive equilibria. The Appendices include the proofs of three results omitted in the main text.


## 2. Preliminaries

A generalized assignment game (amarket) consists of three finite and disjoint sets: the set ℬ of B
buyers, the set 𝒢 of G
goods, and the set 𝒮 of S
sellers. We denote a generic buyer by i, a generic good by j, and a generic seller by k. Buyers have a constant marginal valuation of each good. Let v
i
j
≥
0 be the monetary valuation that buyer i assigns to each unit of good j; namely, v
i
j is the maximum price that buyer i is willing to pay for each unit of good j. Denote by V
=
(
v
i
j
)
(
i
,
j
)
∈
ℬ
×
𝒢 thematrix of valuations. We assume that buyer i
∈
ℬ can buy at most d
i
∈
ℤ
+
∖
{
0
} units in total, where ℤ
+ is the set of nonnegative integers. The strictly positive integer d
i should be interpreted as a capacity constraint due to limits on i's ability for storage, transport, and so forth. Denote by d
=
(
d
i
)
i
∈
ℬ thevector of maximal demands. Each seller k
∈
𝒮 has q
j
k
∈
ℤ
+ indivisible units of each good j
∈
𝒢. Denote by Q
=
(
q
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮 thematrix of capacities. We assume that there is a strict amount of each good; namely,
(1)
for
each
j
∈
𝒢
there
exists
k
∈
𝒮
such
that
q
j
k
>
0
.
Let r
j
k
≥
0 be the monetary valuation that seller k assigns to each unit of good j; that is, r
j
k is the reservation (or minimum) price that seller k is willing to accept for each unit of good j. Denote by R
=
(
r
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮 thematrix of reservation prices.Amarket
M is a 7-tuple (
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) satisfying condition (1). Shapley and Shubik’s [2] (one-to-one) assignment game is a special case of a market where each buyer can buy at most one unit, there is only one unit of each good, and each seller only owns one unit of one of the goods; that is, d
i
=
1, for all i
∈
ℬ, G
=
S, and, for all (
j
,
k
)
∈
𝒢
×
𝒮, q
j
k
=
1 if j
=
k and q
j
k
=
0 if j
≠
k.LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market. Anassignment for market M is a three-dimensional integer matrix (i.e., a 3rd-order tensor) A
=
(
A
i
j
k
)
(
i
,
j
,
k
)
∈
ℬ
×
𝒢
×
𝒮
∈
ℤ
+
B
×
G
×
S describing a collection of deliveries of units of the goods from sellers to buyers. Each A
i
j
k should be interpreted as “buyer i receives A
i
j
k units of good j from seller k.” We often omit the sets to which the subscripts belong to and write, for instance, ∑
i
j
k
‍
A
i
j
k and ∑
i
‍
A
i
j
k instead of ∑
(
i
,
j
,
k
)
∈
ℬ
×
𝒢
×
𝒮
‍
A
i
j
k and ∑
i
∈
ℬ
‍
A
i
j
k, respectively.The assignmentA isfeasible for market M if each buyer i buys at most d
i units and each seller k sells at most q
j
k units of each good j. We are only interested in feasible assignments, namely, in the set
(2)
{
A
∈
ℤ
+
B
×
G
×
S
∣
∑
j
k
‍
A
i
j
k
≤
d
i
∀
i
∈
ℬ
,
∑
i
‍
A
i
j
k
≤
q
j
k
∀
(
j
,
k
)
∈
𝒢
×
𝒮
∑
j
k
‍
}
.
For further reference, we denote this set of feasible assignments for market M by ℱ
0
(
M
) (or simply by ℱ
0).Thetotal gain from trade of market
M
at assignment
A is
(3)
T
M
(
A
)
=
∑
i
j
k
‍
(
v
i
j
-
r
j
k
)
·
A
i
j
k
.Definition 1.
A feasible assignmentA isoptimal for market M if, for any feasible assignment A
′, T
M
(
A
)
≥
T
M
(
A
′
).Example2 below contains an instance of a market with a unique optimal assignment.Example 2.
Let(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market where ℬ
=
{
b
1
,
b
2
}, 𝒢
=
{
g
1
,
g
2
,
g
3
}, 𝒮
=
{
s
1
},  V
=
(
6
4
4
7
3
5
),  d
=
(
10,10
), Q
=
(
10,5
,
1
), and R
=
(
5,2
,
1
). For any A
′
∈
ℱ
0,
(4)
T
M
(
A
′
)
=
(
6
-
5
)
·
A
111
′
+
(
4
-
2
)
·
A
121
′
+
(
4
-
1
)
·
A
131
′
+
(
7
-
5
)
·
A
211
′
+
(
3
-
2
)
·
A
221
′
+
(
5
-
1
)
·
A
231
′
=
A
111
′
+
2
·
A
121
′
+
3
·
A
131
′
+
2
·
A
211
′
+
A
221
′
+
4
·
A
231
′
.
It is easy to check that A
=
(
1
5
0
9
0
1
) is the unique optimal assignment for M and T
M
(
A
)
=
1
+
2
·
5
+
2
·
9
+
4
=
33.Letℱ
(
M
) (or simply ℱ) be the set of all optimal assignments for market M. The set ℱ is always nonempty.4 Denote by T
M the total gain from trade of market M at any optimal assignment.Fix a marketM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
). Denote by G
> the set of goods that are exchanged at some optimal assignment. Namely,
(5)
G
>
=
{
j
∈
𝒢
∣
there
exists
A
∈
ℱ
such
that
A
i
j
k
>
0
for
some
(
i
,
k
)
∈
ℬ
×
𝒮
A
i
j
k
}
.
Moreover, for each buyer i
∈
ℬ and each seller k
∈
𝒮, define
(6)
G
i
k
>
=
{
j
∈
𝒢
∣
there
exists
A
∈
ℱ
such
that
A
i
j
k
>
0
}
,
as the set of goods that i buys to k at some optimal assignment.


## 3. Cooperative Solutions: Core and Group Stability

Massó and Neme [13] define, for any market M, two cooperative solutions: the Core and a group stable set (they call it setwise stable). As described in the Introduction the two concepts are based on the idea that a coalition will object to a proposed payoff vector if all agents in the coalition can improve upon their payoffs, but differ in that, when objecting, the Core requires that all members of the blocking coalition break their exchanges with agents outside the coalition while group stability (which we will call here type 1-group stability) allows that the exchanges of an agent in the blocking coalition with agents outside the coalition are maintained or reduced (since sale contracts are unit-by-unit). Here we propose two alternative notions of group stability. Type 2-group stability makes sense when sale contracts are performed good-by-good and therefore an agent in the blocking coalition can maintain with an agent outside the coalition the exchange of all units of the good or else delete them all. Type 3-group stability makes sense when between a buyer and a seller there exists only a sale contract and therefore an agent in the blocking coalition can maintain with an agent outside the coalition all exchanges or delete them all.LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market and let C
⊂
ℬ
∪
𝒮 be a coalition. Denote the sets of buyers and sellers in C by ℬ
C
=
C
∩
ℬ and 𝒮
C
=
C
∩
𝒮, respectively.Definition 3.
LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market and letC
⊂
ℬ
∪
𝒮 be a coalition. A feasible assignment A
^
∈
ℱ
0 is1-group compatible with
C if there exists an optimal assignment A
∈
ℱ such that,(i)
for alli
∈
ℬ
C, A
^
i
j
k
>
0 implies that either k
∈
𝒮
C or else A
^
i
j
k
≤
A
i
j
k,
(ii)
for allk
∈
𝒮
C, A
^
i
j
k
>
0 implies that either i
∈
ℬ
C or else A
^
i
j
k
≤
A
i
j
k.5We want to emphasize that the above definition considers as compatible any reallocation of goods between the agents within the coalition and only decreases (with respect of some optimal assignment) the trade, of any good, between an agent in the coalition with another agent outside. The next two definitions of group compatibility limit the reallocations of goods between members of the blocking coalition and outsiders depending on whether sale contracts are good-by-good or global.Definition 4.
LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market and let C
⊂
ℬ
∪
𝒮 be a coalition. A feasible assignment A
^
∈
ℱ
0 is 2-group compatible with
C if there exists an optimal assignment A
∈
ℱ such that,(i)
for alli
∈
ℬ
C, A
^
i
j
k
>
0 implies that either k
∈
𝒮
C or else A
^
i
j
k
=
A
i
j
k,
(ii)
for allk
∈
𝒮
C, A
^
i
j
k
>
0 implies that either i
∈
ℬ
C or else A
^
i
j
k
=
A
i
j
k.Definition 5.
LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market and C
⊂
ℬ
∪
𝒮 be a coalition. A feasible assignment A
^
∈
ℱ
0 is 3-group compatible with
C if there exists an optimal assignment A
∈
ℱ such that,(i)
for alli
∈
ℬ
C, A
^
i
j
k
>
0 implies that either k
∈
𝒮
C or else A
^
i
j
′
k
=
A
i
j
′
k for all j
′
∈
𝒢,
(ii)
for allk
∈
𝒮
C, A
^
i
j
k
>
0 implies that either i
∈
ℬ
C or else A
^
i
j
′
k
=
A
i
j
′
k for all j
′
∈
𝒢.Let M
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market, C
⊂
ℬ
∪
𝒮 a coalition, and t
∈
{
1,2
,
3
}. Denote by ℱ
t
(
C
) the set of all feasible assignments that aret-group compatible with C.Example
2 (continued). To see the differences among the three types of group compatibility, consider the coalition C
=
{
b
1
,
s
1
} in market M of Example 2. Then,
(7)
ℱ
1
(
C
)
=
{
A
^
∈
ℱ
0
∣
0
≤
A
^
211
≤
9
,
A
^
221
=
0
,
0
≤
A
^
231
≤
1
}
,
ℱ
2
(
C
)
=
{
A
^
∈
ℱ
0
∣
A
^
211
∈
{
0,9
}
,
A
^
221
=
0
,
A
^
231
∈
{
0,1
}
}
,
ℱ
3
(
C
)
=
{
A
^
∈
ℱ
0
∣
(
A
^
211
,
A
^
221
,
A
^
231
)
=
(
9,0
,
1
)
or
(
A
^
211
,
A
^
221
,
A
^
231
)
=
(
0,0
,
0
)
}
.
Thus, ℱ
3
(
C
)
⊂
ℱ
2
(
C
)
⊂
ℱ
1
(
C
) and
(8)
(
5
5
0
5
0
1
)
∈
ℱ
1
(
C
)
∖
ℱ
2
(
C
)
,
(
1
5
1
9
0
0
)
∈
ℱ
2
(
C
)
∖
ℱ
3
(
C
)
,
(
4
5
1
0
0
0
)
∈
ℱ
3
(
C
)
.LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market. A 3rd-order tensor Γ
=
(
Γ
i
j
k
)
(
i
,
j
,
k
)
∈
ℬ
×
𝒢
×
𝒮
∈
ℝ
+
B
×
G
×
S is adistribution matrixfor market M if, for all (
i
,
j
,
k
)
∈
ℬ
×
𝒢
×
𝒮 such that v
i
j
≥
r
j
k and j
∈
G
i
k
>, v
i
j
≥
Γ
i
j
k
≥
r
j
k holds. Let Γ be a distribution matrix for market M and assume that v
i
j
≥
r
j
k for some (
i
,
j
,
k
)
∈
ℬ
×
𝒢
×
𝒮 and j
∈
G
i
k
>. Then, Γ
i
j
k describes a possible way of how buyer i and seller k can split the gain v
i
j
-
r
j
k
≥
0 they could obtain by exchanging one unit of good j: buyer i receives v
i
j
-
Γ
i
j
k and seller k receives Γ
i
j
k
-
r
j
k. If j
∉
G
i
k
>, the value Γ
i
j
k will be irrelevant since i and k will not exchange any unit of good j in any optimal assignment. Observe that distribution matrices are not necessarily anonymous because a buyer may obtain different gains per unit of good j if he buys the same good from different sellers, and vice versa. Denote by 𝒟
(
M
) (or simply by 𝒟) the set of all distribution matrices for market M.Definition 6.
A vector(
u
i
,
w
k
)
(
i
,
k
)
∈
ℬ
×
𝒮
∈
ℝ
B
×
S is afeasible payofffor market M if
(9)
∑
i
∈
ℬ
‍
u
i
+
∑
k
∈
𝒮
‍
w
k
=
T
M
.Denote by𝒳
(
M
) (or simply by 𝒳) the set of all feasible payoffs for market M.LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market and C
⊂
ℬ
∪
𝒮 a coalition. For every Γ
∈
𝒟 and A
^
∈
ℱ
0, define thegain for
C
at
A
^
according to
Γ by the expression6
(10)
ϕ
M
(
C
,
A
^
,
Γ
)
≡
∑
(
i
,
j
,
k
)
∈
ℬ
C
×
𝒢
×
𝒮
C
‍
(
v
i
j
-
r
j
k
)
·
A
^
i
j
k
+
∑
(
i
,
j
,
k
)
∈
ℬ
C
×
𝒢
×
(
𝒮
C
)
c
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
^
i
j
k
+
∑
(
i
,
j
,
k
)
∈
(
ℬ
C
)
c
×
𝒢
×
𝒮
C
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
^
i
j
k
.
Observe that ϕ
M
(
C
,
A
^
,
Γ
) is independent of t
∈
{
1,2
,
3
}.We are now ready to define the blocking notions according to the assignments that the coalition can use.Definition 7.
LetM be a market and t
∈
{
1,2
,
3
}. A payoff (
u
,
w
)
∈
𝒳
(
M
)
is not t-group blockedif there exists a distribution matrix Γ
=
(
Γ
i
j
k
)
(
i
,
j
,
k
)
∈
ℬ
×
𝒢
×
𝒮
∈
𝒟
(
M
) such that, for all coalition C
⊂
ℬ
∪
𝒮 and A
^
∈
ℱ
t
(
C
),
(11)
∑
i
∈
ℬ
C
‍
u
i
+
∑
k
∈
𝒮
C
‍
w
k
≥
ϕ
M
(
C
,
A
^
,
Γ
)
.It is useful to point out that the definition depends ont
∈
{
1,2
,
3
} since the gain for C depends on the set ℱ
t
(
C
) of feasible assignments (i.e.,t-group compatible) with C. Finally, we define the three notions of group stability.Definition 8.
LetM be a market and t
∈
{
1,2
,
3
}. A payoff (
u
,
w
)
∈
𝒳
(
M
) ist-group stable for
M if it is nott-group blocked.7Denote by𝒢
𝒮
t
(
M
) (or simply 𝒢
𝒮
t) the set of payoffs that aret-group stable for M. Since ℱ
3
(
C
)
⊂
ℱ
2
(
C
)
⊂
ℱ
1
(
C
) for all C
⊂
ℬ
∪
𝒮, it follows that
(12)
𝒢
𝒮
1
⊂
𝒢
𝒮
2
⊂
𝒢
𝒮
3
.
Moreover, there are markets for which these inclusions are strict and, hence,8
(13)
𝒢
𝒮
1
⫋
𝒢
𝒮
2
⫋
𝒢
𝒮
3
.By the above remark and the fact that𝒢
𝒮
1
≠
∅ (see Massó and Neme [13]) allt-group stable sets are nonempty. For further reference, we present this result as Proposition 9 below.Proposition 9.
For any marketM and t
∈
{
1,2
,
3
}, 𝒢
𝒮
t
(
M
)
≠
∅.Massó and Neme [13] define the Core of market M as the Core of the cooperative game with transferable utility induced by M. They show first that the 1-group stable set is a strict subset of the Core and strictly contains the set of competitive equilibrium payoffs. Second, the 1-group stable set converges in the second replica to the set of competitive equilibrium payoffs while the Core does not converge to it in a finite number of replicas. Hence, one may infer from the two results that the two cooperative notions are essentially different. We will see here that the difference does not refer so much to the solution concept but rather to how the game for which the Core is obtained is defined. Massó and Neme [13] define the cooperative game by assuming that the assignment A
^ is feasible for a coalition C
⊂
ℬ
∪
𝒮 if and only if members of C only exchange goods among themselves.Definition 10.
LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market and let C
⊂
ℬ
∪
𝒮 be a coalition. A feasible assignment A
^
∈
ℱ
0 isCore-compatible with
C if,(i)
for alli
∈
ℬ
C, A
^
i
j
k
>
0 implies k
∈
𝒮
C,
(ii)
for allk
∈
𝒮
C, A
^
i
j
k
>
0 implies i
∈
ℬ
C.Given C
⊂
ℬ
∪
𝒮, the set of all Core-compatible assignments with C will be denoted by ℱ
C
o
(
C
). Using this notion, we define the cooperative game with transferable utility (
ℬ
∪
𝒮
,
v
) where, for every C
⊂
ℬ
∪
𝒮,9
(14)
v
(
C
)
=
max
⁡
A
^
∈
ℱ
C
o
(
C
)
ϕ
M
(
C
,
A
^
,
Γ
)
.
Then, theCore of market
M, denoted by 𝒞
(
M
), is the Core of the game (
ℬ
∪
𝒮
,
v
); namely,
(15)
𝒞
(
M
)
=
{
(
u
,
w
)
∈
𝒳
(
M
)
∣
v
(
C
)
≤
∑
i
∈
ℬ
C
‍
u
i
+
∑
k
∈
𝒮
C
‍
w
k
∀
C
⊂
ℬ
∪
𝒮
∑
k
∈
𝒮
C
‍
}
.Now, if we accept the notions of group stability as reasonable solutions, we can define new cooperative games with transferable utility where compatible assignments with a coalitionC admit that its members may have certain exchanges with agents outside C. For this purpose it is necessary to consider a distribution matrix Γ
∈
𝒟 indicating how the gains from trade are distributed with members outside coalition C. We now present these notions formally.Definition 11.
LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market, Γ
∈
𝒟, and t
∈
{
1,2
,
3
}. Thecooperative game with transferable utility associated with
t
and
Γ, denoted by (
ℬ
∪
𝒮
,
v
t
Γ
), is defined as follows: for every C
⊂
ℬ
∪
𝒮,
(16)
v
t
Γ
(
C
)
=
max
⁡
A
^
∈
ℱ
t
(
C
)
ϕ
M
(
C
,
A
^
,
Γ
)
.IfΓ
∈
𝒟 is given and we allow C to choose among the set of assignments in ℱ
t
(
C
), the game (
ℬ
∪
𝒮
,
v
t
Γ
) can be interpreted in a similar way as we interpreted the game defined in (20), where each coalition maximizes the total payoff since ϕ
M
(
C
,
A
^
,
Γ
) is the total gain received by members of C under A
^. We will denote by 𝒞
t
Γ
(
M
) (or simply by 𝒞
t
Γ) the Core of the game (
ℬ
∪
𝒮
,
v
t
Γ
).Remark 12.
Note that, for allΓ
∈
𝒟 and t
∈
{
1,2
,
3
},
(17)
T
M
=
v
(
ℬ
∪
𝒮
)
=
v
1
Γ
(
ℬ
∪
𝒮
)
=
v
2
Γ
(
ℬ
∪
𝒮
)
=
v
3
Γ
(
ℬ
∪
𝒮
)
.
Hence, (
u
,
w
) is a feasible payoff (i.e., (
u
,
w
)
∈
𝒳) if and only if ∑
i
∈
ℬ
‍
u
i
+
∑
k
∈
𝒮
‍
w
k
=
v
t
Γ
(
ℬ
∪
𝒮
).
Using the games(
ℬ
∪
𝒮
,
v
t
Γ
) associated with M we can now see that the notions of Core and group stability are extremely related. Indeed, the following result holds.Theorem 13.
LetM be a market. Then, for all t
∈
{
1,2
,
3
},
(18)
𝒢
𝒮
t
(
M
)
=
⋃
Γ
∈
𝒟
(
M
)
‍
𝒞
t
Γ
(
M
)
.Proof.
FixM and t. We first show that, for all Γ
∈
𝒟, 𝒞
t
Γ
⊂
𝒢
𝒮
t. Let (
u
,
w
)
∈
𝒞
t
Γ. By Remark 12, (
u
,
w
) is a feasible payoff. Moreover, for all C
⊂
ℬ
∪
𝒮, ∑
i
∈
ℬ
C
‍
u
i
+
∑
k
∈
𝒮
C
‍
w
k
≥
v
t
Γ
(
C
). Hence, for all C and all A
^
∈
ℱ
t
(
C
), ∑
i
∈
ℬ
C
‍
u
i
+
∑
k
∈
𝒮
C
‍
w
k
≥
ϕ
M
(
C
,
A
^
,
Γ
). Thus, (
u
,
w
)
∈
𝒢
𝒮
t. Namely, ⋃
Γ
∈
𝒟
(
M
)
𝒞
t
Γ
⊂
𝒢
𝒮
t.
Take now a payoff(
u
,
w
)
∈
𝒢
𝒮
t. Since (
u
,
w
) is a feasible payoff, by Remark 12, ∑
i
∈
ℬ
‍
u
i
+
∑
k
∈
𝒮
‍
w
k
=
v
t
Γ
(
ℬ
∪
𝒮
), for all Γ
∈
𝒟. Moreover, since (
u
,
w
) is not 𝒢
𝒮
t-blocked, there exists Γ
∈
𝒟 such that, for all C
⊂
ℬ
∪
𝒮 and all A
^
∈
ℱ
t
(
C
),
(19)
∑
i
∈
ℬ
𝒞
‍
u
i
+
∑
k
∈
𝒮
𝒞
‍
w
k
≥
ϕ
M
(
C
,
A
^
,
Γ
)
.
Hence, there exists Γ
∈
𝒟 such that ∑
i
∈
ℬ
C
‍
u
i
+
∑
k
∈
𝒮
C
‍
w
k
≥
v
t
Γ
(
C
), for all C
⊂
ℬ
∪
𝒮; namely, (
u
,
w
)
∈
𝒞
t
Γ. Thus, (
u
,
w
)
∈
⋃
Γ
∈
𝒟
(
M
)
𝒞
t
Γ.In the Appendices we show, using the market of Example2, that the sets 𝒞
t
Γ may be empty for some Γ.


### 3.1. Cartesian Product Structure and Computation of the Group Stable Solutions

In this section we present, using Theorem13, results on the structure of thet-group stable set of payoffs for t
=
1,2
,
3 and how to compute them.FixΓ
∈
𝒟 and A
∈
ℱ
0. Define theutility of buyer
i
∈
ℬ at the pair (
Γ
,
A
) as the total net gain obtained by i from his exchanges specified by A and the distribution of gains given by Γ. Denote such utility by u
i
(
Γ
,
A
); namely,
(20)
u
i
(
Γ
,
A
)
=
∑
j
k
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
.
Similarly, define theutility of seller
k
∈
𝒮 at the pair (
Γ
,
A
) as the total net gain obtained by k from his exchanges specified by A and the distribution of gains given by Γ. Denote such utility by w
k
(
Γ
,
A
); namely,
(21)
w
k
(
Γ
,
A
)
=
∑
i
j
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
.
Given (
Γ
,
A
), we will denote by u
(
Γ
,
A
)
=
(
u
(
Γ
,
A
)
)
i
∈
ℬ and w
(
Γ
,
A
)
=
(
w
k
(
Γ
,
A
)
)
k
∈
𝒮 the vectors of utilities of buyers and sellers at (
Γ
,
A
), respectively.Proposition 14.
LetM be a market, Γ a distribution matrix, and t
∈
{
1,2
,
3
}. Then,
(22)
𝒞
t
Γ
≠
∅
i
f
f
𝒞
t
Γ
=
{
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∣
A
∈
ℱ
}
.Proof.
It is immediate to check that𝒞
t
Γ
=
{
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
|
A
∈
ℱ
} implies 𝒞
t
Γ
≠
∅. To show that the other implication holds, assume 𝒞
t
Γ
≠
∅. We first check that (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ, for all A
∈
ℱ. Let A
∈
ℱ be arbitrary and let (
u
,
w
)
∈
𝒞
t
Γ. Consider any coalition C
=
{
i
} with i
∈
ℬ. Then, A
∈
ℱ
t
(
{
i
}
). Hence, since (
u
,
w
)
∈
𝒞
t
Γ and the definition of v
t
Γ,
(23)
u
i
≥
ϕ
M
(
C
,
A
,
Γ
)
=
∑
(
j
,
k
)
∈
𝒢
×
𝒮
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
.
Similarly, considering any coalition C
=
{
k
} with k
∈
𝒮,
(24)
w
k
≥
ϕ
M
(
C
,
A
,
Γ
)
=
∑
(
i
,
j
)
∈
ℬ
×
𝒢
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
.
Moreover, by Remark 12, ∑
i
∈
ℬ
‍
u
i
+
∑
k
∈
𝒮
‍
w
k
=
v
t
Γ
(
ℬ
∪
𝒮
)
=
T
M. But
(25)
T
M
=
∑
i
∈
ℬ
‍
∑
(
j
,
k
)
∈
𝒢
×
𝒮
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
+
∑
k
∈
𝒮
‍
∑
(
i
,
j
)
∈
ℬ
×
𝒢
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
holds. Hence, (23) and (24) imply
(26)
u
i
=
∑
(
j
,
k
)
∈
𝒢
×
𝒮
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
∀
i
∈
ℬ
,
w
k
=
∑
(
i
,
j
)
∈
ℬ
×
𝒢
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
∀
k
∈
𝒮
.
Thus, (
u
,
w
)
=
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
). Therefore, (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ. Now it remains to be proven that if (
u
,
w
)
∈
𝒞
t
Γ, then there exists A
∈
ℱ such that (
u
,
w
)
=
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
), but observing that ℱ
=
ℱ
t
(
ℬ
∪
𝒮
), it is proven similarly as we did previously.Denote by𝒟
t
(
M
)
=
{
Γ
:
𝒞
t
Γ
(
M
)
≠
∅
} (or simply by 𝒟
t) the set of distribution matrices whose associated game v
t
Γ has a nonempty Core. By Theorem 13 and Proposition 14, the set 𝒢
𝒮
t has the following Cartesian product structure.Corollary 15.
LetM be a market and t
∈
{
1,2
,
3
}. Then,
(27)
𝒢
𝒮
t
=
{
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∣
(
Γ
,
A
)
∈
𝒟
t
×
ℱ
}
.We will refer to the set𝒟
t as the set oft-distributions by groups. The above Corollary establishes that 𝒢
𝒮
t has a similar structure to the set of competitive equilibrium payoffs.10Lemma 16.
Lett
∈
{
1,2
,
3
} and Γ
∈
𝒟
t be such that 𝒞
t
Γ
≠
∅. Then, (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
=
(
u
(
Γ
,
A
′
)
,
w
(
Γ
,
A
′
)
), for all A
,
A
′
∈
ℱ.Proof.
Observe that the proof of Proposition14 does not depend on the particular optimal assignment A
∈
ℱ. Hence, with fixed Γ, if 𝒞
t
Γ
≠
∅, then the vector of utilities (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
) at the pair (
Γ
,
A
) is independent of the chosen optimal assignment A
∈
ℱ.By Lemma16, for Γ
∈
𝒟
t and A
∈
ℱ, we can write (
u
(
Γ
)
,
w
(
Γ
)
) instead of (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
). Hence, the following result follows immediately from Theorem 13 and Lemma 16.Corollary 17.
LetM be a market and t
∈
{
1,2
,
3
}. Then,
(28)
𝒢
𝒮
t
=
{
(
u
(
Γ
)
,
w
(
Γ
)
)
∣
Γ
∈
𝒟
t
}
.The above corollary establishes that each payoff vector in𝒢
𝒮
t comes from a distribution matrix Γ
∈
𝒟
t. Again, Jaume et al. [12] show that a similar result holds for the set of competitive equilibrium payoffs when the gains from trade are determined by an equilibrium price vector (a price for each good).Proposition18 below gives necessary and sufficient conditions under which a distribution matrix Γ is at-distribution by groups. But to state it, we present, given an optimal assignment A
∈
ℱ, the following system of inequalities on Γ:
(29)
ϕ
M
(
C
,
A
^
,
Γ
)
≤
ϕ
M
(
C
,
A
,
Γ
)
∀
C
⊂
ℬ
∪
𝒮
,
all
A
^
∈
ℱ
t
(
C
)
.Proposition 18.
LetM be a market and t
∈
{
1,2
,
3
}. Then, the following statements are equivalent. (i)
Γ
is a t-distribution by groups.
(ii)
(30)
v
t
Γ
(
ℬ
∪
𝒮
)
=
∑
i
∈
ℬ
‍
v
t
Γ
(
{
i
}
)
+
∑
k
∈
𝒮
‍
v
t
Γ
(
{
k
}
)
,
v
t
Γ
(
C
)
≤
∑
i
∈
ℬ
C
‍
v
t
Γ
(
{
i
}
)
+
∑
k
∈
𝒮
C
‍
v
t
Γ
(
{
k
}
)
∀
C
⊂
ℬ
∪
𝒮
.
(iii)
There exists
A
∈
ℱ
such that
v
t
Γ
(
C
)
=
ϕ
M
(
C
,
A
,
Γ
)
, for all
C
⊂
ℬ
∪
𝒞
.
(iv)
For all
A
∈
ℱ, v
t
Γ
(
C
)
=
ϕ
M
(
C
,
A
,
Γ
)
for all
C
⊂
ℬ
∪
𝒞.
(v)
Γ
solves the system in (29).Proof.
The equivalence between (iii) and (v) is immediate. That (ii) implies (i) is immediate since, by (30), (
v
t
Γ
(
{
i
}
)
,
v
t
Γ
(
{
k
}
)
(
i
,
k
)
∈
ℬ
∪
𝒮
∈
𝒞
t
Γ
). By the definition of v
t
Γ, we have that (iii) implies (ii). That (iv) implies (iii) is also immediate. It remains to be proven that (i) implies (iv).
Assume𝒞
t
Γ
≠
∅ and let A
∈
ℱ. By Proposition 14, (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ. Hence,
(31)
u
i
(
Γ
,
A
)
≥
v
t
Γ
(
{
i
}
)
∀
i
∈
ℬ
,
w
k
(
Γ
,
A
)
≥
v
t
Γ
(
{
k
}
)
∀
k
∈
𝒮
.
Thus, by the definition of v
t
Γ,
(32)
u
i
(
Γ
,
A
)
=
v
t
Γ
(
{
i
}
)
∀
i
∈
ℬ
,
w
k
(
Γ
,
A
)
=
v
t
Γ
(
{
k
}
)
∀
k
∈
𝒮
.
Hence,
(33)
v
t
Γ
(
{
i
}
)
=
ϕ
M
(
{
i
}
,
A
,
Γ
)
∀
i
∈
ℬ
,
v
t
Γ
(
{
k
}
)
=
ϕ
M
(
{
k
}
,
A
,
Γ
)
∀
k
∈
𝒮
.
Now, since (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ holds, by the definition of v
t
Γ
(
C
) it follows that
(34)
v
t
Γ
(
ℬ
∪
𝒮
)
=
∑
i
∈
ℬ
‍
u
i
(
Γ
,
A
)
+
∑
k
∈
𝒮
‍
w
k
(
Γ
,
A
)
,
∀
C
⊂
ℬ
∪
𝒮
,
ϕ
M
(
C
,
A
,
Γ
)
≤
v
t
Γ
(
C
)
≤
∑
i
∈
ℬ
C
‍
u
i
(
Γ
,
A
)
+
∑
k
∈
𝒮
C
‍
w
k
(
Γ
,
A
)
=
ϕ
M
(
C
,
A
,
Γ
)
.
Thus, v
t
Γ
(
C
)
=
ϕ
M
(
C
,
A
,
Γ
) for all C
⊂
ℬ
∪
𝒮.


## 3.1. Cartesian Product Structure and Computation of the Group Stable Solutions

In this section we present, using Theorem13, results on the structure of thet-group stable set of payoffs for t
=
1,2
,
3 and how to compute them.FixΓ
∈
𝒟 and A
∈
ℱ
0. Define theutility of buyer
i
∈
ℬ at the pair (
Γ
,
A
) as the total net gain obtained by i from his exchanges specified by A and the distribution of gains given by Γ. Denote such utility by u
i
(
Γ
,
A
); namely,
(20)
u
i
(
Γ
,
A
)
=
∑
j
k
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
.
Similarly, define theutility of seller
k
∈
𝒮 at the pair (
Γ
,
A
) as the total net gain obtained by k from his exchanges specified by A and the distribution of gains given by Γ. Denote such utility by w
k
(
Γ
,
A
); namely,
(21)
w
k
(
Γ
,
A
)
=
∑
i
j
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
.
Given (
Γ
,
A
), we will denote by u
(
Γ
,
A
)
=
(
u
(
Γ
,
A
)
)
i
∈
ℬ and w
(
Γ
,
A
)
=
(
w
k
(
Γ
,
A
)
)
k
∈
𝒮 the vectors of utilities of buyers and sellers at (
Γ
,
A
), respectively.Proposition 14.
LetM be a market, Γ a distribution matrix, and t
∈
{
1,2
,
3
}. Then,
(22)
𝒞
t
Γ
≠
∅
i
f
f
𝒞
t
Γ
=
{
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∣
A
∈
ℱ
}
.Proof.
It is immediate to check that𝒞
t
Γ
=
{
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
|
A
∈
ℱ
} implies 𝒞
t
Γ
≠
∅. To show that the other implication holds, assume 𝒞
t
Γ
≠
∅. We first check that (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ, for all A
∈
ℱ. Let A
∈
ℱ be arbitrary and let (
u
,
w
)
∈
𝒞
t
Γ. Consider any coalition C
=
{
i
} with i
∈
ℬ. Then, A
∈
ℱ
t
(
{
i
}
). Hence, since (
u
,
w
)
∈
𝒞
t
Γ and the definition of v
t
Γ,
(23)
u
i
≥
ϕ
M
(
C
,
A
,
Γ
)
=
∑
(
j
,
k
)
∈
𝒢
×
𝒮
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
.
Similarly, considering any coalition C
=
{
k
} with k
∈
𝒮,
(24)
w
k
≥
ϕ
M
(
C
,
A
,
Γ
)
=
∑
(
i
,
j
)
∈
ℬ
×
𝒢
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
.
Moreover, by Remark 12, ∑
i
∈
ℬ
‍
u
i
+
∑
k
∈
𝒮
‍
w
k
=
v
t
Γ
(
ℬ
∪
𝒮
)
=
T
M. But
(25)
T
M
=
∑
i
∈
ℬ
‍
∑
(
j
,
k
)
∈
𝒢
×
𝒮
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
+
∑
k
∈
𝒮
‍
∑
(
i
,
j
)
∈
ℬ
×
𝒢
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
holds. Hence, (23) and (24) imply
(26)
u
i
=
∑
(
j
,
k
)
∈
𝒢
×
𝒮
‍
(
v
i
j
-
Γ
i
j
k
)
·
A
i
j
k
∀
i
∈
ℬ
,
w
k
=
∑
(
i
,
j
)
∈
ℬ
×
𝒢
‍
(
Γ
i
j
k
-
r
j
k
)
·
A
i
j
k
∀
k
∈
𝒮
.
Thus, (
u
,
w
)
=
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
). Therefore, (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ. Now it remains to be proven that if (
u
,
w
)
∈
𝒞
t
Γ, then there exists A
∈
ℱ such that (
u
,
w
)
=
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
), but observing that ℱ
=
ℱ
t
(
ℬ
∪
𝒮
), it is proven similarly as we did previously.Denote by𝒟
t
(
M
)
=
{
Γ
:
𝒞
t
Γ
(
M
)
≠
∅
} (or simply by 𝒟
t) the set of distribution matrices whose associated game v
t
Γ has a nonempty Core. By Theorem 13 and Proposition 14, the set 𝒢
𝒮
t has the following Cartesian product structure.Corollary 15.
LetM be a market and t
∈
{
1,2
,
3
}. Then,
(27)
𝒢
𝒮
t
=
{
(
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∣
(
Γ
,
A
)
∈
𝒟
t
×
ℱ
}
.We will refer to the set𝒟
t as the set oft-distributions by groups. The above Corollary establishes that 𝒢
𝒮
t has a similar structure to the set of competitive equilibrium payoffs.10Lemma 16.
Lett
∈
{
1,2
,
3
} and Γ
∈
𝒟
t be such that 𝒞
t
Γ
≠
∅. Then, (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
=
(
u
(
Γ
,
A
′
)
,
w
(
Γ
,
A
′
)
), for all A
,
A
′
∈
ℱ.Proof.
Observe that the proof of Proposition14 does not depend on the particular optimal assignment A
∈
ℱ. Hence, with fixed Γ, if 𝒞
t
Γ
≠
∅, then the vector of utilities (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
) at the pair (
Γ
,
A
) is independent of the chosen optimal assignment A
∈
ℱ.By Lemma16, for Γ
∈
𝒟
t and A
∈
ℱ, we can write (
u
(
Γ
)
,
w
(
Γ
)
) instead of (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
). Hence, the following result follows immediately from Theorem 13 and Lemma 16.Corollary 17.
LetM be a market and t
∈
{
1,2
,
3
}. Then,
(28)
𝒢
𝒮
t
=
{
(
u
(
Γ
)
,
w
(
Γ
)
)
∣
Γ
∈
𝒟
t
}
.The above corollary establishes that each payoff vector in𝒢
𝒮
t comes from a distribution matrix Γ
∈
𝒟
t. Again, Jaume et al. [12] show that a similar result holds for the set of competitive equilibrium payoffs when the gains from trade are determined by an equilibrium price vector (a price for each good).Proposition18 below gives necessary and sufficient conditions under which a distribution matrix Γ is at-distribution by groups. But to state it, we present, given an optimal assignment A
∈
ℱ, the following system of inequalities on Γ:
(29)
ϕ
M
(
C
,
A
^
,
Γ
)
≤
ϕ
M
(
C
,
A
,
Γ
)
∀
C
⊂
ℬ
∪
𝒮
,
all
A
^
∈
ℱ
t
(
C
)
.Proposition 18.
LetM be a market and t
∈
{
1,2
,
3
}. Then, the following statements are equivalent. (i)
Γ
is a t-distribution by groups.
(ii)
(30)
v
t
Γ
(
ℬ
∪
𝒮
)
=
∑
i
∈
ℬ
‍
v
t
Γ
(
{
i
}
)
+
∑
k
∈
𝒮
‍
v
t
Γ
(
{
k
}
)
,
v
t
Γ
(
C
)
≤
∑
i
∈
ℬ
C
‍
v
t
Γ
(
{
i
}
)
+
∑
k
∈
𝒮
C
‍
v
t
Γ
(
{
k
}
)
∀
C
⊂
ℬ
∪
𝒮
.
(iii)
There exists
A
∈
ℱ
such that
v
t
Γ
(
C
)
=
ϕ
M
(
C
,
A
,
Γ
)
, for all
C
⊂
ℬ
∪
𝒞
.
(iv)
For all
A
∈
ℱ, v
t
Γ
(
C
)
=
ϕ
M
(
C
,
A
,
Γ
)
for all
C
⊂
ℬ
∪
𝒞.
(v)
Γ
solves the system in (29).Proof.
The equivalence between (iii) and (v) is immediate. That (ii) implies (i) is immediate since, by (30), (
v
t
Γ
(
{
i
}
)
,
v
t
Γ
(
{
k
}
)
(
i
,
k
)
∈
ℬ
∪
𝒮
∈
𝒞
t
Γ
). By the definition of v
t
Γ, we have that (iii) implies (ii). That (iv) implies (iii) is also immediate. It remains to be proven that (i) implies (iv).
Assume𝒞
t
Γ
≠
∅ and let A
∈
ℱ. By Proposition 14, (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ. Hence,
(31)
u
i
(
Γ
,
A
)
≥
v
t
Γ
(
{
i
}
)
∀
i
∈
ℬ
,
w
k
(
Γ
,
A
)
≥
v
t
Γ
(
{
k
}
)
∀
k
∈
𝒮
.
Thus, by the definition of v
t
Γ,
(32)
u
i
(
Γ
,
A
)
=
v
t
Γ
(
{
i
}
)
∀
i
∈
ℬ
,
w
k
(
Γ
,
A
)
=
v
t
Γ
(
{
k
}
)
∀
k
∈
𝒮
.
Hence,
(33)
v
t
Γ
(
{
i
}
)
=
ϕ
M
(
{
i
}
,
A
,
Γ
)
∀
i
∈
ℬ
,
v
t
Γ
(
{
k
}
)
=
ϕ
M
(
{
k
}
,
A
,
Γ
)
∀
k
∈
𝒮
.
Now, since (
u
(
Γ
,
A
)
,
w
(
Γ
,
A
)
)
∈
𝒞
t
Γ holds, by the definition of v
t
Γ
(
C
) it follows that
(34)
v
t
Γ
(
ℬ
∪
𝒮
)
=
∑
i
∈
ℬ
‍
u
i
(
Γ
,
A
)
+
∑
k
∈
𝒮
‍
w
k
(
Γ
,
A
)
,
∀
C
⊂
ℬ
∪
𝒮
,
ϕ
M
(
C
,
A
,
Γ
)
≤
v
t
Γ
(
C
)
≤
∑
i
∈
ℬ
C
‍
u
i
(
Γ
,
A
)
+
∑
k
∈
𝒮
C
‍
w
k
(
Γ
,
A
)
=
ϕ
M
(
C
,
A
,
Γ
)
.
Thus, v
t
Γ
(
C
)
=
ϕ
M
(
C
,
A
,
Γ
) for all C
⊂
ℬ
∪
𝒮.


## 4. Competitive Solutions

### 4.1. Two Competitive Equilibrium Notions

In this section we first present two already known competitive solutions for generalized assignment games. Using a similar approach to the one already used witht-group stability we will see how competitive equilibria are related with the notions of Core, provided that the cooperative games with transferable utility are defined properly. This will allow us to draw conclusions with regard to the structure of competitive solutions and how to compute them.The first competitive solution was presented by Jaume et al. [12]. We will see how we can obtain some of their results using the approach used in the previous section. This solution assumes that buyers and sellers exchange goods through competitive markets. Namely, there is a unique market for each of the goods (with its corresponding price). Hence, a price vector is an n-dimensional vector of nonnegative real numbers. Buyers and sellers are price-takers in the following sense. Given a price vector p
=
(
p
j
)
j
∈
G
∈
ℝ
+
n each seller offers units of the goods he owns (up to his capacity) to maximize his net gains and each buyer demands units of the goods (up to his maximal capacity) to maximize his total net valuation. The unique information that each agent has about the markets, besides the price vector, is his per unit valuations of the goods and his capacity of maximal demand (if the agent is a buyer) and his reservation prices and number of units owned of each of the goods. Agents do not know the aggregate capacities.In the second notion we will assume that the aggregate capacities of the market are known by the agents. For instance, because the market is small and all exchanges are performed simultaneously at the same place. Hence, given a price vectorp, agents will maximize their utility taking into account the market aggregate capacities. Namely, a buyer i will never demand of good j a quantity larger than ∑
k
‍
q
j
k, even though this amount is smaller than d
i and the net valuation (v
i
j
-
p
j) of good j is strictly larger than the net valuations of all the other goods. This notion can be seen as an extension of the competitive equilibrium notions introduced and studied in Sotomayor [6], in an assignment model with indivisible goods and by Sotomayor [7, 8], in a model with infinitely divisible goods, but in both cases and in contrast with our model, it is assumed that sellers only own units of the same good. In these three papers, given a price vector p, agents’ demands and supplies are obtained by solving their maximizing problems over the set offeasible assignments; that is, it is assumed that agents know the aggregate capacities.It is also possible to consider the case where only buyers know the aggregate capacities and only they adjust their demands to such constraints, and vice versa. Our proofs could be adapted easily to these two settings to obtain similar conclusions for them.To present the first approach, we transcribe some definitions in Jaume et al. [12].Supply of Seller
k. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, seller k offers of each good j any feasible amount that maximizes his gain; namely,
(35)
𝒮
j
k
(
p
j
)
=
{
{
q
j
k
}
if
p
j
>
r
j
k
{
0,1
,
…
,
q
j
k
}
if
p
j
=
r
j
k
{
0
}
if
p
j
<
r
j
k
.
To define the demand of buyer i
∈
ℬ, we will use the following notation. Let p
∈
ℝ
+
G and let
(36)
∇
i
>
(
p
)
=
{
j
∈
𝒢
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
{
v
i
j
′
-
p
j
′
}
>
0
}
be the set of goods that give to buyer i the maximal (and strictly positive) net valuation at p. Obviously, for some p, the set ∇
i
>
(
p
) may be empty. Let
(37)
∇
i
≥
(
p
)
=
{
j
∈
𝒢
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
{
v
i
j
′
-
p
j
′
}
≥
0
}
be the set of goods that give to buyer i the maximal (and strictly positive) net valuation at p. Obviously, for some p, the set ∇
i
≥
(
p
) may be empty. It is obvious that, for all p
∈
ℝ
+
G and all i
∈
ℬ,
(38)
∇
i
>
(
p
)
⊆
∇
i
≥
(
p
)
.Demand of Buyer
i. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, buyer i demands any feasible amount of goods that maximize his net valuation at p; namely,(39)
D
i
(
p
)
=
{
∑
k
‍
α
=
(
α
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮
∈
ℤ
G
×
S
∣
(
D
.
a
)
α
j
k
≥
0
∀
(
j
,
k
)
∈
𝒢
×
𝒮
,
(
D
.
b
)
∑
j
k
‍
α
j
k
≤
d
i
,
(
D
.
c
)
∇
i
>
(
p
)
≠
∅
⟹
∑
j
k
‍
α
j
k
=
d
i
,
(
D
.
d
)
∑
k
‍
α
j
k
>
0
⟹
j
∈
∇
i
≥
(
p
)
}
.GivenA
∈
ℱ
0 and i
∈
ℬ, denote by A
(
i
)
=
(
A
(
i
)
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮 the element in ℤ
+
G
×
S such that, for all (
j
,
k
)
∈
𝒢
×
𝒮, A
(
i
)
j
k
=
A
i
j
k.Definition 19.
A -1-competitive equilibrium
11 of market M is a pair (
p
,
A
)
∈
ℝ
+
G
×
ℱ
0 such that(E.D) for alli
∈
ℬ,A
(
i
)
∈
D
i
(
p
),
(E.S) for allj
∈
𝒢 and all k
∈
𝒮,∑
i
‍
A
i
j
k
∈
𝒮
j
k
(
p
j
).Next, we present the second competitive solution related to situations where agents, given a price vector, adjust their demands and supplies to the aggregate restrictions of the market. Given a price vectorp
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G sellers will offer units of the goods (below their capacities) to maximize the net gains at p, but sellers will know that buyers will be able to buy at most D
=
∑
i
∈
ℬ
‍
d
i units in total, and buyers will demand units of the goods (below their capacities) to maximize the net valuations at p, but knowing that sellers will be able to sell at most Q
j
=
∑
k
∈
𝒮
‍
q
j
k units of each good j. To define the supply of seller k
∈
𝒮, we will need the following notation. Let p
∈
ℝ
+
G be a price vector and let(40)
∇
k
1
>
(
p
)
=
{
j
∈
𝒢
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}
,
∇
k
2
>
(
p
)
=
{
j
∈
𝒢
∖
∇
k
1
>
(
p
)
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
∖
∇
k
1
>
(
p
)
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}
,
⋮
∇
k
z
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
k
m
>
(
p
)
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
k
m
>
(
p
)
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}
,
⋮
∇
k
J
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
k
m
>
(
p
)
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
k
m
>
(
p
)
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}be the sets of goods that give to sellerk a strictly positive net gain at p, ordered in such a way that goods in ∇
k
z
>
(
p
) give a larger net gain than goods in ∇
k
z
′
>
(
p
) if and only if z
<
z
′. Obviously, for some p, the set ∇
k
z
>
(
p
) may be empty from a given z onwards.Since sellerk knows the market constraints, k knows that the maximal possible demand is D
=
∑
i
∈
ℬ
‍
d
i. Hence, k will adjust his supply to this demand. Now define
(41)
s
1
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
1
>
(
p
)
‍
q
j
k
,
D
}
,
s
2
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
2
>
(
p
)
‍
q
j
k
,
D
-
s
1
k
(
p
)
}
,
⋮
s
z
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
z
>
(
p
)
‍
q
j
k
,
D
-
∑
m
=
1
z
-
1
‍
s
m
k
(
p
)
}
,
⋮
s
J
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
J
>
(
p
)
‍
q
j
k
,
D
-
∑
m
=
1
J
-
1
‍
s
m
k
(
p
)
}
.We may haves
z
k
(
p
)
=
0 from some z onwards.Now, let(42)
∇
k
≥
(
p
)
=
{
j
∈
𝒢
∣
p
j
-
r
j
k
≥
0
}
be the set of goods that give to seller k a nonnegative net gain at p. Obviously, for some p, the set ∇
k
≥
(
p
) may be empty. It is obvious that, for all p
∈
ℝ
+
G and all k
∈
𝒮,
(43)
∇
k
z
>
(
p
)
⊆
∇
k
≥
(
p
)
,
∀
z
=
1
,
…
,
J
.Supply-0 of Seller
k
. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, seller k supplies any feasible amount for the market of the goods that maximize his net gain at p; namely,(44)
S
k
0
(
p
)
=
{
∑
j
∈
∇
k
z
>
(
p
)
‍
β
=
(
β
j
)
j
∈
𝒢
∈
ℤ
G
∣
(
S
.
a
0
)
β
j
≥
0
∀
j
∈
𝒢
,
(
S
.
b
0
)
β
j
≤
q
j
k
∀
j
∈
𝒢
,
(
S
.
c
0
)
∇
k
z
>
(
p
)
≠
∅
⟹
∑
j
∈
∇
k
z
>
(
p
)
‍
β
j
=
s
z
k
(
p
)
∀
z
=
1
,
…
,
J
,
(
S
.
d
0
)
β
j
>
0
⟹
j
∈
∇
k
≥
(
p
)
∑
j
∈
∇
k
z
>
(
p
)
‍
}
.Therefore,S
k
0
(
p
) describes the set of sales that maximize the net gain of seller k at p (taking into account the market constraints).12 Observe that the set of sales described by each element in S
k
0
(
p
) gives, to seller k, the same net gain; namely, k is indifferent among all sales in S
k
0
(
p
).To define the demand of buyeri
∈
ℬ, we will need the following notation. Let p
∈
ℝ
+
G be a price vector and let(45)
∇
i
1
>
(
p
)
=
{
j
∈
𝒢
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}
,
∇
i
2
>
(
p
)
=
{
j
∈
𝒢
∖
∇
i
1
>
(
p
)
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
∖
∇
i
1
>
(
p
)
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}
,
⋮
∇
i
z
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
i
m
>
(
p
)
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
i
m
>
(
p
)
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}
,
⋮
∇
i
J
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
i
m
>
(
p
)
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
i
m
>
(
p
)
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}be the sets of goods that give to buyeri a strictly positive net valuation at p, ordered in such a way that goods in ∇
i
z
> give a larger net valuation than goods in ∇
i
z
′
> if and only if z
<
z
′. Obviously, for some p, the set ∇
i
z
>
(
p
) may be empty from some z onwards.Now we define(46)
d
1
i
(
p
)
=
min
⁡
{
d
i
,
∑
j
∈
∇
i
1
>
(
p
)
‍
Q
j
}
,
d
2
i
(
p
)
=
min
⁡
{
d
i
-
d
1
i
(
p
)
,
∑
j
∈
∇
i
2
>
(
p
)
‍
Q
j
}
,
⋮
d
z
i
(
p
)
=
min
⁡
{
d
i
-
∑
m
=
1
z
-
1
‍
d
m
i
(
p
)
,
∑
j
∈
∇
i
z
>
(
p
)
‍
Q
j
}
,
⋮
d
J
i
(
p
)
=
min
⁡
{
d
i
-
∑
m
=
1
J
-
1
‍
d
m
i
(
p
)
,
∑
j
∈
∇
i
J
>
(
p
)
‍
Q
j
}
.
Obviously, for some p, we may have d
z
i
(
p
)
=
0 from some z onwards. Also, for all p
∈
ℝ
+
G and all i
∈
ℬ,
(47)
∇
i
z
>
(
p
)
⊆
∇
i
≥
(
p
)
,
∀
z
=
1
,
…
,
J
.Demand-0 of Buyer
i
. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, buyer i demands any feasible amount for the market that maximizes his net valuation at p; namely,(48)
D
i
0
(
p
)
=
{
∑
k
‍
α
=
(
α
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮
∈
ℤ
G
×
S
∣
(
D
.
a
0
)
α
j
k
≥
0
∀
(
j
,
k
)
∈
𝒢
×
𝒮
,
(
D
.
b
0
)
∑
j
k
‍
α
j
k
≤
d
i
,
(
D
.
c
0
)
∇
i
z
>
(
p
)
≠
∅
⟹
∑
j
∈
∇
i
z
>
(
p
)
‍
∑
k
‍
α
j
k
=
d
z
i
(
p
)
∀
=
1
,
…
,
J
,
(
D
.
d
0
)
∑
k
‍
α
j
k
>
0
⟹
j
∈
∇
i
≥
(
p
)
}
.Thus,D
i
0
(
p
) describes the set of all purchases that maximize the net valuation of buyer i at p, taking into account the aggregate constraints of the market.13 Observe that the set of purchases described by each element in D
i
0
(
p
) give to i the same net valuation; namely, i is indifferent among all purchases in D
i
0
(
p
).Definition 20.
A 0-competitive equilibriumof market M is a pair (
p
,
A
)
∈
ℝ
+
G
×
ℱ
0 such that(E.D0) for alli
∈
ℬ, A
(
i
)
∈
D
i
0
(
p
),
(E.S0) for allk
∈
𝒮, (
∑
i
‍
A
i
j
k
)
j
∈
𝒢
∈
S
k
0
(
p
).In the remaining of this section,t will be an index in {
-
1,0
}. We say that the vector p
∈
ℝ
+
G is at-competitive equilibrium price(or simply at-equilibrium price) of market M if there exists A
∈
ℱ
0 such that (
p
,
A
) is at-competitive equilibrium of M (or simply at-equilibrium). Denote by 𝒫
t the set of allt-equilibrium prices of market M.Fix a price vectorp
∈
ℝ
+
G and a feasible assignment A
∈
ℱ
0. According to (20) and (21), the utility of buyer i
∈
ℬ at (
p
,
A
) is
(49)
u
i
(
p
,
A
)
=
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
,
and the utility of seller k
∈
𝒮 at (
p
,
A
) is
(50)
w
k
(
p
,
A
)
=
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
.Definition 21.
LetM be a market and t
∈
{
-
1,0
}. The set oft-competitive equilibrium payoffs is given by
(51)
𝒞
ℰ
t
=
{
(
u
,
w
)
∈
ℝ
B
×
ℝ
S
∣
(
u
,
w
)
=
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
for
some
t
-equilibrium
(
p
,
A
)
ℝ
B
×
ℝ
S
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
}
.We now define a cooperative game with transferable utility that will allow us to draw conclusions about𝒫
t and 𝒞
ℰ
t, for t
=
-
1,0, similarly as we did for 𝒟
t and 𝒢
𝒮
t, for t
=
1,2
,
3.Definition 22.
LetM be a market. A pair (
A
B
,
A
S
)
∈
ℤ
+
B
×
G
×
S
×
ℤ
+
B
×
G
×
S is -1-compatible in M if,(i)
for eachi
∈
ℬ, ∑
j
k
‍
A
i
j
k
B
≤
d
i,
(ii)
for eachk
∈
𝒮 and j
∈
𝒢, ∑
i
‍
A
i
j
k
S
≤
q
j
k.The set of pairs -1-compatible in M will be denoted by ℱ
-
1. Moreover, and with an abuse of notation, we will denote by ℱ
0
=
{
(
A
,
A
)
∣
(
A
,
A
)
∈
ℱ
-
1
} the set of 0-compatible assignments in M.14Definition 23.
LetM be a market, t
∈
{
-
1,0
}, p
∈
ℝ
+
G a price vector, C
⊂
ℬ
∪
𝒮 a coalition, and (
A
B
,
A
S
)
∈
ℱ
t. Define thenet gain for
C
at
(
A
B
,
A
S
)
according to
p by
(52)
φ
M
(
C
,
(
A
B
,
A
S
)
,
p
)
=
∑
i
∈
ℬ
C
‍
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
B
+
∑
k
∈
𝒮
C
‍
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
S
.Note that if(
A
,
A
)
∈
ℱ
0, then φ
M
(
C
,
(
A
,
A
)
,
p
)
=
ϕ
M
(
C
,
A
,
p
), where ϕ
M is given by (10) after setting, for all j
∈
𝒢, Γ
i
j
k
=
p
j for all (
i
,
k
)
∈
ℬ
×
𝒮. For each price vector p, we can define the following associated games to market M.Definition 24.
LetM be a market, t
=
{
-
1,0
}, and p a price vector. Thecooperative game
(
ℬ
∪
𝒮
,
v
t
p
)
with transferable utility associated with
t
and
p is defined as follows:
(53)
v
t
p
(
C
)
=
{
max
⁡
(
A
B
,
A
S
)
∈
ℱ
t
⁡
φ
M
(
C
,
(
A
B
,
A
S
)
,
p
)
if
C
⊊
ℬ
∪
𝒮
T
M
if
C
=
ℬ
∪
𝒮
.We denote by𝒞
t
p
(
M
) (or simply by 𝒞
t
p) the Core of the game (
ℬ
∪
𝒮
,
v
t
p
). We now see that these Cores are intimately related with the corresponding notions of competitive equilibria.Theorem 25.
LetM be a market and t
=
{
-
1,0
}. Then,
(54)
p
∈
𝒫
t
i
f
f
𝒞
t
p
≠
∅
.To prove Theorem25 we need the following two results.Lemma 26.
LetM be a market and t
=
{
-
1,0
}. Then, (
p
,
A
) is at-equilibrium if and only if, for all (
A
B
,
A
S
)
∈
ℱ
t,
(55)
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
≥
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
B
,
∀
i
∈
ℬ
,
(56)
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
≥
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
S
,
∀
k
∈
𝒮
.Proof.
See the Appendices.Parallel to Proposition14, we now have Proposition 27.Proposition 27.
LetM be a market, t
=
{
-
1,0
} and p
∈
ℝ
+
G a price vector. Then,
(57)
𝒞
t
p
≠
∅
i
f
f
𝒞
t
p
=
{
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∣
A
∈
ℱ
}
.Proof.
It is similar to the proof of Proposition14 and therefore it is omitted.Proof of Theorem25.
Assumep
∈
𝒫
t and let A be such that (
p
,
A
) is at-equilibrium. Then, by the definition of v
t
p and Lemma 26, (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. To see that the other implication holds, let p be such that 𝒞
t
p
≠
∅ and let ∈
ℱ. By Proposition 27, (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. Hence, for all (
A
B
,
A
S
)
∈
ℱ
t,
(58)
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
≥
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
B
,
∀
i
∈
ℬ
,
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
≥
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
S
,
∀
k
∈
𝒮
.
Thus, by Lemma 26, (
p
,
A
) is at-equilibrium and, hence, p
∈
𝒫
t.It is easy to check that, for allp
∈
ℝ
+
G,
(59)
v
-
1
p
(
C
)
≥
v
0
p
(
C
)
,
∀
C
⊊
ℬ
∪
𝒮
,
v
-
1
p
(
ℬ
∪
𝒮
)
=
v
0
p
(
ℬ
∪
𝒮
)
hold. Hence, 𝒞
-
1
p
⊂
𝒞
0
p, for all p
∈
ℝ
+
G. Thus, by Theorem 25, the following result holds.Corollary 28.
LetM be a market. Then, ∅
≠
𝒫
-
1
⊊
𝒫
0.Proof.
Jaume et al. [12] show that ∅
≠
𝒫
-
1. The inclusion follows from Theorem 25, (59). The strict inclusion follows from Example 29 below.Example 29.
LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market where B
=
{
1,2
}, G
=
{
1,2
}, S
=
{
1
}, V
=
(
6
4
7
0
), d
=
(
7,5
) Q
=
(
8,4
), and R
=
(
5,2
). The unique optimal assignment is A
=
(
3
4
5
0
). Consider the price vector p
=
(
5,2
). Then, v
0
p
(
{
b
1
,
b
2
,
s
1
}
)
=
T
(
A
)
=
1
·
3
+
2
·
4
+
2
·
5
=
21
,
v
0
p
(
{
b
1
,
s
1
}
)
=
1
·
3
+
2
·
4
=
11,v
0
p
(
{
b
2
,
s
1
}
)
=
2
·
5
=
10, v
0
p
(
{
s
1
}
)
=
0
,
v
0
p
(
{
b
1
}
)
=
1
·
3
+
2
·
4
=
11
,
v
0
p
(
{
b
2
}
)
=
2
·
5
=
10. Thus, (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
=
(
11,10,0
)
∈
C
0
p and, hence, (
5,2
)
∈
𝒫
0. But (
5,2
)
∉
𝒫
-
1, since at p
=
(
5,2
) buyer b
1 would demand 7 units of good 2.The next proposition follows immediately from Lemma26 and the fact that if A
^
∈
ℱ
0, then (
A
^
,
A
^
)
∈
ℱ
t, for all t
∈
{
-
1,0
}.Proposition 30.
LetM be a market and t
∈
{
-
1,0
}. Then, (
p
,
A
) is at-equilibrium if and only if p
∈
𝒫
t and A
∈
ℱ.15A result, similar to Theorem13 for group stable sets, holds for the sets of competitive equilibrium payoffs.Theorem 31.
LetM be a market. Then, for t
∈
{
-
1,0
},16
(60)
𝒞
ℰ
t
=
⋃
p
∈
ℝ
+
G
‍
𝒞
t
p
.Proof.
That𝒞
ℰ
t
⊂
⋃
p
∈
ℝ
+
G
‍
𝒞
t
p holds follows from Theorem 25 and Propositions 27 and 30. To see that the other inclusion holds, let (
u
,
w
)
∈
⋃
p
∈
ℝ
+
G
‍
𝒞
t
p. By Proposition 27, there exists (
p
,
A
)
∈
ℝ
+
G
×
ℱ such that (
u
,
w
)
=
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. Hence, by Lemma 26 and Theorem 25, (
u
,
w
)
∈
𝒞
ℰ
t.Corollary 32.
LetM be a market. Then, ∅
≠
𝒞
ℰ
-
1
⊊
𝒞
ℰ
0.Proof.
Jaume et al. [12] show that ∅
≠
𝒞
ℰ
-
1. The inclusion follows from Theorem 31, (59). Example 29 below shows that the inclusion may be strict.Example
2
9 (continued). We already saw that p
=
(
5,2
)
∈
𝒫
0
∖
𝒫
-
1. Hence, (
11,10,0
)
∈
C
0
p and (
11,10,0
)
∈
𝒞
ℰ
0. Moreover, we have that (
u
(
p
*
,
A
)
,
w
(
p
*
,
A
)
)
=
(
11,10,0
) if and only if p
*
=
(
5,2
). But since (
5,2
)
∉
𝒫
-
1, (
11,10,0
)
∉
𝒞
ℰ
-
1. Namely, 𝒞
ℰ
-
1
⊊
𝒞
ℰ
0.


### 4.2. Cartesian Product Structure and Computation of Competitive Equilibria

We have already seen that fort
∈
{
-
1,0
} the set 𝒞
ℰ
t is a Cartesian product in the following sense:
(61)
𝒞
ℰ
t
=
{
(
u
,
w
)
∈
ℝ
B
×
S
∣
for
some
(
p
,
A
)
∈
𝒫
t
×
ℱ
,
(
u
,
w
)
=
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
ℝ
B
×
S
}
.Now, parallel to Lemma16, the following result holds.Lemma 33.
LetM be a market, t
∈
{
-
1,0
}, and p
∈
ℝ
+
G a price vector. If 𝒞
t
p
≠
∅, then (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
=
(
u
(
p
,
A
′
)
,
w
(
p
,
A
′
)
) for all pairs A
,
A
′
∈
ℱ.Proof.
The proof proceeds similarly to the proof of Proposition14, using the fact that if A
∈
ℱ, then (
A
,
A
)
∈
ℱ
t for t
∈
{
-
1,0
}.Thus, if𝒞
t
p
≠
∅ and A
∈
ℱ, we will write (
u
(
p
,
A
)
,
w
(
p
,
A
)
) simply by (
u
(
p
)
,
w
(
p
)
), without any reference to A. We present this fact in the following corollary.Corollary 34.
LetM be a market and t
∈
{
-
1,0
}. Then, 𝒞
ℰ
t
=
{
(
u
(
p
)
,
w
(
p
)
)
∣
p
∈
𝒫
t
}.Parallel to Proposition14, we present several necessary and sufficient conditions for 𝒞
t
p
≠
∅ (one of them can be used to check whether or not p belongs to 𝒫
t). Observe that the condition
(62)
v
t
p
(
C
)
≤
∑
i
∈
ℬ
C
‍
v
t
p
(
{
i
}
)
+
∑
k
∈
𝒮
C
‍
v
t
p
(
{
k
}
)
,
∀
C
⊂
ℬ
∪
𝒮
,
is trivially satisfied for t
∈
{
-
1,0
}.FixA
∈
ℱ and consider the system on p of lineal inequalities given by
(63)
φ
M
(
C
,
(
A
B
,
A
S
)
,
p
)
≤
φ
M
(
C
,
(
A
,
A
)
,
p
)
,
∀
C
⊂
ℬ
∪
𝒞
with
#
C
=
1
,
∀
(
A
B
,
A
A
)
∈
ℱ
t
.Proposition 35.
LetM be a market, t
∈
{
-
1,0
}, and p
∈
ℝ
+
G a price vector. Then, the following statements are equivalent.(i)
p
is a
t
-equilibrium price.
(ii)
𝒞
t
p
≠
∅.
(iii)
(64)
v
t
p
(
ℬ
∪
𝒮
)
=
∑
i
∈
ℬ
‍
v
t
p
(
{
i
}
)
+
∑
k
∈
𝒮
‍
v
t
p
(
{
k
}
)
.
(iv)
There exists
A
∈
ℱ
such that
v
t
p
(
C
)
=
φ
M
(
C
,
(
A
,
A
)
,
p
),
for all
C
⊂
ℬ
∪
𝒮
with
#
C
=
1.
(v)
For all
A
∈
ℱ
,
v
t
p
(
C
)
=
φ
M
(
C
,
(
A
,
A
)
,
p
)
for all
C
⊂
ℬ
∪
𝒮
with
#
C
=
1.
(vi)
p
solves system (63).Proof.
The equivalence between (i) and (ii) follows from Theorem25. The equivalence between (iv) and (vi) is immediate. That (iii) implies (ii) follows from the fact that (
v
t
p
(
{
i
}
)
,
v
t
p
(
{
k
}
)
(
i
,
k
)
∈
ℬ
∪
𝒮
∈
𝒞
t
Γ
). That (iv) implies (iii) follows easily from the definition v
t
p. That (v) implies (iv) is also immediate. Hence, it only remains to be proved that (ii) implies (v).
Assume𝒞
t
p
≠
∅. By Proposition 14, if A
∈
ℱ, then (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. Hence,
(65)
u
i
(
p
)
≥
v
t
p
(
{
i
}
)
,
∀
i
∈
ℬ
,
w
k
(
p
)
≥
v
t
p
(
{
k
}
)
,
∀
k
∈
𝒮
.
By the definition of v
t
p,
(66)
φ
M
(
{
i
}
,
(
A
,
A
)
,
p
)
=
u
i
(
p
,
A
)
=
v
t
p
(
{
i
}
)
,
∀
i
∈
ℬ
,
φ
M
(
{
k
}
,
(
A
,
A
)
,
p
)
=
w
k
(
p
,
A
)
=
v
t
p
(
{
k
}
)
,
∀
k
∈
𝒮
.The above proposition gives criteria and procedures to compute price vectors in𝒫
t and therefore payoff vectors in 𝒞
ℰ
t.


## 4.1. Two Competitive Equilibrium Notions

In this section we first present two already known competitive solutions for generalized assignment games. Using a similar approach to the one already used witht-group stability we will see how competitive equilibria are related with the notions of Core, provided that the cooperative games with transferable utility are defined properly. This will allow us to draw conclusions with regard to the structure of competitive solutions and how to compute them.The first competitive solution was presented by Jaume et al. [12]. We will see how we can obtain some of their results using the approach used in the previous section. This solution assumes that buyers and sellers exchange goods through competitive markets. Namely, there is a unique market for each of the goods (with its corresponding price). Hence, a price vector is an n-dimensional vector of nonnegative real numbers. Buyers and sellers are price-takers in the following sense. Given a price vector p
=
(
p
j
)
j
∈
G
∈
ℝ
+
n each seller offers units of the goods he owns (up to his capacity) to maximize his net gains and each buyer demands units of the goods (up to his maximal capacity) to maximize his total net valuation. The unique information that each agent has about the markets, besides the price vector, is his per unit valuations of the goods and his capacity of maximal demand (if the agent is a buyer) and his reservation prices and number of units owned of each of the goods. Agents do not know the aggregate capacities.In the second notion we will assume that the aggregate capacities of the market are known by the agents. For instance, because the market is small and all exchanges are performed simultaneously at the same place. Hence, given a price vectorp, agents will maximize their utility taking into account the market aggregate capacities. Namely, a buyer i will never demand of good j a quantity larger than ∑
k
‍
q
j
k, even though this amount is smaller than d
i and the net valuation (v
i
j
-
p
j) of good j is strictly larger than the net valuations of all the other goods. This notion can be seen as an extension of the competitive equilibrium notions introduced and studied in Sotomayor [6], in an assignment model with indivisible goods and by Sotomayor [7, 8], in a model with infinitely divisible goods, but in both cases and in contrast with our model, it is assumed that sellers only own units of the same good. In these three papers, given a price vector p, agents’ demands and supplies are obtained by solving their maximizing problems over the set offeasible assignments; that is, it is assumed that agents know the aggregate capacities.It is also possible to consider the case where only buyers know the aggregate capacities and only they adjust their demands to such constraints, and vice versa. Our proofs could be adapted easily to these two settings to obtain similar conclusions for them.To present the first approach, we transcribe some definitions in Jaume et al. [12].Supply of Seller
k. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, seller k offers of each good j any feasible amount that maximizes his gain; namely,
(35)
𝒮
j
k
(
p
j
)
=
{
{
q
j
k
}
if
p
j
>
r
j
k
{
0,1
,
…
,
q
j
k
}
if
p
j
=
r
j
k
{
0
}
if
p
j
<
r
j
k
.
To define the demand of buyer i
∈
ℬ, we will use the following notation. Let p
∈
ℝ
+
G and let
(36)
∇
i
>
(
p
)
=
{
j
∈
𝒢
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
{
v
i
j
′
-
p
j
′
}
>
0
}
be the set of goods that give to buyer i the maximal (and strictly positive) net valuation at p. Obviously, for some p, the set ∇
i
>
(
p
) may be empty. Let
(37)
∇
i
≥
(
p
)
=
{
j
∈
𝒢
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
{
v
i
j
′
-
p
j
′
}
≥
0
}
be the set of goods that give to buyer i the maximal (and strictly positive) net valuation at p. Obviously, for some p, the set ∇
i
≥
(
p
) may be empty. It is obvious that, for all p
∈
ℝ
+
G and all i
∈
ℬ,
(38)
∇
i
>
(
p
)
⊆
∇
i
≥
(
p
)
.Demand of Buyer
i. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, buyer i demands any feasible amount of goods that maximize his net valuation at p; namely,(39)
D
i
(
p
)
=
{
∑
k
‍
α
=
(
α
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮
∈
ℤ
G
×
S
∣
(
D
.
a
)
α
j
k
≥
0
∀
(
j
,
k
)
∈
𝒢
×
𝒮
,
(
D
.
b
)
∑
j
k
‍
α
j
k
≤
d
i
,
(
D
.
c
)
∇
i
>
(
p
)
≠
∅
⟹
∑
j
k
‍
α
j
k
=
d
i
,
(
D
.
d
)
∑
k
‍
α
j
k
>
0
⟹
j
∈
∇
i
≥
(
p
)
}
.GivenA
∈
ℱ
0 and i
∈
ℬ, denote by A
(
i
)
=
(
A
(
i
)
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮 the element in ℤ
+
G
×
S such that, for all (
j
,
k
)
∈
𝒢
×
𝒮, A
(
i
)
j
k
=
A
i
j
k.Definition 19.
A -1-competitive equilibrium
11 of market M is a pair (
p
,
A
)
∈
ℝ
+
G
×
ℱ
0 such that(E.D) for alli
∈
ℬ,A
(
i
)
∈
D
i
(
p
),
(E.S) for allj
∈
𝒢 and all k
∈
𝒮,∑
i
‍
A
i
j
k
∈
𝒮
j
k
(
p
j
).Next, we present the second competitive solution related to situations where agents, given a price vector, adjust their demands and supplies to the aggregate restrictions of the market. Given a price vectorp
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G sellers will offer units of the goods (below their capacities) to maximize the net gains at p, but sellers will know that buyers will be able to buy at most D
=
∑
i
∈
ℬ
‍
d
i units in total, and buyers will demand units of the goods (below their capacities) to maximize the net valuations at p, but knowing that sellers will be able to sell at most Q
j
=
∑
k
∈
𝒮
‍
q
j
k units of each good j. To define the supply of seller k
∈
𝒮, we will need the following notation. Let p
∈
ℝ
+
G be a price vector and let(40)
∇
k
1
>
(
p
)
=
{
j
∈
𝒢
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}
,
∇
k
2
>
(
p
)
=
{
j
∈
𝒢
∖
∇
k
1
>
(
p
)
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
∖
∇
k
1
>
(
p
)
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}
,
⋮
∇
k
z
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
k
m
>
(
p
)
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
k
m
>
(
p
)
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}
,
⋮
∇
k
J
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
k
m
>
(
p
)
∣
p
j
-
r
j
k
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
k
m
>
(
p
)
⁡
{
p
j
′
-
r
j
′
k
}
>
0
}be the sets of goods that give to sellerk a strictly positive net gain at p, ordered in such a way that goods in ∇
k
z
>
(
p
) give a larger net gain than goods in ∇
k
z
′
>
(
p
) if and only if z
<
z
′. Obviously, for some p, the set ∇
k
z
>
(
p
) may be empty from a given z onwards.Since sellerk knows the market constraints, k knows that the maximal possible demand is D
=
∑
i
∈
ℬ
‍
d
i. Hence, k will adjust his supply to this demand. Now define
(41)
s
1
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
1
>
(
p
)
‍
q
j
k
,
D
}
,
s
2
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
2
>
(
p
)
‍
q
j
k
,
D
-
s
1
k
(
p
)
}
,
⋮
s
z
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
z
>
(
p
)
‍
q
j
k
,
D
-
∑
m
=
1
z
-
1
‍
s
m
k
(
p
)
}
,
⋮
s
J
k
(
p
)
=
min
⁡
{
∑
j
∈
∇
k
J
>
(
p
)
‍
q
j
k
,
D
-
∑
m
=
1
J
-
1
‍
s
m
k
(
p
)
}
.We may haves
z
k
(
p
)
=
0 from some z onwards.Now, let(42)
∇
k
≥
(
p
)
=
{
j
∈
𝒢
∣
p
j
-
r
j
k
≥
0
}
be the set of goods that give to seller k a nonnegative net gain at p. Obviously, for some p, the set ∇
k
≥
(
p
) may be empty. It is obvious that, for all p
∈
ℝ
+
G and all k
∈
𝒮,
(43)
∇
k
z
>
(
p
)
⊆
∇
k
≥
(
p
)
,
∀
z
=
1
,
…
,
J
.Supply-0 of Seller
k
. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, seller k supplies any feasible amount for the market of the goods that maximize his net gain at p; namely,(44)
S
k
0
(
p
)
=
{
∑
j
∈
∇
k
z
>
(
p
)
‍
β
=
(
β
j
)
j
∈
𝒢
∈
ℤ
G
∣
(
S
.
a
0
)
β
j
≥
0
∀
j
∈
𝒢
,
(
S
.
b
0
)
β
j
≤
q
j
k
∀
j
∈
𝒢
,
(
S
.
c
0
)
∇
k
z
>
(
p
)
≠
∅
⟹
∑
j
∈
∇
k
z
>
(
p
)
‍
β
j
=
s
z
k
(
p
)
∀
z
=
1
,
…
,
J
,
(
S
.
d
0
)
β
j
>
0
⟹
j
∈
∇
k
≥
(
p
)
∑
j
∈
∇
k
z
>
(
p
)
‍
}
.Therefore,S
k
0
(
p
) describes the set of sales that maximize the net gain of seller k at p (taking into account the market constraints).12 Observe that the set of sales described by each element in S
k
0
(
p
) gives, to seller k, the same net gain; namely, k is indifferent among all sales in S
k
0
(
p
).To define the demand of buyeri
∈
ℬ, we will need the following notation. Let p
∈
ℝ
+
G be a price vector and let(45)
∇
i
1
>
(
p
)
=
{
j
∈
𝒢
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}
,
∇
i
2
>
(
p
)
=
{
j
∈
𝒢
∖
∇
i
1
>
(
p
)
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
∖
∇
i
1
>
(
p
)
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}
,
⋮
∇
i
z
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
i
m
>
(
p
)
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
z
-
1
∇
i
m
>
(
p
)
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}
,
⋮
∇
i
J
>
(
p
)
=
{
j
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
i
m
>
(
p
)
∣
v
i
j
-
p
j
=
max
⁡
j
′
∈
𝒢
∖
⋃
m
=
1
J
-
1
∇
i
m
>
(
p
)
⁡
{
v
i
j
′
-
p
j
′
}
>
0
}be the sets of goods that give to buyeri a strictly positive net valuation at p, ordered in such a way that goods in ∇
i
z
> give a larger net valuation than goods in ∇
i
z
′
> if and only if z
<
z
′. Obviously, for some p, the set ∇
i
z
>
(
p
) may be empty from some z onwards.Now we define(46)
d
1
i
(
p
)
=
min
⁡
{
d
i
,
∑
j
∈
∇
i
1
>
(
p
)
‍
Q
j
}
,
d
2
i
(
p
)
=
min
⁡
{
d
i
-
d
1
i
(
p
)
,
∑
j
∈
∇
i
2
>
(
p
)
‍
Q
j
}
,
⋮
d
z
i
(
p
)
=
min
⁡
{
d
i
-
∑
m
=
1
z
-
1
‍
d
m
i
(
p
)
,
∑
j
∈
∇
i
z
>
(
p
)
‍
Q
j
}
,
⋮
d
J
i
(
p
)
=
min
⁡
{
d
i
-
∑
m
=
1
J
-
1
‍
d
m
i
(
p
)
,
∑
j
∈
∇
i
J
>
(
p
)
‍
Q
j
}
.
Obviously, for some p, we may have d
z
i
(
p
)
=
0 from some z onwards. Also, for all p
∈
ℝ
+
G and all i
∈
ℬ,
(47)
∇
i
z
>
(
p
)
⊆
∇
i
≥
(
p
)
,
∀
z
=
1
,
…
,
J
.Demand-0 of Buyer
i
. For each price vector p
=
(
p
j
)
j
∈
𝒢
∈
ℝ
+
G, buyer i demands any feasible amount for the market that maximizes his net valuation at p; namely,(48)
D
i
0
(
p
)
=
{
∑
k
‍
α
=
(
α
j
k
)
(
j
,
k
)
∈
𝒢
×
𝒮
∈
ℤ
G
×
S
∣
(
D
.
a
0
)
α
j
k
≥
0
∀
(
j
,
k
)
∈
𝒢
×
𝒮
,
(
D
.
b
0
)
∑
j
k
‍
α
j
k
≤
d
i
,
(
D
.
c
0
)
∇
i
z
>
(
p
)
≠
∅
⟹
∑
j
∈
∇
i
z
>
(
p
)
‍
∑
k
‍
α
j
k
=
d
z
i
(
p
)
∀
=
1
,
…
,
J
,
(
D
.
d
0
)
∑
k
‍
α
j
k
>
0
⟹
j
∈
∇
i
≥
(
p
)
}
.Thus,D
i
0
(
p
) describes the set of all purchases that maximize the net valuation of buyer i at p, taking into account the aggregate constraints of the market.13 Observe that the set of purchases described by each element in D
i
0
(
p
) give to i the same net valuation; namely, i is indifferent among all purchases in D
i
0
(
p
).Definition 20.
A 0-competitive equilibriumof market M is a pair (
p
,
A
)
∈
ℝ
+
G
×
ℱ
0 such that(E.D0) for alli
∈
ℬ, A
(
i
)
∈
D
i
0
(
p
),
(E.S0) for allk
∈
𝒮, (
∑
i
‍
A
i
j
k
)
j
∈
𝒢
∈
S
k
0
(
p
).In the remaining of this section,t will be an index in {
-
1,0
}. We say that the vector p
∈
ℝ
+
G is at-competitive equilibrium price(or simply at-equilibrium price) of market M if there exists A
∈
ℱ
0 such that (
p
,
A
) is at-competitive equilibrium of M (or simply at-equilibrium). Denote by 𝒫
t the set of allt-equilibrium prices of market M.Fix a price vectorp
∈
ℝ
+
G and a feasible assignment A
∈
ℱ
0. According to (20) and (21), the utility of buyer i
∈
ℬ at (
p
,
A
) is
(49)
u
i
(
p
,
A
)
=
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
,
and the utility of seller k
∈
𝒮 at (
p
,
A
) is
(50)
w
k
(
p
,
A
)
=
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
.Definition 21.
LetM be a market and t
∈
{
-
1,0
}. The set oft-competitive equilibrium payoffs is given by
(51)
𝒞
ℰ
t
=
{
(
u
,
w
)
∈
ℝ
B
×
ℝ
S
∣
(
u
,
w
)
=
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
for
some
t
-equilibrium
(
p
,
A
)
ℝ
B
×
ℝ
S
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
}
.We now define a cooperative game with transferable utility that will allow us to draw conclusions about𝒫
t and 𝒞
ℰ
t, for t
=
-
1,0, similarly as we did for 𝒟
t and 𝒢
𝒮
t, for t
=
1,2
,
3.Definition 22.
LetM be a market. A pair (
A
B
,
A
S
)
∈
ℤ
+
B
×
G
×
S
×
ℤ
+
B
×
G
×
S is -1-compatible in M if,(i)
for eachi
∈
ℬ, ∑
j
k
‍
A
i
j
k
B
≤
d
i,
(ii)
for eachk
∈
𝒮 and j
∈
𝒢, ∑
i
‍
A
i
j
k
S
≤
q
j
k.The set of pairs -1-compatible in M will be denoted by ℱ
-
1. Moreover, and with an abuse of notation, we will denote by ℱ
0
=
{
(
A
,
A
)
∣
(
A
,
A
)
∈
ℱ
-
1
} the set of 0-compatible assignments in M.14Definition 23.
LetM be a market, t
∈
{
-
1,0
}, p
∈
ℝ
+
G a price vector, C
⊂
ℬ
∪
𝒮 a coalition, and (
A
B
,
A
S
)
∈
ℱ
t. Define thenet gain for
C
at
(
A
B
,
A
S
)
according to
p by
(52)
φ
M
(
C
,
(
A
B
,
A
S
)
,
p
)
=
∑
i
∈
ℬ
C
‍
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
B
+
∑
k
∈
𝒮
C
‍
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
S
.Note that if(
A
,
A
)
∈
ℱ
0, then φ
M
(
C
,
(
A
,
A
)
,
p
)
=
ϕ
M
(
C
,
A
,
p
), where ϕ
M is given by (10) after setting, for all j
∈
𝒢, Γ
i
j
k
=
p
j for all (
i
,
k
)
∈
ℬ
×
𝒮. For each price vector p, we can define the following associated games to market M.Definition 24.
LetM be a market, t
=
{
-
1,0
}, and p a price vector. Thecooperative game
(
ℬ
∪
𝒮
,
v
t
p
)
with transferable utility associated with
t
and
p is defined as follows:
(53)
v
t
p
(
C
)
=
{
max
⁡
(
A
B
,
A
S
)
∈
ℱ
t
⁡
φ
M
(
C
,
(
A
B
,
A
S
)
,
p
)
if
C
⊊
ℬ
∪
𝒮
T
M
if
C
=
ℬ
∪
𝒮
.We denote by𝒞
t
p
(
M
) (or simply by 𝒞
t
p) the Core of the game (
ℬ
∪
𝒮
,
v
t
p
). We now see that these Cores are intimately related with the corresponding notions of competitive equilibria.Theorem 25.
LetM be a market and t
=
{
-
1,0
}. Then,
(54)
p
∈
𝒫
t
i
f
f
𝒞
t
p
≠
∅
.To prove Theorem25 we need the following two results.Lemma 26.
LetM be a market and t
=
{
-
1,0
}. Then, (
p
,
A
) is at-equilibrium if and only if, for all (
A
B
,
A
S
)
∈
ℱ
t,
(55)
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
≥
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
B
,
∀
i
∈
ℬ
,
(56)
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
≥
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
S
,
∀
k
∈
𝒮
.Proof.
See the Appendices.Parallel to Proposition14, we now have Proposition 27.Proposition 27.
LetM be a market, t
=
{
-
1,0
} and p
∈
ℝ
+
G a price vector. Then,
(57)
𝒞
t
p
≠
∅
i
f
f
𝒞
t
p
=
{
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∣
A
∈
ℱ
}
.Proof.
It is similar to the proof of Proposition14 and therefore it is omitted.Proof of Theorem25.
Assumep
∈
𝒫
t and let A be such that (
p
,
A
) is at-equilibrium. Then, by the definition of v
t
p and Lemma 26, (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. To see that the other implication holds, let p be such that 𝒞
t
p
≠
∅ and let ∈
ℱ. By Proposition 27, (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. Hence, for all (
A
B
,
A
S
)
∈
ℱ
t,
(58)
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
≥
∑
j
k
‍
(
v
i
j
-
p
j
)
·
A
i
j
k
B
,
∀
i
∈
ℬ
,
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
≥
∑
i
j
‍
(
p
j
-
r
j
k
)
·
A
i
j
k
S
,
∀
k
∈
𝒮
.
Thus, by Lemma 26, (
p
,
A
) is at-equilibrium and, hence, p
∈
𝒫
t.It is easy to check that, for allp
∈
ℝ
+
G,
(59)
v
-
1
p
(
C
)
≥
v
0
p
(
C
)
,
∀
C
⊊
ℬ
∪
𝒮
,
v
-
1
p
(
ℬ
∪
𝒮
)
=
v
0
p
(
ℬ
∪
𝒮
)
hold. Hence, 𝒞
-
1
p
⊂
𝒞
0
p, for all p
∈
ℝ
+
G. Thus, by Theorem 25, the following result holds.Corollary 28.
LetM be a market. Then, ∅
≠
𝒫
-
1
⊊
𝒫
0.Proof.
Jaume et al. [12] show that ∅
≠
𝒫
-
1. The inclusion follows from Theorem 25, (59). The strict inclusion follows from Example 29 below.Example 29.
LetM
=
(
ℬ
,
𝒢
,
𝒮
,
V
,
d
,
R
,
Q
) be a market where B
=
{
1,2
}, G
=
{
1,2
}, S
=
{
1
}, V
=
(
6
4
7
0
), d
=
(
7,5
) Q
=
(
8,4
), and R
=
(
5,2
). The unique optimal assignment is A
=
(
3
4
5
0
). Consider the price vector p
=
(
5,2
). Then, v
0
p
(
{
b
1
,
b
2
,
s
1
}
)
=
T
(
A
)
=
1
·
3
+
2
·
4
+
2
·
5
=
21
,
v
0
p
(
{
b
1
,
s
1
}
)
=
1
·
3
+
2
·
4
=
11,v
0
p
(
{
b
2
,
s
1
}
)
=
2
·
5
=
10, v
0
p
(
{
s
1
}
)
=
0
,
v
0
p
(
{
b
1
}
)
=
1
·
3
+
2
·
4
=
11
,
v
0
p
(
{
b
2
}
)
=
2
·
5
=
10. Thus, (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
=
(
11,10,0
)
∈
C
0
p and, hence, (
5,2
)
∈
𝒫
0. But (
5,2
)
∉
𝒫
-
1, since at p
=
(
5,2
) buyer b
1 would demand 7 units of good 2.The next proposition follows immediately from Lemma26 and the fact that if A
^
∈
ℱ
0, then (
A
^
,
A
^
)
∈
ℱ
t, for all t
∈
{
-
1,0
}.Proposition 30.
LetM be a market and t
∈
{
-
1,0
}. Then, (
p
,
A
) is at-equilibrium if and only if p
∈
𝒫
t and A
∈
ℱ.15A result, similar to Theorem13 for group stable sets, holds for the sets of competitive equilibrium payoffs.Theorem 31.
LetM be a market. Then, for t
∈
{
-
1,0
},16
(60)
𝒞
ℰ
t
=
⋃
p
∈
ℝ
+
G
‍
𝒞
t
p
.Proof.
That𝒞
ℰ
t
⊂
⋃
p
∈
ℝ
+
G
‍
𝒞
t
p holds follows from Theorem 25 and Propositions 27 and 30. To see that the other inclusion holds, let (
u
,
w
)
∈
⋃
p
∈
ℝ
+
G
‍
𝒞
t
p. By Proposition 27, there exists (
p
,
A
)
∈
ℝ
+
G
×
ℱ such that (
u
,
w
)
=
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. Hence, by Lemma 26 and Theorem 25, (
u
,
w
)
∈
𝒞
ℰ
t.Corollary 32.
LetM be a market. Then, ∅
≠
𝒞
ℰ
-
1
⊊
𝒞
ℰ
0.Proof.
Jaume et al. [12] show that ∅
≠
𝒞
ℰ
-
1. The inclusion follows from Theorem 31, (59). Example 29 below shows that the inclusion may be strict.Example
2
9 (continued). We already saw that p
=
(
5,2
)
∈
𝒫
0
∖
𝒫
-
1. Hence, (
11,10,0
)
∈
C
0
p and (
11,10,0
)
∈
𝒞
ℰ
0. Moreover, we have that (
u
(
p
*
,
A
)
,
w
(
p
*
,
A
)
)
=
(
11,10,0
) if and only if p
*
=
(
5,2
). But since (
5,2
)
∉
𝒫
-
1, (
11,10,0
)
∉
𝒞
ℰ
-
1. Namely, 𝒞
ℰ
-
1
⊊
𝒞
ℰ
0.


## 4.2. Cartesian Product Structure and Computation of Competitive Equilibria

We have already seen that fort
∈
{
-
1,0
} the set 𝒞
ℰ
t is a Cartesian product in the following sense:
(61)
𝒞
ℰ
t
=
{
(
u
,
w
)
∈
ℝ
B
×
S
∣
for
some
(
p
,
A
)
∈
𝒫
t
×
ℱ
,
(
u
,
w
)
=
(
u
(
p
,
A
)
,
w
(
p
,
A
)
)
ℝ
B
×
S
}
.Now, parallel to Lemma16, the following result holds.Lemma 33.
LetM be a market, t
∈
{
-
1,0
}, and p
∈
ℝ
+
G a price vector. If 𝒞
t
p
≠
∅, then (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
=
(
u
(
p
,
A
′
)
,
w
(
p
,
A
′
)
) for all pairs A
,
A
′
∈
ℱ.Proof.
The proof proceeds similarly to the proof of Proposition14, using the fact that if A
∈
ℱ, then (
A
,
A
)
∈
ℱ
t for t
∈
{
-
1,0
}.Thus, if𝒞
t
p
≠
∅ and A
∈
ℱ, we will write (
u
(
p
,
A
)
,
w
(
p
,
A
)
) simply by (
u
(
p
)
,
w
(
p
)
), without any reference to A. We present this fact in the following corollary.Corollary 34.
LetM be a market and t
∈
{
-
1,0
}. Then, 𝒞
ℰ
t
=
{
(
u
(
p
)
,
w
(
p
)
)
∣
p
∈
𝒫
t
}.Parallel to Proposition14, we present several necessary and sufficient conditions for 𝒞
t
p
≠
∅ (one of them can be used to check whether or not p belongs to 𝒫
t). Observe that the condition
(62)
v
t
p
(
C
)
≤
∑
i
∈
ℬ
C
‍
v
t
p
(
{
i
}
)
+
∑
k
∈
𝒮
C
‍
v
t
p
(
{
k
}
)
,
∀
C
⊂
ℬ
∪
𝒮
,
is trivially satisfied for t
∈
{
-
1,0
}.FixA
∈
ℱ and consider the system on p of lineal inequalities given by
(63)
φ
M
(
C
,
(
A
B
,
A
S
)
,
p
)
≤
φ
M
(
C
,
(
A
,
A
)
,
p
)
,
∀
C
⊂
ℬ
∪
𝒞
with
#
C
=
1
,
∀
(
A
B
,
A
A
)
∈
ℱ
t
.Proposition 35.
LetM be a market, t
∈
{
-
1,0
}, and p
∈
ℝ
+
G a price vector. Then, the following statements are equivalent.(i)
p
is a
t
-equilibrium price.
(ii)
𝒞
t
p
≠
∅.
(iii)
(64)
v
t
p
(
ℬ
∪
𝒮
)
=
∑
i
∈
ℬ
‍
v
t
p
(
{
i
}
)
+
∑
k
∈
𝒮
‍
v
t
p
(
{
k
}
)
.
(iv)
There exists
A
∈
ℱ
such that
v
t
p
(
C
)
=
φ
M
(
C
,
(
A
,
A
)
,
p
),
for all
C
⊂
ℬ
∪
𝒮
with
#
C
=
1.
(v)
For all
A
∈
ℱ
,
v
t
p
(
C
)
=
φ
M
(
C
,
(
A
,
A
)
,
p
)
for all
C
⊂
ℬ
∪
𝒮
with
#
C
=
1.
(vi)
p
solves system (63).Proof.
The equivalence between (i) and (ii) follows from Theorem25. The equivalence between (iv) and (vi) is immediate. That (iii) implies (ii) follows from the fact that (
v
t
p
(
{
i
}
)
,
v
t
p
(
{
k
}
)
(
i
,
k
)
∈
ℬ
∪
𝒮
∈
𝒞
t
Γ
). That (iv) implies (iii) follows easily from the definition v
t
p. That (v) implies (iv) is also immediate. Hence, it only remains to be proved that (ii) implies (v).
Assume𝒞
t
p
≠
∅. By Proposition 14, if A
∈
ℱ, then (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
∈
𝒞
t
p. Hence,
(65)
u
i
(
p
)
≥
v
t
p
(
{
i
}
)
,
∀
i
∈
ℬ
,
w
k
(
p
)
≥
v
t
p
(
{
k
}
)
,
∀
k
∈
𝒮
.
By the definition of v
t
p,
(66)
φ
M
(
{
i
}
,
(
A
,
A
)
,
p
)
=
u
i
(
p
,
A
)
=
v
t
p
(
{
i
}
)
,
∀
i
∈
ℬ
,
φ
M
(
{
k
}
,
(
A
,
A
)
,
p
)
=
w
k
(
p
,
A
)
=
v
t
p
(
{
k
}
)
,
∀
k
∈
𝒮
.The above proposition gives criteria and procedures to compute price vectors in𝒫
t and therefore payoff vectors in 𝒞
ℰ
t.


## 5. Comparison and Relationships among Solutions

Our notation will enable us to compare the solutions and to show how the group stability notions, the notions of competitive equilibria, and the Core of a market are related. We first observe that, for allC
⊂
ℬ
∪
𝒮,
(67)
ℱ
𝒞
(
C
)
×
ℱ
𝒞
(
C
)
⊂
ℱ
3
(
C
)
×
ℱ
3
(
C
)
⊂
ℱ
2
(
C
)
×
ℱ
2
(
C
)
⊂
ℱ
1
(
C
)
×
ℱ
1
(
C
)
⊂
ℱ
0
⊂
ℱ
-
1
.
Moreover, if (
A
,
A
)
∈
ℱ
t
(
C
)
×
ℱ
t
(
C
), then φ
M
(
C
,
(
A
,
A
)
,
p
)
=
ϕ
M
(
C
,
A
,
p
). Hence, for all p and all C
⊊
ℬ
∪
𝒮,
(68)
v
(
C
)
≤
v
3
p
(
C
)
≤
v
2
p
(
C
)
≤
v
1
p
(
C
)
≤
v
0
p
(
C
)
≤
v
-
1
p
(
C
)
,
v
(
ℬ
∪
𝒮
)
=
v
3
p
(
ℬ
∪
𝒮
)
=
v
2
p
(
ℬ
∪
𝒮
)
=
v
1
p
(
ℬ
∪
𝒮
)
=
v
0
p
(
ℬ
∪
𝒮
)
=
v
-
1
p
(
ℬ
∪
𝒮
)
.
Thus, for all p,
(69)
𝒞
⊃
𝒞
3
p
⊃
𝒞
2
p
⊃
𝒞
1
p
⊃
𝒞
0
p
⊃
𝒞
-
1
p
,
and, therefore,
(70)
if
𝒞
t
′
p
≠
∅
,
then
𝒞
t
p
=
𝒞
t
′
p
for
t
≥
t
′
.
It is easy to describe markets for which there exists p such that C
1
p
≠
∅ and C
0
p
=
∅.Now, we state a result showing that the set of payoffs associated with all six solutions are nonempty and have a strictly nested structure.Theorem 36.
LetM be a market. Then,
(71)
∅
≠
𝒞
ℰ
-
1
⊊
𝒞
ℰ
0
⊊
𝒢
𝒮
1
⊊
𝒢
𝒮
2
⊊
𝒢
𝒮
3
⊊
𝒞
.Proof.
By Corollary32, (13), Theorems 13 and 31, and (69) it only remains to be proven that the inclusion of 𝒞
ℰ
0 in 𝒢
𝒮
1 is strict. But Example 29 below will show that.Example
2
9 (continued). Consider p
=
(
5,4
). Then, v
1
p
(
{
b
1
,
s
1
}
)
=
11, v
1
p
(
{
b
2
,
s
1
}
)
=
18, v
1
p
(
{
s
1
}
)
=
8
,
v
1
p
(
{
b
1
}
)
=
3
,
v
1
p
(
{
b
2
}
)
=
10. Hence, (
u
(
p
,
A
)
,
w
(
p
,
A
)
)
=
(
3,10,8
)
∈
C
1
p. Thus, (
3,10,8
)
∈
𝒢
𝒮
1. But p
∉
𝒫
0, since b
1 would demand 8 units of good 1. Moreover, (
u
(
p
*
,
A
)
,
w
(
p
*
,
A
)
)
=
(
3,10,8
) if and only if p
*
=
(
5,4
). That is, (
3,10,8
)
∉
𝒞
ℰ
0.Massó and Neme [13] show that 𝒞
ℰ
-
1
⊊
𝒢
𝒮
1 using an alternative proof. Moreover, from the inclusion relationships established in Theorem 36 and by Theorems 13 and 31, we observe that all solutions have a similar structure because to compute the payoff vectors in the solutions it is sufficient to identify the appropriated Γ (or p). Namely,
(72)
𝒢
𝒮
t
=
{
(
u
(
Γ
)
,
w
(
Γ
)
)
∣
Γ
∈
𝒟
t
}
for
t
=
1,2
,
3
,
𝒞
ℰ
t
=
{
(
u
(
p
)
,
w
(
p
)
)
∣
p
∈
𝒫
t
}
for
t
=
-
1,0
.By Propositions18 and 35, the elements in 𝒟
t and 𝒫
t are solutions of a system of nonstrict lineal inequalities (the functions ϕ
M and φ
M are lineal and continuous in Γ and p, resp.). Hence, a procedure to compute payoff vectors in 𝒢
𝒮
t and 𝒞
ℰ
t is by solving the respective systems. In addition, the sets of solutions of such systems are convex and closed. Thus, 𝒟
t and 𝒫
t are convex and closed sets. But since the functions (
u
(
Γ
)
,
w
(
Γ
)
) are lineal and continuous in Γ, it follows that 𝒢
𝒮
t and 𝒞
ℰ
t are convex and closed sets. Moreover, 𝒢
𝒮
t and 𝒞
ℰ
t are compact sets since 𝒢
𝒮
t
⊂
𝒞
(
M
) and 𝒞
ℰ
t
⊂
𝒞
(
M
). Thus, the inclusions given in Theorem 36 constitute a chain of nested convex sets.



---

*Source: 190614-2014-04-30.xml*