Collective profitability in semi-competitive intermediation networks

Abstract

We analyze intermediation business processes that enable companies to use multiple distribution channels for expanding their market horizon of potential customers that are interested in purchasing their products and/or services. These distribution channels are represented by sequences of intermediation transactions supported by usually self-interested middle-agents that enable the connection of the providers with the end costumers. We propose a new formal model of network-structured intermediation business processes represented as Directed-Acyclic-Graphs. Using this model we obtained sound theoretical results of collectively profitable intermediation transactions. This paves the way for further proposal of optimal pricing strategies of the participating agents in semi-competitive environments.

Keywords

Welfare economics intermediation networks collective intelligence multi-agent system graph theory linear algebra

1 Introduction

Networks have a long and well-established tradition in Social Sciences, including Trading and Economics [8]. Recent advances in Computing and Information Technology enabled the wide-spread adoption and application of network-based technologies in virtually all areas of life and science, with a high impact on the advancement of the emergent field of E-Commerce & E-Business.

Researchers in Computer Science and Economics studied formation of intermediation networks on both technical and conceptual levels. Economists were interested in intermediation arising in decentralized trading markets involving multiple self-interested buyer, seller and intermediary agents. Buyer and seller agents exploit the opportunity created by various individual relationships to meet, interact and trade either directly, or through intermediation chains involving other intermediary agents. Computer Scientists proposed digital environments in which agents can automatically register their capabilities, as well as search for potential trading partners, thus enabling the efficient implementation of digital decentralized trading markets [4].

A lot of research efforts were spent to model and understand the structure of complex intermediation networks in competitive context by modeling the strategic dynamic interactions between companies as bargaining games such that the players are interconnected via a network structure. These works typically employ mathematical modeling tools inspired by the theory of complex networks and bargaining games [16] and are focused on various aspects like network formation, network impact on trading outcomes, and intermediation power in resale networks [13 , 31].

On the other hand companies including manufacturing and wholesale businesses are developing complex business processes of supply and distribution chains for the management of their supply and distribution activities, rather than directly interacting with their end customers. Such processes usually incorporate one or more distribution channels representing groups of individuals or organizations that are responsible for directing the flow of products and services to the potential customers [17]. For example, such intermediation networks can be found in finance and logistics [24 , 27].

It is interesting to observe that intermediation networks serving supply and distribution chains involve interacting business agents that are operating in a semi-competitive, rather than purely competitive context. This means that on the one hand involved agents are collaborating to ensure that the underlying business process is correctly delivering its functions to its external customers, while on the other hand they are self-interested seeking to maximize their own profit and to improve their longer-term welfare.

In this paper the focus is on modeling and analysis of semi-competitive intermediation networks serving the complex business process for the management of the distribution activities of a company through multiple inter-related and concurrently operating distribution channels. The paper is an extended and refined version of our preliminary results on this subject that were initially reported in [5, 6].

This paper presents our contribution is the definition of a simple formal model of intermediation that is suitable for semi-competitive multi-agent business processes containing the producers (or sellers), the intermediaries and the customers (or buyers) [2, 14]. This model captures sellers, buyers and market intermediaries as self-interested agents engaged in an intermediation business process, seeking for collaborative advantage [19]. We propose correctness criteria that provide the collective profitability as an incentive for all the business agents to engage in a collaborative intermediation process, thus ensuring systems’s robustness and sustainability.

Although this model was initially thought to serve a single company’s distribution process, we believe that it can be relevant for both single and multiple company settings. We have in mind especially B2B models of industrial consortia and private industrial networks that promote network-based B2B e-commerce as a form of “extended enterprises”. Either collectively or privately own, they involve multiple independent participants, carefully selected, aiming to coordinate and collaborate for achieving industry-wide goals, usually serving a very large manufacturer [23].

Our research endeavour can be also placed in the larger context of computational collective intelligence [28]. There the focus is on the applicability of consensus methods for knowledge mediation and integration in collectives of possibly networked agents. Although placed in the same context of interconnected agents, our work is addressing agents’ profitability rather than knowledge integration, with the goal of understanding group’s profitability as maximization of its social welfare.

In particular, our modeling approach is based on the agent metaphor, here understood in a computational context, as a new model of a “computer system situated in some environment that is capable of flexible autonomous action in order to meet its design objectives” [18]. In our work we assume that a multi-agent system is a computational system containing a collective of loosely-coupled agents representing the business participants of the intermediation process, that interact and collaborate to solve the given intermediation problem.

Following [6], we assume that a distribution channel contains a set of zero or more market intermediaries that link sellers to customers or to other intermediaries with the overall goal of linking the initial sellers to the ultimate buyers. An intermediation process must satisfy the following requirements:

R1. A seller can be simultaneously involved in multiple different distribution channels, i.e. multiple different distribution channels can serve the same seller. This approach allows sellers to expand their market horizon by increasing the set of potentially reachable customers.

R2. Distribution channels can share market intermediaries, i.e. a market intermediary can serve more distribution channels, thus improving the efficiency of the system.

R3. A business can enroll multiple seller agents to improve its capacity of reaching more potential buyers that are interested in purchasing its products.

We have started by proposing a model that addresses only requirement R1, by capturing the structure of the business process as a rooted tree [5]. Then, we extended the model to incorporate all the requirements R1-R3 by generalizing the process structure to a directed acyclic graph (DAG hereafter) [5]. Using this model, the business can enroll multiple sellers, thus addressing requirement R3, while intermediaries can be shared by distinct distribution channels, thus addressing requirement R2.

In this paper we revise and refine our model by considering the most general case – DAG-structured intermediation networks involving multiple seller agents. We also present formal mathematical proofs of all our results, by explaining the most critical aspects with suitable chosen examples.

The most important result of this research is the establishment of necessary and sufficient conditions for the existence of profitable pricing strategies for all the participants to the intermediation business process. These conditions involve a set of linear algebraic inequalities derived from the network structure that constrain the values of the seller and buyer agents limit prices. Meeting these conditions enables agents collaboration, while allowing them to optimize either their private or social goals using the mathematical theory of social welfare [17].

