Week 10

During the 10th and final week we completed the proofs for our paper. We discovered that we needed to prove that if the top nk items are valued at n, then the APS is at most 1. This helps show that rescaling the items as such provides that APS is at most 1, so then we can give value 1/2 or more to items, and this will certainly be at least 1/2-APS. At first we were not sure how to approach this problem as we could not find any price assignemnts that caused the objective function to take value 1, proving that after minimization, APS could only be less or equal to 1. We then found aid in a lemma stating that the bundle of items that optimizes the objective value in the APS definition contains items only from the top nk items. We proved this through induction, which involved a proof by contradiction in the inductive step. Once we had this fact, we could create a price assignment that provides the objective within the min to be at most 1, and so APS after being minimized is also at most 1. With this proof, we were able to use all the algorithms we had for MMS for goods on APS as well. This assumption helps prove that there is enough value in the top nk items, and so if other agents take bags of at most value 1 and size k, then there will be enough value left.

Written on July 31, 2023