Skip to main content

Questions tagged [fair-division]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
54 views

Fairest way to share gifts between kids

I want to give to 3 kids the possibility to choose 2 gifts each, out of a total of 10 gifts. All gifts are of exactly the same value. You can think of them as all being frisbees (or whatever) but ...
stratosgear's user avatar
1 vote
1 answer
25 views

Is the Even–Paz cake-cutting protocol a finite algorithm that guarantees proportional and connected pieces?

In theorem 8.2 of "Cake-cutting algorithms" by Robertson and Webb, it is stated that No finite algorithm can guarantee each of $n$ players at least $1/n$ of the cake using only $n - 1$ cuts ...
Abelaer's user avatar
  • 11
0 votes
0 answers
23 views

Money division based on attendance percentage.

I am organizing a tour for the musicians in my orchestra, and I want to create a formula that will reduce the cost of this tour for each musician based on their percentage of attendance at rehearsals. ...
Mateusz Mgum's user avatar
1 vote
0 answers
17 views

What is the solution of the Fair Division of Transportation Costs problem?

Firstly, this is - in a way - somewhat golf-ish question (as in: code golf stack exchange), so if it doesn't fit this forum then feel free to close it. But nevertheless please read the rest of the ...
Spook's user avatar
  • 946
0 votes
0 answers
34 views

Fair choice allocation using Edmonds Karp, adding group choices

I have an algorithm that uses Edmonds-Karp algorithm to distribute users into groups in a fair manner given a rating for their choice of groups. Currently a given graph for two users ($u1$, $u2$) and ...
Lucy Kalwa's user avatar
1 vote
0 answers
46 views

Dividing a cake into two pieces and/or choosing between them takes $(n^2-n) \over \log(n)$ steps!?

After reading the article of the cake cutting problem in the September 2023 issue of science news. I was thinking about using a divide and conquer strategy by having the cake eaters divide themselves ...
Steven Owens's user avatar
1 vote
1 answer
78 views

Algorithm for allocating whole gold bars amongst thieves by % share of the booty

I have N big gold bars and 1 small gold bar equivalent in weight to some fraction x of a large bar. E.g N = 10 and x = 0.5 then I have 10.5 large bars worth of gold, in 10 large bars and 1 small bar I ...
Greedo's user avatar
  • 201
0 votes
0 answers
52 views

A fair division algorithm

Imagine two individuals, R and G, are to inherit 100 ancient coins. The coins are perceived to be of somewhat different but unspecified values. By the division 60 coins will go to R and 40 to G. The ...
Maesumi's user avatar
  • 3,702
3 votes
1 answer
116 views

evaluate $\int_0^{\infty} e^{-x} \prod_{m=0}^{\infty} ( 1-e^{-2^m x}) \space dx$ to find a fair sharing constant