2 Related works

Economists and Computer Scientists were interested in understanding and formulating the conceptual foundations of the modeling of intermediation networks, as well as in the technical details of their implementation and development using networked digital technologies.

Economists proposed new conceptual and quantitative models of decentralized trading markets, thus following the tradition in Economics that “sees markets as populated by agents interacting anonymously through the price system“ [13].

On the other hand, Computer Science and Information Technology are mostly interested in the development of digital business environments where agents can register their requirements and capabilities and search for potential partners. These are E-Business implementations of the models of decentralized trading markets [4, 24].

Connecting requesters with providers is known as the connection problem in MAS. According to [32], “trade in a wide range of markets involves a plethora of other subjects, such as intermediaries, dealers, brokers, market-makers, wholesalers, retailers”, sometimes called “middlemen”.

We can notice that solving the connection problem requires the enrollment of specialized agents known as middle-agents with the role of managing the intermediation activity. One of the main advantages of digital decentralized trading markets is to enable the dynamic discovery of business partners by matching their requirements and capabilities [2, 9].

It is recognized that complex intermediation chains could play a vital role in various markets, including financial markets and market for agricultural goods in developing countries. Moreover, complex production and distribution processes can lead to formation of supply chains that are a natural example of chains of intermediaries [13].

Most existing research in intermediation processes was set in a competitive context, by trying to answer questions like: i) how do networks of intermediaries emerge?, ii) what are the mechanisms for dynamic network formation?, iii) what is the network impact on the trading outcome of participants?, and iv) how can we assess and control the power gained by intermediation in resale networks? Research works on these topics used approaches inspired by: social and economic networks [16], bargaining games [25], and formal methods in Computer Science [2].

Related research has been carried out on the network flow optimization problem in the domain of Operations Research [1]. The problem has been addressed under various contexts imposing for example budget constraints or multi-commodity distribution. The research literature on this subject is quite reach.

Nevertheless, the flow optimization problem has notable differences from our particular problem of providing collective profitability in semi-competitive intermediation networks. More specifically, flow optimization problems are interested to optimize the transport of a specific amount of flow through a given network under given capacity and / or budget constraints [15]. For example, multi-commodity distribution in automotive industry simultaneously addresses facility location and supply chain network design [7], thus being mainly concerned about planning and vehicle routing issues, rather than profitability of network participants.

In our work we are interested in semi-competitive intermediation. We assume that participant agents are collaborating to ensure that the underlying business process is achieving its functions, while they are self-interested by seeking to maximize their own profit and improve their longer-term welfare. The research goal is to propose correctness criteria for aligning the structure of the intermediation network with participant pricing strategies in order to provide their collective profitability. Achievement of this goal ensures participant incentives for engaging in semi-competitive intermediation, and thus providing the sustainability and robustness of the whole intermediation chain.

3 A network-based model of intermediation

Let us assume that a company is interested to distribute a set of products and/or services $P = {1, 2, \dots, k}$ to the market of its potential customers. The whole distribution process is managed by a set of agents called sellers in what follows. Let us assume that the distribution department of this company is organized as a set $S$ of seller agents such that each agent $S \in S$ is responsible for the management of the distribution of a nonempty subset of products $P_{S} \subseteq P$ . We assume that seller agents are not in conflict or competition, i.e. they are not assigned overlapping duties. So formally, the family of sets ${P_{S}}_{S \in S}$ defines a non-trivial partition of $P$ .

Let us assume that $B$ is the set of “potential customers”, called buyers in what follows, that are interested to “purchase” some of the products in $P$ . So each buyer agent $B \in B$ is interested in a nonempty subset of products $P_{B} \subseteq P$ . We assume that buyers are not in competition, i.e. they do not have overlapping purchases, so the family of sets ${P_{B}}_{B \in B}$ defines a partition of $P$ . Note that in fact these buyers are still part of the company’s distribution process, i.e. they are not the real “end customers” of the company products and/or services, thus partly explaining our assumption. In some sense they define the last level of intermediation representing “end-level dealers”, before the company products actually reach the market. Obviously, these agents can enter in competition with agents representing other companies, but this aspect is not captured into our model.

Moreover, the process contains a set of intermediaries $I$ representing “mid-level” dealers that help connecting the seller agents with the buyer agents. Each intermediary $I \in I$ has both “buyer”, as well as “seller” role, thus reflecting its intermediation position in the network. Agent I acquires one or more products from one or more provider agents that can be either seller agents from $S$ or other intermediaries from $I$ . Then agent I provides the acquired products to other agents that can be either buyers from $B$ or other intermediaries from $I$ .

Note that our model follows exactly the description of [13]: “Intermediaries accomplish the task by buying from sellers or from other intermediaries and reselling to buyers or to other intermediaries. Intermediaries do not just match buyers and sellers or mediate the transaction; they are dealers.”. This entirely explains the “buyer-seller” paradigm that we use for defining the roles of our agents, following the tradition of “buyer-seller networks” from [21]. This also shows that although our agents are placed in a collaborative setting, they still posses private goals.

Intermediation is a complex activity that can be represented by a business process with a complex structure capturing the company distribution operations over a set of multiple interconnected distribution channels. This process enables the business to distribute its products by engaging seller agents $S$ through a complex intermediation structure connecting them to the potential customer agents $B$ through a complex network of intermediaries or dealers. Let us call this structure an intermediation DAG.

Intuitively, the structure of an intermediation process defines a Directed Acyclic Graph (DAG in what follows). Formally, an intermediation business process is modelled by a directed graph $G = 〈 V, A 〉$ . $V$ is the set of graph vertices capturing the agents (buyers, sellers and intermediaries),while $V$ is the set of directed edges or arcs, capturing agent interactions. Let us introduce the following functions:

$in : V \to 2^{V}$ defined as $in (v) = {u | (u, v) \in A}$ for all $v \in V$

$out : V \to 2^{V}$ defined $out (v) = {u | (v, u) \in A}$ for all $v \in V$

