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.

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.

During the 8th week we met to explore new directions for both MMS and APS, goods and chores. We looked into bidding algorithms which consist of rounds in which agents make bids according to some information on their own budgets and values of items remaining, and each round ends with an agent getting an item. This algorithm was used to prove 3/5-APS for goods, and we explored how it could be applied and used alongside round-robin for MMS for goods and chores. Although it seems to be very applicaple to these cases, it is not immediate that cardinalities can be incorporated. We also explored algorithms that may produce an OR of guarantees, like a proportion of MMS OR some cardinality conditions. There are many possibilities for where we can take the project next, but my partner and I started by exploring the bidding for APS. We plan to see how we can apply the bidding algorithm to chores for APS, and try to achieve a bound there. We also plan to begin making a poster for a conference in Columbia in mid August. Ruta will be giving a talk there and there will be a poster session. There is also a poster session at the end of July for the summer research students at UIUC, where we can present as well.

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.

Due to 4th of July holiday, the sixth week was a short one. We mainly focused on discussing a new notion of categories, where essentially instead of cardinality applying to all items, there are different cardinalities for each category of items. We discussed a similar algorithm to the one we had for this case, but it required the agents to have an order such that all cardinalities for i before j, agent i’s cardinality for category x must be less than agent j’s cardinality for category x, for all x. Otherwise, we could not guarantee termination as we did before. We don’t see how we can reduce a general instance to have cardinalities ordered in this way, so this result does not extend yet. We now hope to begin similar algorithms and proofs for APS. We spent the rest of the time writing up the algorithm for 1/2-MMS for goods, and applied it to chores for 2-MMS by flipping equality signs and tweaking conditions.

During the fifth week, we decided to try some new approaches to the problem. We had been focusing on bagging algorithms, where bags were filled with items in a strategic fashion until an agent valued it at more than 2/3 and claimed it. We decided that since we kept running into the same problem when trying to construct algorithms using bagging, we should try something else. We explored both round-robin and LP. With round robin, each agent takes turns (in a predetermined constant order) picking the best item, and since we assume ordinality in the problem, essentially the first agent will get the 1st, n+1st, 2n+1st, and so on items, while agent n will get the nth, 2nth, 3nth, and so on items, all of which are worse than the first agents. However, this does not matter as long as we can prove that since we know agent 1 had value greater than 1, then maybe agent n is only off by a factor of 2/3. This method works great in the case of 1/2-MMS, but the issue with 2/3-MMS is it lacks the guarantee that every item is less than 1/3, because after we perform something called a two-good reduction, there are n items that may have value greater than 1/3. Thus we cannot guarantee that each of agent n’s items are at most 1/3 less than each of agent 1’s items as needed. We though maybe we could improve round robin slightly by turning it into a sort of round-robin/bagging algorithm, where the agents aren’t in predetermined order and assigned a bag, but they can claim a good bag by choice. However, we ran into the same issue we had with bagging before, and decided to move on to LP. We defined the linear program and familarized ourselves with a process that has been proved to work for the case of 1/2. Essentially, the LP solution would provide each agent with at most k items with value 1 (guaranteed by assignment of 1/nth of each of the top nk item to each agent) and then through reassignment of the items, a binary solution can be found that guarantees 1/2 value for each agent. We want to proceed to prove this for 2/3, but again have to tackle the issue of the n items that might not have value less than 1/3.

During the fourth week, my partner and I tried and failed to finish the proof for our algorithm for 2/3-MMS. Our issue was with an invariant that we hoped to maintain throughout the algorithm, and that was used to prove termination of each iteration - or rather a valid assignment of a bag of goods to an agent in each iteration. In order to prove this, our invariant claims that there is enough value in each chunk of items of size r*k (k is cardinality), for example in the original chunk of nk items, there should be value n, since we rescale the items as such in the beginning. Thus the chunk of size rk should have value at least r, and we needed this to hold for all r from 1 to n at each iteration and for every agent. What we really care about is that the top chunk of k items has enough value (2/3, or overestimated to be 1), so we know at least some bag would be taken, but since the top k items may change at any iteration, we need to know that the iteration before has the top 2k items with value at least 2, and only value 1 is removed in the iteration. Thus the invariant needs to hold for all r = 1,…,n. Since we were struggling to prove the invariant true, we decided to attempt constructing a counter-example, and we succeeded to do so. Although our counter-example disproved the r = 1 case of the invariant, the value in the top k items was still >2/3 (although less than 1, as demanded by the invariant). Thus, we disproved the invariant but we were not convinced that the algorithm was necessarily wrong or that the problem was impossible. We decided to move away from this algorithm though, as we realized we could not find another invariant that would ensure termination.

During the third week of the DREU program, I attended an online summer school on current research areas in theoretical computer science (https://newhorizons.ttic.edu/). I participated in a number of mini-courses, problem-solving sessions, and ice-breaker activities which exposed me to new CS topics and social connections. I did not learn much that would contribute to my current research project, but the program did allow me to understand which areas of research I would prefer to continue in, during the DREU program and in graduate school. The courses took up most of the day, so I did not have much time to work on something new. Instead, Arjun and I spent the week focusing on proving an algorithm that achieves a 2/3-MMS allocation of goods. We managed to formally write up the introduction, algorithm, and most of the proof before running into a slight problem. We need to find a new way to approach the proof for one specific case, and if we manage to do so, we will be able to proceed with submitting the proof. Afterwards, we can contiunue to prove similar ideas with new notions of fiarness, such as APS, or for chores instead of goods.

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.

During the first week of the DREU program, I read papers on Fairness measurements such as Envy-Freeness and Proportionality in https://arxiv.org/abs/2202.02672. I met with Professor Mehta and another student, Arjun Aggarwal, and read on papers regarding Maixmin share (MMS for chores latest paper: https://arxiv.org/pdf/2302.04581.pdf MMS with goods and cardinality constraints: https://arxiv.org/abs/2106.07300) And decided to begin the project by focusing on the MMS measurement of fairness. We plan to continue by providing an approximation factor for which we can guarantee a distribution of goods with a cardinality constraint, using an algorithm composed of bagging and reductions.