Stochastics and Statistics
Distributed consensus in noncooperative inventory games

https://doi.org/10.1016/j.ejor.2007.10.012Get rights and content

Abstract

This paper deals with repeated nonsymmetric congestion games in which the players cannot observe their payoffs at each stage. Examples of applications come from sharing facilities by multiple users. We show that these games present a unique Pareto optimal Nash equilibrium that dominates all other Nash equilibria and consequently it is also the social optimum among all equilibria, as it minimizes the sum of all the players’ costs. We assume that the players adopt a best response strategy. At each stage, they construct their belief concerning others probable behavior, and then, simultaneously make a decision by optimizing their payoff based on their beliefs. Within this context, we provide a consensus protocol that allows the convergence of the players’ strategies to the Pareto optimal Nash equilibrium. The protocol allows each player to construct its belief by exchanging only some aggregate but sufficient information with a restricted number of neighbor players. Such a networked information structure has the advantages of being scalable to systems with a large number of players and of reducing each player’s data exposure to the competitors.

Introduction

The main contribution of this paper is the design of a consensus protocol (see, e.g. [3], [24]) that allows the convergence of strategies to a Pareto optimal Nash equilibrium [2], [26] for repeated nonsymmetric congestion games under partial information.

The repeated games considered in this work are congestion games [25] as, at each stage or time period, the payoff (cost) that the ith player pays for playing a strategy is a monotonically nonincreasing function of the total number of players playing the same strategy. The games are also nonsymmetric as the payoffs are player-specific functions [22]. Finally, the games are under partial information as we assume that: each player cannot observe its payoff at each stage since the payments occur only on the long term; each player learns [30], i.e., constructs its belief concerning other players’ probable behavior, by exchanging information with a restricted number of neighbor players.

A networked information structure has the advantages of being scalable to systems with a large number of players and of reducing each player’s data exposure to the competitors. On the other hand, delay in the propagation of information through the network implies that players’ strategies cannot converge immediately but only after some stages.

We prove that players can learn using a consensus protocol where the quality of the information exchanged does not force the players to reveal their past decisions (see the minimal information paradigm in [11]). In the last part of the work, we also prove that players can use linear predictors to increase the protocol speed of convergence.

Congestion games always admit at least one Nash equilibrium as established by Rosenthal in [25]. However, its efficient computation is a non trivial issue. Then, from a different perspective, we can review our results as a further attempt of providing an algorithm that finds Nash equilibria in polynomial time for special classes of congestion games [19], [30], [32]. Our results prove also that the Nash equilibrium that we find is the unique Pareto optimal one.

In addition, we prove that, in our problem, the Pareto optimal Nash equilibrium dominates all other Nash equilibria, i.e., it minimizes the cost of each player and therefore it is also social optimal, as it minimizes the social cost defined as the sum of players’ costs. This is an important property as it implies that competition does not induce loss of efficiency in the system.

Examples of applications come from situations where multiple players share a service facility as airport facilities or telephone systems, drilling for oil, cooperative farming, and fishing (see also the literature on cost-sharing games [29], and on externality games [14]).

As motivating example, we consider a multi-retailer inventory application. The players, namely different competing retailers, share a common warehouse (or supplier) and cannot hold any private inventory from stage to stage, i.e., inventory left in excess at one stage is no longer utilizable in the future. The latter fact prevents the retailers from having large replenishment and stocks. Such a situation occurs when dealing with perishable goods as, for instance, the newspapers. Transportation is provided at the retailers’ expense by the supplier at every stage, e.g., every day, but the players adjust their transportation payments with the supplier only every once in a while, e.g., once every two months.

Players aim at coordinating joint orders thus to share fixed transportation costs. As typical of repeated games, we assume that the retailers act myopically, that is, at each stage, they choose their best strategy on the basis of a payoff defined on single stage [23]. The reader is referred to [27] for a general introduction to multi-retailer inventory problems with particular emphasis on coordination among non cooperative retailers. Recent more specific examples are [4], [6], [7], [13], [31]. The role of information is discussed, e.g., in [9], [10]. The modelling of such problems as non cooperative games is in [1], [17], [20], [28]. Our idea of selecting the best (Pareto optimal) among several Nash equilibria presents some similarities with [7], which however do not consider the possibility of sharing transportation costs. Alternative ways to achieve coordination proposed in the literature are either to centralize control at the supplier [8], [18], or to allow side payments [16], [21].

The rest of the paper is organized as follows. In Section 2, we develop the game theoretic model of the inventory system and formally state the problem. In Section 3, we prove the existence of and characterize the unique Pareto optimal Nash equilibrium. In Section 4 we prove some stability properties of the Pareto optimal Nash equilibrium. In Section 5, we design a distributed protocol that allows the convergence of the strategies to the Pareto optimal Nash equilibrium. In Section 6, we analyze the speed of convergence of the protocol. In Section 7, we introduce a numerical example. Finally, in Section 8, we draw some conclusions.

Section snippets

The inventory game

We consider a set of n players Γ={1,,n} where each player may exchange information only with a subset of neighbor players. Hereafter, we indicate with the same symbol i both the generic player and the associated index. More formally, we assume that the set Γ induces a single component graph G=(Γ,E) whose edgeset E includes all the non oriented couples (i,j) of players that exchange information with each other. In this context, we define the neighborhood of a player i the set Ni={j:(i,j)E}{i}.

A Pareto optimal Nash equilibrium

