When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations.
In the worst case, the agents may have to rank all possible bundles, so the run-time might be exponential in the number of items.
There are various notions of "almost" envy-freeness: An allocation is called EF1 if for every two agents A and B, if we remove at most one item from the bundle of B, then A does not envy B.
It assumes that the agents have responsive preferences and returns an allocation that is necessarily envy-free (NEF).
It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.
[26] If the agents have additive utility functions that are drawn from probability distributions satisfying some independence criteria, and the number of items is sufficiently large relative to the number of agents, then an EF allocation exists with high probability.
Particularly: On the other hand, if the number of items is not sufficiently large, then, with high probability, an EF allocation does not exist.