On Worst-Case Allocations in the Presence of Indivisible Goods

About the Algorithm

This algorithm implements the fair allocation method proposed by Markakis and Psomas in their 2011 paper:

"On Worst-Case Allocations in the Presence of Indivisible Goods"

The algorithm guarantees that each agent receives a bundle worth at least V_n(α_i), where α_i is the value of the most valuable item to the agent relative to their total value of all items.

Read the Paper

How It Works

1. For each agent, compute α_i (largest item value / total value)
2. Calculate V_n(α_i) using the formula from the paper
3. Allocate items incrementally until one agent meets their threshold
4. Assign the bundle to that agent
5. Normalize the valuations of remaining agents for remaining items
6. Recursively allocate remaining items to remaining agents

Try It Now

Key Features

• Guarantees proportional allocation
• Handles indivisible goods
• Works with asymmetric valuations
• Efficient implementation
• Detailed logging for transparency