Ex ante and ex post envy-freeness on polytope resources

Allocating goods among agents under ordinal preferences is a well-studied problem. In this study, each type of good may have multi-copies with quotas varying in a polytope. When goods are indivisible, it is difficult to achieve exact fairness, but various approximations have been suggested. An exact ex ante envy-freeness (before the randomization or decomposition is realized) can be obtained based on past research. This study achieves the envy-freeness for up to two copies of goods based on a “nearest” structure. The fairness is called “Best-of-Both-Worlds (BoBW),” meaning it achieves the best possible fairness notions in both the ex ante and ex post senses, or before and after randomization. What differentiates this work is that we deal with the multi-copies of goods and integer demands, i.e., each entry of a discrete allocation can be an arbitrary positive integer instead of a binary number. Although our approximation is for two copies of goods, instead of one indivisible good, this may lead to a much better approximation when the number of copies is larger. Additionally, these allocations are also efficient in stochastic dominance (a Pareto optimality). We give a solution to this problem by constructing box-integer networks. Moreover, the randomized allocations can be obtained in polynomial time when the resource polytope is a polymatroid through computing so-called independent flows.