Note that a DAG always contains at least one vertex v with in (v) =∅ and at least one vertex w with out (w) =∅, i.e. an intermediation process contains at least one seller and one buyer agent. So, in what follows we shall define vertices v with no incoming arcs, i.e. in (v) =∅, to represent the seller agents, and vertices w with no outgoing arcs, i.e. out (w) =∅, to represent the buyer agents. Vertices u such that they have at least one incoming arc and at least one outgoing arc, i.e. in (u)≠ ∅ and out (u)≠ ∅, are defined to represent intermediary agents. Observe that an intermediary agent has dual buyer and seller (actually re-seller) role. An empty set of intermediary nodes captures the situation when our business process does not contain intermediation activities.

A basic requirement is that the intermediation graph must be a DAG, i.e. it does not contain cycles. This is motivated by the fact that it is both inefficient and counter-intuitive to let an agent sell a product and then latter re-purchase in a distribution channel with the overall goal of distributing the product to the end customers as efficiently as possible. This intuition can be formally captured with the following definition of an intermediation DAG.

Definition 1. (Intermediation DAG) Let $S$ , $B$ , and $I$ be three finite, nonempty and pairwise disjoint sets of seller, buyer and intermediary agents, and let $P$ be a finite set of products. An intermediation DAG is defined by quadruple $G = 〈 V, A, p, g 〉$ such that:

$〈 V, A 〉$ is a DAG with the set of vertices defined as $V = S \cup B \cup I$ such that:

in (s) =∅ for all $s \in S$ and out (b) =∅ for all $b \in B$

in (i)≠ ∅ and out (i)≠ ∅ for all $i \in I$

$p : V \to 2^{P} \ {\emptyset}$ and $g : A \to 2^{P} \ {\emptyset}$ are two functions mapping agents (vertices) and transactions (arcs) to nonempty sets of products such that:

{g ((u, v))} _v∈out(u) is a nontrivial partition of set p (u) for each $u \in S \cup I$

{g ((u, v))} _u∈in(v) is a nontrivial partition of set p (v) for each $v \in I \cup B$

$\cup_{s \in S} p (s) = \cup_{b \in B} p (b) = P$

Part i of Definition 1 states the basic requirement that the underlying graph of an intermediation process must be a DAG. Part ii of Definition 1 states the conditions for correct product flow from sellers to buyers.

Figure 1 presents an example of intermediation DAG containing 8 agents such that: $S = {1, 2}$ , $B = {5, 7, 8}$ , and $I = {3, 4, 6}$ .

Fig.1

DAG-based intermediation process.

For each arc (u, v), the set g ((u, v)) denotes the products that are transacted by seller agent agent u and buyer agent v. For example g ((6, 7)) = {1} means that seller agent 6 and buyer agent 7 are transacting product 1.

For each agent u, the set p (u) denotes the products that are managed by agent u. If u has seller role then p (u) denotes the products sold by u. If u has buyer role then p (u) denotes the products bought by u. If u has an intermediary position then p (u) captures the products bought and resold by agent u.

Observe that if $S \in S$ then p (S) = P_S and if $B \in B$ then p (B) = P_B. Moreover, Fig. 1 shows that p (1) = P₁ = {1, 2} and p (7) = P₇ = {1}.

Condition i.1 of definition 1 states that each seller agent is responsible only with selling its assigned products to other agents. For example, agent 2 sells products 2 and 1 to agents 3 and respectively 4. Condition i.2 states that each buyer agent is responsible only with buying its assigned products from other agents. For example, agent 7 purchases product 1 from agent 6.

Condition i.3 states that each intermediary agent is actually intermediating at least one transaction by buying and then reselling at least one product. For example, agent 4 purchases products 1 and 4 from agents 1 and respectively 2, while also selling both products {1, 4} in a single bundle to agent 6.

Condition ii.1 states that each agent, excepting buyer agents, is involved in selling activities such that: it sells all its assigned products to the outgoing agents, while never selling the same product twice to different agents. For example, agent 6 sells products {1, 2, 4} to agents 7 and 8 such that it sells product {1} to agent 7 and products {2, 4} to agent 8.

Condition ii.2 states that each agent, excepting seller agents, is involved in buying activities such that: it buys all its assigned products of the incoming agents, while never buying the same product twice from different agents. For example, agent 4 buys products {1, 4} from agents 1 and 2 such that it buys product {1} to agent 1 and product {2} from agent 2.

Last but not least, condition ii.3 states that all the products sold by the seller agents eventually reach the buyer agents. For example Fig. 1 illustrates that p (1) ∪ p (2) = {1, 2} ∪ {3, 4} = {1, 2, 3, 4}, while p (5) ∪ p (7) ∪ p (8) = {1} ∪ {3} ∪ {2, 4} = {1, 2, 3, 4}, showing that condition ii.3 holds.

A directed graph is called weakly connected if by removing the arc orientation we obtain a connected undirected graph. We restrict our attention to weakly connected intermediation DAGs. If the weakly connected property is dropped then this means that the graph can be decomposed into disjoint connected components. As each component is a weakly connected intermediation DAG, it can be analyzed in isolation.

A weakly connected intermediation DAG for given sets of buyer, seller, and intermediation agents must contain a minimum number of intermediation transactions to ensure that the products correctly flow from selling side to buying side.

Proposition 1. (Number of transactions) If a weakly connected intermediation DAG has t transactions then t satisfies the inequality: $t \geq | S | + | B | + | I | - 1$

This property follows from the observations that t represents the number of arcs and that a weakly connected directed graph with n vertices contains at least n - 1 arcs. We obtain equality for the special case when the intermediation DAG reduces to a rooted tree [5].

Consider for example the DAG shown in Fig. 1. We have: t = 8, $| S | = 2$ , $| B | = 3$ , and $| I | = 3$ , so the inequality holds. Note that the inequality is strict as the DAG is not a rooted tree. The minimum number of intermediation transaction is 7 in this particular case.

4 Collectively profitable networks

The structure of a complex intermediation transaction is rigorously defined by an intermediation DAG. However, the problem of creating these structures is not in the scope of the present paper. Nevertheless, we can imagine that involved seller, intermediation and buyer agents can use the services provided by suitable middle-agents [3, 10], computational methods of service composition [14], and standard interaction protocols [22] combined with well-defined collaborative e-business models based on customer relations and trust management [22], to incrementally and autonomously create the business process that represents the intermediation DAG.

