Maximin Fairness with Mixed Divisible and Indivisible Goods.

摘要: We study fair resource allocation when the resources contain a mixture of divisible and indivisible goods, focusing on well-studied fairness notion maximin share (MMS). With only full MMS may not exist, but constant multiplicative approximate always does. analyze how approximation guarantee would be affected to allocated also goods. In particular, we show that worst-case with mixed goods is no worse than However, there exist problem instances which adding some strictly decrease ratio instance. On algorithmic front, propose constructive algorithm will produce an $\alpha$-MMS for any number agents, where $\alpha$ takes values between $1/2$ $1$ monotone increasing function determined by agents value relative their values.