Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions

Abstract

Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp showed the existence of stable outcomes and competitive equilibria in a model of trading networks under the assumption that all agents’ preferences satisfy a condition called the full substitutes condition. In this paper, we extend their model by using discrete concave utility functions called twisted $\hbox {M}^{\natural }$-concave functions. We show that a valuation function of an agent is twisted $\hbox {M}^{\natural }$-concave if and only if the agent’s preference satisfies the generalized variant of the full substitutes condition. We also show that under the generalized full substitutes condition, there exist stable outcomes and competitive equilibria in the extended model and the set of competitive equilibrium price vectors forms a lattice. In addition, we discuss the connection among competitive equilibria, stability, and efficiency. Finally, we investigate the relationship among stability, strong group stability, and chain stability and verify these three stability concepts are equivalent as long as valuation functions of all agents are twisted $\hbox {M}^{\natural }$-concave.

1 Introduction

The two-sided market model is well known and well studied, with many known results and extensions in such fields as economics, computer science, operations research, and so on. It has also been successfully applied to many real world problems.

All variants and extensions of the two-sided market model stem from two basic models: the stable matching model due to Gale and Shapley [5], and the assignment model due to Shapley and Shubik [21]. These two models differ in that the assignment model allows commodity prices, while the stable matching model does not. There are many extensions and generalizations of these two models, not all of which can be clearly classified as being based on which one; indeed, many can be viewed as common generalizations, and results on one model have been successfully interpreted into results on the other. As our model can be regarded as an extension in the “assignment direction” we will introduce notable generalizations, with emphasis on those based on the assignment model.

We first introduce the stable matching model and extensions which are related to our model. The stable matching model was proposed in 1962 by Gale and Shapley [5]. They introduced the deferred acceptance algorithm by which they proved the existence of stable matchings. Hatfield and Milgrom [11] introduced the concept of contracts, which allows discrete prices to be implicitly considered. They showed that under the condition called the substitutes condition, stable outcomes always exist and that they form a lattice structure. Ostrovsky [19] further generalized the Hatfield–Milgrom model by extending the two-sidedness to general acyclic digraphs, and introduced two new conditions, which he called same side substitutability (SSS) and cross side complementarity (CSC). He showed the existence of chain stable allocations when these conditions are satisfied.

We now turn to the assignment model and its extensions. The assignment model was proposed by Shapley and Shubik [21] in a game-theoretic setting. They proved the nonemptiness of the core and showed that the core has a lattice structure. Sotomayor [23] extended this result to the multiple-partners assignment model. Kelso and Crawford [13] showed the existence of core allocations in the two-sided job matching model, if preferences of firms satisfy the so-called gross substitutes condition.¹ The gross substitutes condition, which is a well known and often prerequisite in economics, says that when the salary of some worker increases, no firms can fire the workers whose salaries do not change. Gul and Stacchetti [6] showed that the gross substitutes condition is equivalent to each of the two conditions called the single improvement condition and the no complementarity condition. In the same way as Ostrovsky [19] extended the two-sided stable matching model to acyclic digraphs, Hatfield et al. [10] generalized the assignment model to general networks. They defined the full substitutes condition and showed that there exists a competitive equilibrium when preferences of all agents satisfy the full substitutes condition. They also studied the relationship between stability and competitive equilibria.

These above models basically consider single-unit trades, that is, all trades are restricted to one unit of commodity. In the stable matching model, trades can be generalized to multi-units by creating duplicate trades, however, as the assignment model explicitly considers commodity prices, this technique does not work. The motivation of our paper is to generalize the model of Hatfield et al. [10] (we call this model the single-unit trading network model) to multi-units. To accomplish this, we believe that the most useful tool at present is discrete convex analysis due to Murota [15, 16].

Discrete convex analysis, which is centered on $\hbox {M}^{\natural }$ and $\hbox {L}^{\natural }$-convexity, has been successfully utilized in various economic models, e.g. [1–3, 14]. In particular, $\hbox {M}^{\natural }$-concavity has many nice properties. For example, Fujishige and Yang [4] showed the equivalence of the gross substitutes condition and $\hbox {M}^{\natural }$-concavity for the unit-trade case. Ikebe and Tamura [12] showed that twisted $\hbox {M}^{\natural }$-concave functions (a variant of $\hbox {M}^{\natural }$-concave functions) satisfy the SSS and CSC conditions proposed by Ostrovsky [19]. Recently, Shioura and Yang [22] considered the auction model, and introduced the generalized gross substitutes and complements (GGSC) condition, which is a generalization of the GSC condition introduced by Sun and Yang [24, 25]. They showed that the GGSC condition is equivalent to twisted $\hbox {M}^{\natural }$-concavity and that under the GGSC condition, a Lyapunov function is a generalized $\hbox {L}^{\natural }$-convex function and the set of Walrasian equilibrium price vectors forms a generalized lattice.

In this paper, we introduce the multi-unit trading network model which is a generalization of the single-unit trading network model of Hatfield et al. [10]. In our model, valuation functions of each agent are twisted $\hbox {M}^{\natural }$-concave functions defined on the set of integer vectors. This allows us to consider multiple units of contracts, which cannot be handled in the single-unit trading network model. We also introduce the generalized full substitutes condition and show that this condition is equivalent to twisted $\hbox {M}^{\natural }$-concavity.

Our main results concern the existence and lattice structure of competitive equilibria. We show that there exists a competitive equilibrium under the generalized full substitutes condition and that the set of competitive equilibrium price vectors forms a lattice. We also consider the relationship among competitive equilibria, stability, and efficiency. Although these concepts are not equivalent, we prove that a competitive equilibrium is stable, and a competitive equilibrium trade vector is efficient. Moreover, we show that we can construct a competitive equilibrium from a stable outcome by changing the price vector. Unlike the single-unit trading network model, there is an obvious gap between competitive equilibria and stable outcomes with respect to price vectors in our model.

We further discuss the relation between the three stability concepts: stability, strong group stability, and chain stability. While these concepts are not equivalent in general, we show that these concepts are equivalent under the generalized full substitutes condition.

The rest of this paper is organized as follows. In Sect. 2, we introduce the multi-unit trading network model and give some preliminaries. In Sect. 3, we review the results on the single-unit trading network model introduced by Hatfield et al. [10]. We define the generalized full substitutes condition in Sect. 4. In Sect. 5, we explain twisted $\hbox {M}^{\natural }$-concave functions and prove that the generalized full substitutes condition is equivalent to twisted $\hbox {M}^{\natural }$-concavity. In Sect. 6, we discuss the existence and lattice structure of competitive equilibria. In Sect. 7, we consider the relationship among competitive equilibria, stability, and efficiency. In Sect. 8, we consider three stability concepts under the generalized full substitutes condition, and in Sect. 9, we give the proofs of the results in Sects. 7 and 8.

2 The multi-unit trading network model

In this section, we introduce our multi-unit trading network model as an extension of the (single-unit) trading network model introduced in [10]. We denote by $\mathbf {R}$ the set of reals and by $\mathbf {Z}$ the set of integers. We also denote by $\mathbf {R}_+$ the set of nonnegative reals and by $\mathbf {Z}_+$ the set of nonnegative integers.

Let I and ${\varOmega }$, respectively, be finite sets of agents and trades. Each agent plays as a buyer or seller in some trades. Each trade t is associated with two agents b(t) and s(t) in I, called the buyer and the seller, respectively. The relationship among the agents can be represented by a directed graph, where each node corresponds to an agent and each arc corresponds to a trade t and goes from the buyer b(t) to the seller s(t). We denote by $\omega _t \in \mathbf {Z}_+$ the number of units of t, and by $p_t\in \mathbf {R}$ the unit price for t. Let $\omega =(\omega _t \mid t \in {\varOmega }) \in \mathbf {Z}^{{\varOmega }}_+$ and $p=(p_t \mid t\in {\varOmega })\in \mathbf {R}^{{\varOmega }}$ be a trade vector and a price vector, respectively. A pair $(\omega , p)$ is called an outcome. For $\omega \in \mathbf {Z}_+^{{\varOmega }}$, we define

$$\begin{aligned} \mathrm {supp}^+(\omega ) = \{t \in {\varOmega }: \omega _t > 0\}. \end{aligned}$$

For $i \in I$, we define

$$\begin{aligned} {\varOmega }_{\rightarrow i}=\{t \in {\varOmega }: b(t)=i \}, \quad {\varOmega }_{i \rightarrow }=\{t \in {\varOmega }: s(t)=i \}, \quad {\varOmega }_i={\varOmega }_{\rightarrow i} \cup {\varOmega }_{i \rightarrow }. \end{aligned}$$

For a subset $T \subseteq {\varOmega }, {\mathrm{ag}}(T)$ represents the set of agents who are involved in trades in T, that is, ${\mathrm{ag}}(T)=\bigcup _{t\in T}\{ b(t), s(t)\}$.

Each agent $i \in I$ has a valuation function $u_i: \mathbf {Z}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ -\infty \}$. We define the effective domain of $u_i$ by

$$\begin{aligned} \mathrm {dom}\, u_i=\{ \omega \in \mathbf {Z}^{{\varOmega }}: u_i(\omega ) \not = -\infty \}. \end{aligned}$$

Throughout this paper, we assume that

$$\begin{aligned} u_i(\omega )=u_i(\omega ^{\prime }) \quad \text{ if }\,\, \omega _t=\omega ^{\prime }_t\quad \hbox { for all }\,\,t \in {\varOmega }_i. \end{aligned}$$

(1)

This assumption means that the value of $u_i$ depends only on trades in ${\varOmega }_i$.

We also assume that

$$\begin{aligned} \mathbf {0} \in \mathrm {dom}\,u_i \subseteq \{\omega \in \mathbf {Z}^{{\varOmega }}: 0 \le \omega _t \le M \,(\forall t \in {\varOmega }_i)\} \end{aligned}$$

(2)

holds for some $M \in \mathbf {Z}_+$. It follows from (2) that $\max \{ u_i(\omega ): \omega \in \mathbf {Z}^{{\varOmega }} \}$ always exists.

The utility function $U: \mathbf {Z}^{{\varOmega }} \times \mathbf {R}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ -\infty \}$ associated with $u_i$ is defined by

$$\begin{aligned} U(\omega , p; u_i)=u_i(\omega )+\sum _{t \in {\varOmega }_{i \rightarrow }}\omega _t \cdot p_t - \sum _{t\in {\varOmega }_{\rightarrow i}} \omega _t \cdot p_t. \end{aligned}$$

The indirect utility function $V: \mathbf {R}^{{\varOmega }} \rightarrow \mathbf {R}$ associated with $u_i$ is defined by

$$\begin{aligned} V(p ; u_i)=\max \{ U(\omega , p ; u_i): \omega \in \mathbf {Z}^{{\varOmega }}\}. \end{aligned}$$

For a price vector p, we define i’s demand correspondence $D(p ; u_i)$ by

$$\begin{aligned} D(p ; u_i)=\mathop {\mathrm{argmax}}\limits \{U(\omega , p ; u_i): \omega \in \mathbf {Z}^{{\varOmega }}\}. \end{aligned}$$

Moreover, for an outcome $(\omega , p)$, we define i’s choice correspondence $C(\omega , p ; u_i)$ by

$$\begin{aligned} C(\omega , p ; u_i) = \mathop {\mathrm{argmax}}\limits \{U(\omega ^{\prime }, p ; u_i): \omega ^{\prime } \le \omega ,\, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}\}. \end{aligned}$$

Since the model is determined by ${\varOmega }$ and $u_i\, (i \in I)$, we represent the model by the pair $({\varOmega }, \{ u_i\}_{i \in I})$, and call it an economy.

We next give definitions of stable outcomes and competitive equilibria. For this, we introduce the concepts of individual rationality and blocking set.

Definition 2.1

An outcome $(\omega , p)$ is said to be individually rational if $\omega \in C(\omega , p ; u_i)$ for all $i\in I$.

Individual rationality means that no agent has an incentive to cancel some trades when taking $\omega$ under the price p.

Definition 2.2

We say that a pair $(z, p^{\prime })$ is a blocking set of $(\omega , p)$ in an economy $({\varOmega }, \{ u_i \}_{i\in I})$ if the following conditions hold:

• 1. $z\in \mathbf {Z}^{{\varOmega }}_+ {\setminus } \{ \mathbf {0}\}$.

• 2. $p^{\prime } \in \mathbf {R}^{{\varOmega }}$ and $p^{\prime }_t=0$ for all $t \in {\varOmega }$ with $t \not \in \mathrm {supp}^+(z)$.

• 3. for all $i \in {\mathrm{ag}}(\mathrm {supp}^+(z))$ and $\omega ^{\prime } \in C(\omega +z, p+p^{\prime } ; u_i)$, we have $\omega ^{\prime }_t=(\omega +z)_t$ for all $t \in \mathrm {supp}^+(z) \cap {\varOmega }_i$.

This definition means that when the number of available units of trade t increases by $z_t$ and the unit price for t changes from $p_t$ to $p_t+p_t^{\prime }$ for all $t \in \mathrm {supp}^+(z)$, each agent $i\in {\mathrm{ag}}(\mathrm {supp}^+(z))$ strictly prefer taking $(\omega +z)_t$ trades for all $t \in \mathrm {supp}^+(z)\cap {\varOmega }_i$, that is, all agents in ${\mathrm{ag}}(\mathrm {supp}^+(z))$ take all additional units of trades. Therefore we regard $(\omega , p)$ as blocked by the pair $(z, p^{\prime })$. The definition implies that if $(z, p^{\prime })$ is a blocking set of $(\omega , p)$, then

$$\begin{aligned} U(\omega ^{\prime }, p+p^{\prime }; u_i) > U(\omega , p+p^{\prime } ; u_i) \end{aligned}$$

holds for all $\omega ^{\prime } \in C(\omega +z, p+p^{\prime } ; u_i)$.

We now define stable outcomes and competitive equilibria in an economy $({\varOmega }, \{ u_i\} _{i\in I})$.

Definition 2.3

An outcome $(\omega , p)$ is stable in an economy $({\varOmega }, \{ u_i \}_{i\in I})$ if the following conditions hold:

• 1. $(\omega , p)$ is individually rational.

• 2. $(\omega , p)$ does not have any blocking sets.

Definition 2.4

An outcome $(\omega , p)$ is said to be a competitive equilibrium in an economy $({\varOmega }, \{ u_i \}_{i\in I})$ if $\omega \in D(p ; u_i)$ for all $i \in I$. The vectors $\omega$ and p are called a competitive equilibrium trade vector and a competitive equilibrium price vector, respectively.

Finally, we give the definition of efficient trade vectors.

Definition 2.5

A trade vector $\omega$ is efficient on $\{u_i\}_{i\in I}$ if

$$\begin{aligned} \sum _{i \in I}u_i(\omega ) \ge \sum _{i\in I}u_i(\omega ^{\prime }) \quad (\forall \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}). \end{aligned}$$

Valuation functions are defined on $\mathbf {Z}^{{\varOmega }}$ in the multi-unit trading network model whereas they are defined on $2^{{\varOmega }}$ in the single-unit trading network model introduced by Hatfield et al. [10]. In the multi-unit trading network model, a vector whose elements are 0 or 1 can be regarded as a subset of trades. In fact, if $\hbox {dom }u_i \subseteq \{0, 1\}^{{\varOmega }}$ for all $i \in I$, the multi-unit trading network model represents the single-unit trading network model in [10] and the definitions of stable outcomes and competitive equilibria in [10] coincide with the above definitions in the multi-unit trading network model.

3 A review of the previous works

As mentioned in the last paragraph in Sect. 2, if $\hbox {dom } u_i \subseteq \{0, 1\}^{{\varOmega }}$ for all $i \in I$, we regard the multi-unit trading network model as the single-unit trading network model. In this section, we describe the results concerning the single-unit trading network model which was shown by Hatfield et al. [10]. First, we explain the definition of the full substitutes condition and the laws of aggregate supply and demand. Let $\chi _{t}$ be the characteristic vector of $t\in {\varOmega }$.

Definition 3.1

([10]) A valuation function $u_i: \{0, 1\}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ - \infty \}$ of agent i satisfies the full substitutes condition if the following conditions hold:

