On the core of ordered submodular cost games

A general ordertheoretic linear programming model fur 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 comb inatorial explanation for many integrality results in discrete optimization . In particular, the submodular intersection theorem of Edmonds and Giles i s seen to extend to the ease with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the exis tence of the core in cooperative game theory are discussed.