Uri Feige: Fair allocation of indivisible goods: the anyprice share

Date: November 10, 2020 Speaker: Uri Feige (Weizmann Institute of Science) Title: Fair allocation of indivisible goods: the anyprice share Abstract: We consider fair allocation of indivisible goods to agents with additive valuation functions, in a setting without money. The notions of fairness that we shall consider are variations on the well known maximin share (MMS). For the case when all agents have equal entitlement to the goods, we shall review known results concerning the fraction of the MMS that one can guarantee to the agents, and also offer some improvements on these results. We then introduce a new fairness notion, that we refer to as the anyprice share (APS). Unlike the maximin share, the anyprice share extends without change to settings in which agents have unequal entitlements. To analyse the fraction of the APS that one can guarantee to all agents, we consider a natural allocation game, and present strategies the guarantee an agent at least a 3/5 fraction of his APS, regardless of the strategies employed by the other agents. Based on work with Moshe Babaioff, Tomer Ezra, Ariel Sapir, Laliv Tauber. (typo on slide 27: “Tauman” should be corrected to “Tauber”)