Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research.

The maximum Nash welfare (MNW) solution --- which selects an allocation that maximizes the product of utilities --- is known to provide outstanding fairness guarantees when allocating divisible goods. And while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is unexpectedly, strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy free up to one good --- a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and --- even more so --- in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation, and demonstrate that it scales well on real data. These results lead us to believe that MNW is the ultimate solution for allocating indivisible goods, and underlie its deployment on a popular fair division website.

The standard problem of rationing a single over-demanded commodity has a natural bipartite extension with multiple types of a one-dimensional commodity (e.g., stored in different locations), and each agent can only consume some types of the commodity (e.g., has only access to a subset of locations).

Each user of the network needs to connect a pair of target nodes. There are no variable congestion costs, only a direct connection cost for each pair of nodes. A centralized mecha-nism elicits target pairs from users, and builds the cheapest forest meeting all demands. We look for cost sharing rules satisfying • Routing-proofness: no user can lower its cost by re-porting as several users along an alternative path con-necting his target nodes; • Stand Alone core stability: no group of users pay more than the cost of a subnetwork meeting all connection needs of the group. We construct first two core stable and routing-proof rules when connecting costs are all 0 or 1. One is derived from the random spanning tree weighted by the volume of traffic on each edge; the other is the weighted Shapley value of the Stand Alone cooperative game. For arbitrary connecting costs, we prove that the core is non empty if the graph of target pairs connects all pairs of nodes. Then we extend both rules above by the piecewise-linear technique. The former rule is computable in polyno-mial time, the latter is not.