The size of the maximum antichains in products of linear orders
- PDF / 1,155,625 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 163 Views
The size of the maximum antichains in products of linear orders Denis Bouyssou1 · Thierry Marchant2 · Marc Pirlot3 Received: 5 March 2020 / Accepted: 7 November 2020 © Sociedad de Estadística e Investigación Operativa 2020
Abstract The size of maximum antichains in the product of n linear orders is known when the n linear orders have the same length. We present an exact expression for the size of maximum antichains when the linear orders have (possibly) different lengths. From this, we derive an exact expression for the size of maximum antichains in the product of n linear orders with the same length. This expression is equivalent to but different from the existing expression. It allows us to present an asymptotic result for the size of maximum antichains of n linear orders with the same length m going to infinity. Keywords Maximal antichain · Sperner · Multichoice cooperative game · Linear orders Mathematics Subject Classification 91B06
Authors are listed alphabetically and have equally contributed. * Thierry Marchant [email protected] Denis Bouyssou [email protected] Marc Pirlot [email protected] 1
LAMSADE, UMR 7243, CNRS, Université Paris-Dauphine, PSL Research University, 75016 Paris, France
2
Ghent University, Dunantlaan 1, 9000 Ghent, Belgium
3
Université de Mons, rue de Houdain 9, 7000 Mons, Belgium
13
Vol.:(0123456789)
D. Bouyssou et al.
1 Introduction Antichains in the poset {0, 1}n equipped with the standard partial ordering are wellstudied and have many different interpretations (Ersek Uyanık et al. 2017). An expression for the maximal size of such antichains in {0, 1}n is given by a classical theorem due to Sperner (1928). If we consider the more general poset {1, … , m}n also equipped with the standard partial ordering, an expression for the size of maximum antichains is given by Sander (1993). Sander also provides asymptotic results when m is fixed and n goes to infinity. The interest of Sander in this problem arose from a recreational mathematics problem posed in Motek (1986). Actually, antichains and, hence, maximal antichains, in the poset {1, … , m}n are of interest in many domains. For instance in game theory, Hsiao and Raghavan (1992) define a multichoice cooperative game as a real-valued mapping on {1, … , m}n , where n is the number of players and {1, … , m} denotes the set of ordered actions that each player can take. A profile in such a game is a vector x = (x1 , … , xn ) ∈ {1, … , m}n and represents the actions taken by each agent. A winning profile is such that the value of the game at that profile is 1. A winning profile x is minimal if there is no other winning profile y such that y ≤ x . If a game is monotone, then the set of all minimal winning profiles is an antichain. Besides, Grabisch (2016) shows that antichains in {1, … , m}n play an important role in the analysis of these multichoice cooperative games. In Hsiao and Liao (2008), a generalization of multichoice cooperative games is presented by considering that the set of actions ava
Data Loading...
