Week 2
During the second week of the DREU program, I read a paper on algorithms that acheive a 2/3 MMS value for each agent, using only goods, and with a cardinality constraint (https://arxiv.org/abs/2106.07300). In this particular paper, an algorithm is presented that assigns bags of items to agents such that each agent receives a bag with cardinality <= k, worth at least 2/3 of their MMS value. They proved that this algorithm will always terminate with a valid assignment. My task with my partner, Arjun, was to create an algorithm for the same problem but where each agent i had a different cardinality constraint k_i. This posed many issues as in the original algorithm, the bags are packed with at most k items and any agent can claim the bag once they are content with its value. In our case, we could not build bags of equal size and offer it to any agent because the agents have a unique cardinality constraint. We struggled to see if the bound was even possilbe in this case, and spent the week meeting and drafting different algorithms and finding many flaws. Finally, we created one that seemed to uphold all constraints, terminated, and guaranteed a 1/2 factor of the MMS. We plan to write up the algorithm and its proof, and then continue to find an algorithm for the 2/3 factor.