• 1. For any $p \in \mathbf {R}^{{\varOmega }}, t \in {\varOmega }_{i \rightarrow }, \omega \in D(p ; u_i)$, and $\delta > 0$, there exists $\tau \in D(p+\delta \chi _t ; u_i)$ such that

  $$\begin{aligned}&\omega _s \ge \tau _s \quad (\forall s \in {\varOmega }_{i \rightarrow } {\setminus } \{ t\}), \qquad \omega _s \le \tau _s \quad (\forall s \in {\varOmega }_{\rightarrow i}). \end{aligned}$$

• 2. For any $p \in \mathbf {R}^{{\varOmega }}, t \in {\varOmega }_{\rightarrow i}, \omega \in D(p ; u_i)$, and $\delta > 0$, there exists $\tau \in D(p-\delta \chi _t ; u_i)$ such that

  $$\begin{aligned}&\omega _s \ge \tau _s \quad (\forall s \in {\varOmega }_{\rightarrow i} {\setminus } \{ t\}), \qquad \omega _s \le \tau _s \quad (\forall s \in {\varOmega }_{i \rightarrow }). \end{aligned}$$

The first condition in Definition 3.1 says that when the price of $t \in {\varOmega }_{i \rightarrow }$ increases, i’s supply of trades other than t does not increase and i’s demand does not decrease. Similarly, the second condition says that when the price of $t \in {\varOmega }_{\rightarrow i}$ decreases, i’s supply does not decrease and i’s demand of trades other than t does not increase. In other words, agent i views trades in ${\varOmega }_{\rightarrow i}({\varOmega }_{i \rightarrow })$ as substitutes, and a trade in ${\varOmega }_{\rightarrow i}$ and one in ${\varOmega }_{i \rightarrow }$ as complements.

Definition 3.2

([10]) A valuation function $u_i: \{0, 1\}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ - \infty \}$ of agent i satisfies the law of aggregate supply if for every $p \in \mathbf {R}^{{\varOmega }}, t \in {\varOmega }_{i \rightarrow }, \omega \in D(p ; u_i)$, and $\delta > 0$, there exists $\tau \in D(p+\delta \chi _t ; u_i)$ such that

$$\begin{aligned} \sum _{s \in {\varOmega }_{i \rightarrow }}\tau _s -\sum _{s \in {\varOmega }_{i \rightarrow }}\omega _s \ge \sum _{s \in {\varOmega }_{\rightarrow i}}\tau _s -\sum _{s \in {\varOmega }_{\rightarrow i}}\omega _s. \end{aligned}$$

Similarly, $u_i$ satisfies the law of aggregate demand if for every $p \in \mathbf {R}^{{\varOmega }}, t \in {\varOmega }_{\rightarrow i}, \omega \in D(p ; u_i)$, and $\delta > 0$, there exists $\tau \in D(p-\delta \chi _t ; u_i)$ such that

$$\begin{aligned} \sum _{s \in {\varOmega }_{\rightarrow i}}\tau _s -\sum _{s \in {\varOmega }_{\rightarrow i}}\omega _s \ge \sum _{s \in {\varOmega }_{i \rightarrow }}\tau _s -\sum _{s \in {\varOmega }_{i \rightarrow }}\omega _s. \end{aligned}$$

The law of aggregate supply means that when the price of $t \in {\varOmega }_{i \rightarrow }$ increases, the amount of increase of trades in ${\varOmega }_{\rightarrow i}$ does not exceed that of increasing trades in ${\varOmega }_{i \rightarrow }$. Similarly, the law of aggregate demand means that when the price of $t \in {\varOmega }_{\rightarrow i}$ decreases, the amount of increase of trades in ${\varOmega }_{i \rightarrow }$ does not exceed that of increasing trades in ${\varOmega }_{\rightarrow i}$.

The laws of aggregate supply and demand were first introduced by Hatfield and Kominers [9] and Hatfield et al. [10] applied these concepts to the single-unit trading network model. For the above conditions, the following statement holds.

Theorem 3.1

([10]) If $u_i$ satisfies the full substitutes condition it satisfies the laws of aggregate supply and demand.

Under the full substitutes condition, there exists a competitive equilibrium in the single-unit trading network model.

Theorem 3.2

([10]) Assume that every $u_i: \{0, 1\}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ -\infty \}$ satisfies the full substitutes condition. Then there exists a competitive equilibrium in the economy $({\varOmega }, \{ u_i\}_{i\in I})$.

We now explain the relationship between competitive equilibria and efficiency of trade vectors.

Theorem 3.3

([10]) Let $(\omega , p)$ be a competitive equilibrium in $({\varOmega }, \{ u_i\}_{i\in I})$. Then $\omega$ is efficient on $\{ u_i\}_{i\in I}$, that is,

$$\begin{aligned} \sum _{i \in I}u_i(\omega ) \ge \sum _{i\in I}u_i(\omega ^{\prime }) \quad (\forall \omega ^{\prime } \in \{0, 1\}^{{\varOmega }}). \end{aligned}$$

Theorem 3.4

([10]) Suppose that every $u_i$ satisfies the full substitutes condition and consider the economy $({\varOmega }, \{ u_i\}_{i\in I})$. Then for any competitive equilibrium $(\omega , p)$ and efficient trade vector $\omega ^{\prime }$ on $\{ u_i\}_{i\in I}, (\omega ^{\prime }, p)$ is also a competitive equilibrium. Moreover, the set of competitive equilibrium price vectors forms a lattice, that is, if p and q are competitive equilibrium price vectors, $p \wedge q$ and $p \vee q$ are also competitive equilibrium price vectors where

$$\begin{aligned} (p \wedge q)_t=\min \{ p_t, q_t\},\quad (p \vee q)_t=\max \{ p_t, q_t\}\quad (\forall t \in {\varOmega }). \end{aligned}$$

Finally, we describe the relationship between stable outcomes and competitive equilibria in the single-unit trading network model.

Theorem 3.5

([10]) If an outcome $(\omega , p)$ is a competitive equilibrium in $({\varOmega }, \{u_i \}_{i \in I})$, then it is stable.

Theorem 3.6

([10]) Suppose that every $u_i$ satisfies the full substitutes condition and $(\omega , p)$ is stable in $({\varOmega }, \{u_i \}_{i\in I})$. Then there exists $q \in \mathbf {R}^{{\varOmega }}$ such that $(\omega , q)$ is a competitive equilibrium and $q_t=p_t$ for all $t \in \mathrm {supp}^+(\omega )$.

Theorem 3.6 means that we can construct a competitive equilibrium from a stable outcome by changing prices of trades which are not taken. We see that stable outcomes and competitive equilibria are essentially equivalent in the single-unit trading network model.

4 The generalized full substitutes condition

The full substitutes condition is defined for valuation functions whose effective domains are included in $\{0, 1\}^{{\varOmega }}$. In this section, we consider extending the full substitutes condition to the multi-unit trading network model.

We now introduce the generalized full substitutes condition as a generalization of the full substitutes condition. For a nonempty finite set $S \subseteq \mathbf {Z}^{\varOmega }$, we say that S is a discretely convex set if it satisfies

$$\begin{aligned} \text{ conv }(S) \cap \mathbf {Z}^{{\varOmega }}=S, \end{aligned}$$

where $\text{ conv }(S)$ is the convex hull of S.

Definition 4.1

A valuation function $u_i: \mathbf {Z}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ - \infty \}$ of agent i satisfies the generalized full substitutes condition if the following conditions hold:

• 1. $D(p ; u_i)$ is a discretely convex set for all $p \in \mathbf {R}^{{\varOmega }}$.

• 2. For any $p \in \mathbf {R}^{{\varOmega }}, t \in {\varOmega }_{i \rightarrow }, \omega \in D(p ; u_i)$, and $\delta > 0$, there exists $\tau \in D(p+\delta \chi _t ; u_i)$ such that

  $$\begin{aligned}&\omega _s \ge \tau _s \quad (\forall s \in {\varOmega }_{i \rightarrow } {\setminus } \{ t\}), \qquad \omega _s \le \tau _s \quad (\forall s \in {\varOmega }_{\rightarrow i}), \end{aligned}$$

  (3)
  $$\begin{aligned}&\sum _{s \in {\varOmega }_{i \rightarrow }}\tau _s -\sum _{s \in {\varOmega }_{i \rightarrow }}\omega _s \ge \sum _{s \in {\varOmega }_{\rightarrow i}}\tau _s -\sum _{s \in {\varOmega }_{\rightarrow i}}\omega _s. \end{aligned}$$

  (4)

• 3. For any $p \in \mathbf {R}^{{\varOmega }}, t \in {\varOmega }_{\rightarrow i}, \omega \in D(p ; u_i)$, and $\delta > 0$, there exists $\tau \in D(p-\delta \chi _t ; u_i)$ such that

  $$\begin{aligned}&\omega _s \ge \tau _s \quad (\forall s \in {\varOmega }_{\rightarrow i} {\setminus } \{ t\}), \qquad \omega _s \le \tau _s \quad (\forall s \in {\varOmega }_{i \rightarrow }), \end{aligned}$$

  (5)
  $$\begin{aligned}&\sum _{s \in {\varOmega }_{\rightarrow i}}\tau _s -\sum _{s \in {\varOmega }_{\rightarrow i}}\omega _s \ge \sum _{s \in {\varOmega }_{i \rightarrow }}\tau _s -\sum _{s \in {\varOmega }_{i \rightarrow }}\omega _s. \end{aligned}$$

  (6)

The first condition is equivalent to the condition that $u_i$ is concave-extensible, that is, there exists a concave function $g: \mathbf {R}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ -\infty \}$ such that $g(\omega )=u_i(\omega )$ for all $\omega \in \mathbf {Z}^{\varOmega }$. We see from Definition 4.1 that the generalized full substitutes condition is a natural combination of the full substitutes condition in Sect. 3 and the laws of aggregate supply and demand in Sect. 3.

Obviously, the generalized full substitutes condition implies the full substitutes condition. On the other hand, the converse does not hold in general, while it turns out that the converse holds true for a valuation function $u_i$ with $\mathrm {dom}\,u_i \subseteq \{0, 1\}^{{\varOmega }}$.

5 Twisted $\hbox {M}^{\natural }$-concave functions

In this section, we introduce twisted $\hbox {M}^{\natural }$-concave functions and describe some of their properties. Moreover, we show that a valuation function satisfies the generalized full substitutes condition if and only if it is a twisted $\hbox {M}^{\natural }$-concave function.

The class of twisted $\hbox {M}^{\natural }$-concave functions is a variant of the class of $\hbox {M}^{\natural }$-concave functions introduced by Murota and Shioura [17]. The concept of twisted $\hbox {M}^{\natural }$-concave functions was first introduced by Sun and Yang [24] as GM-concave functions and applied to the single-unit auction model where goods are substitutable or complementary. The result in [24] is extended to the multi-unit auction model by Shioura and Yang [22]. Ikebe and Tamura [12] showed that a twisted $\hbox {M}^{\natural }$-concave function satisfies the SSS and CSC conditions.

Let $N=\{ 1, \dots , n\}$. For a vector $\omega \in \mathbf {Z}^{N}$, we define

$$\begin{aligned} \mathrm {supp}^+(\omega )=\{t \in N : \omega _t > 0\}, \quad \mathrm {supp}^-(\omega )=\{t \in N : \omega _t < 0\}. \end{aligned}$$

For a function $u: \mathbf {Z}^{N} \rightarrow \mathbf {R} \cup \{ -\infty \}$, we define the effective domain $\mathrm {dom} \,u$ by

$$\begin{aligned} \hbox {dom } \,u =\{ \omega \in \mathbf {Z}^N : u(\omega )\not = -\infty \}. \end{aligned}$$

Let $\chi _t \in \{ 0, 1\} ^{N}$ be the characteristic vector of $t\in N$, that is,

