A Simple and Fast Fair Allocation Algorithm Under Binary Submodular Valuations

Abstract: The classic problem of fair allocation asks how to divide a set of indivisible goods among a set of agents who have different preferences over these goods. In this talk I will focus on fair allocation instances where agent preferences can be modeled using binary submodular functions. Under binary submodular functions, the value that each agent places on each good is binary (either they like a good or dislike it) and each good provides a decreasing marginal gain (adding a good to a large bundle will provide lesser value than adding a good to a small bundle). I will introduce several desirable fairness notions for this problem and then present an algorithm that computes allocations that satisfy (almost) all of these fairness notions. Finally, I will analyze the time complexity of this algorithm and show that it is significantly faster than all the algorithms in prior work.

This is joint work with Yair Zick.

The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.