The game under consideration always has a Nash equilibrium because it is a congestion game [25]. In this section we prove that there exists a unique Pareto optimal Nash equilibrium and we describe its characteristics. To this end, here and in the rest of the paper, we make, without loss of generality, the following assumptions:

Assumption 1

The set Γ of players is ordered so that l1l2ln.

Assumption 2

There may exist other players i=n+1,n+2, not included in Γ, all of them with thresholds li=.

Assumption 3

The players in the empty

Stability of Nash equilibria

In this section, we assume that at each stage k of the repeated game, each player i knows the number of active players at the previous stage, sets χˆi(k)=s-i(k-1)1 and applies the best response strategy (3). In this context, we prove that the Pareto optimal Nash equilibrium s is stable with respect to its neighborhood of strategies s such that ss componentwise. On the basis of this result, in the next section, we will be able to study the convergence properties of the repeated inventory

A consensus protocol

In this section, we exploit the stability properties introduced in the previous section to design a protocol Π^={ϕi,hi,iΓ} that allows the distributed convergence of the best response strategies (3) to the Pareto optimal Nash equilibrium.

Consider the graph G induced by the set of players Γ as defined in Section 2. Let L be the Laplacian matrix of G and use Lij and Li· to denote respectively the i,j entry and the ith row of L.

Let us consider the almost-linear protocol Π^ defined by the

A priori information and speed of convergence of the protocol

In this section, we determine the values of both α and T as functions of the players’ computation capabilities and their knowledge about the structure of graph G. We show that T grows linearly with n when players can use linear predictors and discuss the non linear correcting term δT(k) in (19). Differently, in absence of linear predictors (δT(k)=0 for all k) the players must wait that the pre-decision information converges to the desired percentage of currently active players. In this latter

Simulation results

In this section we provide a numerical example and some simulation results for a set Γ of eight players implementing the designed protocol with and without predictors. We will see that in both cases the strategies converge to the Pareto optimal Nash equilibrium though with different speed of convergence. Fig. 1 reports the induced graph G, whereas Table 4 lists the players’ thresholds li and the initial strategies si(0). Note that at k=0 the strategies are not in the Pareto optimal Nash

Conclusion

In this paper, we have introduced a consensus protocol to achieve distributed convergence to a Pareto optimal Nash equilibrium, for a class of repeated nonsymmetric congestion games under partial information. We have specialized the game to a multi-retailer application, where transportation or set up costs are shared among all retailers, reordering from a common warehouse. The main results concern: (i) the existence and the stability of Pareto optimal Nash equilibria, (ii) the structure of the

References (32)

  • N.L. Biggs

    Algebraic Graph Theory

    (1993)
  • F. Blanchini et al.

    Control of production-distribution systems with unknown inputs and systems failures

    IEEE Transactions on Automatic Control

    (2000)
  • G. Cachon

    Stock wars: Inventory competition in a two-echelon supply chain with multiple retailers

    Operations Research

    (2001)
  • S. Cetinkaya et al.

    Stock replenishment and shipment scheduling for vendor-managed inventory systems

    Management Science

    (2000)
  • F. Chen et al.

    Quantifying the bullwhip effect in a simple supply chain: The impact of forecasting, lead times, and information

    Management Science

    (2000)
  • C.J. Corbett

    Stochastic inventory systems in a supply chain with asymmetric information: Cycle stocks, safety stocks, and consignment stock

    Operations Research

    (2001)
  • Cited by (12)

    • The uniqueness property for networks with several origin-destination pairs

      2014, European Journal of Operational Research
      Citation Excerpt :

      Koutsoupias and Papadimitriou (1999) initiated a precise quantitative study of this loss, which lead soon after to the notion of “Price of Anarchy” that is the cost of the worst equilibrium divided by the optimal cost, see (Roughgarden & Tardos, 2002) among many other references. Some recent researches proposed also ways to control this loss, see Bauso, Giarré, and Pesenti (2009) and Knight and Harper (2013) for instance. When the users are assumed to be nonatomic – the effect of a single user is negligible – equilibrium is known to exist (Milchtaich, 2000).

    • Decentralised minimum-time consensus

      2013, Automatica
      Citation Excerpt :

      Of related interest is Ref. (Bauso, Giarre, & Pesenti, 2009), which considers a game-theoretical approach to consensus when agents have prediction capabilities. The approach in Bauso et al. (2009) relies on the use of characteristic polynomials to obtain an upper bound on the number of steps required by any node to compute the consensus value. The structure of this paper is as follows.

    • From competitive to collaborative supply networks: A simulation study

      2011, Applied Mathematical Modelling
      Citation Excerpt :

      Cai et al. [15] studied how advanced strategies affect the interactions between the supply chain members, considering multiple buyers by introducing a demand function under uncertainty. Zhao et al. [16], Bauso et al. [17], Yang and Zhou [18] and Nagarajan [19] also developed game theory models applied to one single supply chain in order to improve co-ordination activities within the supply chain. From a supply chain optimization point of view, Silva et al. [20] developed a supply chain ant colony optimization for modeling supply chain distributed actors.

    • Dynamic Games with Strategic Complements and Large Number of Players

      2023, Journal of Optimization Theory and Applications
    • Dynamic Coordination Games with Activation Costs

      2021, Dynamic Games and Applications
    • Invariant properties and bounds on a finite time consensus algorithm

      2019, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    View all citing articles on Scopus
    View full text