Talk:Fair division

Solomon?

Does King Solomon really belong here? I'm pretty sure it's original research to try and extend the fair division problem to babies, where the players' utility functions are, shall we say, degenerate. Would I be wrong in assuming that this hasn't appeared in the literature? Melchoir 02:36, 10 March 2006 (UTC)

Hi Melchoir. It's not original research, as it is appears in Brams's book "Fair division : from cake-cutting to dispute resolution", whose full reference should appear in the article, I guess.

best wishes

Robinh 11:21, 10 March 2006 (UTC)

Wow, no kidding. Okay! Melchoir 19:32, 10 March 2006 (UTC)

I still don't get the need for the King Solomon's example in this article. It is a childish story (no pun intended) which can't solve a real problem. Why would the false-mother be so dumb as to accept the child to be divided? Surely she can see it wouldn't profit anybody. Also, what if the false-mother genuinely believes that she is the mother (which is what fair division is all about). -HRJ 14 Jun 2008

I can't justify having this example mentioned, but then again it is somewhat related and it can be useful to think about it when dealing with the matter. However, I believe in the story of King Solomon the false-mother does not genuinely believe to be the real mother. 83.78.6.212 (talk) 22:42, 17 July 2008 (UTC)

The judgement of Solomon is a good example of something called a fair division that does not satisfy any of the theory of fair divisions definitions of a fair division. Not a very good example as I found out though as I posed the question of why it wasn't a fair division and followed with some cutouts looking like gingerbread men for people to try dividing between themselves in pairs. Bad idea. Smack hand for being insensitive. People got too caught up with it and identified the gingerbread man figure as a baby. And anyway the idea that the women should have decided between themselves on how to cut up the baby is just a bit too gruesome. Dmcq (talk) 23:19, 17 July 2008 (UTC)

Good Article

I don't see anything wrong with it. So a good article it is. --SeizureDog 08:55, 13 June 2006 (UTC)

There is plenty wrong with it, no history of the study, so fails on 3a it addresses all major aspects of the topic. Very far for GA standard, barely B-class. --Salix alba (talk) 08:23, 3 September 2006 (UTC)

Merge discussion

This should definitely be a separate article from envy-free. Though envy-free division is the most common goal of fair division, there are also other goals, such as maximizing the welfare of the worst off player.

I agree to keep the two separated. Envy-free is a different idea, although it is a stub at the moment. Sinas 14:39, 6 February 2007 (UTC)

The envy-free division problem is the one that was really hard to solve and which Brams and Taylor found a general n-person solution for rather than the straight or 'proportionate' fair division problem. So parts of the current article on fair division should be put into a separate article. If that is done though 'fair division' should possibly be a general article outlining the various forms of fair-division problem with a short history and reference both envy-free division and proportionate division articles. The procedures described in the current fair division article do proportionate division and do not ensure envy-freeness (except for divide and choose where one can hardly avoid it). Special 3 or 4 person envy-free division procedures were found before Brams and Taylor and they should probably also be mentioned in the envy free article.  —Dmcq 23:03, 3 April 2007 (UTC)

Simpler solution with many players?

I understand the mentioned method for distributing to 3 (or more) players and I agree it is fair. However, I have a simpler solution that I do not understand why it might be considered less fair (I must assume it is less fair, otherwise it would be mentioned in the article). My method goes like this: The first person (out of n persons) cuts the cake into n parts. Then everyone in turn may choose a part for themselves and the cutter gets the remaining part. Assuming everyone is greedy, then if the cutter doesn't make n equal parts, the remaining part will be less than 1/n of the whole cake, therefore he's motivated to make n equal parts. What's wrong with this approach? 83.78.6.212 (talk) 22:50, 17 July 2008 (UTC)

Consider A just likes the icing, B and C like the fruit cake part of the cake. A divides the icing pretty fairly but cuts the fruit cake part into different size bits as he doesn't care about it or value it the same way as B and C. B takes the bit with the largest fruit cake part, C has to make do with a piece of fruit cake that he can see is much smaller than that of B. C envies B. Problem not solved. There isn't a single uniform valuation of the cake for everyone so you can't just say 1/n of the cake. Dmcq (talk) 23:07, 17 July 2008 (UTC)