$$\begin{aligned} (\chi _t)_s= {\left\{ \begin{array}{ll} 1 &{} \quad \text{ if } \,\,s=t,\\ 0 &{} \quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$

We also consider an element $0 (\not \in N)$ and define $\chi _0=\mathbf {0}$. $\hbox {M}^{\natural }$-concave functions are defined as follows.

Definition 5.1

(Murota and Shioura [17]) A function $u: \mathbf {Z}^{N} \rightarrow \mathbf {R} \cup \{ -\infty \}$ with $\mathrm {dom}\, u \not = \emptyset$ is an $\hbox {M}^{\natural }$ -concave function if for all $\omega , \tau \in \mathrm {dom}\, u$ and $s \in \mathrm {supp}^+(\omega - \tau )$, there exists $t \in \mathrm {supp}^-(\omega - \tau ) \cup \{ 0\}$ such that

$$\begin{aligned} u(\omega )+u(\tau ) \le u(\omega -\chi _s+\chi _t)+u(\tau +\chi _s-\chi _t). \end{aligned}$$

Let W be a subset of N. We define $\text{ twist }(\omega ; W) \in \mathbf {Z}^{N}$ as

$$\begin{aligned} (\text{ twist }(\omega ; W))_t= {\left\{ \begin{array}{ll} \omega _t &{}\quad \text{ if } \,\,t \not \in W,\\ -\omega _t &{}\quad \text{ if } \,\,t \in W. \end{array}\right. } \end{aligned}$$

Definition 5.2

Let W be a subset of N. Then a function $u: \mathbf {Z}^{N} \rightarrow \mathbf {R} \cup \{ -\infty \}$ is a W -twisted $\hbox {M}^{\natural }$ -concave function if there exists an $\hbox {M}^{\natural }$-concave function $\hat{u}: \mathbf {Z}^{N} \rightarrow \mathbf {R} \cup \{ - \infty \}$ such that

$$\begin{aligned} u(\omega )=\hat{u}(\text{ twist }(\omega ; W))\quad (\forall \omega \in \mathbf {Z}^N). \end{aligned}$$

Note that if W is empty, a W-twisted $\hbox {M}^{\natural }$-concave function is an $\hbox {M}^{\natural }$-concave function. Therefore the class of twisted $\hbox {M}^{\natural }$-concave functions contains the class of $\hbox {M}^{\natural }$-concave functions.

Twisted $\hbox {M}^{\natural }$-concave functions are closely related to the full substitutes condition. In fact, Ikebe and Tamura [12] showed that if $\mathrm {dom}\, u_i \subseteq \{ 0, 1\} ^{{\varOmega }}$, an ${\varOmega }_{i \rightarrow }$-twisted $\hbox {M}^{\natural }$-concave function satisfies the full substitutes condition. In this paper, we prove a stronger result.

Theorem 5.1

A valuation function $u_i: \mathbf {Z}^{{\varOmega }} \rightarrow \mathbf {R} \cup \{ -\infty \}$ of agent i satisfies the generalized full substitutes condition if and only if it is an ${\varOmega }_{i \rightarrow }$-twisted $\hbox {M}^{\natural }$-concave function.

Recall that a valuation function $u_i$ satisfies (1). Therefore if $u_i$ is an ${\varOmega }_{i \rightarrow }$-twisted $\hbox {M}^{\natural }$-concave function it is also an A-twisted $\hbox {M}^{\natural }$-concave function where ${\varOmega }_{i\rightarrow } \subseteq A \subseteq {\varOmega }{\setminus } {\varOmega }_{\rightarrow i}$. From here, a valuation function of agent i is simply said to be a twisted $\hbox {M}^{\natural }$-concave function if it is an ${\varOmega }_{i \rightarrow }$-twisted $\hbox {M}^{\natural }$-concave function.

The generalized full substitutes condition is closely related to the generalized gross substitutes and complements (GGSC) condition which was defined by Shioura and Yang [22] in auction theory. They showed that a valuation function satisfies the GGSC condition if and only if it is twisted $\hbox {M}^{\natural }$-concave. In the proof they used the following property, (GGS$\pm$). Let $\hat{u_i}: \mathbf {Z}^{{\varOmega }_i} \rightarrow \mathbf {R} \cup \{-\infty \}$ be a function whose effective domain is bounded.

(GGS $\pm )$

• 1. For all $p \in \mathbf {R}^{{\varOmega }_i}, \tilde{D}(p ; \hat{u_i})$ is a discretely convex set where

  $$\begin{aligned} \tilde{D}(p ; \hat{u_i})=\mathop {\mathrm{argmax}}\limits \left\{ \hat{u}_i(\omega )-\sum _{s\in {\varOmega }_i}p_s\cdot \omega _s : \omega \in \mathbf {Z}^{{\varOmega }_i} \right\} . \end{aligned}$$

• 2. Let $p \in \mathbf {R}^{{\varOmega }_i}, \delta > 0$, and $\omega \in \tilde{D}(p ; \hat{u_i})$.

  • (a) For all $t \in {\varOmega }_{i \rightarrow }$, there exists $\tau \in \tilde{D}(p+\delta \chi _t ; \hat{u}_i)$ such that

    $$\begin{aligned} \tau _s \ge \omega _s \,\, (\forall s \in {\varOmega }_i {\setminus } \{ t \}), \quad \sum _{s \in {\varOmega }_i} \tau _s \le \sum _{s \in {\varOmega }_i} \omega _s. \end{aligned}$$

  • (b) For all $t \in {\varOmega }_{\rightarrow i}$, there exists $\tau \in \tilde{D}(p-\delta \chi _t ; \hat{u}_i)$ such that

    $$\begin{aligned} \tau _s \le \omega _s \,\, (\forall s \in {\varOmega }_i {\setminus } \{ t \}), \quad \sum _{s \in {\varOmega }_i} \tau _s \ge \sum _{s \in {\varOmega }_i} \omega _s. \end{aligned}$$

Theorem 5.2

(Shioura and Yang [22]) A function $\hat{u}_i: \mathbf {Z}^{{\varOmega }_i} \rightarrow \mathbf {R} \cup \{ -\infty \}$ whose effective domain is bounded satisfies (GGS$\pm )$ condition if and only if it is an $\hbox {M}^{\natural }$-concave function.

By Theorem 5.2, we can easily verify that Theorem 5.1 holds.

Finally, we describe some properties of W-twisted $\hbox {M}^{\natural }$-concave functions. These properties are used in the proofs in this paper.

Proposition 5.1

(Murota [16]) Let $u: \mathbf {Z}^N \rightarrow \mathbf {R}\cup \{ -\infty \}$ be a W-twisted $\hbox {M}^{\natural }$-concave function. Then the following statements hold:

• 1. The sum of a W-twisted $\hbox {M}^{\natural }$-concave function and a linear function is W-twisted $\hbox {M}^{\natural }$-concave, that is, for $p \in \mathbf {R}^N,$

  $$\begin{aligned} u(\omega )+\sum _{t\in N} p_t\cdot \omega _t \end{aligned}$$

  is W-twisted $\hbox {M}^{\natural }$-concave.

• 2. For $a, b \in (\mathbf {Z}\cup \{ \pm \infty \})^N$ with $a \le b,$

  $$\begin{aligned} u_{[a, b]}(\omega )= {\left\{ \begin{array}{ll} u(\omega ) &{}\quad \hbox {if }\,a_t \le \omega _t \le b_t\quad \hbox { for all }t \in N,\\ -\infty &{} \quad \hbox {otherwise,} \end{array}\right. } \end{aligned}$$

  is W-twisted $\hbox {M}^{\natural }$-concave.

• 3. For $A \subseteq N$, define $u^A: \mathbf {Z}^A \rightarrow \mathbf {R} \cup \{ -\infty \}$ as

  $$\begin{aligned} u^A(\sigma )=\sup \{ u(\omega ): \omega _t=\sigma _t \, (\forall t\in A),\, \omega \in \mathbf {Z}^{N} \}. \end{aligned}$$

  If $u^A(\sigma ) < + \infty$ for all $\sigma \in \mathbf {Z}^A, u^A$ is $(W\cap A)$-twisted $\hbox {M}^{\natural }$-concave.

6 Existence and lattice structure of competitive equilibria

In this section, we show the existence of competitive equilibria and discuss the structure of the set of competitive equilibrium price vectors under the generalized full substitutes condition for each $u_i$, which is equivalent to twisted $\hbox {M}^{\natural }$-concavity by Theorem 5.1. Since the concept of twisted $\hbox {M}^{\natural }$-concave function is a variant of $\hbox {M}^{\natural }$-concave function, the existing results for $\hbox {M}^{\natural }$-concave function in discrete convex analysis can be applied to derive the results in this section.

First, we show the existence of competitive equilibria.

Theorem 6.1

Suppose that every $u_i$ satisfies the generalized full substitutes condition, that is, $u_i$ is twisted $\hbox {M}^{\natural }$-concave for all $i \in I$. Then there exists a competitive equilibrium in the economy $({\varOmega }, \{ u_i\}_{i\in I})$.

To prove Theorem 6.1, we use the following property of the sum of $\hbox {M}^{\natural }$-concave functions.

Theorem 6.2

(Murota [16]) For $\hbox {M}^{\natural }$-concave functions $f_1, f_2: \mathbf {Z}^{N} \rightarrow \mathbf {R} \cup \{-\infty \}$ and $\omega ^{*} \in \mathrm {dom}\, f_1 \cap \mathrm {dom}\, f_2$, we have

$$\begin{aligned} f_1(\omega ^*)+f_2(\omega ^*) \ge f_1(\omega )+f_2(\omega ) \end{aligned}$$

for all $\omega \in \mathbf {Z}^{N}$ if and only if there exists $p^* \in \mathbf {R}^{N}$ such that

$$\begin{aligned} f_1(\omega ^*)-\sum _{t\in N} \omega ^*_t \cdot p^*_t&\ge f_1(\omega )-\sum _{t\in N} \omega _t \cdot p^*_t\quad (\forall \omega \in \mathbf {Z}^{N}),\\ f_2(\omega ^*)+\sum _{t\in N} \omega ^*_t \cdot p^*_t&\ge f_2(\omega )+\sum _{t\in N} \omega _t \cdot p^*_t\quad (\forall \omega \in \mathbf {Z}^N). \end{aligned}$$

We now prove Theorem 6.1.

Proof

First, we split each trade $t \in {\varOmega }$ into two trades $t_b$ and $t_s$, and define

$$\begin{aligned} \tilde{{\varOmega }} = \bigcup _{t \in {\varOmega }}\{ t_b, t_s \}, \qquad \tilde{{\varOmega }}_i=\{ t_b : t\in {\varOmega }_{\rightarrow i}\} \cup \{t_s : t \in {\varOmega }_{i \rightarrow }\} \quad (i \in I). \end{aligned}$$

Since there are exactly one buyer and one seller for each trade $t \in {\varOmega }$, it follows that $\tilde{{\varOmega }}_j \cap \tilde{{\varOmega }}_k=\emptyset$ if $j \not =k$.

For $i\in I$, we construct a function $\tilde{u}_i: \mathbf {Z}^{\tilde{{\varOmega }}_i} \rightarrow \mathbf {R} \cup \{ -\infty \}$ which satisfies

$$\begin{aligned} \tilde{u}_i(\tilde{\omega })=u_i(T_i(\tilde{\omega })) \quad (\forall \tilde{\omega } \in \mathbf {Z}^{\tilde{{\varOmega }}_i}), \end{aligned}$$

where $T_i(\tilde{\omega }) \in \mathbf {Z}^{{\varOmega }}$ is defined by

$$\begin{aligned} (T_i(\tilde{\omega }))_t= {\left\{ \begin{array}{ll} \tilde{\omega }_{t_b} &{}\quad \text{ if } \quad t\in {\varOmega }_{\rightarrow i},\\ -\tilde{\omega }_{t_s} &{}\quad \text{ if } \quad t\in {\varOmega }_{i \rightarrow },\\ \text{ arbitrary } &{}\quad \text{ if } \quad t \not \in {\varOmega }_i. \end{array}\right. } \end{aligned}$$

By (1), $\tilde{u}_i$ is well defined. By its definition, $\tilde{u}_i$ is an $\hbox {M}^{\natural }$-concave function. Let $u: \mathbf {Z}^{\tilde{{\varOmega }}} \rightarrow \mathbf {R} \cup \{ -\infty \}$ be defined by

$$\begin{aligned} u(\tilde{\omega })=\sum _{i\in I}\tilde{u}_i (\tilde{\omega }^{\tilde{{\varOmega }}_i}) \quad (\tilde{\omega } \in \mathbf {Z}^{\tilde{{\varOmega }}}), \end{aligned}$$

(7)

where $\tilde{\omega }^{\tilde{{{\varOmega }}_i}}$ is the restriction of $\tilde{\omega }$ on $\tilde{{{\varOmega }}_i}$. As $\tilde{{\varOmega }}_j \cap \tilde{{\varOmega }}_k = \emptyset$ for all $j, k \in I$ with $j \not =k, u$ is also an $\hbox {M}^{\natural }$-concave function. We further define $f: \mathbf {Z}^{\tilde{{\varOmega }}} \rightarrow \mathbf {R} \cup \{ -\infty \}$ by

$$\begin{aligned} f(\tilde{\omega })= {\left\{ \begin{array}{ll} 0 &{}\quad \hbox {if }~\tilde{\omega }_{t_b}+\tilde{\omega }_{t_s} = 0\quad \hbox { for all }t\in {\varOmega },\\ -\infty &{}\quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$

(8)

It is easy to check that f is an $\hbox {M}^{\natural }$-concave function.

Since $\mathbf {0} \in \mathrm {dom}\,u \cap \mathrm {dom}\, f$ and $\mathrm {dom}\,u$ is bounded, there exists a maximizer of $u+f$. Let $\tilde{\omega }^*$ be such a maximizer. By Theorem 6.2, there exists $\tilde{p}^* \in \mathbf {R}^{\tilde{{\varOmega }}}$ such that

$$\begin{aligned} u(\tilde{\omega }^*)-\sum _{k \in \tilde{{\varOmega }}} \tilde{\omega }^*_k \cdot \tilde{p}^*_k&\ge u(\tilde{\omega })- \sum _{k\in \tilde{{\varOmega }}} \tilde{\omega }_k \cdot \tilde{p}^*_k \quad (\forall \tilde{\omega } \in \mathbf {Z}^{\tilde{{\varOmega }}}), \end{aligned}$$

(9)

$$\begin{aligned} f(\tilde{\omega }^*)+\sum _{k \in \tilde{{\varOmega }}} \tilde{\omega }^*_k \cdot \tilde{p}^*_k&\ge f(\tilde{\omega })+ \sum _{k\in \tilde{{\varOmega }}} \tilde{\omega }_k \cdot \tilde{p}^*_k \quad (\forall \tilde{\omega } \in \mathbf {Z}^{\tilde{{\varOmega }}}). \end{aligned}$$

(10)

By the definition of f, we have $\tilde{\omega }^*_{t_b}+\tilde{\omega }^*_{t_s}=0$ for all $t \in {\varOmega }$. We claim $\tilde{p}^*_{t_b}= \tilde{p}^*_{t_s}$ for all $t \in {\varOmega }$. If $\tilde{p}^*_{t_b} > \tilde{p}^*_{t_s}$ for some $t \in {\varOmega }$, we have

$$\begin{aligned} f(\tilde{\omega }^*+\chi _{t_b}-\chi _{t_s})+\sum _{k \in \tilde{{\varOmega }}} (\tilde{\omega }^*+\chi _{t_b}-\chi _{t_s})_k \cdot \tilde{p}^*_k > f(\tilde{\omega }^*)+\sum _{k \in \tilde{{\varOmega }}} \tilde{\omega }^*_k \cdot \tilde{p}^*_k. \end{aligned}$$

This contradicts (10). Similarly, $\tilde{p}^*_{t_b} < \tilde{p}^*_{t_s}$ for some $t \in {\varOmega }$ also leads to a contradiction. Therefore $\tilde{\omega }^*_{t_b}+\tilde{\omega }^*_{t_s}=0$ and $\tilde{p}^*_{t_b} = \tilde{p}^*_{t_s}$ for all $t \in {\varOmega }$.

We define $\omega ^* \in \mathbf {Z}^{{\varOmega }}$ and $p^* \in \mathbf {R}^{{\varOmega }}$ by

$$\begin{aligned} \omega ^*_t=\tilde{\omega }^*_{t_b} \, (=-\tilde{\omega }^*_{t_s}),\quad p^*_t=\tilde{p}^*_{t_b} \, (=\tilde{p}^*_{t_s})\quad (\forall t \in {\varOmega }). \end{aligned}$$

Finally, we show that $\omega ^* \in D(p^* ; u_i)$ for all $i \in I$. Since $\tilde{{\varOmega }}_j \cap \tilde{{\varOmega }}_k = \emptyset$ for all distinct $j, k \in I$, it holds that

$$\begin{aligned} \sum _{i \in I}\tilde{u}_i(\tilde{\omega }^{\tilde{{\varOmega }}_i})- \sum _{k\in \tilde{{\varOmega }}} \tilde{\omega }_k \cdot \tilde{p}^*_k&=\sum _{i\in I}\left( \tilde{u}_i(\tilde{\omega }^{\tilde{{\varOmega }}_i})- \sum _{k \in \tilde{{\varOmega }}_i} \tilde{\omega }_k \cdot \tilde{p}^*_k \right) . \end{aligned}$$

This fact and (9) imply that

$$\begin{aligned} \tilde{u}_i(\tilde{\omega }^{*{\tilde{{\varOmega }}_i}})- \sum _{k \in \tilde{{\varOmega }}_i} \tilde{\omega }^*_k \cdot \tilde{p}^*_k \ge \tilde{u}_i(\tilde{\omega }^{\tilde{{\varOmega }}_i})- \sum _{k \in \tilde{{\varOmega }}_i} \tilde{\omega }_k \cdot \tilde{p}^*_k \quad (\forall i \in I,\ \tilde{\omega }^{\tilde{{\varOmega }}_i} \in \mathbf {Z}^{\tilde{{\varOmega }}_i}). \end{aligned}$$

(11)

Moreover, for all $i \in I$ and $\tilde{\omega } \in \mathbf {Z}^{\tilde{{\varOmega }}}$ we have

$$\begin{aligned} \tilde{u}_i(\tilde{\omega }^{\tilde{{\varOmega }}_i})- \sum _{k \in \tilde{{\varOmega }}_i} \tilde{\omega }_k \cdot \tilde{p}^*_k&=u_i(T_i(\tilde{\omega }^{\tilde{{\varOmega }}_i})) +\sum _{t \in {\varOmega }_{i \rightarrow }} (T_i(\tilde{\omega }^{\tilde{{\varOmega }}_i}))_{t}\cdot p^*_t -\sum _{t \in {\varOmega }_{\rightarrow i}}( T_i(\tilde{\omega }^{\tilde{{\varOmega }}_i}))_{t}\cdot p^*_t\nonumber \\&=U(T_i(\tilde{\omega }^{\tilde{{\varOmega }}_i}), p^* ; u_i). \end{aligned}$$

(12)

From (11) and (12), it follows that

$$\begin{aligned} U(\omega ^*, p^*; u_i) \ge U(\omega , p^*; u_i)\quad (\forall \omega \in \mathbf {Z}^{{\varOmega }}). \end{aligned}$$

Thus $\omega ^* \in D(p^* ; u_i)$ for all $i \in I$, that is, $(\omega ^*, p^*)$ is a competitive equilibrium.

$\square$

The next statement describes the structure of the set of competitive equilibrium price vectors.

Theorem 6.3

Suppose that every $u_i$ satisfies the generalized full substitutes condition and consider the economy $({\varOmega }, \{ u_i\}_{i\in I})$. Then the set of competitive equilibrium price vectors forms a lattice.

To prove Theorem 6.3, we use the concept of polyhedral $\hbox {L}^{\natural }$-convex function.

Definition 6.1

(Murota and Shioura [18], Murota [16]) A function $g: \mathbf {R}^{N} \rightarrow \mathbf {R} \cup \{+\infty \}$ is a polyhedral $\hbox {L}^{\natural }$ -convex function if it is a polyhedral convex function and satisfies

$$\begin{aligned} g(p \wedge (q+\alpha \mathbf {1}))+g((p-\alpha \mathbf {1}) \vee q) \le g(p)+g(q) \end{aligned}$$

for all $p, q \in \mathbf {R}^{N}$ and $\alpha \in \mathbf {R}_+$, where $\mathbf {1}$ is the all-one vector.

Polyhedral $\hbox {L}^{\natural }$-convex functions satisfy the following properties.

Proposition 6.1

(Murota [16]) Let $g_1, g_2: \mathbf {Z}^N \rightarrow \mathbf {R} \cup \{ + \infty \}$ be polyhedral $\hbox {L}^{\natural }$-convex functions. Then $g_1+g_2$ is a polyhedral $\hbox {L}^{\natural }$-convex function.

Proposition 6.2

(Murota and Shioura [18], Murota [16]) The set of minimizers of a polyhedral $\hbox {L}^{\natural }$-convex function forms a lattice.

The concept of $\hbox {L}^{\natural }$-convex function is deeply related to that of $\hbox {M}^{\natural }$-concave function.

Theorem 6.4

(Murota and Shioura [18], Murota [16]) Let $f: \mathbf {Z}^{N} \rightarrow \mathbf {R} \cup \{ -\infty \}$ be an $\hbox {M}^{\natural }$-concave function such that $\mathrm {dom}\, f$ is nonempty and bounded. Then, the function $g: \mathbf {R}^{N} \rightarrow \mathbf {R}\cup \{ -\infty \}$ defined by

$$\begin{aligned} g(p)&= \sup \left\{ f(\omega )-\sum _{t\in N}\omega _t\cdot p_t: \omega \in \mathbf {Z}^N \right\} \end{aligned}$$

is a polyhedral $\hbox {L}^{\natural }$-convex function.

We now prove Theorem 6.3. We roughly describe the idea of the proof. First, we show that $\sum _{i\in I}V(\cdot ; u_i)$ is a polyhedral $\hbox {L}^{\natural }$-convex function (Proposition 6.3). Then we prove that p is a competitive equilibrium price vector if and only if p is a minimizer of $\sum _{i\in I}V(\cdot ; u_i)$ (Proposition 6.5). By using Propositions 6.2, 6.3, and 6.5, we obtain Theorem 6.3.

Proposition 6.3

Suppose that $u_i$ is twisted $\hbox {M}^{\natural }$-concave for all $i \in I$. Then $\sum _{i\in I}V(\cdot ; u_i)$ is a polyhedral $\hbox {L}^{\natural }$-convex function.

Proof

Since the sum of polyhedral $\hbox {L}^{\natural }$-convex functions is also polyhedral $\hbox {L}^{\natural }$-convex (Proposition 6.1), it suffices to show that each $V(\cdot ; u_i)$ is a polyhedral $\hbox {L}^{\natural }$-convex function. It holds that

$$\begin{aligned} V(p; u_i)&=\max \{ U(\omega , p; u_i): \omega \in \mathbf {Z}^{{\varOmega }}\} \\&=\max \left\{ u_i(\omega )+\sum _{t\in {\varOmega }_{i \rightarrow }} \omega _t \cdot p_t-\sum _{t\in {\varOmega }_{\rightarrow i}} \omega _t \cdot p_t : \omega \in \mathbf {Z}^{{\varOmega }}\right\} \\&=\max \left\{ u_i(T_i(\tilde{\omega }))+\sum _{t\in {\varOmega }_{i \rightarrow }}(T_i(\tilde{\omega }))_t\cdot p_t -\sum _{t\in {\varOmega }_{\rightarrow i}}(T_i(\tilde{\omega }))_t\cdot p_t: \tilde{\omega } \in \mathbf {Z}^{\tilde{{\varOmega }}_i} \right\} \\&=\max \left\{ \tilde{u}_i(\tilde{\omega })-\sum _{k\in \tilde{{\varOmega }}_i}\tilde{\omega }_k\cdot \tilde{p}_k: \tilde{\omega } \in \mathbf {Z}^{\tilde{{\varOmega }}_i} \right\} , \end{aligned}$$

where $\tilde{p}_{t_b}=\tilde{p}_{t_s}=p_t$ for all $t \in {\varOmega }$ and $\tilde{u}_i$ is the function defined in the proof of Theorem 6.1. Since $\tilde{u}_i$ is an $\hbox {M}^{\natural }$-concave function, by Theorem 6.4, $V(\cdot ; u_i)$ is a polyhedral $\hbox {L}^{\natural }$-convex function. $\square$

Proposition 6.4

For all $p \in \mathbf {R}^{{\varOmega }}$, we have

$$\begin{aligned} \sum _{i\in I}U(\omega , p; u_i) = \sum _{i \in I}u_i(\omega ). \end{aligned}$$

Proof

It follows that

$$\begin{aligned} \sum _{i \in I} U(\omega , p ; u_i)&=\sum _{i \in I}\left( u_i(\omega ) +\sum _{t \in {\varOmega }_{i \rightarrow }} \omega _t\cdot p_t -\sum _{t \in {\varOmega }_{\rightarrow i}} \omega _t\cdot p_t \right) \\&=\sum _{i \in I} u_i(\omega ) + \sum _{i \in I}\left( \sum _{t \in {\varOmega }_{i \rightarrow }} \omega _t\cdot p_t -\sum _{t \in {\varOmega }_{\rightarrow i}} \omega _t\cdot p_t \right) \\&=\sum _{i \in I}u_i(\omega ). \end{aligned}$$

$\square$

Proposition 6.5

Assume that there exists a competitive equilibrium. Then p is a competitive equilibrium price vector if and only if p is a minimizer of $\sum _{i\in I}V(\cdot ; u_i)$.

Proof

Let $(\omega ^*, p^*)$ be a competitive equilibrium and $p \in \mathbf {R}^{{\varOmega }}$. By the definition of $V(\cdot ; u_i)$, we have

$$\begin{aligned} V(p^* ; u_i)&= U(\omega ^* , p^* ; u_i) \quad (\forall i \in I), \nonumber \\ V(p ; u_i)&\ge U(\omega ^*, p ; u_i)\quad \;\, (\forall i \in I), \end{aligned}$$

(13)

from which follows that

$$\begin{aligned} \sum _{i\in I}V(p ; u_i)&\ge \sum _{i \in I}U(\omega ^*, p ; u_i) \nonumber \\&=\sum _{i \in I} u_i(\omega ^*)\nonumber \\&= \sum _{i \in I} U(\omega ^*, p^* ; u_i)\nonumber \\&=\sum _{i\in I}V(p^* ; u_i), \end{aligned}$$

(14)

where the first and second equalities are by Proposition 6.4. This shows that $p^*$ is a minimizer of $\sum _{i \in I}V(\cdot ; u_i)$.

We then assume that p is a minimizer of $\sum _{i \in I}V(\cdot ; u_i)$. Since $p^*$ is also a minimizer, we have $\sum _{i\in I}V(p ; u_i) = \sum _{i\in I}V(p^* ; u_i)$. Hence, the inequalities in (13) and (14) hold with equality. This implies that $\omega ^* \in D(p ; u_i)$ for all $i\in I$, that is, p is a competitive equilibrium price vector. $\square$

By Propositions 6.2, 6.3, and 6.5, the set of competitive equilibrium price vectors forms a lattice. This concludes the proof of Theorem 6.3.

7 Competitive equilibria, stability, and efficiency

In this section, we discuss the connection among competitive equilibria, stability, and efficiency in the multi-unit trading network model. We generalize most of the results in Sect. 3 concerning the single-unit trading network model, while Theorem 3.6 in Sect. 3 does not admit a generalization, as explained below. Proofs of the results are given in Sect. 9.

We first show a relationship between competitive equilibria and efficiency of trade vectors. The statements of the following two theorems can be regarded as the first and second welfare theorems of economics, respectively.

Theorem 7.1

Let $(\omega , p)$ be a competitive equilibrium in $({\varOmega }, \{ u_i\}_{i\in I})$. Then $\omega$ is efficient on $\{ u_i\}_{i\in I}$.

Theorem 7.2

Let $(\omega , p)$ be a competitive equilibrium in $({\varOmega }, \{ u_i\}_{i\in I})$. For any efficient trade vector $\omega ^{\prime }$ on $\{ u_i\}_{i\in I}, (\omega ^{\prime }, p)$ is also a competitive equilibrium.

Note that no assumptions are required for preferences of agents in the two theorems above.

We next show that a competitive equilibrium is always stable.

Theorem 7.3

If an outcome $(\omega , p)$ is a competitive equilibrium in $({\varOmega }, \{u_i \}_{i \in I})$, then it is stable.

The converse of Theorem 7.3 does not hold, as shown in the following example.

Example 7.1

Consider an economy with two agents, a and b, and only one trade. Agent a is the buyer and agent b is the seller. Valuation functions of each agent are given in Table 1.

We can easily check that $u_a$ and $u_b$ are twisted $\hbox {M}^{\natural }$-concave functions. Thus preferences of all agents satisfy the generalized full substitutes condition. In this example, we can verify that $(\omega , p)=(2, 2)$ is a stable outcome, while (2, 2) is not a competitive equilibrium since

$$\begin{aligned} 2 \not \in D(2; u_b)=\{ 3 \}. \end{aligned}$$

Table 1 The valuations of agents in Example 7.1

We see from Example 7.1 that a stable outcome is not a competitive equilibrium in general, even if preferences of all agents satisfy the generalized full substitutes condition. Moreover, Example 7.1 shows that the following statement, a generalization of Theorem 3.6, does not hold in the multi-unit trading network model:

Statement A    Suppose that every $u_i$ satisfies the generalized full substitutes condition. If an outcome $(\omega , p)$ is stable in $({\varOmega }, \{u_i \}_{i\in I})$, then there exists $q \in \mathbf {R}^{{\varOmega }}$ such that $(\omega , q)$ is a competitive equilibrium and $q_t=p_t$ for all $t \in \mathrm {supp}^+(\omega )$.

This shows an obvious gap between competitive equilibria and stable outcomes with respect to price vectors in the multi-unit trading network model.

On the other hand, it can be shown that stability of an outcome implies efficiency of a trade vector.

Theorem 7.4

Suppose that every $u_i$ satisfies the generalized full substitutes condition. If an outcome $(\omega , p)$ is stable in $({\varOmega }, \{u_i \}_{i\in I})$, then $\omega$ is efficient on $\{u_i \}_{i\in I}$.

By Theorems 7.2 and 7.4, we have the following weaker statement than Statement A.

Corollary 7.1

Suppose that every $u_i$ satisfies the generalized full substitutes condition. If an outcome $(\omega , p)$ is stable in $({\varOmega }, \{u_i \}_{i\in I})$, then there exists $q \in \mathbf {R}^{{\varOmega }}$ such that $(\omega , q)$ is a competitive equilibrium in $({\varOmega }, \{u_i \}_{i\in I})$.

Remark 7.1

We see from Theorem 7.4 that stability of an outcome implies efficiency of a trade vector. The following example shows that the converse does not hold, that is, an outcome $(\omega , p)$ may have a blocking set, even if it is individually rational and $\omega$ is efficient on $\{u_i\}_{i\in I}$.

Example 7.2

Let a, b, and c be three agents, and $t_1$ and $t_2$ be two types of trades such that $b(t_1)=a, s(t_1)=b, b(t_2)=a$, and $s(t_2)=c$. Valuation functions of each agent are given in Table 2. Then $(\omega , p)=((1, 0), (3, 0))$ has a blocking set $(z, p^{\prime })=((0, 1), (0, 2))$ while ((1, 0), (3, 0)) is individually rational and $(t_1, t_2)=(1, 0)$ is efficient on $\{u_i\}_{i\in I}$.

Table 2 The valuations of agents in Example 7.2

8 The relationship among three stability concepts

We extend the concepts of strong group stability and chain stability in the multi-unit trading network model. While these stability concepts are different from the stability defined in Sect. 2 in general, they are equivalent in the case where preferences of all agents satisfy the generalized full substitutes condition. Proofs of the results are given in Sect. 9.

First, we consider the concept of strong group stability, originally introduced by Hatfield et al. [10] in the single-unit trading network model, as a combination of strong stability by Hatfield and Kominers [8] and group stability by Roth and Sotomayor [20].

For $i\in I$, an outcome $(\omega , p), z\in \mathbf {Z}^{{\varOmega }}_+ {\setminus } \{ \mathbf {0} \}$, and $p^{\prime } \in \mathbf {R}^{{\varOmega }}$ we define

$$\begin{aligned}&\Delta (z, p^{\prime } ; u_i, (\omega , p))\\&\quad =\max \{ U(\omega ^{\prime }, p ; u_i): \omega ^{\prime }\le \omega +z, \, \omega ^{\prime }_t=(\omega +z)_t \, (t \in \mathrm {supp}^+(z)) \}\\&\qquad +\sum _{t\in {\varOmega }_{i \rightarrow }}z_t\cdot (p^{\prime }_t-p_t) -\sum _{t\in {\varOmega }_{\rightarrow i}}z_t\cdot (p^{\prime }_t-p_t)-U(\omega , p ; u_i). \end{aligned}$$

The value $\Delta (z, p^{\prime } ; u_i, (\omega , p))$ can be understood as follows: when agent i takes $z_t$ more trades with price $p_t^{\prime }$ for all $t\in \mathrm {supp}^+(z)$ (and may cancel some trades which are not in $\mathrm {supp}^+(z)$) she/he can increase her/his utility by up to $\Delta (z, p^{\prime } ; u_i, (\omega , p))$. The value $\Delta (z, p^{\prime } ; u_i, (\omega , p))$ admits an alternative formulation:

$$\begin{aligned}&\Delta (z, p^{\prime } ; u_i, (\omega , p))\\&\quad =\max \bigg \{ u_i(\omega ^{\prime })+ \sum _{t\in {\varOmega }_{i \rightarrow }}\omega ^{\prime }_t\cdot p_t- \sum _{t\in {\varOmega }_{\rightarrow i}}\omega ^{\prime }_t\cdot p_t:\nonumber \\&\quad \qquad \qquad \quad \omega ^{\prime }\le \omega +z, \, \omega ^{\prime }_t=(\omega +z)_t \, (t \in \mathrm {supp}^+(z)) \bigg \}\\&\qquad +\sum _{t\in {\varOmega }_{i \rightarrow }}z_t\cdot (p^{\prime }_t-p_t) -\sum _{t\in {\varOmega }_{\rightarrow i}}z_t\cdot (p^{\prime }_t-p_t)-U(\omega , p ; u_i). \end{aligned}$$

We now extend the concept of strong group stability in the multi-unit trading network model.

Definition 8.1

Let $(\omega , p)$ be an outcome. A pair $(z, p^{\prime })$ is a strong group blocking set of $(\omega , p)$ in $({\varOmega }, \{u_i\}_{i\in I})$ if the following conditions hold:

• 1. $z \in \mathbf {Z}^{{\varOmega }}_+ {\setminus } \{ \mathbf {0} \}$.

• 2. $p^{\prime } \in \mathbf {R}^{{\varOmega }}$ and $p^{\prime }_t=p_t$ for all $t \in {\varOmega }$ with $t \not \in \mathrm {supp}^+(z)$.

• 3. for all $i \in {\mathrm{ag}}(\mathrm {supp}^+(z)), \Delta (z, p^{\prime } ; u_i, (\omega , p))>0$.

Definition 8.2

An outcome $(\omega , p)$ is strong group stable in $({\varOmega }, \{u_i \}_{i\in I})$ if the following conditions hold:

• 1. $(\omega , p)$ is individually rational.

• 2. $(\omega , p)$ does not have any strong group blocking sets.

The strong group stability defined above coincides with the original strong group stability in [10] when applied to the single-unit trading network model.

Strong group stability is a more restricted condition than stability.

Proposition 8.1

Let $(\omega , p)$ be an outcome.

• (i) If $(\omega , p)$ has a blocking set, then it also has a strong group blocking set.

• (ii) If $(\omega , p)$ is strong group stable, then it is stable.

It is shown by Hatfield et al. [10] that the converse of Proposition 8.1 (ii) holds in single-unit trading network model.

Proposition 8.2

(Hatfield et al. [10]) For the single-unit trading network model under the full substitutes condition, strong group stability is equivalent to stability.

We show that the converse of Proposition 8.1 (ii) still holds in the multi-unit trading network model under the generalized full substitutes condition.

Theorem 8.1

Suppose that every $u_i$ satisfies the generalized full substitutes condition. Let $(\omega , p)$ be an outcome.

• (i) Suppose that $(\omega , p)$ is individually rational. If $(\omega , p)$ has a strong group blocking set, then it also has a blocking set.

• (ii) If $(\omega , p)$ is stable, then it is strong group stable.

From Proposition 8.1 and Theorem 8.1, strong group stability and stability are equivalent under the generalized full substitutes condition.

We now introduce chain stability in the multi-unit trading network model. This concept was first introduced by Ostrovsky [19] on the supply chain network, then extended to the single-unit trading network model by Hatfield et al. [10]. Our definition of chain stability is similar to that in [10].

Definition 8.3

A trade vector $z \in \{ 0, 1 \} ^{{\varOmega }}$ is a chain if there exists an ordering $t_1, \dots , t_k$ of elements in $\mathrm {supp}^+(z)$ such that $s(t_{l+1})=b(t_l)$ for all $l=1, \dots , k-1$, where $k=|\mathrm {supp}^+(z)|$. A blocking set $(z, p^{\prime })$ is called a blocking chain if z is a chain.

Definition 8.4

An outcome $(\omega , p)$ is chain stable in $({\varOmega }, \{u_i \}_{i\in I})$ if the following conditions hold:

• 1. $(\omega , p)$ is individually rational.

• 2. $(\omega , p)$ does not have any blocking chains.

Trivially, chain stability is a weaker condition than stability since a blocking chain is a blocking set. The converse is also true under the generalized full substitutes condition.

Theorem 8.2

Suppose that every $u_i$ satisfies the generalized full substitutes condition. Let $(\omega , p)$ be an outcome.

• (i) Suppose that $(\omega , p)$ is individually rational. If $(\omega , p)$ has a blocking set, then it has a blocking chain.

• (ii) $(\omega , p)$ is stable if and only if it is chain stable.

By Proposition 8.1 and Theorems 8.1 and 8.2, we obtain the equivalence among the three stability concepts under the generalized full substitutes condition.

Corollary 8.1

Suppose that every $u_i$ satisfies the generalized full substitutes condition. Then stability, strong group stability, and chain stability are equivalent.

9 Proofs

9.1 Proof of Theorem 7.1

Since $(\omega , p)$ is a competitive equilibrium we have

$$\begin{aligned} u_i(\omega )+\sum _{t\in {\varOmega }_{i \rightarrow }} \omega _t \cdot p_t- \sum _{t\in {\varOmega }_{\rightarrow i}} \omega _t \cdot p_t&=U(\omega , p ; u_i) \\&\ge U(\omega ^{\prime }, p ; u_i) \\&=u_i(\omega ^{\prime })+\sum _{t\in {\varOmega }_{i \rightarrow }} \omega ^{\prime }_t \cdot p_t- \sum _{t\in {\varOmega }_{\rightarrow i}} \omega ^{\prime }_t \cdot p_t \end{aligned}$$

for all $i \in I$ and $\omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}$. Since $\{ {\varOmega }_{i \rightarrow }: i \in I\}$ and $\{ {\varOmega }_{\rightarrow i}: i\in I \}$ are partitions of ${\varOmega }$, by summing these inequalities over all $i \in I$ we have

$$\begin{aligned} \sum _{i \in I} u_i(\omega ) \ge \sum _{i \in I} u_i(\omega ^{\prime })\quad (\forall \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}). \end{aligned}$$

9.2 Proof of Theorem 7.2

Since $\omega ^{\prime }$ is efficient on $\{u_i \}_{i\in I}$, by Proposition 6.4 we have

$$\begin{aligned} \sum _{i \in I} U(\omega ^{\prime }, p ; u_i)&=\sum _{i \in I}u_i(\omega ^{\prime })\\&\ge \sum _{i \in I}u_i(\omega )= \sum _{i \in I}U(\omega , p ; u_i). \end{aligned}$$

On the other hand, since $(\omega , p)$ is a competitive equilibrium it follows that

$$\begin{aligned} U(\omega , p ; u_i)&\ge U(\omega ^{\prime }, p ; u_i) \end{aligned}$$

for all $i \in I$. From these inequalities, we obtain

$$\begin{aligned} U(\omega , p ; u_i)=U(\omega ^{\prime }, p ; u_i) \quad (\forall i \in I). \end{aligned}$$

Therefore $\omega ^{\prime } \in D(p ; u_i)$ for all $i \in I$, that is, $(\omega ^{\prime }, p)$ is a competitive equilibrium.

9.3 Proof of Theorem 7.3

Suppose that $(\omega , p)$ is not stable. To show that $(\omega , p)$ is not a competitive equilibrium, we prove that $\omega \not \in D(p; u_j)$ holds for some $j \in I$.

First, we consider the case where $(\omega , p)$ is not individually rational. Then, there exists $j \in I$ such that $\omega \not \in C(\omega , p ; u_j)$. This implies $\omega \not \in D(p ; u_j)$ since

$$\begin{aligned} U(\omega ^{\prime } , p ; u_j) > U(\omega , p ; u_j) \qquad (\forall \omega ^{\prime } \in C(\omega , p; u_j)). \end{aligned}$$

We next consider the case where $(\omega , p)$ is individually rational and there exists a blocking set $(z, p^{\prime })$ of $(\omega , p)$. Denote $J={\mathrm{ag}}(\mathrm {supp}^+(z))$. For $i \in J$ and $\omega ^i \in C(\omega +z, p+p^{\prime } ; u_i)$ we have

$$\begin{aligned} \omega ^i_t=(\omega +z)_t \quad (t \in \mathrm {supp}^+(z) \cap {\varOmega }_i). \end{aligned}$$

Therefore, we have $\omega \not \in C(\omega +z, p+p^{\prime } ; u_i)$ for all $i \in J$, implying that

$$\begin{aligned} U(\omega , p+p^{\prime } ; u_i) < U(\omega ^i, p+p^{\prime } ; u_i)\quad (\forall i \in J). \end{aligned}$$

By summing these inequalities over all $i\in J$, we obtain

$$\begin{aligned} \sum _{i\in J}U(\omega , p+p^{\prime } ; u_i) < \sum _{i \in J}U(\omega ^i, p+p^{\prime } ; u_i). \end{aligned}$$

(15)

As shown below, it holds that

$$\begin{aligned} \sum _{i\in J}U(\omega , p+p^{\prime } ; u_i)&= \sum _{i\in J}U(\omega , p ; u_i), \end{aligned}$$

(16)

$$\begin{aligned} \sum _{i \in J}U(\omega ^i, p+p^{\prime } ; u_i)&= \sum _{i \in J}U(\omega ^i, p ; u_i). \end{aligned}$$

(17)

By (15), (16), and (17) we have

$$\begin{aligned} \sum _{i\in J}U(\omega , p ; u_i) < \sum _{i \in J}U(\omega ^i, p ; u_i), \end{aligned}$$

implying that there exists $j\in J$ such that $U(\omega ^j, p ; u_j) > U(\omega , p ; u_j)$. Hence, $\omega \not \in D(p; u_j)$ holds and $(\omega , p)$ is not a competitive equilibrium.

We now prove the Eq. (16). By Proposition 6.4, we have

$$\begin{aligned} \sum _{i \in I}U(\omega , p ; u_i) =\sum _{i \in I} u_i(\omega ) = \sum _{i \in I}U(\omega , p+p^{\prime } ; u_i). \end{aligned}$$

(18)

Since $p^{\prime }_t=0$ for all $t \in {\varOmega }{\setminus }\mathrm {supp}^+(z)$, it holds that

$$\begin{aligned} \sum _{i \in I {\setminus } J}U(\omega , p ; u_i) =\sum _{i \in I {\setminus } J}U(\omega , p+p^{\prime } ; u_i). \end{aligned}$$

(19)

The Eq. (16) follows from (18) and (19).

We then prove the Eq. (17). We have $\omega ^i_t=(\omega +z)_t$ for all $t\in \mathrm {supp}^+(z) \cap {\varOmega }_i$ and $i\in J$, and $p^{\prime }_t=0$ for all $t \in {\varOmega }{\setminus } \mathrm {supp}^+(z)$. Therefore, it holds that

$$\begin{aligned}&\sum _{i\in J}\left( \sum _{t \in {\varOmega }_{i \rightarrow } } \omega ^i_t \cdot p^{\prime }_t - \sum _{t \in {\varOmega }_{\rightarrow i}} \omega ^i_t \cdot p^{\prime }_t \right) \\&\quad = \sum _{i\in J}\left( \sum _{t \in {\varOmega }_{i \rightarrow } } (\omega +z)_t \cdot p^{\prime }_t - \sum _{t \in {\varOmega }_{\rightarrow i}} (\omega +z)_t \cdot p^{\prime }_t \right) =0. \end{aligned}$$

Hence, we can obtain (17) as follows:

$$\begin{aligned} \sum _{i \in J}U(\omega ^i , p ; u_i)&=\sum _{i \in J} \left( u_i(\omega ^i)+\sum _{t \in {\varOmega }_{i \rightarrow }} \omega ^i_t \cdot p_t - \sum _{t \in {\varOmega }_{\rightarrow i}} \omega ^i_t \cdot p_t \right) \nonumber \\&=\sum _{i \in J} \left( u_i(\omega ^i)+\sum _{t \in {\varOmega }_{i \rightarrow }} \omega ^i_t \cdot p_t - \sum _{t \in {\varOmega }_{\rightarrow i}} \omega ^i_t \cdot p_t \right) \nonumber \\&\quad +\sum _{i\in J} \left( \sum _{t \in {\varOmega }_{i \rightarrow } } \omega ^i_t \cdot p^{\prime }_t - \sum _{t \in {\varOmega }_{\rightarrow i}} \omega ^i_t \cdot p^{\prime }_t \right) \nonumber \\&=\sum _{i \in J} \left( u_i(\omega ^i)+\sum _{t \in {\varOmega }_{i \rightarrow }} \omega ^i_t \cdot (p+p^{\prime })_t - \sum _{t \in {\varOmega }_{\rightarrow i}} \omega ^i_t \cdot (p+p^{\prime })_t \right) \nonumber \\&=\sum _{i \in J}U(\omega ^i , p+p^{\prime } ; u_i). \end{aligned}$$

9.4 Proof of Theorem 7.4

Suppose that $(\omega , p)$ is individually rational. We show that if $\omega$ is not efficient on $\{u_i\}_{i\in I}$, then $(\omega , p)$ has a blocking set.

To prove this, we define a new valuation function. For a nonempty $A \subseteq {\varOmega }$ we define the valuation function $u^A_i(\cdot ; (\omega , p)): \mathbf {Z}^A \rightarrow \mathbf {R} \cup \{ -\infty \}$ of agent i by

$$\begin{aligned} u^A_i(\tau ; (\omega , p))&= \max \bigg \{ u_i(\omega ^{\prime })+\sum _{t\in {\varOmega }_{i \rightarrow }{\setminus } A}\omega ^{\prime }_t\cdot p_t -\sum _{t\in {\varOmega }_{\rightarrow i}{\setminus } A}\omega _t^{\prime }\cdot p_t \nonumber \\&\quad \qquad \qquad : \omega ^{\prime }_t \le \omega _t \,(t \in {\varOmega }{\setminus } A), \, \omega ^{\prime }_t=\tau _t \,(t \in A), \, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }} \bigg \}. \end{aligned}$$

For convenience, we define $\max \{ -\infty \}=-\infty$. By Proposition 5.1, $u_i^A(\cdot ;(\omega , p))$ is $({\varOmega }_{i \rightarrow } \cap A)$-twisted $\hbox {M}^{\natural }$-concave. Function $u_i^A(\cdot ; (\omega , p))$ is helpful in investigating the relationship between efficiency and stability. Indeed, the following lemma holds.

Lemma 9.1

Suppose that every $u_i$ is twisted $\hbox {M}^{\natural }$-concave and $(\omega , p)$ is individually rational in $({\varOmega }, \{u_i\}_{i\in I})$. Then $\omega ^A$ is not efficient on $\{u_i^A(\cdot ; (\omega , p))\}_{i\in I}$ for some $A \subseteq {\varOmega }$ if and only if there exists a blocking set of $(\omega , p)$. Furthermore, if $\omega ^A$ is not efficient on $\{u_i^A(\cdot ; (\omega , p))\}_{i\in I}$, then there exists a blocking set $(z, p^{\prime })$ of $(\omega , p)$ such that $z \in \{0, 1\}^{{\varOmega }}$ and $\mathrm {supp}^+(z) \subseteq A$.

If $\omega$ is not efficient on $\{u_i\}_{i \in I}, \omega ^{{\varOmega }}\, (=\omega )$ is not efficient on $\{u_i^{{\varOmega }}(\cdot ; (\omega , p))\}$ (note that $u_i^{{\varOmega }}(\cdot ; (\omega , p))=u_i$). Therefore, Theorem 7.4 follows from Lemma 9.1. The proof of Lemma 9.1 is given in Sect. 9.4.3.

Before showing Lemma 9.1, we discuss the inefficiency of trade vectors and some properties of $u_i^A(\cdot ; (\omega , p))$ in Sects. 9.4.1 and 9.4.2.

9.4.1 Inefficiency of trade vectors

We discuss the inefficiency of trade vectors. We show in Lemma 9.3 that if $\omega$ is not efficient on $\{u_i\}_{i\in I}$, there exists $\omega ^{\prime }$ such that $\sum _{i\in I} u_i(\omega )< \sum _{i\in I} u_i(\omega ^{\prime })$ and $\max _{t \in {\varOmega }}|\omega ^{\prime }_t-\omega _t| \le 1$. We define $\chi _T$ as the characteristic vector of T, that is,

$$\begin{aligned} (\chi _T)_s= {\left\{ \begin{array}{ll} 1 &{} \quad \text{ if } s\in T,\\ 0 &{} \quad \text{ otherwise }. \end{array}\right. } \end{aligned}$$

The sum of two $\hbox {M}^{\natural }$-concave functions has the following property.

Lemma 9.2

(Murota [16]) Let $f_1, f_2: \mathbf {Z}^N \rightarrow \mathbf {R} \cup \{ -\infty \}$ be $\hbox {M}^{\natural }$-concave functions and $\omega \in \mathrm {dom}\, f_1 \cap \mathrm {dom}\, f_2$. If $\omega \not \in \mathop {\mathrm{argmax}}\limits \{ f_1+f_2\}$ then there exist $A, B \subseteq N$ such that $A\cap B=\emptyset$ and

$$\begin{aligned} f_1(\omega )+f_2(\omega ) < f_1(\omega +\chi _A-\chi _B)+f_2(\omega +\chi _A-\chi _B). \end{aligned}$$

The next lemma follows from Lemma 9.2.

Lemma 9.3

Suppose that $u_i$ is twisted $\hbox {M}^{\natural }$-concave for all $i\in I$ and $\omega$ is not efficient on $\{ u_i \}_{i\in I}$. Then there exist $A, B \subseteq {\varOmega }$ such that $A \cap B=\emptyset$, and

$$\begin{aligned} \sum _{i\in I} u_i(\omega ) < \sum _{i\in I}u_i(\omega +\chi _A-\chi _B). \end{aligned}$$

Proof

Let u and f be functions defined by (7) and (8), respectively. It is easy to check that

$$\begin{aligned} \sum _{i \in I}u_i(\omega ^{\prime })=u(\tilde{T}(\omega ^{\prime })) +f(\tilde{T}(\omega ^{\prime })) \quad (\forall \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}), \end{aligned}$$

(20)

where $\tilde{T}(\omega ^{\prime }) \in \mathbf {Z}^{\tilde{{\varOmega }}}$ is defined by

$$\begin{aligned} (\tilde{T}(\omega ^{\prime }))_{t_b}=\omega ^{\prime }_t,\quad (\tilde{T}(\omega ^{\prime }))_{t_s}=-\omega ^{\prime }_t\quad (\forall t \in {\varOmega }). \end{aligned}$$

By (20), $\tilde{T}(\omega ) \not \in \mathop {\mathrm{argmax}}\limits \{u+f \}$. Since u and f are $\hbox {M}^{\natural }$-concave, by Lemma 9.2 there exist $U, W \subseteq \tilde{{\varOmega }}$ such that

$$\begin{aligned} u(\tilde{T}(\omega ))+f(\tilde{T}(\omega )) < u(\tilde{T}(\omega )+\chi _U-\chi _W)+f(\tilde{T}(\omega )+\chi _U-\chi _W). \end{aligned}$$

This inequality implies, in particular, that $f(\tilde{T}(\omega )+\chi _U-\chi _W)>-\infty$. By the definition of f, for each $t \in {\varOmega }$ we have $t_b \in U$ if and only if $t_s \in W$, and $t_b \in W$ if and only if $t_s \in U$. Let

$$\begin{aligned} A=\{ t \in {\varOmega }: t_b \in U\},\quad B=\{ t \in {\varOmega }: t_s \in U\}. \end{aligned}$$

By (20), we have

$$\begin{aligned} \sum _{i\in I} u_i(\omega ) < \sum _{i\in I}u_i(\omega +\chi _A-\chi _B). \end{aligned}$$

$\square$

9.4.2 Some properties of $u_i^A$

We next explain some properties of $u_i^A(\cdot ; (\omega , p))$ used in the proof of Lemma 9.1. Let $\omega ^A \in \mathbf {Z}^A$ and $p^A \in \mathbf {R}^A$ be restrictions of $\omega$ and p on A, respectively. The following propositions state the relation between two kinds of valuation functions, $u_i$ and $u_i^A(\cdot ; (\omega , p))$. Note that $U(\cdot , \cdot ; u_i^A(\cdot ; (\omega , p)))$ denotes the utility function associated with $u_i^A(\cdot ; (\omega , p))$, that is,

$$\begin{aligned} U(\tau , q ; u_i^A(\cdot ; (\omega , p)))=u_i^A(\tau ; (\omega , p))+\sum _{t\in {\varOmega }_{i \rightarrow }\cap A}\tau _t\cdot q_t -\sum _{t\in {\varOmega }_{\rightarrow i}\cap A}\tau _t\cdot q_t. \end{aligned}$$

(21)

Proposition 9.1

For $\tau \in \mathbf {Z}^A$ and $q \in \mathbf {R}^A$, it holds that

$$\begin{aligned}&U(\tau , q ; u_i^A(\cdot ; (\omega , p)))\nonumber \\&\quad =\max \{ U(\omega ^{\prime } , q^{\prime }; u_i): \omega ^{\prime }_t \le \omega _t \, (t \in {\varOmega }{\setminus } A), \, \omega ^{\prime }_t=\tau _t \, (t \in A),\, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}\}, \end{aligned}$$

(22)

where $q^{\prime } \in \mathbf {R}^{{\varOmega }}$ is the vector such that $q^{\prime }_t=q_t \,(\forall t \in A)$ and $q^{\prime }_t=p_t \,(\forall t\in {\varOmega }{\setminus } A)$. Moreover, the following statements hold.

• (i) Suppose that $(z, p^{\prime })$ is a blocking set of $(\omega , p)$ in the economy $({\varOmega }, \{u_i\}_{i\in I})$ and define $A=\mathrm {supp}^+(z)$. Then, for $i \in {\mathrm{ag}}(A)$ and $\tau \le \omega ^A+z^A$ with $\tau \not =\omega ^A+z^A$, it holds that

  $$\begin{aligned} U(\tau , (p+p^{\prime })^A; u_i^A(\cdot ;(\omega , p))) < U(\omega ^A+z^A, (p+p^{\prime })^A; u_i^A(\cdot ;(\omega , p))). \end{aligned}$$

• (ii) If $(\omega , p)$ is individually rational in $({\varOmega }, \{ u_i\}_{i\in I})$, then for all $A\subseteq {\varOmega }$ we have

  $$\begin{aligned} U(\omega ^A , p^A ; u_i^A(\cdot ; (\omega , p)))=U(\omega , p ; u_i), \end{aligned}$$

  (23)
  $$\begin{aligned} \sum _{i \in I}u_i^A(\omega ^A; (\omega , p))=\sum _{i \in I} u_i(\omega ). \end{aligned}$$

  (24)

• (iii) If ${\varOmega }_i \cap A=\emptyset$, then $U(\cdot , \cdot ; u_i^A(\cdot ; (\omega , p)))$ is a constant function. That is, $U(\tau , q; u_i^A(\cdot ; (\omega , p)))$ does not depend on $\tau$ and q.

Proof

The Eq. (22) follows immediately from the definitions of U and $u_i^A(\cdot ; (\omega , p))$. Indeed, we have

$$\begin{aligned}&U(\tau , q; u_i^A(\cdot ; (\omega , p)))\\&\quad =u_i^A(\tau ; (\omega , p))+\sum _{t\in {\varOmega }_{i \rightarrow }\cap A}\tau _t\cdot q_t -\sum _{t\in {\varOmega }_{\rightarrow i}\cap A}\tau _t\cdot q_t\\&\quad =\max \Bigg \{ u_i(\omega ^{\prime \prime }) +\sum _{t\in {\varOmega }_{i \rightarrow }{\setminus } A}\omega ^{\prime \prime }_t\cdot p_t -\sum _{t\in {\varOmega }_{\rightarrow i}{\setminus } A}\omega ^{\prime \prime }_t\cdot p_t \\&\qquad \qquad \qquad : \omega ^{\prime \prime }_t \le \omega _t \, (t\in {\varOmega }{\setminus } A), \, \omega ^{\prime \prime }_t = \tau _t \, (t\in A),\, \omega ^{\prime \prime } \in \mathbf {Z}^{\varOmega }\Bigg \} \\&\qquad +\sum _{t\in {\varOmega }_{i \rightarrow }\cap A}\tau _t\cdot q_t -\sum _{t\in {\varOmega }_{\rightarrow i}\cap A}\tau _t\cdot q_t\\&\quad =\max \Bigg \{ u_i(\omega ^{\prime \prime }) +\sum _{t\in {\varOmega }_{i \rightarrow }{\setminus } A}\omega ^{\prime \prime }_t\cdot p_t -\sum _{t\in {\varOmega }_{\rightarrow i}{\setminus } A}\omega ^{\prime \prime }_t\cdot p_t \\&\qquad \qquad \quad \quad +\sum _{t\in {\varOmega }_{i \rightarrow }\cap A}\tau _t\cdot q_t-\sum _{t\in {\varOmega }_{\rightarrow i}\cap A}\tau _t\cdot q_t\\&\quad \qquad \quad \qquad : \omega ^{\prime \prime }_t \le \omega _t \, (t\in {\varOmega }{\setminus } A),\, \omega ^{\prime \prime }_t = \tau _t \, (t\in A), \, \omega ^{\prime \prime } \in \mathbf {Z}^{\varOmega }\Bigg \}\\&\quad =\max \{ U(\omega ^{\prime } , q^{\prime }; u_i): \omega ^{\prime }_t \le \omega _t \, (t \in {\varOmega }{\setminus } A), \\&\qquad \omega ^{\prime }_t=\tau _t \, (t \in A),\, \omega ^{\prime } \in \mathbf {Z}^{\varOmega }\}. \end{aligned}$$

The claim (i) follows from the fact that $\omega ^{\prime }_t=(\omega +z)_t \, (\forall t \in \mathrm {supp}^+(z) \cap {\varOmega }_i)$ for all $\omega ^{\prime } \in C(\omega +z, p+p^{\prime } ; u_i)$ and the Eq. (22).

We next show the claim (ii). Suppose that $(\omega , p)$ is individually rational in $({\varOmega }, \{ u_i\}_{i\in I})$, that is,

$$\begin{aligned} \omega \in C(\omega , p ; u_i)=\mathop {\mathrm{argmax}}\limits \{U(\omega ^{\prime }, p ; u_i): \omega ^{\prime } \le \omega , \, \omega ^{\prime } \in \mathbf {Z}^{\varOmega }\} \quad (\forall i \in I). \end{aligned}$$

Since

$$\begin{aligned} \omega \in \{\omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}: \omega ^{\prime }_t \le \omega _t \, (t \in {\varOmega }{\setminus } A), \, \omega ^{\prime }_t=\omega _t \, (t \in A)\} \subseteq \{\omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}: \omega ^{\prime } \le \omega \}, \end{aligned}$$

