Week 9

During the 9th week we developed proofs for theorems that allowed our MMS algorithms to work for APS as well. For goods, we needed to have a one good reduction, a method that states that the removal of one item of one agent leaves an instance in which all remaining agents’ APS only improves. The purpose of this method is to help prove 1/2-APS, we can give any item valued 1/2 or more by any agent to such an agent, and both the item and agent can be resolved. This leaves only items valued less than 1/2 by all items, and so whenever an item is added to a bundle, it can only change the value of the bundle by 1/2. We also did some work on the chores case, which entailed proving some lemmas that bounded the value of the APS in that case. My partner worked on proving these lemmas and adjusting our MMS algorithms to incorporate APS as well. I then used the written solutions to create a poster to present at the UIUC CS Summer Research showcase. At the poster session, I had the pleasure of discussing our research with other undergraduates, graduate students, and professors. I explained our problem setting and each of our definitions, lemmas, and algorithms. The poster session gave me great practice communication information about my research to others who were not yet familiar with the problem. I hope to remake the poster soon to present at a conference at Columbia in mid-August.

Written on July 24, 2023