ﻻ يوجد ملخص باللغة العربية
We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division. Towards resolving this problem, many impressive results show the existence of its relaxations, e.g., the existence of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated goods. The latter result was recently improved for three agents, in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for arbitrary number of agents is a systematic way to settle the big question. In this paper, we develop a new approach, and show that for every $varepsilon in (0,1/2]$, there always exists a $(1-varepsilon)$-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We introduce the notion of rainbow cycle number $R(cdot)$. For all $d in mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite digraph $G =(cup_{i in [k]} V_i, E)$, in which 1) each part has at most $d$ vertices, i.e., $lvert V_i rvert leq d$ for all $i in [k]$, 2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming edge from some vertex in $V_j$ and vice-versa, and 3) there exists no cycle in $G$ that contains at most one vertex from each part. We show that any upper bound on $R(d)$ directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on $R(d)$, yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation.
We study equilibria of markets with $m$ heterogeneous indivisible goods and $n$ consumers with combinatorial preferences. It is well known that a competitive equilibrium is not guaranteed to exist when valuations are not gross substitutes. Given the
We study the problem of distributing a set of indivisible items among agents with additive valuations in a $mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many resea
In this paper we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-free (EF) allocation is not guaranteed to exist, we consider the notion of
Computational and economic results suggest that social welfare maximization and combinatorial auction design are much easier when bidders valuations satisfy the gross substitutes condition. The goal of this paper is to evaluate rigorously the folklor
We model and study the problem of assigning traffic in an urban road network infrastructure. In our model, each driver submits their intended destination and is assigned a route to follow that minimizes the social cost (i.e., travel distance of all t