we have

$$\begin{aligned} \omega&\in \mathop {\mathrm{argmax}}\limits \{ U(\omega ^{\prime } , p ; u_i): \omega ^{\prime }_t \le \omega _t \, (t \in {\varOmega }{\setminus } A), \\&\quad \omega ^{\prime }_t=\omega _t \, (t \in A),\, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}\}\quad (\forall i \in I). \end{aligned}$$

Therefore

$$\begin{aligned} U(\omega ^A , p^A ; u_i^A(\cdot ; (\omega , p)))&=\max \{ U(\omega ^{\prime } , p ; u_i): \omega ^{\prime }_t \le \omega _t \, (t \in {\varOmega }{\setminus } A), \\&\quad \omega ^{\prime }_t=\omega _t \, (t \in A),\, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}\}\\&=U(\omega , p ; u_i). \end{aligned}$$

Summing these equations over all $i \in I$, we obtain from Proposition 6.4 that

$$\begin{aligned} \sum _{i \in I}u_i^A(\omega ^A ; (\omega , p))&=\sum _{i \in I}U(\omega ^A, p^A ; u_i^A(\cdot ; (\omega , p)))\\&=\sum _{i \in I}U(\omega , p ; u_i)\\&=\sum _{i \in I} u_i(\omega ). \end{aligned}$$

