Week 7

During the 7th week of the program, my partner and I tried to wrap up previous works to prepare for moving onto new topics using APS and categories. Arjun worked to write up an algorithm for ordered instances using categories, which is an unlikely instance but a good step in the direction for using categories. I worked on writing up code to find counterexamples for a proportion of the MMS. Essentially, I hope to find a set of items and corresponding valuations such that there is no assignment that satisfies x-MMS where x is a proportion between 2/3 and 1. I constructed a system in SymPy that finds an instance and assignment that ensures each object is assigned to exactly one person, each person has maximum ki items, and that every agent receives x proportion of their MMS. It also finds each agents MMS in order to use it with x = 8/9 so I can try to see if there is an instance where there is no assignment that acheives 8/9MMS for all agents, in which case, there would be a counterexample. If I do find a counterexample, I will then decrease x. I started with examples with 4 agents, since it has been proving that 1-MMS can be acheived in all scenarios given 3 or fewer agents. I will also increase the number of agents if we fail to find a counterexample after tries of different numbers of items. My partner and I also focused on reading papers on APS (https://arxiv.org/abs/2103.04304v4) and on a different method than we had previously attempted regarding chores.

Written on July 10, 2023