Ah yes, I see. My solution doesn't work if the evaluation functions of the players aren't all identical. But I claim that in this situation, even the method mentioned in the article doesn't work. For example, let's assume a cake that has chocolate on one half, has strawberries on the other half and icing over both halves. Person A likes the icing but has no preferences otherwise. Person B prefers chocolate but has no preferences otherwise. Person C likes strawberries but has no preferences otherwise. Person A then cuts the cake in two portions that he considers equal: He cuts the cake in the middle, so one half is only chocolate and the other is only strawberries (since he has no preferences with regard to that); the icing is equally on both halves. Obviously, person B then chooses the chocolate part, leaving person A with the strawberry part. Then comes the next step: Person A cuts his strawberry half in three equal parts with regard to both, strawberries and icing. Person B does the same with his chocolate half. Person C now chooses a third of each portion, ending up with a bit of chocolate and a bit of strawberries. C now envies A, because A has more strawberries than he has himself. 83.78.6.212 (talk) 16:06, 18 July 2008 (UTC)

Oh dear. The problem is that this article should really be an overview with a couple of articles on the different types of fair divisions. The algorithm described is part of what is called 'simple' or 'proportionate' fair division which is basic to all fair divisions. It only requires everyone have at least 1/n of the cake by their own valuation. I'd referred above to 'envy-free' division which is the most popular extension, it requires that everyone thinks they have as least as much as everyone else by their own valuation. Your first algorithm didn't satisfy simple fair division though. The algorithm in the article ensures C gets at least 1/3 of the cake by their own valuation but as you've worked out it isn't an envy-free division. Congratulations on that and sorry about my mistake assuming envy-free division. Dmcq (talk) 19:31, 18 July 2008 (UTC)

Ah, I think I understand now. To summarize: My method above only works if everyone has the same evaluation function, which is a trivial case. The method in the article also works if the evaluation function of each player is different, but still only is a function of the quantity of cake portions; i.e. it would still not work if the cake is heterogeneous and some players have preferences over certain parts of the cake. In any case, thank you very much for explaining this! 83.78.43.34 (talk) 21:23, 18 July 2008 (UTC)

Not quite. The method in the article ensures what is called a simple or proportionate fair division. Each person will get at least 1/n of the cake by their own valuation, but it is perfectly possible they will envy somebody else who they think got more. Since C gets at least 1/3 by his valuation of what each of A and B had then he must get 1/3 by his valuation of the sum of what A and B had which is the whole cake. A division where nobody thinks anybody else got more than them is called an envy-free division and the algorithm doesn't achieve that. Dmcq (talk) 22:55, 18 July 2008 (UTC)

I think the idea is that the way cited in the article makes sure that even if the first person who is cutting the cake "makes a mistake" nobody suffers (i.e. gets less cake than they should) except him. Yeah? Iudaeus (talk) 20:47, 6 December 2008 (UTC)

Yes that's right. Each player is assured of whatever the procedure is supposed to assure them of. It doesn't matter if other people make mistakes - that's their problem.Dmcq (talk) 22:06, 6 December 2008 (UTC)

Splitting the article

I propose to split this article in two

• This article will be an overview of the subject of fair division and reference other articles for the various variants.

• A new article 'Simple fair division' will cover the straightforward basic case of proportionate division of a divisible resource.

This hopefully will clear up the business and not mix up envy-freeness into the basic case. Dmcq (talk) 22:43, 18 July 2008 (UTC)

In fact there is a Proportional (fair division) so I'll use that for simple fair division Dmcq (talk) 00:24, 19 July 2008 (UTC)

Okay I think I've got to the point where it should be open season on what I've written if you've been nice whilst I revamped it. Dmcq (talk) 15:22, 29 July 2008 (UTC)

Image

Re: [1] "it is here because it's a great example of division" - according to whom? why? Images are supposed to illustrate information in the article - the only other occurrence of "Berlin" in the article is in the two sentence paragraph "A common requirement for the division of land is that the pieces be connected, i.e. only whole pieces and not fragments are allowed. For example the division of Berlin after World War 2 resulted in four connected parts." - the first sentence refers probably to some kind of continuity/measurability requirement but in a very unclear way. The second sentence is completely arbitrary.

I don't see any reason to include this image in the article.Volunteer Marek (talk) 10:03, 17 August 2011 (UTC)

(Not to mention that - depending on the definition of "connected" - two of the pieces in the image not exactly connected).Volunteer Marek (talk) 10:10, 17 August 2011 (UTC)

Split of Berlin

There was a perfectly adequate response as an edit comment without needing a big spiel here. The picture directly illustrates the topic which is division without an arbiter. If you really need it there's a reference to this exact thing in one of the books about fair division but I think it is a pretty obvious illustration. Dmcq (talk) 15:38, 19 August 2011 (UTC)

