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.
Assuming all agents have responsive preferences, it is possible to lift the item-ranking to a partial bundle-ranking.
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).
[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.