The next step of developing our model consists in the assignment of economic information to each component of an intermediation DAG.

Let us denote with $P \subseteq P$ a nonempty set of products. We define the limit price $σ_{P}^{s}$ of seller s for selling the set P of products. The meaning is that s will agree to sell the set P of products only when price p is such that $p \geq σ_{P}^{S}$ . Similarly, we define the limit price $β_{P}^{b}$ of buyer b for buying the set P of products. The meaning is that b will agree to purchase the set P of products only when price p is such that $p \leq β_{P}^{b}$ .

We proceed by showing how can we augment an intermediation DAG with annotations containing limit and transaction prices. Limit prices are attached to sellers and buyers, while transaction prices are attached to arcs denoting transactions of the intermediation DAG.

Definition 2. (Annotated intermediation DAG) Let $G = 〈 V, A, p, g 〉$ be an intermediation DAG. We define the annotated version of G as $G^{a} = 〈 V, A, p, g, π 〉$ such that the extra parameter $π : S \cup B \cup A \to (0, + \infty)$ denotes the annotation function for attaching economic information to each component of G as follows:

If $s \in S$ is a seller agent then $π (s) = σ_{p (s)}^{s} > 0$ represents the limit price of seller s for selling the set of products p (s)

If $b \in B$ is a buyer agent then $π (b) = β_{p (b)}^{b} > 0$ represents the limit price of buyer b for buying the set of products p (b)

If $t = (u, v) \in A$ is a transaction then $π (t) = π_{g ((u, v))}^{u, v} > 0$ represents the transaction price for which agent u sells the products g ((u, v)) to agent v.

Let us consider Fig. 1 showing that transaction price $π_{{1, 4}}^{4, 6}$ is attached to the arc linking node 4 to node 6, while limit prices $σ_{{3, 4}}^{2}$ and $β_{{1}}^{7}$ are attached to nodes 2 and 7.

Let us look at a potential transaction from the point of view of a seller s with limit price σ. Let us also assume that s agreed to transact using price π. The utility gained by seller s is π - σ, so this transaction is profitable for s if and only if π - σ ≥ 0.

Now let us apply the same reasoning for a buyer b with limit price β that agreed to transact for a price π. The utility gained by B is β - π, so this transaction is profitable for b if and only if β - π ≥ 0.

Combining these results by considering agents b and s together, the transaction will be profitable for both, i.e. collectively profitable, if and only if β ≥ σ. Conversely, if this condition holds then we can set the transaction price to any arbitrary value π ∈ [σ, β]. Note that the DAG with two nodes b and s and one arc from s to b is also the simplest example of nontrivial “intermediation network” (see Fig. 2) where actually no intermediation occurs, as there are no intermediary agents involved.

Fig.2

Simplest nontrivial intermediation DAG.

Nevertheless, the same reasoning can be applied to an intermediary agent that is involved in a buying transaction with price π_b, as well as in a selling transaction with price π_s. His utility will be π_s - π_b and the agent is profitable if and only if π_s ≥ π_b.

We can apply this observation to generalize the results by formulating a necessary and sufficient condition of the collective profitability of an arbitrary intermediation DAG.

Definition 3. [Collective profitability] Let G be an intermediation DAG and σ and β two vectors of limit prices of buyers and sellers that are present in G. Then G is called collectively profitable if and only if we can annotate G with transaction prices such that each transaction participant gains by performing the transaction, i.e. it is profitable.

A participant $v \in V$ is profitable if and only if it gains a positive utility, i.e. u (v) >0. We can compute utility u (v) as follows:

The utility of a seller agent $s \in S$ is defined as follows: $\begin{matrix} u (s) = - σ_{p (s)}^{s} + \sum_{v \in out (s)} π_{g ((s, v))}^{s, v} \end{matrix}$ (1)

The utility of a buyer agent $b \in B$ is defined as follows: $\begin{matrix} u (b) = β_{p (b)}^{b} - \sum_{v \in in (b)} π_{g ((v, b))}^{v, b} \end{matrix}$ (2)

The utility of an intermediary agent $i \in I$ is defined as follows: $\begin{matrix} u (i) = \sum_{v \in out (i)} π_{g ((i, v))}^{i, v} - \sum_{v \in in (i)} π_{g ((v, i))}^{v, i} \end{matrix}$ (3)

We construct a system of linear inequalities by considering inequalities attached to the nodes of the intermediation graph according to Definition 3 and Eq. (1–3). The resulting system (4) consists of $| V | = | S | + | B | + | I |$ inequalities and t variables, where $t = | A |$ is the number of transactions (see Proposition 1). $\begin{matrix} - σ_{p (s)}^{s} + \sum_{v \in out (s)} π_{g ((s, v))}^{s, v} \geq 0 & s \in S \\ β_{p (b)}^{b} - \sum_{v \in in (b)} π_{g ((v, b))}^{v, b} \geq 0 & b \in B \\ \sum_{v \in out (i)} π_{g ((i, v))}^{i, v} - \sum_{v \in in (i)} π_{g ((v, i))}^{v, i} \geq 0 & i \in I \end{matrix}$ (4)

The following lemma states a necessary and sufficient condition for the collective profitability of an intermediation DAG.

Lemma 1. An intermediation DAG is collectively profitable if and only it can be annotated with transaction prices such that the system of inequalities (4) is satisfied.

The result of Lemma 1 follows immediately by connecting the Eq. (1–3) that define utilities u (s), u (b), and u (i) with the profitability condition of each participating agent. Note that however, this result is not immediately usable. In what follows we are refining it by formulating a set of practically usable conditions defined as a system of linear homogeneous inequalities [11].

5 Collective profitability conditions

The expression of profitability conditions can be facilitated by defining a function that maps each set of nodes $W \subseteq V$ of the intermediation DAG to the set of nodes reachable from W. Let us call this function $reachable : 2^{V} \to 2^{V}$ . It is well-defined for DAGs using recursive Eq. (5). $\begin{matrix} reachable (\emptyset) = \emptyset \\ reachable (W) = \\ W \cup ⋃_{w \in W} reachable (out (w))) \end{matrix}$ (5)

