Dissertation
Super Fair Divisions: A Minimum Number of Cuts
Doctor of Philosophy (PhD), Washington State University
01/2011
Handle:
https://hdl.handle.net/2376/3516
Abstract
This dissertation develops procedures for super fair division that use marks to reduce the number of cuts required for super fair division when compared to all known existing procedures that use marks or can be modified to use marks. Further, our procedures work for the division of desirables, and undesirable, and with entitlements. We further show that for 2 players, at most 3 cuts are required for a super fair division, and we develop a procedure that requires at most 3 cuts for both desirables and undesirable, and with entitlements.
For n players, we provide the first known proof that at least n+1 cuts are required for a super fair division, and develop a procedure that requires only 2n+3 cuts, which, to our knowledge, is vast improvement on all known n player procedures. Lastly, we prove that for one of our procedures, the number of cuts required is a function of the number of distinct measures. For the case that there are only 2 distinct measures, the number of cuts achieves the minimum bound of n+1.
Metrics
10 File views/ downloads
33 Record Views
Details
- Title
- Super Fair Divisions
- Creators
- Thomas Haydock
- Contributors
- William Webb (Advisor)Matthew Hudelson (Committee Member)Hong-Ming Yin (Committee Member)
- Awarding Institution
- Washington State University
- Academic Unit
- Mathematics and Statistics, Department of
- Theses and Dissertations
- Doctor of Philosophy (PhD), Washington State University
- Number of pages
- 99
- Identifiers
- 99900581858201842
- Language
- English
- Resource Type
- Dissertation