Week 8
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.