Perhaps, but there's a million images which could illustrate the idea of "division without an arbiter". In fact, out of that set of millions, there's a subset of hundreds if not thousands involving countries or cities. Why this particular one?Volunteer Marek (talk) 06:11, 20 August 2011 (UTC)

Is there? Please provide an example. And why would that be a reason for deleting this one? I haven't noticed you coming up with a better image. Dmcq (talk) 11:51, 20 August 2011 (UTC)

Notice the statement above 'there's a reference to this exact thing in one of the books about fair division' as an answer to why this particular one. Dmcq (talk) 11:59, 20 August 2011 (UTC)

Fair division is not identical to cake-cutting

The beginning of this article - "Fair division, also known as the cake-cutting problem..." - is IMHO incorrect. "Fair division" relates to both divisible goods (like a cake), and indivisible goods (like heirlooms). The "cake-cutting problem" is a synonym for "fair division of divisible goods", but not to "fair division" in general. For example, see google scholar articles about fair division of indivisible goods. --Erel Segal (talk) 05:24, 17 April 2013 (UTC)

Sol Garfunklel???

Oh ffs. Someone is doing a bit of self-promotion here. Unless there's some actual reason this nobody is here, he should probably be removed. The claim that he made an uncited claim is also un-cited. — Preceding unsigned comment added by 69.181.168.139 (talk) 20:17, 20 April 2013 (UTC)

Apartment/Appartment

"Apartment" is misspelled in the image containing "X = piano, car, appartment". — Preceding unsigned comment added by 128.32.90.36 (talk) 18:14, 7 June 2013 (UTC)

Dr. Brams's comment on this article

Dr. Brams has reviewed this Wikipedia page, and provided us with the following comments to improve its quality:

This entry gives a reasonably comprehensive overview of Fair Division, with helpful categories, but it is several years out of date, especially on the contributions of computer scientists. For a summary of these contributions, see the section, “Fair Allocation,” which comprises three chapters, in

Felix Brandt, et al. (eds.), Handbook of Computational Social Choice (Cambridge University Press, 2016).

This book is scheduled to be published in November 2016, but it can be downloaded free, with instructions as to how, on the website, under “Research,” of Ariel Procaccia (one of the editors):

http://procaccia.info/research/

Also, the seven chapters in part 2 of

Steven J. Brams, Mathematics and Democracy: Better Voting and Fair Division Procedures (Princeton University Press, 2008),

discuss fair-division algorithms and includes applications in political science and related fields. A 2014 article,

Julius B. Barbanel and Steven J. Brams, “Two-Person Cake Cutting: The Optimal Number of Cuts,” Mathematical Intelligencer 34, no. 3 (Fall 2014), pp. 23-35,

includes a recent survey of cake-cutting results at the beginning.

The present entry contains numerous errors in punctuation, grammar, and syntax that could benefit from copy-editing by a native English-language speaker.

We hope Wikipedians on this talk page can take advantage of these comments and improve the quality of the article accordingly.

Dr. Brams has published scholarly research which seems to be relevant to this Wikipedia article:

• Reference 1: Brams, Steven J. & Kilgour, D. Marc & Klamler, Christian, 2014. "An algorithm for the proportional division of indivisible items," MPRA Paper 56587, University Library of Munich, Germany.

• Reference 2: Brams, Steven & Kilgour, D. Marc & Klamler, Christian, 2014. "How to divide things fairly," MPRA Paper 58370, University Library of Munich, Germany.

• Reference 3: Barbanel, Julius B. & Brams, Steven J., 2011. "Two-person cake-cutting: the optimal number of cuts," MPRA Paper 34263, University Library of Munich, Germany.

ExpertIdeasBot (talk) 12:03, 15 June 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Fair division. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20060220022042/http://www.elsevier.com/framework_aboutus/Nobel/Nobel2005/nobel2005pdfs/aum16.pdf to http://www.elsevier.com/framework_aboutus/Nobel/Nobel2005/nobel2005pdfs/aum16.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 15:53, 27 September 2017 (UTC)

"3 straight cuts through its middle"?

I challenge anyone to show how you can can get 8 equal pieces of cake by making "3 straight cuts through its middle". You would get 6 pieces that way, but you would need 4 straight cuts to get 8 pieces. After the first cut you would have 2 pieces, and each cut through the middle after that would add two pieces. 1 cut = 2 pieces, 2 cuts = 4 pieces, 3 cuts = 6 pieces, 4 cuts = 8 pieces, 5 cuts = 10 pieces, 6 cuts = 12 pieces, etc. And better wording would be "through its center". Chris the speller ^yack 04:34, 4 July 2020 (UTC)