If $W \subseteq V$ then we are also interested to determine the leaf nodes (representing buyers) reachable from W, using function leaves defined by Eq. (6). $\begin{matrix} leaves (W) = reachable (W) \cap B B \end{matrix}$ (6)

We consider the image of the restriction of function leaves to the set $2^{S} \ {\emptyset}$ , let us call it $B \subseteq 2^{B} \ {\emptyset}$ .

The set of necessary (and possibly sufficient) conditions for collective profitability is defined using a set P of pairs of sets (B, S_B) for all subsets B ∈ B such that $S_{B} \subseteq S$ is the unique maximal subset of B with respect to set inclusion such that Eq. (7) holds. Let us call this the set of matching pairs of an intermediation DAG. $\begin{matrix} leaves (S_{B}) = B \end{matrix}$ (7)

Referring to the intermediation DAG from Figure 1, observe that: $\begin{matrix} reachable ({2}) = {2, 4, 5, 6, 7, 8} \\ leaves ({2}) = leaves ({1, 2}) = {5, 7, 8} \\ B = {{7, 8}, {5, 7, 8}} \\ P = {({7, 8}, {1}), ({5, 7, 8}, {1, 2})} \end{matrix}$

Proposition 2. (Necessary condition) Let us consider an intermediation DAG denoted $G = 〈 V, A, p, g 〉$ and let P_G be its set of matching pairs. If G is collectively profitable then the system (8) of linear homogenous inequations holds. $\begin{matrix} \forall (B, S_{B}) \in P_{G} \sum_{b \in B} β_{p (b)}^{b} \geq \sum_{s \in S_{B}} σ_{p (s)}^{s} \end{matrix}$ (8)

Proof sketch. If G is collectively profitable then according to Lemma 1, the set of inequalities (4) has at least one solution given by prices π. Each inequality corresponds exactly to one graph node.

Let us consider an arbitrary inequality from inequalities (8) corresponding to (B, S) ∈ P_G. Let V_S = reachable (S) and let us denote with $A_{S} = \cup_{v \in V_{S}} (in (v) \ V_{S}) \times {v}$ the set of arcs originating outside V_S and flowing into V_S, Note that if $S \subset S$ is strict then A_S is definitely nonempty.

Let us consider the sum of the subset of inequalities (4) corresponding to nodes V_S. After the obvious simplifications we obtain inequality (9). Taking into account that elements prices π are positive, inequalities (8) follow immediately. $\begin{matrix} \sum_{b \in B} β_{p (b)}^{b} - \sum_{s \in S_{B}} σ_{p (s)}^{s} \geq \sum_{(v, w) \in A_{S}} π_{g ((w, v))}^{wv} \end{matrix}$ (9)

■

There are two observations related to Proposition 2.

Observation 1. Note the restriction to the set of inequalities corresponding to matching pairs, rather than considering all the pairs (S, leaves (S)) for each nonempty set S of sellers. Clearly, each such pair is able to generate an inequality of type (8). The restriction is motivated by the fact that if S₁ ⊂ S₂ and leaves (S₁) = leaves (S₂) then the equation derived from pair with S₁ is redundant, resulting from the inequality generated from pair with S₂ so it can be discarded.

Observation 2. The set of inequalities (8) is consistent, i.e. there are always limit prices σ and β satisfying them for each intermediation DAG. This statement can be formally proven using results of Dines regarding systems of linear inequalities [11]. In our case the system matrix has the property that each column contains either 1s or -1s (never both) and possibly 0s. This drastically simplifies the definition of I-complements and I-minors, to find out that the I-rank of this matrix is always strictly positive, so that conditions of Dines’s theorem hold. Note however that Dines’s theorem doesn’t ensure that the solution is consisting of positive values. Nevertheless, if this is not the case then the solution can be easily transformed into a positive solution using a suitable translation scheme.

Applying the result of Proposition 2 for the intermediation DAG shown in Fig. 1, we obtain inequalities (10). So, if this intermediation DAG is collectively profitable we will conclude that inequalities (10) hold. Moreover, if at least one of them is not satisfied then the intermediation DAG is not collectively profitable. $\begin{matrix} β_{1}^{7} + β_{2, 4}^{8} + β_{3}^{5} \geq σ_{1, 2}^{1} + σ_{3, 4}^{2} \\ β_{1}^{7} + β_{2, 4}^{8} \geq σ_{1, 2}^{1} \end{matrix}$ (10)

We believe that the reciprocal of Proposition 2 is true, thus providing not only a necessary, but also sufficient condition for collective profitability. In the context of the example from Fig. 1 this would mean that if inequalities (10) hold then the intermediation DAG is collectively profitable.

We focus now on providing a formal proof of this result for single-rooted intermediation DAGs. Note that this situation also covers intermediation trees [5]. This proof is an update of our proving approach initially presented in [6].

Please note also that for single-rooted intermediation DAGs, system of inequalities (8) reduces to a single equation corresponding to the matching pair $({s}, B)$ where s is the single seller representing the root of the single-rooted intermediation DAG. Moreover, as the graph is weakly connected the equality $leaves (s) = B$ trivially holds.

Proposition 3. (Sufficient condition) If a single-rooted intermediation DAG $G = 〈 V, A, p, g 〉$ with root s satisfies the following condition: $\begin{matrix} \sum_{b \in B} β_{p (b)}^{b} \geq σ_{p (s)}^{s} \end{matrix}$ (11)then it is collectively profitable. We can prove Proposition 3 using a classic result of linear algebra known as Farkas’ lemma [12]. We review this result, and then we proceed to the proof outline.

Theorem 1. (Farkas’ lemma [12]) Let us consider two nonzero matrices $A \in ℝ^{m} \times ℝ^{n}$ and $b \in ℝ^{m}$ . Then only one of the following conditions holds:

The system Ax = b has a strictly positive solution $u \in ℝ^{n}$ .