We finally consider the case where ${\varOmega }_i \cap A=\emptyset$. By (21), it holds that

$$\begin{aligned} U(\tau , q ; u_i^A(\cdot ; (\omega , p)))=u_i^A(\tau ; (\omega , p))\quad (\forall q \in \mathbf {R}^A). \end{aligned}$$

By the definition of $u_i^A(\cdot ; (\omega , p))$ and the fact that the value of $u_i$ depends only on trades in ${\varOmega }_i$, the claim (iii) holds. $\square$

Proposition 9.2

Let A and $A^{\prime }$ be subsets of ${\varOmega }$ with $A \supseteq A^{\prime }$. Then for all $\tau \in \mathbf {Z}^{{\varOmega }}$ with $\tau _t \le \omega _t \,(\forall t \in {\varOmega }{\setminus } A^{\prime })$ and $q \in \mathbf {R}^{{\varOmega }}$ with $q_t=p_t \,(\forall t \in {\varOmega }{\setminus } A^{\prime })$, it holds that

$$\begin{aligned} U(\tau , q ; u_i) \le U(\tau ^A, q^A ; u_i^A(\cdot ; (\omega , p))) \le U(\tau ^{A^{\prime }}, q^{A^{\prime }} ; u_i^{A^{\prime }}(\cdot ; (\omega , p))), \end{aligned}$$

