For various problems related to dividing a resource among several parties.

learn more… | top users | synonyms

4
votes
1answer
95 views

Cutting a pie with a fork

You baked a pie in the shape of a disc, with some cherries spread unevenly on its top. You want to give each of your two children a piece of cake such that: The pieces are congruent - have the same ...
1
vote
1answer
376 views

Divide a set of $n$ elements into $k$ subsets having equal sum

Given $n$ ( $n$ <= 20) non-negative numbers. Is there / Can there be an algorithm with acceptable time complexity that determines whether the n numbers can be divided into $k$ ( $k$ <= 10) ...
2
votes
2answers
95 views

The fair meat bazaar: Who has right?

In a local town the girl scouts have been selling tickets, and now it is the time to pick winners. The number of winners is yet to be decided. The names are collected in $3$ books. With respectively ...
0
votes
1answer
9 views

For 2 people, division of good s is equitable, why following statement is true?

As I said, For 2 people, division of goods is equitable, then One of the following is true 1) The division is envy free 2) If they switch their shares, then the division is envy free. I started ...
0
votes
1answer
18 views

Shipping Question.

I need to work out the most effective way of shipping the following amount of boxes in different containers. 889210 boxes 666911 boxes 444606 boxes 222305 boxes The largest container can hold 4004 ...
2
votes
4answers
57 views

Challenge: “Dividing” a number above 0 and ending up with the same, or a greater number (creative task)

Here's a question/challenge for those of you who know quite a bit about math, or enjoy to be creative with what you do know (just for reference: I'm virtually illiterate when it comes to any math more ...
1
vote
1answer
41 views

How to solve this problem? Distributed Game theory?

I have this problem: We dispose of some resources, say $\{f_1, f_2, \dotsc, f_m\}$; We have some agents or players, say $\{\mathrm{p}_1, \mathrm{p}_2, \dotsc, \mathrm{p}_n\}$; Every player has some ...
2
votes
2answers
102 views

Protocol to split a common item between 2 people

I have a question related to the "pizza splitting" problem (split the pizza in a fair way), and I am looking for an answer of hopefully the same elegance (first splits, second chooses). Not sure if ...
1
vote
1answer
65 views

Fair three-way sandwich division

This question discusses fair three-way sandwich division. Mentoined solutions include the Selfridge–Conway discrete procedure and the moving-knife procedure. I posed the question to the guys at the ...
406
votes
25answers
52k views

Splitting a sandwich and not feeling deceived

This is a problem that has haunted me for more than a decade. Not all the time - but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an ...
2
votes
1answer
83 views

Fair Division: Making the Differences in Players' Valuations Believable

When teaching basic fair division algorithms, the students always propose some simple and (at the first glance) correct solutions for $n$ players, which unfortunately are not correct! The only way I ...
6
votes
1answer
111 views

Fair division of an octagon

A land-plot belongs to two partners. Its form is a regular octagon with area 1. They want to divide it such that one gets area $p$ and one gets area $1-p$, where $p \in (0,1)$ is a given constant. ...
2
votes
1answer
159 views

Lyapunov Theorem for beginners

I study the subject of fair division (cake-cutting), and many papers contain a reference to a theorem by Lyapunov, which states that the range of any real-valued, non-atomic vector measure is compact ...
0
votes
1answer
30 views

Partition set to contain the same number of elements distributing the remainder

Given $|B| = 23$ and number of partitions $P=4$. We want to partition the given set $B = B_1\cup\dots\cup B_P$ so that every partition $B_i$ contains the same amount of elements where the remaining ...
1
vote
1answer
138 views

Weighted division?

Let's say I have 10,000 dollars I want divided among 10 people. With simple division each person gets $1,000. Easy enough. Now suppose each person has a score on a test from 0 to 200. Now I want ...
0
votes
2answers
104 views

A beer problem (divide bills)

I am making an application to divide bills. I have the following problem: Jhon and Paul were to a pub , and they consumed 20 beers. James get in the bar and they consumed ten more beers. How much ...
6
votes
4answers
481 views

Cutting the cake problem if the value measures are not finitely additive

Background I have (rather recently) dabbled in game theory. I need it to design an algorithm to share chores. Obviously this is a kind of cake-cutting problem. So far, I have fought my way through An ...
1
vote
3answers
112 views

How to derive the share of a prize given scores

I am curious to find out reasonable ways of dividing a prize among $n$ people in the following situation: To make the example specific, we have $6$ people in total who are going to share a prize of ...
2
votes
1answer
175 views

Evenly dividing candy bar into $n$ pieces

I have 2 friends. We have one candybar and we want to divide it evenly. Unfortunately we don't have any way of accurately measuring and cutting the candybar. Therefore we are looking for a method ...
1
vote
1answer
96 views

Allowance distribution problem

When I say allowance, I mean like the kind you earned as a child. Here is the problem I am trying to solve. A parent has $20 they want to give to the child for doing all of their chores. If the child ...
4
votes
6answers
2k views

Cutting the Cake Problem

The tradition way for two children to divide a piece of cake fairly between them is "you cut, I choose", What process accomplishes this is intuitively clear. Is there a similar process which works for ...
16
votes
8answers
5k views

Is it possible to 'split' coin flipping 3 ways?

When flipping a coin to make important decisions in life you can flip once to choose between 2 possible outcomes. (Heads I eat cake, Tails I eat chocolate!) You can also flip twice to choose between ...