There exists a vector $v \in ℝ^{m}$ such that v^TA ≤ 0 and v^Tb > 0.

Proof sketch (of Proposition 3). In Eq. (4) are transformed into Eq. (12): $\begin{matrix} A π = b + α \end{matrix}$ (12) If we denote with n the number of nodes and with e is the number of arcs of the intermediation DAG then: $A \in ℝ^{n} \times ℝ^{e}$ , $b, α \in ℝ^{n}$ , and $π \in ℝ^{e}$ . Note also that A is the incidence matrix of the DAG and b can be defined as follows: $\begin{matrix} b_{s} & = σ_{p (s)}^{s} & s \in S \\ b_{b} & = - β_{p (b)}^{b} & b \in B \\ b_{i} & = 0 & i \in I \end{matrix}$ (13) Then the following condition holds: $\begin{matrix} \sum_{b \in B} β_{p (b)}^{b} = σ_{p (s)}^{s} + \sum_{i = 1}^{n} α_{i} \end{matrix}$ (14)

Then, according to Farkas’ lemma, we must find values of parameters α_i ≥ 0 such that there is no vector $v \in ℝ^{n}$ that satisfies v^TA ≤ 0 and v^T (b + α) >0.

We define a partition $(X_{b})_{b \in B}$ of the set of graph nodes $B \cup I$ such that:

For each $b \in B$ we have $b \in X_{b}$ .

For each $b \in B$ and $x \in X_{B}$ node x is a member of the path from root s to b.

Following (14) we obtain: $\begin{matrix} \sum_{b \in B} (β_{p (b)}^{b} - α_{b}) > \sum_{b \in B} \sum_{i \in X_{b} \ {b}} α_{i} \end{matrix}$ (15)

According to (15), we can choose α_i > 0 for all i = 1, …, n such that for each $b \in B$ in equality (16) holds. $\begin{matrix} β_{p (b)}^{b} - α_{b} > \sum_{i \in X_{b} \ {b}} α_{i} \end{matrix}$ (16)

We assume by contradiction that there exists a vector $v \in ℝ^{n}$ such that v^TA ≤ 0 and v^T (b + α) >0, i.e. conditions (ii) of Farkas’ lemma are met.

But v^TA ≤ 0, so for each node $b \in B$ and for each node $i \in I$ on a path from s to i we have: $\begin{matrix} v_{b} \geq v_{i} \end{matrix}$ (17)

After a simple algebraic transformation, substituting $σ_{p (s)}^{s}$ from Eq. (14) into in equality v^T (b + α) >0, we obtain: $\begin{matrix} \sum_{b \in B} (v_{b} - v_{s}) (β_{p (b)}^{b} - α_{b}) < \sum_{i \in I} (v_{i} - v_{s}) α_{i} \end{matrix}$ (18)

Inequality (18) can be rewritten into equivalent form (19). $\begin{matrix} \sum_{b \in B} (v_{b} - v_{s}) (β_{p (b)}^{b} - α_{b}) < \\ \sum_{b \in B} \sum_{i \in X_{b} \ {b}} (v_{i} - v_{s}) α_{i} \end{matrix}$ (19)

However, one can easily observe that inequality (19) contradicts (16) and (17), thus concluding our proof of Proposition 3.■

6 Discussion

The goal of this section is to reflect a bit on the result formulated by Proposition 2. Firstly, we address the possible limits of applying the conditions of this proposition. For that, it is enough to provide a suitable example addressing this aspect (see Section 6.1). Secondly, we focus on the sufficiency of conditions stated by Proposition 2 for ensuring the collective profitability of an intermediation DAG. Although we were not able to provide a general mathematical proof of this result, we consider the case study from Fig. 1 showing that in this particular situation the conditions are sufficient, i.e. if inequalities (10) hold then the intermediation DAG is collectively profitable (see Section 6.2).

6.1 Number of Inequalities

One question regards the applicability of the conditions stated by Proposition 2. We are interested to analyze if there are any potential limits of using them.

It is not immediately noticeable that the number of inequalities of system (8) can grow very fast, actually exponentially, with the number of nodes of the intermediation graph. The main concern of this section is to support this claim by means of an example. Obviously, this will highlight some possible limit of our model.

Let us consider a DAG with 2N + 1 nodes such that N = 4n - 2 where n ≥ 1 is a given natural number. We assume that the graph nodes are numbered with the values from 1 to 2N + 1. Let us assume that nodes 1, 2, …, N represent sellers and nodes N + 1, N + 2, …, 2N + 1 represent buyers. Let us also assume that the arcs (transactions) of this graph are represented by the ordered pairs (i, i + N) and (i, i + N + 1) for all i = 1, 2, …, N.

Figure 3 illustrates this graph for n = 2. Products are not relevant for this example, so they are omitted from this figure. In this case N = 4n - 2 =6 so this graph has 2N + 1 =13 nodes.

Fig.3

Intermediation DAG that contains many matching pairs.

Let us consider the subsets of sellers S of the form {i₁, i₂, …, i_n} defined for i_j ∈ {4j - 3, 4j - 2} for all j = 1, 2, …, n}. Referring to the graph shown in Fig. 3, these subsets are: {1, 5}, {2, 5}, {1, 6}, and {2, 6}.

Note that i_j + 3 ≤ i_j+1 for all j = 1, 2, …, n - 1. This shows that: $\begin{matrix} leaves (S) = {i_{1} + N, i_{1} + N + 1, \\ i_{2} + N, i_{2} + N + 1, \dots, \\ i_{n} + N, i_{n} + N + 1} \end{matrix}$

Clearly, each subset of sellers S defined in this way cannot be extended to a superset S ⊂ S′ such that leaves (S) = leaves (S′). So each pair (leaves (S) , S) is a matching pair of the intermediation graph and it will generate an inequality of type (8). Referring to the graph shown in Fig. 3, these matching pairs are: $\begin{matrix} ({7, 8, 11, 12}, {1, 5}) \\ ({8, 9, 11, 12}, {2, 5}) \\ ({7, 8, 12, 13}, {1, 6}) \\ ({8, 9, 12, 13}, {2, 6}) \end{matrix}$