(25)

$$\begin{aligned} \sum _{i\in I} u_i(\tau ) \le \sum _{i\in I}u_i^A(\tau ^A ; (\omega , p)) \le \sum _{i\in I}u_i^{A^{\prime }}(\tau ^{A^{\prime }} ; (\omega , p)). \end{aligned}$$

(26)

Proof

The Eq. (25) follows from the Eq. (22) in Proposition 9.1 and

$$\begin{aligned}&\tau \in \{\omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}: \omega ^{\prime }_t \le \omega _t\, (t \in {\varOmega }{\setminus } A),\, \omega ^{\prime }_t =\tau _t \, (t\in A)\}\\&\quad \subseteq \{\omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}: \omega ^{\prime }_t \le \omega _t\, (t \in {\varOmega }{\setminus }A^{\prime }),\, \omega ^{\prime }_t =\tau _t \, (t\in A^{\prime })\} \end{aligned}$$

for all $A \supseteq A^{\prime }$. The Eq. (26) follows from (25) and Proposition 6.4. $\square$

The next statement shows a useful inequality for the value $\sum _{i\in I}u_i^A(\cdot ; (\omega , p))$ under the individual rationality.

Lemma 9.4

Suppose that $(\omega , p)$ is individually rational in $({\varOmega }, \{ u_i\}_{i\in I})$. For $\tau \le \omega ^A$, we have

$$\begin{aligned} \sum _{i\in I}u_i^A(\tau ; (\omega , p)) \le \sum _{i\in I}u_i^A(\omega ^A ;(\omega , p)). \end{aligned}$$

Proof

By Proposition 6.4 and the Eq. (22) in Proposition 9.1, we have

$$\begin{aligned} \sum _{i \in I}u_i^A(\tau ;(\omega , p))&= \sum _{i \in I}U(\tau , p^A ; u_i^A(\cdot ; (\omega , p))) \\&=\sum _{i \in I} \max \{ U(\omega ^{\prime } , p ; u_i): \omega _t^{\prime } \le \omega _t \, (t \in {\varOmega }{\setminus } A),\nonumber \\&\quad \; \omega _t^{\prime } =\tau _t \, (t \in A), \, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }} \} \\&\le \sum _{i \in I} \max \{ U(\omega ^{\prime } , p ; u_i): \omega ^{\prime } \le \omega , \, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }} \}, \end{aligned}$$

where the last inequality follows from

$$\begin{aligned} \{\omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}: \omega _t^{\prime } \le \omega _t \, (t \in {\varOmega }{\setminus } A),\, \omega _t^{\prime }=\tau _t \, (t \in A)\} \subseteq \{\omega ^{\prime } \in \mathbf {Z}^{{\varOmega }}: \omega ^{\prime } \le \omega \}. \end{aligned}$$

By the individual rationality, Proposition 6.4, and (26) in Proposition 9.2, we have

$$\begin{aligned} \sum _{i \in I} \max \{ U(\omega ^{\prime } , p ; u_i): \omega ^{\prime } \le \omega , \, \omega ^{\prime } \in \mathbf {Z}^{{\varOmega }} \}&=\sum _{i \in I} U(\omega , p ; u_i) \\&=\sum _{i\in I}u_i(\omega )\\&\le \sum _{i\in I}u_i^A(\omega ^A ;(\omega , p)). \end{aligned}$$

Hence, we have

$$\begin{aligned} \sum _{i\in I}u_i^A(\tau ; (\omega , p)) \le \sum _{i\in I}u_i^A(\omega ^A ;(\omega , p)). \end{aligned}$$

$\square$

9.4.3 Proof of Lemma 9.1

We now prove Lemma 9.1. First, we show the “if” part of Lemma 9.1.

Proposition 9.3

If $(\omega , p)$ has a blocking set, there exists $A\subseteq {\varOmega }$ such that $\omega ^A$ is not efficient on $\{ u_i^A(\cdot ; (\omega , p))\}_{i\in I}$.

Proof

Let $(z, p^{\prime })$ be a blocking set of $(\omega , p)$. We denote $A=\mathrm {supp}^+(z)$. By the claim (i) in Proposition 9.1, we have

$$\begin{aligned} U(\omega ^A, (p+p^{\prime })^A ; u_i^A(\cdot ; (\omega , p))) <U(\omega ^A+z^A, (p+p^{\prime })^A ; u_i^A(\cdot ; (\omega , p))) \end{aligned}$$

(27)

for all $i \in {\mathrm{ag}}(A)$. Since ${\varOmega }_i \cap A=\emptyset$ for each $i \in I {\setminus } {\mathrm{ag}}(A)$, by the claim (iii) in Proposition 9.1, we have

$$\begin{aligned} U(\omega ^A, (p+p^{\prime })^A ; u_i^A(\cdot ; (\omega , p))) =U(\omega ^A+z^A, (p+p^{\prime })^A ; u_i^A(\cdot ; (\omega , p))) \end{aligned}$$

(28)

for all $i \in I {\setminus } {\mathrm{ag}}(A)$. By (27), (28), and Proposition 6.4, we obtain

