Abstract:

Items have to be distributed to agents in a fair manner. The agents have valuations for the goods and the value of a set of goods is simply the sum of the valuations. Nash introduced axioms for fairness and showed that for divisible goods maximizing the product of the agent's valuations leads to a fair division. The allocation maximizing the product is the same as the allocation in a Fisher market in which all agents have the same budget. For indivisible goods the problem is harder. Cole/Gkatzelis gave an approximation algorithm based on rounding the allocation in a Fisher market with earning caps. We go further and consider Fisher markets with earning and utility caps, i.e., buyers do not want to buy goods beyond a certain utility and sellers do not want to earn money above a certain amount. We show how to computer approximate equilibria in such markets and how this leads to fair divisions for buyers with utility caps. The talksg is based on papers in SODA '18, SAGT '17, ESA '16, and SODA '16.