Hana Salavcová – DIMACS REU Summer 2025

Week 1 (May 27 - May 30)

• Read introductory materials on fair allocation problems
• Initial meeting with mentor to discuss basics of fair allocation and possible research directions
• Brainstormed new research idea and discussed possible settings and models with Martin to formalize the approach
• Began outlining ideas for the initial presentation

Literature

• Amanatidis et al. (2023). Fair division of indivisible goods: Recent progress and open questions. [DOI]
• Aziz et al. (2022). Algorithmic fair allocation of indivisible items: A survey and new questions. [DOI]

Week 2 (June 2 - June 6)

• Finished preparing the initial presentation
• Shared our Overleaf document and initial notes with our mentor
• Held a short online meeting to discuss early ideas and feedback
• Presented our initial presentation [view slides]
• Significantly rewrote and reorganized our notes describing the shared setting (now with formal definitions and clearer structure)
• Added basic proofs of fundamental properties of the model
• Had an extended in-person meeting with our mentor to discuss various possible fairness notions (e.g., multiple variants of EFX, MMS)
• Noted a connection between MMS in the cost-free setting and MMS in constrained settings

Literature

• Kurokawa, Procaccia, and Wang (2018). Fair Enough: Guaranteeing Approximate Maximin Shares. [DOI]
• Anonymous (n.d.). Preprint manuscript, details withheld for confidentiality.
• Chaudhury et al. (2021). A Little Charity Guarantees Almost Envy-Freeness. [DOI]

Week 3 (June 9 - June 13)

• Updated the Overleaf template to make collaborative editing more structured and readable
• Added new existential results for MMS and a preliminary result for EFX (which later turned out to be incorrect :( )
• Attended the Tuesday seminar on mechanism design (mostly introductory, but engaging!)
• Established a result connecting EFX across goods and chores
• Met with our mentor on Thursday and agreed on formalization of the model and fairness notions
• Reviewed and discussed our results related to SMMS and MMS — mentor was pleasantly surprised by our progress
• Received detailed feedback on our Overleaf document (notation and further directions) and alredy addressed part of the comments and planned to revisit a specific result next week
• Made initial progress on PROPx-related results
• Participated in Friday's Culture Day, presented a Czech animal sound quiz (e.g., “chro chro”), enjoyed presentations and food!

Literature

• Feige, Sapir, and Tauber (2021). A tight negative example for MMS fair allocations. [DOI]
• Guo et al. (2023). A Survey on Fair Allocation of Chores. [DOI]

Week 4 (June 16 - June 19)

• Started with a stronger MMS/PROPx result expected to hold for all numbers of agents, but detailed proof showed it holds exactly only for even values of n, and only approximately for odd — the distinction turned out to be surprisingly insightful
• Found a surprisingly good fit between MMS (bounding the number of items) and q-ary covering codes!
• Dived into older covering code literature (mostly before 2011) and translated relevant results into our model
• Joined the REU-wide pasta competition with homemade mushroom-pepper lasagna (fresh pasta included!)
• Met with our mentor and discussed new ideas for PROPX, as well as new results for MMS
• Considered preparing a paper focused on MMS and SMMS for submission to WINE 2025 (discussed directions for the write-up)

Literature

• Haas et al. (2009). Lower Bounds forq-ary Codeswith Large Covering Radius. [DOI]
• Gijswijt and Polak (2025). Semidefinite lower bounds for covering codes. [DOI]

Week 5 (June 23 - June 27)

• Finalized a draft of our paper — polished proofs, formalized results, and refined the overall structure and exposition
• Learned from our mentor about a newly published paper with significant overlap
• Reviewed the preprint and confirmed that much of our work was already covered
• Decided not to submit the current paper and shifted focus to new, unexplored directions suggested by the uncovered gaps

Literature

• Barman et al. (2025). Exact Maximin Share Fairness via Adjusted Supply. [DOI]
• Brederek et al. (2023). Improving Resource Allocations by Sharing in Pairs. [DOI]

Week 6 (June 30 - July 3)

• Derived new bounds on SMMS in various models, and bounds on MMS and SMMS using full-sharing SMMS
• Used known approximation results for CMMS to obtain new approximations for MMS and SMMS
• Studied in more depth the recent paper discovered last week and analyzed its probabilistic approach
• Adapted a similar probabilistic technique to prove a new theoretical result approximating MMS
• Explored a weighted version of MMS for the weighted-cost setting, but observed unintuitive behavior on examples and decided to drop this direction

Week 7 (July 7 - July 11)

• Shifted focus toward the algorithmic side — reviewed existing algorithms, most of which failed or gave weak guarantees in the shared setting
• Successfully adapted the Bag-Filling algorithm to improve MMS approximations in equal-share models
• Generalized the new algorithm to arbitrary cost models, leading to exact MMS under milder conditions than before
• Started preparing a polished write-up of our results (now both theoretical and algorithmic!)
• Identified a new conference where we may present our framework for shared fair allocation — fingers crossed this time!

Literature

• Amanatidis et al. (2023). Fair Division of Indivisible Goods: Recent Progress and Open Qestions. [DOI]
• Garg et al. (2019). Approximating Maximin Share Allocations. [DOI]

Week 8 (July 14 - July 18)

• ...

Literature

• ...

Week 9 (July 21 - July 25)

• ...

Literature

• ...

Week 10 (July 28 - August 1)

• ...

Literature

• ...