Fair Allocation with Optional Selling����joint work with Uri Feige
Uri Feige’s Group Meeting
June 2026
Yotam Gafni
Weizmann Institute of Science
1
2
We present a ”twist” on classic Fair Allocation, where Goods can be sold.
3
Some Related Models
4
A model with subjective valuations and market price. Study welfare approximation s.t. envy-free allocations. Market price derived from subjective valuations.
Subjective divisibility. Subjective valuations, and items are marked subjectively as divisible or not. If divisible, the agent linearly benefits from a partial item. Otherwise, all or nothing.
Consider both subjective valuations and a market price. Goods are not sold. They aim for allocations that are fair both in agent perspective, and the ‘objective’ market perspective.
Model
5
Example
6
Example
7
| 10 | 0 | 1 | 0 |
| 5 | 10 | 2 | 0 |
| 2 | 0 | 5 | 0 |
| 3 | 0.1 | 2 | 10 |
Example
8
Example
9
Example
10
Example
11
Seems to work out well...
Can we give general algorithms?
12
But first, what are we trying to achieve?
Proportional Share
13
| | |
| 10 | |
| 10 | |
| 2 | |
Can not be guaranteed!
Maximin Share
14
Comparison of share guarantees…
15
In this talk
16
MMS for n=2, First Attempt
17
Recall our example…
18
| 10 | 0 | 1 | 0 |
| 5 | 10 | 2 | 0 |
| 3 | 2 | 2 | 10 |
Monkey goes to market, sells bush, tomato and oyster for 14.
Offers elephant a choice between:
19
| 10 | 0 | 1 | 0 |
| 3 | 2 | 2 | 10 |
+ 2 } , {12}
{
20
| 5 | 10 | 2 | 0 |
| 3 | 2 | 2 | 10 |
+ 2 } , {12}, elephant chooses {12}.
{
Between
But wait… Is that MMS for elephant?
No! Elephant’s MMS is 13.5
21
Why did you sell the Acacia bush??
It was so green and luscious.
You truly are an ignorant monkey
Ooh ooh ahh ahh
Which translates to…
22
I have sold
the Acacia bush
that was in
your MMS partition
and which
you were probably
saving
for your fair share
Forgive me
the market price was decent
so liquid
and so divisible
Cut & Give to the rescue…
23
+ 2 } , {12}
{
Monkey wants either
Elephant is obliged to give it to him, but can
optimize over how, and what Elephant is left with.
24
| 5 | 10 | 2 | 0 |
| 3 | 2 | 2 | 10 |
+ 2 }.
{
Elephant sells the oyster, gives monkey
Elephant is left with { , + 8}, for a value of 20.
Cut & Give
25
Consider only MMS partitions where a single good is split between the bundles.
Among the two agents, let the agent who generates less
sale proceeds in their MMS partition be the Cutter.
The Giver gives the Cutter one of their bundles, while optimizing over the value left for the Giver.
We can assume at most a single split good
26
MMS Partition
We can assume at most a single split good
27
MMS Partition
We can assume at most a single split good
28
MMS Partition
We can assume at most a single split good
29
MMS Partition
Two options for the allocation
Alternative Proposal
1st Option
Cutter Proposal
Aggregate Giver Allocation
Giver
Cutter
Giver
Cutter
2nd Option
Alternative Proposal
1st Option
Cutter Proposal
Aggregate Giver Allocation
Giver
Cutter
Giver
Cutter
2nd Option
n=3 11/12 MMS gap
32
In this talk
33
Get Ready!
Precursor: 2/3-MMS without selling
[Kurokawa, Procaccia & Wang ‘14], [Amanatidis, Markakis, Nikzad
& Saberi ‘18]
34
Main loop:
i) Let an arbitrary agent suggest a 2/3-MMS partition.
ii) Draw the bi-partite graph of acceptable (>=2/3-MMS) bundles to agents.
iii) Perfect matching: We are done.
iv) No perfect matching – A Violating set (Hall’s Theorem).
v) Assign according to the violating set, remove the agents and their assigned bundles.
Matching algorithm illustration
35
2/3-MMS Partition by agent 1:
…
n bundles
Agent 1
Agent 2
Agent n
Matching algorithm illustration
36
Partial matching:
Agent 1
Agent 2
All remaining agents do not find the matched bundles acceptable.
Matching algorithm illustration
37
2/3-MMS Partition by agent 3:
…
n-2 bundles
Agent 3
Agent 4
Agent n
Why does this work for 2/3-apx?
A simple argument from a paper by [Akrami & Rathi ‘25]
38
…
n bundles
39
…
n bundles
40
…
n bundles
Why this fails with selling?
Agent 1 proposes a partition:
41
…
n bundles
To tackle this, we devise a 3-step plan
42
Upper Bound value of items in main loop
We add a pre-processing “moving-knife" procedure
43
Upper Bound value of items in main loop
We add a pre-processing “moving-knife" procedure
44
g
Agent 1
Agent 2
Agent 3
Why is this pre-processing safe?
If an agent sells good g in their MMS partition, they do not experience additional loss from the sale itself, and by the moving knife, they have a loss of at most 2/3-MMS.
If an agent keeps good g in their MMS partition, any loss they experience (by another agent getting parts / all of the good g) is limited to a single bundle in the MMS partition.
45
Lower bound payments in main loop
46
Sale proceeds from g
However
47
Our refined argument is not airtight, and suffers additional losses that prohibit 2/3-MMS.
Notice that beyond the first round of the main loop, we do not start from a clean MMS partition.
(recall the argument where we stitch together different bundles)
Canonical Partition to the rescue…
48
Lemma: It is possible to have a 2/3-MMS partition composed of only pure bundles, singleton bundles, and one wildcard bundle
Pure bundle:
Only complete goods
Singleton bundle:
One complete good, one sold good
Wildcard bundle:
No restrictions
Handling the wildcard bundle
49
We leave the wildcard aside during the main loop matching phase
If we get a perfect matching between all non-partitioning agents and the other bundles, we also allocate the wildcard
to the partitioning agent.
Thus, at any round, we may assume that previously
assigned bundles are either pure or singleton.
Wildcard bundle:
No restrictions
Handling pure bundles loss
50
Pure bundles that are already assigned do not force a sale.
They cause a loss of at most 2/3-MMS, and are handled similarly to the setting without selling.
Pure bundle:
Only complete goods
Handling singleton bundles loss
51
Singleton bundle:
One complete good, one sold good
Handling singleton bundles loss
52
Singleton bundle:
One complete good, one sold good
The full 2/3-MMS with selling alg
53
More in the paper…
54
Thanks for listening!�
Email: yotam.gafni@gmail.com
Website: https://www.yotamgafni.com