Algorithms for Pareto efficient and envy-free allocation

In the setting of fair allocation of indivisible goods, there are various desiderata that one might want from an allocation. Two important ones are envy-freeness and Pareto efficiency. In general, one cannot guarantee to find an allocation that satisfies both, and its computationally hard to find an allocation satisfying both, even if it exists. Moreover, this problem cannot even be directly encoded (efficiently) into SAT or similar (NP-complete) problems. In this talk, we will present a counterexample-guided abstraction refinement (CEGAR) algorithm for this problem.