EconCS Seminar

 

Lecturer: 

Gefen Frosh (Hebrew University)

Title: 

Near-Optimal Best-of-Both-Worlds Fairness for Few Agents

Abstract: 

 

How should we fairly divide resources - such as goods of sentimental value in an inheritance - among a small number of people with different preferences? This problem arises across many fields, yet perfect fairness is often impossible when items cannot be split. In this talk, we focus on a modern approach known as best-of-both-worlds fairness. Rather than committing to a single outcome, we allow randomness: fairness is required in expectation (before the allocation is realized), and additionally, every realized outcome must satisfy strong deterministic fairness guarantees. We focus on settings with two or three people - common and relevant settings – and show that when valuations are additive, it is possible to achieve fairness guarantees that are nearly optimal in both senses. With three agents, every outcome ensures both envy-based and share-based fairness: each agent is guaranteed a degree of envy-freeness, and each participant receives a value nearly as high as her maximin share (MMS), the value she can guarantee herself if she were the one dividing the items but picking last. When perfect guarantees are impossible, the remaining unfairness is tightly controlled and compensated in the strongest achievable way. We conclude by briefly discussing efficient algorithms that compute such fair randomized allocations, and by explaining why these guarantees are close to the best possible.

Joint work with Moshe Babaioff. Link to arxiv: https://arxiv.org/abs/2602.14668

 

 

Location: 

Elath Hall, Feldman Building, Edmond J. Safra Campus.

Click here to add the EconCS Seminar to your Google Calendar