$$\begin{aligned} \sum _{i\in I}u_i^A(\omega ^A ; (\omega , p))&= \sum _{i\in I}U(\omega ^A, (p+p^{\prime })^A ; u_i^A(\cdot ; (\omega , p))) \\&<\sum _{i\in I}U(\omega ^A+z^A, (p+p^{\prime })^A ; u_i^A(\cdot ; (\omega , p)))\\&= \sum _{i\in I}u_i^A(\omega ^A+z^A ; (\omega , p)). \end{aligned}$$

Hence, $\omega ^A$ is not efficient on $\{ u_i^A(\cdot ; (\omega , p))\}_{i\in I}$. $\square$

We then prove the “only if” part of Lemma 9.1.

Proposition 9.4

Suppose that every $u_i$ is twisted $\hbox {M}^{\natural }$-concave and $(\omega , p)$ is individually rational in $({\varOmega }, \{ u_i\}_{i\in I})$. If $\omega ^A$ is not efficient on $\{ u_i^A(\cdot ; (\omega , p))\}_{i\in I}$ for some $A\subseteq {\varOmega }$, there exists a blocking set $(z, p^{\prime })$ of $(\omega , p)$ with $z \in \{0, 1\}^{{\varOmega }}$.

Proof

For $A \subseteq {\varOmega }$, we define

