Questions tagged [fair-division]
For various problems related to dividing a resource among several parties.
12 questions
31
votes
5
answers
1k
views
Fair cutting of the plane with lines
An infinite countable family $\cal{L}$ of straight lines in the plane $\mathbb{R}^2$ forms a fair cutting of the plane if the following conditions are satisfied:
$\bullet$ No circle intersects ...
- 4,786
50
votes
7
answers
3k
views
Dividing a cake between $n-1$, $n$, or $n+1$ guests
A housewife is waiting for guests and has prepared a cake. She doesn't know how many guests will come, but it will be $n-1$, $n$, or $n+1$.
What is the minimal number $f(n)$ of pieces the cake ...
- 5,409
21
votes
4
answers
2k
views
Fairest way to choose gifts
Suppose that a parent brings home from a trip $2n$ gifts of roughly equal value for his/her two children. The children get to choose one at a time which gifts they want. What is the fairest way to ...
- 50.8k
15
votes
4
answers
817
views
Fair cake-cutting between groups
The cake-cutting game is usually played between individuals. What if we try to play it between groups?
A certain land has to be divided between two states. There are $n$ citizens in each state. ...
- 3,549
19
votes
3
answers
1k
views
What is the fairest order for stage-striking (and is it the Thue-Morse sequence)?
Here's a fair-sequencing problem that doesn't quite match the usual fair-division problems. I think that, like those, the answer should also be the Thue-Morse sequence ("balanced alternation"), ...
- 800
3
votes
1
answer
252
views
Is there a moving knife procedure for envy-free cake cutting with connected pieces?
In the wikipedia page on envy-free cake cutting, continuous "moving knife" algorithms for envy free cake cutting to connected pieces is only mentioned for up to 4 players. As the wikipedia article ...
CommunityBot
- 1
7
votes
0
answers
168
views
Cutting a piece of cake that $n$ people value as exactly $w$
Stromquist and Woodall (1985) study the problem of Sets on which several measures agree. There are $n$ non-atomic value measures on the unit circle, and a parameter $w\in(0,1)$. The goal is to find a ...
- 3,549
1
vote
0
answers
42
views
rank-choice shared-resource fair-division
I'm looking for an algorithm or a paper that solves a problem with a particular set of properties.
Imagine you have some number of rooms and some greater number of people. Each person should be ...
- 63.9k
4
votes
2
answers
350
views
How many cuts are required for a weighted-proportional cake-cutting?
In proportional cake-cutting, there are $n$ agents with equal entitlements to a "cake" (an interval). Each agent $i$ has a nonatomic value measure $V_i$ over the cake, and it is required to create a ...
- 3,549
1
vote
2
answers
301
views
Mediated envy-free and efficient cake cutting with n=2?
Is there an algorithm in literature to compute an efficient (pareto optimal) and envy-free cake cutting when there are only $n=2$ players and a mediator?
- 1,329
14
votes
1
answer
969
views
Stromquist's 3 knives procedure
(copied from math.SE)
BACKGROUND: A cake has to be divided among 3 people with possibly different tastes, such that each person receives a single connected piece, and no person prefers another person'...
CommunityBot
- 1
4
votes
2
answers
9k
views
Seeking a solution algorithm to the 3-partition problem
I need to divide 48 pieces of jewelry between 3 inheritors so as to give equal, or nearly equal value, to each. I have learned that this is called the 3-partition problem. I solved it for 9 pieces of ...
- 362