| bibtype |
V -
Research Report
|
| ARLID |
0600173 |
| utime |
20241107153915.3 |
| mtime |
20241104235959.9 |
| title
(primary) (eng) |
On combinatorial descriptions of faces of the cone of supermodular functions |
| publisher |
| place |
Praha |
| name |
UTIA AV CR |
| pub_time |
2024 |
|
| specification |
|
| edition |
| name |
Research Report |
| volume_id |
2397 |
|
| keyword |
supermodular/submodular game |
| keyword |
face lattice |
| keyword |
generalized permutohedron |
| keyword |
rank test |
| keyword |
core structure |
| keyword |
conditional independence |
| keyword |
structural semi-graphoid |
| keyword |
polymatroid |
| author
(primary) |
| ARLID |
cav_un_auth*0101202 |
| name1 |
Studený |
| name2 |
Milan |
| institution |
UTIA-B |
| full_dept (cz) |
Matematická teorie rozhodování |
| full_dept (eng) |
Department of Decision Making Theory |
| department (cz) |
MTR |
| department (eng) |
MTR |
| full_dept |
Department of Decision Making Theory |
| fullinstit |
Ústav teorie informace a automatizace AV ČR, v. v. i. |
|
| source |
|
| source |
|
| cas_special |
| abstract
(eng) |
This paper is to relate five different ways of combinatorial description of non-empty faces of the cone of supermodular functions on the power set of a finite basic set N. Instead of this cone we consider its subcone of supermodular games; it is also a polyhedral cone and has the same (= isomorphic) lattice of faces. This step allows one to associate supermodular games with certain polytopes in N-dimensional real Euclidean space, known as cores (of these games) in context of cooperative game theory, or generalized permutohedra in context of polyhedral geometry. Non-empty faces of the supermodular cone then correspond to normal fans of those polytopes. This (basically) geometric way of description of faces of the cone then leads to the combinatorial ways of their description.\n\nThe first combinatorial way is to identify the faces with certain partitions of the set of enumerations of N, known as rank tests in context of algebraic statistics. The second combinatorial way is to identify faces with certain collections of posets on N, known as (complete) fans of posets in context of polyhedral geometry. The third combinatorial way is to identify the faces with certain coverings of the power set of N, introduced relatively recently in context of cooperative game theory under name core structures. The fourth combinatorial way is to identify the faces with certain formal conditional independence structures, introduced formerly in context of multivariate statistics under name structural semi-graphoids.\nThe fifth way is to identify the faces with certain subgraphs of the permutohedral graph, whose nodes are enumerations of N. We prove the equivalence of those six ways of description of non-empty faces of the supermodular cone. This result also allows one to describe the faces of the polyhedral cone of (rank functions of) polymatroids over N and the faces of the submodular cone over N: this is because these cones have the same face lattice as the supermodular cone over N. The respective polytopes are known as base polytopes in context of optimization and (poly)matroid theory. |
| RIV |
BA |
| reportyear |
2025 |
| num_of_auth |
1 |
| inst_support |
RVO:67985556 |
| permalink |
https://hdl.handle.net/11104/0357784 |
| confidential |
S |
| arlyear |
2024 |
| mrcbU10 |
2024 |
| mrcbU10 |
Praha UTIA AV CR |
|