$$\int_0^{\infty} e^{-x} \prod_{m=0}^{\infty} ( 1-e^{-2^m x}) \space dx$$ Is the amount more than Bob that Alice gets when dividing objects according to the Thue-Morse fair sharing sequence (ABBABAAB.....
Zoe Allen's user avatar
  • 5,633
1 vote
2 answers
267 views

How is Armageddon in chess like fair cake-cutting in game theory?

In chess (or 9LX), Armageddon is a kind of blitz/rapid chess used as tiebreakers: Black has draw odds, but white gets more time. Eg In the 2022 women's US Chess Championship, Jennifer Yu won the coin ...
BCLC's user avatar
  • 13.7k
-1 votes
2 answers
517 views

cutting bread problem

Here's the question: If we have m loaves of bread and want to divide them between n people equally what is the minimum number of cuts we should make? example: 3 loaves of bread and 15 people the ...
Tiffany light's user avatar
0 votes
1 answer
16 views

Has this set bipartition optimization problem been studied?

Suppose a couple is getting divorced and they want to split some collection of objetcs, say their books. They have $N$ books, labeled with indices from $1$ to $N$. You are the arbiter of this division....
Marcel's user avatar
  • 1,583
0 votes
0 answers
134 views

How to create a fair distribution algorithm?

I am even a math noob but need to understand what is the best mathematical formula for fair distribution. The problem statement is as follows: We choose 2 numbers at a given time to distribute ...
RAY's user avatar
  • 1
0 votes
2 answers
265 views

Why do we add a decimal point in division [closed]

In class, my teacher showed me this example: 8 / 10 in long division. She said: "Take 8 and divide by 10; you can't do it because 8 < 10 and 8 is not in 10's table; so add a decimal point, add ...
Jandroid's user avatar
  • 127
1 vote
0 answers
51 views

Thoughts about a how to share a cake

So when i was a kid we used to do this thing when we shared a snack. one kid would cut the snack in half and the other would pick which of the two halfs he wants. this way, even though the picker will ...
DAcheese's user avatar
0 votes
2 answers
77 views

Fair Division: for $n > 2$

I apologize if this is a dumb question. Basically, I'm wondering if the following is equivalent to the last diminisher procedure. If not, I'm curious why this fails. What I have in mind is as follows: ...
Yonas Oberlin's user avatar
2 votes
1 answer
121 views

Bonus scheme calculation

Problem Background: We are a project based company. Employees work on project basis and each project duration can be between 3 days to 30 days. At the end of each project, the employee will get rated ...
upchuck1's user avatar
1 vote
1 answer
27 views

Which practicable solutions exist to fair distribution of a finite resource over a finite time horizon?

Imagine we have $X$ amount of some resource available over a fixed, known, and finite time period $T$. An unknown but finite number $N$ of users can each at arbitrary times request some share $Y = y/X$...
Thomas Arildsen's user avatar
0 votes
1 answer
14 views

Find the set of 'fair' groupings from non-square binary matrix and cost vector

Given an m by n binary matrix $P$ and a 'cost' vector $v_1$ I want to find the set of $P$ matrices where the product $Pv_1=v_2$ results in all the elements of $v_2$ being within a certain lower and ...
Alan Cash's user avatar
0 votes
1 answer
20 views

Fair way to split fees

So I have a very simple problem, but I am unable to find a proper solution top it. Four friends rented and apartment for 1 year. They paid \$590 of deposit each (\$2360 total). By the end of the year, ...
Italo's user avatar
  • 3
0 votes
0 answers
18 views

Division of losses

Partner A borrows 40000 and invests in business. Partner B borrows 15000 and invests in same business. The business didnt go through. Both Parties invested a total of 55 000. One partner invested more ...
zizu 112233's user avatar
0 votes
2 answers
35 views

Real life problem: How many finalists can participate per school?

I have to organize a tournament with following numbers: I have a total of 1338 participants from different schools, and we need to distribute the 16 finalist's places as fair as possible. The students ...
math2hard's user avatar
0 votes
0 answers
197 views

What is the preferred algorithm for fair item allocation?

Lets say my friends and I ($n$ people in total) are moving together to an $n$-room house and each one uf us has a precise ordering of the rooms we'd like to live in. That is, if $\{R_j\}_{j=1}^n$ is ...
augustoperez's user avatar
  • 3,226
10 votes
7 answers
3k views

What's a fair way to share fees in a group road trip with a personal and a rental car?

I'm planning vacations with a group of friends (12 people), and it involves a ~1200km return trip by car. Only one of us owns a suitable car (4 pax), so we've rented a minivan to transport the other 8,...
foucdeg's user avatar
  • 211
0 votes
1 answer
33 views

fair disivion of indivisibles with qualification constraint

Let there be $n$ indivisible heterogenous items. Let there be $m$ agents. The subjective utility functions of the agents are additive and identical. i.e $\forall X,i,j\ V_i(X) = V_j(X)$. The ...
Gal Avineri's user avatar
1 vote
2 answers
170 views

Understanding Austin's two moving knives procedure for cutting a cake fairly

From wikipedia description, the Austin procedure goes as follows Alice places one knife on the left of the cake and a second parallel to it on the right where she judges it splits the cake in two. ...
markeb's user avatar
  • 13
8 votes
2 answers
458 views

Selecting cards to form a fair game

Background In an old card game we draw 2 cards from a pile of 2 red and 2 black cards without replacement. If the two cards have the same color (for instance red and red) you win. However, if the ...
N3buchadnezzar's user avatar
0 votes
1 answer
33 views

Assigning 257 applications between two assessors each, from uneven panel number

So I am very bad at math and have a problem I am dealing with. I have 257 applications for a job. Each application has to be assessed by two assessors. The panel of assessors has five assessors. ...
the_t_test_1's user avatar
1 vote
1 answer
63 views

Fair turn sequence for 6 (or n≥3) players, when we care who goes after whom

My searching has come up with, at best, this question: What's the fairest turn sequence for n players? which as far as I can tell does not answer my question. I have a game with 6 players - let's ...
NeatNit's user avatar
  • 127
0 votes
1 answer
41 views

Dividing n balls of different mass into 2 groups with the groups having a similar mass to one another

If there are n balls, each with a different mass, how could you divide the balls into two groups, so that the sum of the mass in one group is as close as possible to the sum of the mass of the other ...
Lukas Grbac Lacković's user avatar
1 vote
0 answers
48 views

MIP programming for fairness

I have a MIP model that allocates 24 rides between 6 drivers (with many constraints irrelevant here), and an important part of my objective is splitting the rides fairly. The easiest implementation ...
ihadanny's user avatar
  • 181
3 votes
2 answers
127 views

Fair Sharing of a Pizza When Opinions About the Edge Differ

Two friends wants to share a pizza. One of them loves the edge of the pizza and the other one hates it. Both consider the pizza to get tastier the closer to the center you get. What is the fairest way ...
Lars Rönnbäck's user avatar
0 votes
1 answer
813 views

Fair choosing rotation with 8 people

I have to divide holiday shifts at work into a group of 8, both AM and PM shifts need to be covered (we rotate between both AM & PM). A total of 24 holiday shifts with 3 major holidays (New Years, ...
Stigs's user avatar
  • 1
0 votes
1 answer
76 views

Game theory problem about 2 students claiming different work amounts

This is quite a simple question I heard and wondered what the mathematical absolute solution to it. There are 2 students, the teacher saw their group project and graded it 100 points. Now he needs ...
Amit TPB's user avatar
  • 195
0 votes
1 answer
192 views

Organizing objects in a near-square pattern

I don't have any fixed constraints but just a general idea. This probably a well known problem too - yet I can't seem to find any literature on it. Given n identical 2D objects, what is an algorithm ...
Charles's user avatar
  • 268
2 votes
2 answers
269 views

Fair cutting of a cake [duplicate]

For the fair cutting of a cake into n pieces for n people, is it sufficient for one person to cut the cake, and for them to get the last pick of piece? If any one piece is bigger than 1/n, another ...
Yashmnash's user avatar
  • 187
65 votes
3 answers
7k views

Optimal strategy for cutting a sausage?

You are a student, assigned to work in the cafeteria today, and it is your duty to divide the available food between all students. The food today is a sausage of 1m length, and you need to cut it into ...
Stenzel's user avatar
  • 633
3 votes
1 answer
83 views

Problem involving directly and inversely proportional division

A father wishes to divide his 500-acre farm between his three sons in portions of land directly proportional to the number of kids each one has and inversely proportional to their incomes. If the ...
Sasaki's user avatar
  • 1,209
5 votes
2 answers
254 views

The Abel-and-Cain Urn Problem

An urn contains three distinguishable kinds of balls, say $A,B,C$. Abel bets to get, in $t$ trials with replacement, at least one ball of kind $A$ and at least one ball of kind $B$. Cain bets to ...
user avatar
0 votes
1 answer
49 views

How to share a cash prize among multiple entries in position A, B and C

How to share a cash prize among entries in position A, B and C. Each position can have multiple entries. Each entry in position A should have 50% more of the cash prize than each entry in position B. ...
Kabelo2ka's user avatar
  • 103
2 votes
0 answers
454 views

Fair sharing sequence for n players

When $2$ players are given an infinite stream of items to divide between them. There is no way to quantify the value of the items, but their value is strictly decreasing. Which person should take the $...
EPICI's user avatar
  • 355
0 votes
1 answer
30 views

If 1x item costs 310, how much of item would 50 get me?

I'm trying to work out what to use to work this out. If ITEM costs 310 for 1, how much would I get if I paid 50? I'm more looking for how to work this out so that I can apply this to other things.
Arnie Cunningham's user avatar
0 votes
0 answers
66 views

how to use full amount in division

How to use the full amount in a division? So if I want to divide 10 / 3, I want the following results [ 3.33, 3.33, 3.34 ] (if ...
pablo's user avatar
  • 101
-2 votes
1 answer
69 views

Renting a house!

Suppose that we are $6$ guests for renting a house, $2$ are going to spend three nights in the house while $4$ of them are going to spend just $2$ nights in this house. The problem is that if the bill ...
RobinHood's user avatar
  • 123
0 votes
1 answer
1k views

Shapley values- airport problem

can anyone help me on this? I am trying to understand how can I find the Shapley values for the following airport problem. There are 3 types of airplanes, type 1, type 2 and type 3 and they require ...
user290335's user avatar
2 votes
2 answers
221 views

How to divide 276 with 15 people?

I have a math question. In our bachelor room our water bill is 276. It is a bill for 31 days. But out of this 15 people, only 12 people used water for 31 days. one went for vacation after 20 days that ...
Muhamad Sadik's user avatar
0 votes
1 answer
57 views

How to divide based on fraction per partipant

I want to fairly divide a random number of sweets I buy every day between kids in my class for the day based on the days test results. I calculate the test results. There are 10 Kids: At the end of ...
dfmetro's user avatar
  • 103
0 votes
1 answer
115 views

How to split a total into smaller disaggregates that match the total it was split from

I need to resolve the following in computer language. I have situations that I have to split totals in smaller various disaggregations. A client gets data from clinics around a district. However ...
dfmetro's user avatar
  • 103
4 votes
2 answers
919 views

Why division gives equal parts?

I'm ashamed to ask this question. For a while, I can't pull out of my mind really basic kindergarten questions like: what is actually a number, what is a function and what is the connection between ...
J.Doe's user avatar
  • 45
10 votes
1 answer
2k views

What's the fairest turn sequence for n players?

For two players, in some sense, the fairest possible turn order is the Thue-Morse-sequence: 01101001100101101001011001101001.... It arises by taking turns ...
kram1032's user avatar
  • 1,105