On the core of ordered submodular cost games

U. Faigle, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

30 Citations (Scopus)

Abstract

A general ordertheoretic linear programming model for the study of matroid-type greedy algorithms is introduced. The primal restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization. In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the case with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative game theory are discussed.
Original languageUndefined
Pages (from-to)483-499
Number of pages16
JournalMathematical programming
Volume87
Issue number3
DOIs
Publication statusPublished - 2000

Keywords

  • core –N-person game – greedy algorithm – Monge property – order – polymatroid – poset – submodular
  • METIS-140636
  • IR-79986

Cite this