Demand operators and the Dutta–Kar rule for minimum cost spanning tree problems

Changyong Han (), Bawoo Kim () and Youngsub Chun ()
Additional contact information
Changyong Han: Korea SMEs and Startups Institute
Bawoo Kim: Samsung Electronics
Youngsub Chun: Seoul National University

Economic Theory, 2024, vol. 78, issue 1, No 4, 124 pages

Abstract: Abstract Granot and Huberman (Math Program 29:323–347, 1984) introduced two demand operators, the weak demand operator and the strong demand operator, for minimum cost spanning tree problems, which are intended to measure the maximum amount that each agent can demand from her followers in compensation for making a link to her. We investigate the implications of these demand operators by introducing a procedure which enables us to sequentially calculate the maximum for each agent. On the irreducible cost matrix, by applying the weak demand operator sequentially to each agent, the Dutta–Kar allocation (Dutta and Kar in Games Econ Behav 48:223–248, 2004) is obtained if the procedure is initiated from any efficient allocation. For the strong demand operator, the Dutta–Kar allocation is obtained if the procedure is initiated from any allocation in the irreducible core.

Keywords: Minimum cost spanning tree problems; Demand operators; Irreducible cost matrix; Dutta–Kar rule; Prim algorithm (search for similar items in EconPapers)
JEL-codes: C71 (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00199-023-01526-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joecth:v:78:y:2024:i:1:d:10.1007_s00199-023-01526-9

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/199/PS2

DOI: 10.1007/s00199-023-01526-9

Access Statistics for this article

Economic Theory is currently edited by Nichoals Yanneils

More articles in Economic Theory from Springer, Society for the Advancement of Economic Theory (SAET) Contact information at EDIRC.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().