Stable and metastable contract networks

Danilov, Vladimir and Karzanov, Alexander (2022): Stable and metastable contract networks.

Abstract

We consider a hypergraph (I, C), with possible multiple (hyper)edges and loops, in which the vertices i ∈ I are interpreted as agents, and the edges c ∈ C as contracts that can be concluded between agents. The preferences of each agent i concerning the contracts where i takes part are given by use of a choice function fi possessing the so-called path independent property. In this general setup we introduce the notion of stable network of contracts.

The paper contains two main results. The first one is that a general problem on stable systems of contracts for (I, C, f) is reduced to a set of special ones in which preferences of agents are described by use of so-called weak orders, or utility functions. However, for a special case of this sort, the stability may not exist. Trying to overcome this trouble when dealing with such special cases, we introduce a weaker notion of metastability for systems of contracts. Our second result is that a metastable system always exists.

• Item Type: MPRA Paper
• Language: English
• Keywords: Plott choice functions, Aizerman-Malishevski theorem, stable marriage, roommate problem, Scarf lemma
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D74 - Conflict ; Conflict Resolution ; Alliances ; Revolutions

References

Aharoni R. and Fleiner T. On a lemma of Scarf. J. Combin. Theory, Ser. B 87 (1) (2003) 72–83.

Aizerman M.A. and Malishevski A.V. Some aspects of choice of the best variants. Avtomatika i Telemechanika. No.2 (1981) 65–83. Engl. translation: Aizerman M.A., Malishevski A.V. General theory of best variants choice. IEEE Trans. Automatic Control AC-26(5) (1981) 1030–1040.

Alkan A. and Gale D. Stable schedule matching under revealed preferences. J. Econ. Theory 112 (2003) 289–306.

Blair C. The lattice structure of the set of stable mathcings with multiple pertners. Math. Oper. Research 13 (4) (1988) 619–628.

Cechlarova K. and Fleiner T. On a gereralization of the stable roommate problem. ACM Trans. Algorithms 1 (1) (2005) 143–156.

Danilov V.I. On Scarf theorem. Economics and Mathimatical Methods 35 (3) (1999) 137–139 (in Russian).

Fleiner T. A fixed-point approach to stable matchings and some applications. Math. Oper. Res. 28 (1) (2003) 103–126.

Fleiner T. The stable roommate problem with choice functions. Algorithmica 58 (2010) 82–101.

Gale D. and Shepley L.S. College admissions and the stability of marriage. Amer. Math. Monthly 69 (1962) 9–15.

Hatfield J. and Milgrom P. Matchings with contracts. Amer. Econ. Rev. 95 (4) (2005) 913–935.

Irving R.W. An effective algorithm for the ‘stable roommate’ problem. J. Algorithms 6 (4) (1985) 577–595.

Irving R.W. and Scott S. The stable fixture problem – A many-to-many extension of stable roommates. Discrete Appl. Math. 155 (2007) 2118–2129.

Kelso A.S. and Crawford V.P. Job matching, coalition formation and gross substitutes. Econometrica 50 (1982) 1483–1593.

Plott C.R. Path independence, rationality, and social choice. Econometrica 41 (6) (1973) 1075–1091.

Roth A.E. Stability and polarization of interests in job matching. Econometrica 52 (1984) 47–57.

Tan J.J.M. A necessary and sufficient conditions for the existence of a complete stable matching. J. Algorithms 12 (1) (1991) 154–178.