Simultaneous Ordinal Maximin Share and Envy-Based Guarantees

We study the fair allocation of indivisible goods among agents with additive valuations. The fair division literature has traditionally focused on two broad classes of fairness notions: envy-based notions and share-based notions. Within the share-based framework, most attention has been devoted to the maximin share (MMS) guarantee and its relaxations, while envy-based fairness has primarily centered on EFX and its relaxations. Recent work has shown the existence of allocations that simultaneously satisfy multiplicative approximate MMS and envy-based guarantees such as EF1 or EFX. Motivated by this line of research, we study for the first time the compatibility between ordinal approximations of MMS and envy-based fairness notions. In particular, we establish the existence of allocations satisfying the following combined guarantees: (i) simultaneous 1-out-of-lceil 3n/2 rceil MMS and EFX for ordered instances; (ii) simultaneous 1-out-of-lceil 3n/2 rceil MMS and EF1 for top-n instances; and (iii) simultaneous 1-out-of-4lceil n/3 rceil MMS and EF1 for ordered instances.