But there are exactly 2ⁿ matching pairs of this type. The total number of matching pairs of this graph is clearly larger than this value ! This shows that the number of inequalities generated for this graph according to Proposition 2 is exponential in the number of graph nodes, thus supporting our claim.

6.2 Case Study

Let us consider the intermediation DAG from Fig. 1. In this case conditions (8) are particularized to inequalities (10). So we must show that if conditions (10) hold then system of inequalities (20) has positive solutions (products are omitted from the notation as they are not relevant for this discussion; moreover, indexes of nodes are now represented as subscripts, rather than as superscripts as in the original notation). $\begin{matrix} - σ_{1} + π_{13} + π_{14} & \geq 0 \\ - σ_{2} + π_{24} + π_{25} & \geq 0 \\ - π_{13} + π_{36} & \geq 0 \\ - π_{14} - π_{24} + π_{46} & \geq 0 \\ β_{5} - π_{25} & \geq 0 \\ - π_{36} - π_{46} + π_{67} + π_{68} & \geq 0 \\ β_{7} - π_{67} & \geq 0 \\ β_{8} - π_{68} & \geq 0 \end{matrix}$ (20)

But system of inequalities (20) has a positive solution if and only if there exists values α_i ≥ 0 such that the system of linear equalities (21) has a positive solution. $\begin{matrix} - σ_{1} + π_{13} + π_{14} & = α_{1} \\ - σ_{2} + π_{24} + π_{25} & = α_{2} \\ - π_{13} + π_{36} & = α_{3} \\ - π_{14} - π_{24} + π_{46} & = α_{4} \\ β_{5} - π_{25} & = α_{5} \\ - π_{36} - π_{46} + π_{67} + π_{68} & = α_{6} \\ β_{7} - π_{67} & = α_{7} \\ β_{8} - π_{68} & = α_{8} \end{matrix}$ (21)

Let: $\begin{matrix} Δ_{1} & = β_{7} + β_{8} - σ_{1} \geq 0 \\ Δ_{2} & = β_{7} + β_{8} + β_{5} - σ_{1} - σ_{2} \geq 0 \end{matrix}$

Solving system (21) we obtain solutions (22). $\begin{matrix} π_{13} & = α_{1} + σ_{1} - π_{14} \\ π_{14} & = π_{14} \\ π_{24} & = Δ_{1} - α_{1} - α_{3} - α_{4} - α_{6} - α_{7} - α_{8} \\ π_{25} & = β_{5} - α_{5} \\ π_{36} & = σ_{1} + α_{1} + α_{3} - π_{14} \\ π_{46} & = Δ_{1} - α_{1} - α_{3} - α_{6} - α_{7} - α_{8} + π_{14} \\ π_{67} & = β_{7} - α_{7} \\ π_{68} & = β_{8} - α_{8} \end{matrix}$ (22)

Positivity of all solutions of system (21) is ensured if positive parameters α_i and π₁₄ satisfy inequalities 23. $\begin{matrix} α_{1} + α_{3} + α_{4} + α_{6} + α_{7} + α_{8} & < Δ_{1} \\ α_{8} & < β_{8} \\ α_{7} & < β_{7} \\ α_{5} & < β_{5} \\ π_{14} & < σ_{1} \\ α_{1} + α_{3} + α_{4} + α_{5} + α_{6} + α_{7} + α_{8} & < Δ_{2} \end{matrix}$ (23)

We can choose α_i and π₁₄ according to (24), thus ensuring that inequalities (23) hold. $\begin{matrix} α_{1} = α_{3} = α_{4} = α_{5} = α_{6} = α_{7} = α_{8} = h \\ α_{2} = Δ_{2} - 7 h \\ π_{14} = p \\ 0 < h < min {β_{5}, β_{7}, β_{8}, \frac{Δ_{2}}{6}, \frac{Δ_{1}}{7}} \\ 0 < p < σ_{1} \end{matrix}$ (24)

Concluding, we can determine the values of π with Eq. (25). It can be easily verified that these values are positive and satisfy system (21), thus concluding our proof. $\begin{matrix} π_{13} & = h + σ_{1} - p \\ π_{14} & = p \\ π_{24} & = Δ_{1} - 6 h \\ π_{25} & = β_{5} - h \\ π_{36} & = σ_{1} + 2 h - p \\ π_{46} & = Δ_{1} - 5 h + p \\ π_{67} & = β_{7} - h \\ π_{68} & = β_{8} - h \end{matrix}$ (25)

7 Conclusions

The achievement of this paper is the proposal of a novel formal model of intermediation business processes of a company or business consortia for distributing their products or services to the market of potential consumers. The model captures a complex intermediation transaction as a DAG, thus being able to serve multiple distribution channels working simultaneously and possibly sharing intermediary agents.

Based on this model, we proposed necessary and sufficient algebraic conditions of collective profitability of an intermediation transaction. They were formulated as systems of linear inequalities involving limit prices of buyer and seller agents. Our results are supported by formal mathematical proofs involving classic results in algebra of linear inequations with positive solutions. We also presented an example showing that the number of inequality conditions can grow exponentially with the number of agents in the intermediation DAG.

Promising future work involves the application of the concepts of welfare economics to analyze optimal pricing strategies of the transaction participants, supported by practical computational methods to determine these optimal strategies. We are also interested to study the stability of participants’ pricing strategies using the results of game theory.

References

Ahuja

R.K.

, Magnanti

T.L.

and Orlin

J.B.

, Network Flows: Theory, Algorithms, and Applications, Pearson, 1993.

Bădică

, Budimac

, Burkhard

H.-D.

and Ivanović

, Software agents: Languages, tools, platforms, Computer Science and Information Systems 8(2)(2011), 255–298. doi: 10.2298/CSIS110214013B

[3] Bădică

and Bădică

, FSP and FLTL framework for specification and verification of middle-agents, Applied Mathematics and Computer Science 21(1) (2011), 9–25. doi: 10.2478/v10006-011-0001-6

Bădică

, Ilie

, Muscar

, Bădică

, Sandu

, Sbora

, Ganzha

and Paprzycki

