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