Speaker: Arkadii Slinko
Affiliation: The University of Auckland
Title: Hierarchical games
Date: Tuesday, 15 Mar 2011
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

In many situations, both in human and artificial societies, cooperating agents have different status with respect to the activity and it is not uncommon that certain actions are only allowed to coalitions that satisfy certain criteria, e.g., to sufficiently large coalitions or coalitions which involve players of sufficient seniority. Simmons (1988) formalised this idea in the context of secret sharing schemes by defining the concept of a (disjunctive) hierarchical access structure.

The mathematical concept which describe access structures of secret sharing schemes is that of a simple game. In this paper we aim to start a systematic study of hierarchical games, both disjunctive and conjunctive, and our results show that they deserve such a treatment. We prove the duality between disjunctive and conjunctive hierarchical games. We introduce a canonical representation theorem for both and characterise disjunctive hierarchical games as complete games with a unique shift-maximal losing coalition. We give a short combinatorial proof of the Beimel-Tassa-Weinreb characterisation theorem of weighted disjunctive hierarchical games. By duality we get similar theorems for conjunctive hierarchical games.

This is a joint work with Tatiana Gvozdeva and Ali Hameed.