, Distributed agent-based online auction system, Computing and Informatics 33(3) (2014), 518–552. http://www.cai.sk/ojs/index.php/cai/article/view/2216

Bădică

, Bădică

, Ivanović

and Buligiu

, Collective Profitability and Welfare in Selling-Buying Intermediation Processes. Computational Collective Intelligence. ICCCI Part II. Lecture Notes in Computer Science, 9876, Springer, Cham, 2016, pp. 14–24. doi: 10.1007/978-3-319-45246-32

Bădică

, Bădică

, Ivanović

and Logofătu

, Collective Profitability of DAG-Based Selling-Buying Intermediation Processes. Intelligent Distributed Computing XII. 12th International Symposium on Intelligent Distributed Computing, IDC 2018. Studies in Computational Intelligence, 798, Springer, Cham, 2018, pp. 414–424. doi: 10.1007/978-3-319-99626-4_3

Boujelben

M.K.

, Gicquel

and Minoux

, A distribution network design problem in the automotive industry: MIP formulation and heuristics. Computers and Operations Research, 52, Part A, Elsevier, 2014, pp. 16–28. doi: 10.1016/j.cor.2014.07.007

Cook

K.S.

and Emerson

R.M.

, Power, equity and commitment in exchange networks, American Sociological Association 43 (1978), 721–739, doi: 10.2307/2094546

Decker

, Sycara

and Williamson

, Middle-Agents for the Internet, Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97), Nagoya, Aichi, Japan, Vol. 1, pp. 1997, 578–583.

10.

Dignum

, Tranier

and Dignum

, Simulation of intermediation using rich cognitive agents, Simulation Modelling Practice and Theory 38(10) (2010), 1526–1536. Elsevier. 10.1016/j.simpat.2010.05.011

11.

Dines

L.L.

, Systems of linear inequalities, Annals of Mathematics, Second Series 20(3) (1919), 191–199. Mathematics Department, Princeton, doi: 10.2307/1967869

12.

(Gyula) Farkas

, Über die theorie der einfachen ungleichungen, Journal für die Reine und Angewandte Mathematik 124(124) (1902), 1–27. doi: 10.1515/crll.1902.124.1

13.

Galeotti

and Condorelli

, Strategic Models of Intermediation Networks, In: Bramoullé

, Galeotti

and Rogers

, (Eds.) The Oxford Handbook of the Economics of Networks, Oxford University Press Chater 27, 2016, pp. 733–753. doi: 10.1093/oxfordhb/9780199948277.013.16

14.

Coria

J.A.G.

, Castellanos-Garzón

J.A.

and Corchado

J.M.

, Intelligent business processes composition based on multi-agent systems, Expert Systems with Applications 41(4) (2014), 1189–1205. Part 1. Elsevier. doi: 10.1016/j.eswa.2013.08.003

15.

Holzhauser

, Krumke

S.O.

and Thielen

, Budget-constrained minimum cost flows, Journal of Combinatorial Optimization 31(4) (2016), 1720–1745. Springer. doi: 10.1007/s10878-015-9865-y

16.

Jackson

M.O.

, Social and Economic Networks, Princeton University Press, 2010.

17.

Jehle

G.A.

and Reny

P.J.

, Advanced Microeconomic Theory, Third Edition. Pearson Education Limited, 2011.

18.

Jennings

N.R.

and Wooldridge

, Applications of Intelligent Agents, In: Jennings

N.R.

and Wooldridge

M.J.

, (eds.): Agent Technology, Springer Berlin Heidelberg, 1998, pp. 3–28. doi: http://dl.acm.org/citation.cfm?id=277789.277799

19.

Kanter

R.M.

, Collaborative advantage: The art of alliances, Harvard Business Review 72(4) (1994), 96–108.

20.

Kerin

R.A.

, Hartley

S.W.

and Rudelius

, Marketing (12th Edition). McGraw-Hill Education, 2014.

21.

Kranton

R.E.

and Minehart

D.F.

, A theory of buyer-seller networks, The American Economic Review 91(3) (2001), 485–508, American Economic Association, doi: 10.1257/aer.91.3.485

22.

Kravari

, Kontopoulos

and Bassiliades

, Trusted reasoning services for semantic web agents, Informatica (Slovenia) 34(4) (2010), 429–440. http://www.informatica.si/index.php/informatica/article/view/317

23.

Laudon

K.C.

and Traver

C.G.

, E-Commerce 2014 (10th Edition). Pearson, 2010.

24.

Leon

and Bădică

, An optimization web service for a freight brokering system, Service Science 9(4) (2017), 324–337. Informs. doi: 10.1287/serv.2017.0191

25.

Manea

, Intermediation and resale in networks, Journal of Political Economy 126(3) (2018), 1250–1301. The University of Chicago Press. doi: 10.1086/697205

26.

Nagurney

and Ke

, Financial networks with intermediation: Risk management with variable weights, European Journal of Operational Research 172(1) (2006), 40–63. Elsevier, 10.1016/j.ejor.2004.09.035

27.

Nault

B.R.

and Dexter

A.S.

, Agent-intermediated electronic markets in international freight transportation, Decision Support Systems 41(4) (2006), 787–802. Elsevier, 10.1016/j.dss.2004.10.008

28.

Nguyen

N.T.

, Inconsistency of knowledge and collective intelligence, Cybernetics and Systems 39(6) (2008), 542–562. Taylor & Francis, doi: 10.1080/01969720802188268

29.

Patil

, Buyer-seller networks with demand shocks and intermediation, Review of Economic Design 15(2) (2011), 121–145, Springer, doi: 10.1007/s10058-009-0097-4

30.

Poslad

, Specifying protocols for multi-agent systems interaction, ACM Transactions on on Autonomous and Adaptive Systems 2(4) (2007), Article 15, ACM. doi: 10.1145/1293731.1293735

31.

Siedlarek

J.-P.

, Intermediation in Networks, Federal Reserve Bank of Cleveland, working paper no. 15–18, 2015.

32.

Spulber

D.F.

, Market Microstructure: Intermediaries and the Theory of the Firm, Cambridge University Press, 1999.