$$\begin{aligned} \mu _i^A(\tau ) \equiv {u_i^A}_{[\mathbf {0}, \omega ^A+\mathbf {1}]}(\tau ; (\omega , p))= {\left\{ \begin{array}{ll} u_i^A(\tau ; (\omega , p))&{}\quad \text{ if } \tau \in [\mathbf {0}, \omega ^A+\mathbf {1}],\\ -\infty &{}\quad \text{ otherwise. } \end{array}\right. } \end{aligned}$$

We consider the economy $(A, \{\mu _i^A\}_{i\in I})$. By Proposition 5.1, $\mu _i^A$ is $({\varOmega }_{i\rightarrow } \cap A)$-twisted $\hbox {M}^{\natural }$-concave. Therefore, by Lemma 9.3 there exist $U, W \subseteq {\varOmega }^A$ such that $U \cap W=\emptyset$ and

$$\begin{aligned} \sum _{i\in I}\mu _i^A(\omega ^A)&=\sum _{i\in I}u_i^A(\omega ^A ;(\omega , p)) \\&< \sum _{i\in I}u_i^A(\omega ^A+\chi _U-\chi _W ; (\omega , p)) =\sum _{i\in I}\mu _i^A(\omega ^A+\chi _U-\chi _W). \end{aligned}$$

This implies that $\omega ^A$ is not efficient on $\{ \mu _i^A\}_{i\in I}$. Let $A^*$ be a minimal subset of ${\varOmega }$ such that $\omega ^{A^*}$ is not efficient on $\{\mu _i^{A^*}\}_{i\in I}$. Note that $A^*\not = \emptyset$. Since $\mu _i^{A^*}$ is $({\varOmega }_{i \rightarrow } \cap A^*)$-twisted $\hbox {M}^{\natural }$-concave, by Theorem 6.1, there exists a competitive equilibrium $(\tau ^*, p^*)$ in the economy $(A^*, \{ \mu _i^{A^*}\}_{i \in I})$.

We now describe the outline of the rest of the proof. We first show that $\tau ^*$ is uniquely given by $\tau ^*=\omega ^{A^*}+\mathbf {1}$. Then we introduce a new function $\bar{u}_i$, which is a perturbation of $\mu _i^{A^*}$, and show that there exists $q \in \mathbf {R}^{A^*}$ such that $(\tau ^*, q)$ is a competitive equilibrium in $(A^*, \{\bar{u}_i\}_{i\in I})$. Finally, we construct a blocking set of $(\omega , p)$ by using $\tau ^*$ and q.

We now show that $\tau ^*=\omega ^{A^*}+\mathbf {1}$.

By Theorem 7.1, $\tau ^*$ is efficient on $\{ \mu ^{A^*}_i\}_{i\in I}$. Since $\omega ^{A^*}$ is not efficient on $\{ \mu ^{A^*}_i\}_{i\in I}$ by assumption, it holds that

$$\begin{aligned} \sum _{i\in I} \mu _i^{A^*}(\omega ^{A^*})&< \sum _{i\in I} \mu _i^{A^*}(\tau ^*). \end{aligned}$$

(29)

Let $A^{\prime }=\{ t \in A^*: \tau ^*_t = \omega _t +1\}$. Note that $A^{\prime }\not = \emptyset$ by Lemma 9.4. Since $\tau ^*_t \le \omega _t$ for all $t \in A^* {\setminus } A^{\prime }$, by Proposition 9.2, we have

$$\begin{aligned} \sum _{i\in I} \mu _i^{A^*}(\tau ^*) \le \sum _{i\in I}\mu _i^{A^{\prime }}({\tau ^*}^{A^{\prime }}). \end{aligned}$$

(30)

Furthermore, by the Eq. (24) in Proposition 9.1, we have

$$\begin{aligned} \sum _{i\in I} \mu _i^{A^*}(\omega ^{A^*})=\sum _{i \in I} u_i(\omega )=\sum _{i\in I} \mu _i^{A^{\prime }}(\omega ^{A^{\prime }}). \end{aligned}$$

(31)

From (29), (30), and (31), it follows that

$$\begin{aligned} \sum _{i\in I} \mu _i^{A^{\prime }}(\omega ^{A^{\prime }}) < \sum _{i\in I}\mu _i^{A^{\prime }}({\tau ^*}^{A^{\prime }}). \end{aligned}$$

That is, $\omega ^{A^{\prime }}$ is not efficient on $\{\mu _i^{A^{\prime }}\}_{i\in I}$. Due to the minimality of $A^*$, we have $A^{\prime }=A^*$. Thus $\tau ^*=\omega ^{A^*}+\mathbf {1}$.

We then define the new valuation function $\bar{u}_i$ as

$$\begin{aligned} \bar{u}_i(\tau )=\mu _i^{A^*}(\tau ) -\delta \sum _{t \in A^* \cap {\varOmega }_i} \tau _t \quad (i\in I), \end{aligned}$$

where $\delta$ is a sufficiently small positive number. Since $\tau ^*$ is the unique competitive equilibrium trade vector in $(A^*, \{\mu _i^{A^*}\}_{i\in I}), \tau ^*$ is also the unique efficient trade vector by Theorem 7.2. We assume that $\delta$ is sufficiently small so that $\tau ^*$ is the unique efficient trade vector in $(A^*, \{\bar{u}_i\}_{i\in I})$. By Proposition 5.1, each $\bar{u}_i$ is $({\varOmega }_{i \rightarrow } \cap A^*)$-twisted $\hbox {M}^{\natural }$-concave. Therefore, by Theorem 6.1 there exists a competitive equilibrium $(\bar{\omega }^*,q)$ in the economy $(A^*, \{ \bar{u}_i\} _{i \in I})$. By Theorem 7.1, we have $\bar{\omega }^*=\tau ^*$.

Finally, we claim that $(z, p^{\prime })$ given by

$$\begin{aligned} z_t= {\left\{ \begin{array}{ll} 1 &{}\quad \text{ if } \;\; t\in A^*,\\ 0 &{}\quad \text{ otherwise, } \end{array}\right. } \qquad p^{\prime }_t= {\left\{ \begin{array}{ll} q_t-p_t &{}\quad \text{ if } \;\; t\in A^*,\\ 0 &{}\quad \text{ otherwise, } \end{array}\right. } \end{aligned}$$

is a blocking set of $(\omega , p)$. It suffices to show that for all $j \in {\mathrm{ag}}(A^*)$ and $\phi \in C(\omega +z, p+p^{\prime } ; u_j)$, we have $\phi _t=\omega _t+1=\tau ^*_t$ for all $t \in A^* \cap {\varOmega }_j$.

Since $\phi _t \le \omega _t$ and $p^{\prime }_t=0$ hold for all $t \in {\varOmega }{\setminus } A^*$, by Proposition 9.2 we have

$$\begin{aligned} U(\phi , p+p^{\prime } ; u_j) \le U(\phi ^{A^*}, (p+p^{\prime })^{A^*} ; \mu _j^{A^*}) =U(\phi ^{A^*}, q ; \mu _j^{A^*}). \end{aligned}$$

(32)

Moreover, by the Eq. (22) in Proposition 9.1, there exists $\psi \in \mathbf {Z}^{{\varOmega }}$ such that $\psi \le \omega +z$ and

$$\begin{aligned} U(\tau ^*, q ; \mu _j^{A^*})=U(\psi ,p+p^{\prime } ; u_j). \end{aligned}$$

(33)

Since $(\tau ^*, q)$ is a competitive equilibrium in $(A^*, \{\bar{u}_i\}_{i \in I})$, we have

$$\begin{aligned} U(\tau ^*, q ; \bar{u}_j) \ge U(\phi ^{A^*} , q ; \bar{u}_j). \end{aligned}$$

This can be rewritten as

$$\begin{aligned}&U(\tau ^*, q ; \mu _j^{A^*})-\delta \sum _{t\in A^* \cap {\varOmega }_j}\tau ^*_t \ge U(\phi ^{A^*}, q ; \mu _j^{A^*})-\delta \sum _{t\in A^* \cap {\varOmega }_j}\phi _t, \end{aligned}$$

which, together with (32) and (33), implies that

$$\begin{aligned} \delta \sum _{t\in A^* \cap {\varOmega }_j}(\phi _t-\tau ^*_t) \ge U(\phi , p+p^{\prime } ; u_j) -U(\psi ,p+p^{\prime } ; u_j)\ge 0, \end{aligned}$$

where the last inequality follows from $\phi \in C(\omega +z, p+p^{\prime } ; u_j)$. Since $\phi ^{A^*} \le \omega ^{A^*}+z^{A^*} = \tau ^*$, we have $\phi _t=\tau ^*_t$ for all $t \in A^* \cap {\varOmega }_j$. Hence, $(z, p^{\prime })$ is a blocking set of $(\omega , p)$ and we complete the proof of Proposition 9.4. $\square$

Lemma 9.1 follows from Propositions 9.3 and 9.4.

9.5 Proof of Proposition 8.1

We give a proof of the claim (i) of Proposition 8.1, from which the claim (ii) of Proposition 8.1 follows immediately. Let $(z, p^{\prime })$ be a blocking set of $(\omega , p)$ and define $J={\mathrm{ag}}(\mathrm {supp}^+(z))$. Then for $i\in J$ and $\omega ^{\prime } \in C(\omega +z, p+p^{\prime } ; u_i)$, we have $\omega _t^{\prime }=(\omega +z)_t$ for all $t \in \mathrm {supp}^+(z)\cap {\varOmega }_i$. Thus, $U(\omega ^{\prime },p+p^{\prime } ; u_i)> U(\omega ,p+p^{\prime } ; u_i)$ holds. It follows from the definition of a utility function that

$$\begin{aligned}&U(\omega ^{\prime }, p+p^{\prime } ; u_i)- U(\omega , p+p^{\prime } ; u_i)\nonumber \\&\quad =u_i(\omega ^{\prime })+\sum _{t \in {\varOmega }_{i \rightarrow }}\omega ^{\prime }_t \cdot (p_t+p^{\prime }_t)-\sum _{t \in {\varOmega }_{\rightarrow i}}\omega ^{\prime }_t \cdot (p_t+p^{\prime }_t)\nonumber \\&\qquad -\left( u_i(\omega )+\sum _{t \in {\varOmega }_{i \rightarrow }}\omega _t \cdot (p_t+p^{\prime }_t)-\sum _{t \in {\varOmega }_{\rightarrow i}}\omega _t \cdot (p_t+p^{\prime }_t)\right) \nonumber \\&\quad =u_i(\omega ^{\prime })-u_i(\omega )+\sum _{t \in {\varOmega }_{i \rightarrow }}(\omega ^{\prime }_t-\omega _t) \cdot p_t+\sum _{t\in {\varOmega }_{i \rightarrow }} z_t \cdot p^{\prime }_t\nonumber \\&\qquad -\sum _{t \in {\varOmega }_{\rightarrow i}}(\omega ^{\prime }_t-\omega _t) \cdot p_t -\sum _{t\in {\varOmega }_{\rightarrow i}}z_t \cdot p^{\prime }_t \end{aligned}$$

(34)

for all $i \in J$. On the other hand, we obtain

$$\begin{aligned} \Delta (z, p+p^{\prime }; u_i, (\omega , p))&\ge u_i(\omega ^{\prime })+\sum _{t \in {\varOmega }_{i \rightarrow }}\omega ^{\prime }_t \cdot p_t-\sum _{t \in {\varOmega }_{\rightarrow i}}\omega ^{\prime }_t \cdot p_t\nonumber \\&\quad +\sum _{t \in {\varOmega }_{i \rightarrow }}z_t \cdot p^{\prime }_t-\sum _{t \in {\varOmega }_{\rightarrow i}}z_t \cdot p^{\prime }_t\nonumber \\&\quad -\left( u_i(\omega )+\sum _{t \in {\varOmega }_{i \rightarrow }}\omega _t \cdot p_t-\sum _{t \in {\varOmega }_{\rightarrow i}}\omega _t \cdot p_t \right) \nonumber \\&=u_i(\omega ^{\prime })-u_i(\omega )+\sum _{t \in {\varOmega }_{i \rightarrow }}(\omega ^{\prime }_t-\omega _t) \cdot p_t+\sum _{t\in {\varOmega }_{i \rightarrow }} z_t \cdot p^{\prime }_t\nonumber \\&\quad -\sum _{t \in {\varOmega }_{\rightarrow i}}(\omega ^{\prime }_t-\omega _t) \cdot p_t-\sum _{t\in {\varOmega }_{\rightarrow i}} z_t \cdot p^{\prime }_t \end{aligned}$$

(35)

for all $i \in J$. By (34) and (35), we have

$$\begin{aligned} \Delta (z, p+p^{\prime }; u_i, (\omega , p)) \ge U(\omega ^{\prime }, p+p^{\prime } ; u_i)-U(\omega , p+p^{\prime } ; u_i) >0\quad (\forall i \in J). \end{aligned}$$

This means $(z, p+p^{\prime })$ is a strong group blocking set of $(\omega , p)$.

9.6 Proof of Theorem 8.1

We give a proof of the claim (i) of Theorem 8.1, from which the claim (ii) of Theorem 8.1 follows immediately. We assume that $(\omega , p)$ is individually rational.

Let $(z, p^{\prime })$ be a strong group blocking set of $(\omega , p)$ and define $A=\mathrm {supp}^+(z)$ and $J={\mathrm{ag}}(A)$. Then by the definition of $\Delta (z, p^{\prime }; u_i, (\omega , p))$, the Eq. (22), and the claim (ii) in Proposition 9.1, we have

$$\begin{aligned} \Delta (z, p^{\prime }; u_i, (\omega , p))&=U({\omega }^A+z^A, p^A ; u_i^A(\cdot ; (\omega , p))) +\sum _{t \in {\varOmega }_{i \rightarrow }}z_t \cdot (p^{\prime }_t-p_t)\\&\quad -\sum _{t \in {\varOmega }_{\rightarrow i}}z_t \cdot (p^{\prime }_t-p_t)-U(\omega , p ; u_i)\\&=U({\omega }^A+z^A, p^A ; u_i^A(\cdot ; (\omega , p))) -U({\omega }^A, p^A ; u_i^A(\cdot ; (\omega , p)))\\&\quad +\sum _{t \in {\varOmega }_{i \rightarrow }}z_t \cdot (p^{\prime }_t-p_t) -\sum _{t \in {\varOmega }_{\rightarrow i}}z_t \cdot (p^{\prime }_t-p_t). \end{aligned}$$

Since $\Delta (z, p^{\prime }; u_i, (\omega , p)) > 0$, we obtain

$$\begin{aligned}&U({\omega }^A+z^A, p^A ; u_i^A(\cdot ; (\omega , p)))\nonumber \\&\quad >U({\omega }^A, p^A ; u_i^A(\cdot ; (\omega , p))) +\sum _{t \in {\varOmega }_{\rightarrow i}}z_t \cdot (p^{\prime }_t-p_t) -\sum _{t \in {\varOmega }_{i \rightarrow }}z_t \cdot (p^{\prime }_t-p_t).\; \end{aligned}$$

(36)

Moreover, it holds that

$$\begin{aligned} \sum _{i\in J}\left( \sum _{t \in {\varOmega }_{\rightarrow i}}z_t \cdot (p^{\prime }_t-p_t) -\sum _{t \in {\varOmega }_{i \rightarrow }}z_t \cdot (p^{\prime }_t-p_t)\right) =0. \end{aligned}$$

(37)

Hence, by (36) and (37) we have

$$\begin{aligned} \sum _{i\in J}U({\omega }^A+z^A, p^A ; u_i^A(\cdot ; (\omega , p))) >\sum _{i\in J}U({\omega }^A, p^A ; u_i^A(\cdot ; (\omega , p))). \end{aligned}$$

(38)

On the other hand, ${\varOmega }_i \cap A=\emptyset$ holds for all $i \in I {\setminus } J$. Thus, by the claim (iii) in Proposition 9.1 we have

$$\begin{aligned} U({\omega }^A+z^A, p^A ; u_i^A(\cdot ; (\omega , p))) =U({\omega }^A, p^A ; u_i^A(\cdot ; (\omega , p)))\quad (\forall i \in I {\setminus } J). \end{aligned}$$

(39)

It follows from (38) and (39) that

$$\begin{aligned} \sum _{i\in I}u_i^A(\omega ^A+z^A ; (\omega , p))&= \sum _{i\in I}U({\omega }^A+z^A, p^A ; u_i^A(\cdot ; (\omega , p)))\\&>\sum _{i\in I}U({\omega }^A, p^A ; u_i^A(\cdot ; (\omega , p)))\\&=\sum _{i\in I}u_i^A(\omega ^A ; (\omega , p)). \end{aligned}$$

This inequality implies that $\omega ^A$ is not efficient on $\{u_i^A(\cdot ; (\omega , p))\}_{i \in I}$. Since each $u_i$ is twisted $\hbox {M}^{\natural }$-concave, by Lemma 9.1, $(\omega , p)$ has a blocking set.

9.7 Proof of Theorem 8.2

We give a proof of the claim (i) of Theorem 8.2, from which the claim (ii) of Theorem 8.2 follows immediately. We assume that $(\omega , p)$ is individually rational.

By Lemma 9.1, there exists a blocking set $(z, p^{\prime })$ of $(\omega , p)$ with $z \in \{0, 1\}^{{\varOmega }}$. In addition, we assume that $\mathrm {supp}^+(z)$ is minimal among all such blocking sets of $(\omega , p)$. We will show that z is a chain. Let $A=\mathrm {supp}^+(z)$. By regarding each trade $t \in A$ as a directed edge from seller s(t) to buyer $b(t), ({\mathrm{ag}}(A), A)$ forms a directed graph with vertex set ${\mathrm{ag}}(A)$ and edge set A. We note that the graph $({\mathrm{ag}}(A), A)$ is connected by the minimality of A.

We first consider the case where

$$\begin{aligned} |{\varOmega }_{\rightarrow i} \cap A| = |{\varOmega }_{i \rightarrow } \cap A| \quad (\forall i \in {\mathrm{ag}}(A)). \end{aligned}$$

In this case, $({\mathrm{ag}}(A), A)$ is an Eulerian graph, that is, z is a chain.

In the sequel, we deal only with the case where there exists $k \in {\mathrm{ag}}(A)$ with

$$\begin{aligned} |{\varOmega }_{\rightarrow k} \cap A| < |{\varOmega }_{k \rightarrow } \cap A|, \end{aligned}$$

(40)

because we can similarly show that z is a chain when $|{\varOmega }_{\rightarrow k} \cap A| > |{\varOmega }_{k \rightarrow } \cap A|$ for some $k \in {\mathrm{ag}}(A)$. We define $U_i: \mathbf {Z}^A \rightarrow \mathbf {R} \cup \{ -\infty \}$ by

$$\begin{aligned} U_i(\tau )=U(\tau , (p+p^{\prime })^A ; u_i^A(\cdot ; (\omega , p)))\quad (i \in I). \end{aligned}$$

By Proposition 5.1, $U_i$ is $({\varOmega }_{i \rightarrow } \cap A)$-twisted $\hbox {M}^{\natural }$-concave. We then consider the following algorithm, FIND_CHAIN, which always returns a chain $z^*$. By showing $z=z^*$, we prove that z is a chain. Validity of the algorithm is shown by Propositions 9.6 and 9.8.

FIND_CHAIN

Step 1.:

Take $k \in {\mathrm{ag}}(A)$ with (40) and $t \in {\varOmega }_{k \rightarrow } \cap A$ with $U_k(\omega ^A) < U_k(\omega ^A+\chi _t)$. Set $j:=b(t)$ and $\hat{z}:=\chi _t\, (\hat{z} \in \{0, 1\}^{A})$.

Step 2.:

While $U_j(\omega ^A) \ge U_j(\omega ^A+\hat{z})$ do $\{$

Take $t \in \mathrm {supp}^+(z^A-\hat{z}) \cap {\varOmega }_{j \rightarrow }$ so that $U_j(\omega ^A) < U_j(\omega ^A+\hat{z}+\chi _t)$ holds, and set $j:=b(t)$ and $\hat{z}:=\hat{z}+\chi _t$.

$\}.$

Step 3.:

Set $z^*_t=\hat{z}_t$ for each $t\in A$ and $z^*_t=0$ for each $t\not \in A$, and return $z^*$.

FIND_CHAIN terminates in a finite number of iterations because $\mathrm {supp}^+(z^A-\hat{z})$ is strictly reduced in each update of $\hat{z}$.

We first show that Step 1 works, where the following property of $\hbox {M}^{\natural }$-concave functions is used.

Proposition 9.5

([17, Theorem 4.2] ) Let $u: \mathbf {Z}^N \rightarrow \mathbf {R} \cup \{-\infty \}$ be an $\hbox {M}^{\natural }$-concave function. For every $\omega , \tau \in \mathrm {dom}\, u$ with $\sum _{t\in N}\omega _t < \sum _{t\in N}\tau _t$, there exists $s \in \mathrm {supp}^-(\omega -\tau )$ such that

$$\begin{aligned} u(\omega )+u(\tau ) \le u(\omega +\chi _s)+u(\tau -\chi _s). \end{aligned}$$

By Proposition 9.5, the following statement holds.

Proposition 9.6

For $k \in {\mathrm{ag}}(A)$ satisfying (40), there exists $t \in {\varOmega }_{k \rightarrow } \cap A$ such that

$$\begin{aligned} U_k(\omega ^A) < U_k(\omega ^A+\chi _t). \end{aligned}$$

Proof

Since $U_k$ is $({\varOmega }_{k\rightarrow } \cap A)$-twisted $\hbox {M}^{\natural }$-concave, there exists an $\hbox {M}^{\natural }$-concave function $\hat{U}_k$ such that

$$\begin{aligned} U_k(\tau )=\hat{U}_k(\mathrm {twist}(\tau ; {\varOmega }_{k \rightarrow } \cap A)) \quad (\forall \tau \in \mathbf {Z}^A). \end{aligned}$$

By (40), we have

$$\begin{aligned} \sum _{s\in A \cap {\varOmega }_{k}}(\mathrm {twist}(\omega ^A+z^A ; {\varOmega }_{k\rightarrow } \cap A))_s < \sum _{s\in A\cap {\varOmega }_{k}}(\mathrm {twist}(\omega ^A ; {\varOmega }_{k\rightarrow } \cap A))_s. \end{aligned}$$

Moreover, it holds that $\omega ^A, \omega ^A+z^A \in \mathrm {dom}\,U_k$ and

$$\begin{aligned} \mathrm {supp}^-(\mathrm {twist}(\omega ^A+z^A ; {\varOmega }_{k\rightarrow } \cap A) -\mathrm {twist}(\omega ^A ; {\varOmega }_{k\rightarrow } \cap A)) ={\varOmega }_{k\rightarrow } \cap A. \end{aligned}$$

Therefore, by Proposition 9.5, there exists $t \in {\varOmega }_{k \rightarrow } \cap A$ such that

$$\begin{aligned}&\hat{U}_k(\mathrm {twist}(\omega ^A+z^A ; {\varOmega }_{k\rightarrow } \cap A)) +\hat{U}_k(\mathrm {twist}(\omega ^A ; {\varOmega }_{k\rightarrow } \cap A)) \\&\quad \le \hat{U}_k(\mathrm {twist}(\omega ^A+z^A ; {\varOmega }_{k\rightarrow } \cap A)+\chi _t) +\hat{U}_k(\mathrm {twist}(\omega ^A ; {\varOmega }_{k\rightarrow } \cap A)-\chi _t). \end{aligned}$$

This implies that

$$\begin{aligned} U_k(\omega ^A+z^A)+U_k(\omega ^A) \le U_k(\omega ^A+z^A-\chi _t)+U_k(\omega ^A+\chi _t). \end{aligned}$$

(41)

By the claim (i) in Proposition 9.1, it holds that

$$\begin{aligned} U_k(\omega ^A+z^A) > U_k(\omega ^A+z^A-\chi _t). \end{aligned}$$

(42)

Therefore, by (41) and (42), we have

$$\begin{aligned} U_k(\omega ^A) < U_k(\omega ^A+\chi _t). \end{aligned}$$

$\square$

By Proposition 9.6, Step 1 works.

We next show that Step 2 works. The following proposition is a direct consequence of the definition of twisted $\hbox {M}^{\natural }$-concavity.

Proposition 9.7

Let $\tau \in \mathbf {Z}^A$ be an integer vector with $\omega ^A \le \tau \le \omega ^A+z^A$. Then for any $t \in \mathrm {supp}^+(\omega ^A+z^A-\tau ) \cap {\varOmega }_{\rightarrow i}$ there exists $s\in (\mathrm {supp}^+(\omega ^A+z^A-\tau ) \cap {\varOmega }_{i \rightarrow }) \cup \{ 0 \}$ such that

$$\begin{aligned} U_i(\omega ^A+z^A)+U_i(\tau ) \le U_i(\omega ^A+z^A-\chi _s -\chi _t)+U_i(\tau +\chi _s+\chi _t). \end{aligned}$$

(43)

Proof

Since $U_i$ is $({\varOmega }_{i\rightarrow } \cap A)$-twisted $\hbox {M}^{\natural }$-concave, there exists an $\hbox {M}^{\natural }$-concave function $\hat{U}_i$ such that

$$\begin{aligned} U_i(\tau )=\hat{U}_i(\mathrm {twist}(\tau ; {\varOmega }_{i \rightarrow } \cap A)) \quad (\forall \tau \in \mathbf {Z}^A). \end{aligned}$$

The Eq. (43) follows from the definition of $\hbox {M}^{\natural }$-concavity and

$$\begin{aligned}&\mathrm {supp}^+(\mathrm {twist}(\omega ^A+z^A ; {\varOmega }_{i\rightarrow } \cap A) -\mathrm {twist}(\tau ; {\varOmega }_{i\rightarrow } \cap A))\cap {\varOmega }_{i}\\&\quad =\mathrm {supp}^+(\omega ^A+z^A-\tau ) \cap {\varOmega }_{\rightarrow i}, \\&\mathrm {supp}^-(\mathrm {twist}(\omega ^A+z^A ; {\varOmega }_{i\rightarrow } \cap A) -\mathrm {twist}(\tau ; {\varOmega }_{i\rightarrow } \cap A))\cap {\varOmega }_{i}\\&\quad =\mathrm {supp}^+(\omega ^A+z^A-\tau ) \cap {\varOmega }_{i \rightarrow }. \end{aligned}$$

$\square$

The following proposition guarantees that Step 2 works.

Proposition 9.8

FIND_CHAIN preserves the following properties:

• (a) at the beginning of each while-loop of Step 2, if $U_j(\omega ^A) \ge U_j(\omega ^A+\hat{z})$ there exists $t \in \mathrm {supp}^+(z^A-\hat{z}) \cap {\varOmega }_{j \rightarrow }$ such that $U_j(\omega ^A) < U_j(\omega ^A+\hat{z}+\chi _t)$;

• (b) at the end of Step 1 and each while-loop,

  $$\begin{aligned} U_i(\omega ^A)&= U_i(\omega ^A+\hat{z})\quad (\forall i \in I {\setminus } {\mathrm{ag}}(\mathrm {supp}^+(\hat{z}))), \end{aligned}$$

  (44)
  $$\begin{aligned} U_i(\omega ^A)&< U_i(\omega ^A+\hat{z})\quad (\forall i \in {\mathrm{ag}}(\mathrm {supp}^+(\hat{z})) {\setminus } \{j \} ). \end{aligned}$$

  (45)

Proof

Since ${\varOmega }_i \cap \mathrm {supp}^+(\hat{z})=\emptyset$ for all $i \in I{\setminus } {\mathrm{ag}}(\mathrm {supp}^+(\hat{z}))$, (44) always holds by the claim (iii) in Proposition 9.1. At the end of Step 1, (45) holds because of the definition of k and ${\mathrm{ag}}(\mathrm {supp}^+(\hat{z})) {\setminus } \{j\}=\{k\}$. If property (a) is preserved, we obtain (45). Therefore it suffices to show property (a).

We assume that $U_j(\omega ^A) \ge U_j(\omega ^A+\hat{z})$ and (45) holds before the last update of $\hat{z}$ and j. Let $t^{\prime } \in {\varOmega }_{\rightarrow j}$ be the trade which is added to $\hat{z}$ in the last update of $\hat{z}$; such $t^{\prime }$ always exists. From the above assumption, it follows that

$$\begin{aligned} U_j(\omega ^A) \le U_j(\omega ^A+\hat{z}-\chi _{t^{\prime }}). \end{aligned}$$

(46)

By Proposition 9.7, there exists $t \in (\mathrm {supp}^+(z-\hat{z}) \cap {\varOmega }_{j\rightarrow })\cup \{ 0\}$ such that

$$\begin{aligned}&U_j(\omega ^A+z^A)+U_j(\omega ^A+\hat{z}-\chi _{t^{\prime }})\nonumber \\&\quad \le U_j(\omega ^A+z^A-\chi _{t^{\prime }}-\chi _t)+U_j(\omega ^A+\hat{z}+\chi _t). \end{aligned}$$

(47)

On the other hand, by the claim (i) in Proposition 9.1, we have

$$\begin{aligned} U_j(\omega ^A+z^A) >U_j(\omega ^A+z^A-\chi _{t^{\prime }}-\chi _t). \end{aligned}$$

(48)

By (46), (47), and (48), we have

$$\begin{aligned} U_j(\omega ^A) \le U_j(\omega ^A+\hat{z}-\chi _{t^{\prime }}) < U_j(\omega ^A+\hat{z}+\chi _t). \end{aligned}$$

Since $U_j(\omega ^A) \ge U_j(\omega ^A+\hat{z}), t\not =0$ must hold. $\square$

We now prove $z^*=z$. At Step 3, it holds by Proposition 9.8 that

$$\begin{aligned} U_i(\omega ^A)&= U_i((\omega +z^*)^A)\quad (\forall i \in I {\setminus } {\mathrm{ag}}(\mathrm {supp}^+(z^*))), \end{aligned}$$

(49)

$$\begin{aligned} U_i(\omega ^A)&< U_i((\omega +z^*)^A)\quad (\forall i \in {\mathrm{ag}}(\mathrm {supp}^+(z^*))). \end{aligned}$$

(50)

We define $A^*=\mathrm {supp}^+(z^*)$. Then we have

Therefore $\omega ^{A^*}$ is not efficient on $\{u_i^{A^*}(\cdot ;(\omega , p))\}_{i\in I}$. By Lemma 9.1, there exists a blocking set $(\tilde{z}, \tilde{p})$ of $(\omega , p)$ such that $\tilde{z} \in \{0, 1\}^{{\varOmega }}$ and $\mathrm {supp}^+(\tilde{z}) \subseteq A^*$. By the minimality of A, we have $\mathrm {supp}^+(\tilde{z})=A^*=A$. Hence, $z^* = z$.