Fair-division problems are ubiquitous. They range from the day-to-day chore assignments to the Israeli-Palestinian conflict and include the division of an inheritance to the heirs (Brams & Taylor, 1999; Massoud, 2000). Many intuitive and self-implementable algorithms guaranteeing fairness have been devised in the past 50 years (Brams & Taylor, 1996). So far, very few empirical studies have put them to the test (Daniel & Parco, 2005; Schneider & Krämer, 2004). In fact, it is not even known to what extent the solutions derived from these algorithms are satisfactory to human players. Here, we present an experiment that investigated the satisfaction of two pairs of players who divided 10 indivisible goods between themselves. A genetic algorithm was used to search for the best division candidates. Results show that some of the best divisions found by the genetic algorithm were rated as more mutually satisfactory than the ones derived from six typical fair-division algorithms. Analyses on temporal fluctuation and non-additivity of preferences could partially explain this result. Ideas for the future implementation of a more flexible and unconstrained approach are discussed.