• Fair allocation of chores
    Repo
    mattandjay
    Abstract
    As long as people have existed, we have been concerned with achieving the best possible outcome for ourselves, or, at the very least, our "fair share." The idea of fair division is a social contract that has evolved out of that desire to achieve the best possible results for us, while acknowledging other parties' wishes to accomplish the same. The goal of our project is to extend this concept to a real-world fair division problem in our own lives. Our house is owned by 46 young collegiate men, and as such, needs constant attention and dedication to maintenance and cleanup. Thus, our home receives weekly cleanings by subsets of our 46 members consisting of regular chores like mopping, taking out the trash, cleaning the kitchen, and more. Our current selection for who cleans on a given weekend and conducts which chores is a random selection by an excel spreadsheet, leaving many people feeling as though they receive an unfair amount of work. However, by incorporating our own variations of several fair division algorithms, we hope to accomplish a fairer outcome, giving each person their best possible chore combinations given everyone's individual preferences. Our solution consists of a manipulation of the Banach-Knaster moving cake algorithm, along with select concepts from several other fair division algorithms, including sealed preferences and negative utility consideration.
    Report
    PDF
    Comments
    Nice project and good data for the experiments. Had trouble running the code locally but managed to do it. A help or README would have been useful.
  • Fair allocation of working time slots
    Repo
    happyscheduling
    Abstract
    The main idea of our project is to implement algorithms to divide and assign working time slots for employees fairly. We try to solve this problem in two ways, one is for each employee, he/she picks the time slots he/she prefers to work on, the other is employee can pick the time slots he/she does not like. We start solving the problem from the simple situation, there are only two employees. Then we try to solve the more complex situation, there are more than 2 employees.
    Report
    PDF
    Comments
    Nice job. For n=2 Divide and Choose, you would expect p1 to be at a disadvantage. Based on the methods you tried, what method would you recommend be used and why?
  • Hubble telescope tasking
    Repo
    bkerr
    Abstract
    We mapped the intricacies of scheduling jobs for the Hubble Space Telescope to fair division algorithms, specifically to naive and modified versions of Last Diminisher. We implemented our Last Diminisher algorithms using preference files that consider time constraints on proposed jobs, as well as the Hubble telescope’s position in space in relation to the Earth and the Sun and the further limitations that imposes on scheduling. We compared our two algorithms based on total time allocated, number of cuts, percent of pending jobs scheduled, and the total weighted value of the jobs selected based on importance to the scientific community.
    Report
    PDF
    Comments
    The description of the modified Last Diminisher is incomplete. A fuller description is needed to understand what was done here.
  • Football draft
    Repo
    football
    Abstract
    In this project we examine how draft ordering can affect the overall happiness of each person drafting. We implemented and ran four algorithms to determine the order of each round in a draft. Two of the algorithms were discussed in class and are common in drafts today, strict ordering (NFL draft) and snake ordering (order reverses after each round, fantasy sport drafts). Two new algorithms were introduced in an attempt to keep the received utilization of each drafter as close as possible. Using realistic preference files representing players in a fantasy football draft we compare the four algorithms and present our results.
    Report
    PDF
    Comments
    Nice job. It will be interesting to compare this with other draft approaches from the class.
  • Repo
    cakecuttersim
    Abstract
    Fair division algorithms, especially the ones that require continuous observation, tend to assume synchronicity in decision making and knife movements in theory. However, in practice, it is not always possible to give an exact solution to a fair division algorithm without making some assumptions or error bounds. As such, we would like implement both an exact and discrete solution to given algorithms and compare how good of an approximation the discrete solution is. In this experiment, we will be implementing this concept to two such algorithms, both Moving Knife algorithms. The first of the two is the classic Moving Knife algorithm, also known as the Dubins- Spanier moving knife. The second of the two algorithms is a custom variation to this moving knife algorithm, which we have coined the “Sistla-Fang” Moving Knife algorithm. In both cases, we will compare the discrete and exact solutions and determine how good an approximation the discrete version is. Further, we will compare the two algorithms mentioned and attempt to show that the “Sistla- Fang” Moving Knife is a more viable option when considering envy-freeness.
    Report
    PDF
    Comments
    Great job. It would be interesting to analzye the Sistla-Fang approach in more detail to get a better handle on why it has less envy than Dubins-Spanier.
  • MMO EVE pilot task assignments
    Repo
    evecake
    Abstract
    This project attempts to implement the Last Diminsher algorithm in order to divide typical tasks among cooperating players in the MMO video game, “EVE Online”. The tasks are considered indivisible in nature, and the algorithm attempts to divide these tasks among the players, given their preferences for how difficult they view a task to be. The algorithm is written in such a way that it can take input for any list of indivisible tasks and any number of individuals who have submitted their preferences; in this way, it is not specific to EVE Online.
    Report
    PDF
    Comments
    Great job. It's interesting that the pilots had trouble valuing tasks. This has been pointed out as a drawback of cake-cutting algorithms, because they assume people know how they feel about cake. Is there some way to derive pilots' utilities from other information so as to make the valuation easier?
  • Bequeathing of iTunes music library to daughters
    Repo
    brucewillis
    Abstract
    Suppose for a moment that iTunes changed its license agreement to allow transfers of ownership for purchased songs or collections of songs. How might the bereaved divide such a resource? If his music collection is as vast as rumors tell it, it may take far too much time for the siblings to divide individually, especially when you consider their unique music preferences.

    As we discussed throughout the semester, there are multiple procedures we can apply to help streamline and even automate such tasks. While there are numerous approaches to take, we will limit our review to: Divide and Choose, Fink’s Lone Chooser, and Knaster’s Sealed Bid procedures.

    Report
    PDF
    Comments
    Great job and interesting problem. Nice that you used real iTunes library (XML) for input. You descibe Divide and Choose, and Fink's Lone Chooser, but I'm not sure why. You settled on a bidding system like Knaster's from what I can tell, and the experimental runs are just for Knaster. I can't run your code because it's set up for Jython. Please stop by next semester and show me how to get it running. The bidding turns out the way you'd expect with Knaster, and that's fine, but you might say how you (if you were Bruce Willis) would use the information to distribute the music library.
  • Dividing an inheritance
    Repo
    saintpeters
    Abstract
    Here in Saint Peters Missouri, the Thomas’s, a family of six siblings, had their dad pass away in May of this year . Unfortunately for this family, Mr. Thomas left them without making a will stating which sibling gets to own which part of his properties. His children, James, Steve, Cindy, Kaitlin, Bob and George, have equal share inheritance in their dad's properties. The properties they intend to share include: the house in which they all grew up in, a type C motor home recreational vehicle (RV), a moped, various Investments, a 1998 Chevy truck, a farm, several pieces of jewelry, and several pieces of furniture. In order for each of the heirs to have a fair share of these eight (8) estate possessions, we, the saintpeters group, decided to help this family divide their dad's estate so that each of them can leave feeling happy about their fair share. In order for us to help divide these indivisible items amongst the family, we thought about all the algorithms covered during the course of the semester, and we decided to apply the Knaster’s sealed bid and adjusted winner in a way to see which algorithm will give us the best results in terms of fair division.
    Report
    PDF
    Comments
    Great job. Interesting that you found Knaster a better approach than AW for this particular problem. Nice analysis and write-up!
  • Poker
    Repo
    cheesepizza
    Abstract
    In real-live division problems, there often is a need to divide goods which, for a particular person, may carry values which are not independent of each other. For example, in a divorce situation, a husband may think that the HDTV and the DVR are of greatest value when put together to watch football, while her wife has independent appraisals of the devices she uses for watching movies and taping soap operas. Current modeling of fair division problems does not account for this phenomenon.

    For this project we created a game that tasks players with dividing a set of playing cards with the intention of forming a poker hand, in conjunction with two cards which only they know about. We decided to make this game because it creates a situation where the goods are discrete, subjectively valued, and non-independently valued. The game is also immediately understandable to anyone with experience playing card games, and involves very little abstraction on our part. With this game, and with a simple-but-effective AI, we simulated thousands of Adjusted Winner divisions and evaluated whether a fair division reliably occurred.

    Report
    PDF
    Comments
    So would it work to enforce a polite strategy as part of the game, or would the game (Horrendous Hog, or other similar games) become non-interesting if card assignment were always polite? Interesting project and well done!
  • Rent and room allocation
    Repo
    neraylevin
    Abstract
    We used a combination of a Dutch auction and the Moving Knife algorithm to divide up rent and rooms in an apartment with three people. In the end, our algorithm allocates one room to each player and no player envies another for more than a previously agreed upon amount (resolution/epsilon).
    Report
    PDF
    Comments
    You did not submit PDF as asked. Cool problem. If you are worried about the rent being paid in full, could the bidders bid on a fraction of the rent? Nice experiment to measure envy-freeness. Think people might use your approach for real?
  • Game spoils division
    Repo
    looters
    Abstract
    A comparison of a Massively Multiplayer Online (MMO) game “Need or Greed” algorithm to Knaster’s sealed bids for the distribution of loot. In MMOs, at high level play, many players are usually needed to take on the greatest challenges. As a reward various items are awarded to players that are participating. Because of various factors certain players may “need” or simply want (“greed”) certain items. Each player has their own valuation of each item. With random assignment dictating who receives an item there is a chance that players will feel that they didn’t get a proportional share for the time they invested. We compared one currently used algorithm (“Need or Greed”) with Knaster’s sealed bids to see how they differ in proportionality, envy-freeness, equitability, and stability.
    Report
    PDF
    Comments
    No abstract? I took your first paragraph. Nice write-up, solid experimentation and analysis.
  • merger and acquisitions
    Repo
    merger
    Abstract
    In this paper, we detail our approach to quantify the continuous pricing errors in corporate mergers and acquisitions and suggest an algorithmic approach to more accurately price an M&A transaction. Qualitatively, our algorithm provides a logical path to prevent certain value destructive transactions and encourage transactions that add economic value. Quantitatively, it also outlines a methodology to ensure proportionality in each transaction, and propose a theoretical envy free solution. We analyze this problem within the scope of cake cutting theory, introduce cheating in the form of pricing discrepancy, and discuss how traditional fair division models fail. The ultimate goal of our analysis is to suggest a procedure with which bankers, target companies, and acquiring companies can value a possible merger systematically and realistically that some of the common causes of failed mergers and acquisitions can naturally be prevented.
    Report
    PDF
    Comments
    You tackled a big problem, and I understand how the lack of real data is frustrating. But I don't see how you applied a fair division algorithm to the problem. It looks like you computed some kind of median information to come to some kind of agreement. I would like to learn more about what you did, and you will have to communicate that in terms a non-business major can understand. I would consider revising your grade once I understand this better.
  • Austin's algorithm with preference dependences
    Repo
    jrjrepo
    Abstract
    The Moving Knives algorithm attributed to Austin provides a method to divide cake between two parties in such a way that each party feels they have received exactly half the value of the overall of the cake. The solution provided by the algorithm is proportional, envy-free, and equitable. The algorithm is written for preferences that are both independent and additive. Since many scenarios in life involve preferences which do not have these characteristics and have dependencies within the preferences, this project is focused on modifying the Moving Knives algorithm to handle these cases. After experimentation with preprocessing the value function input and modifying the way the algorithm evaluates potential divisions, a variation was produced that searches for a division location that yields proportional results while ensuring necessary dependencies are met. The resulting algorithm however does not guarantee such an outcome is available. It only applies a single method in an attempt to find one.
    Report
    PDF
    Comments
    Interesting problem, and it's fine that not every situation has a solution. It might be interesting to characterize what kinds of dependences do lead to solutions (provably). Perhaps you could begin with some common kinds of dependences in preferences for some set of problems?
  • Stromquist visualized
    Repo
    carleton
    Abstract
    For my project I investigated the Stromquist Moving Knives algorithm. The project consisted of two parts: visualization and analysis. The Stromquist moving knife algorithm is a cake cutting algorithm that attempts to divide a cake between three people such that none of the three envy a different person’s piece. Each player and a referee are given knives. Each player moves his or her knife anywhere along the cake while the referee moves his knife continuously from the left. At some point a player says stop, and according to the algorithm’s rules, the cake is split up among the players based on where their knives are at that moment. The visualization component is an interactive web application that allows the user to input preferences for three players and watch the algorithm play out in an animation. The analysis portion of the was trying different strategies for knife placement to see if a player could gain an advantage by straying from the standard position. These strategies were also added to the web app.
    Report
    PDF
    Comments
    Initially I thought this would just be the visualization but the analysis of strategies is very interesting. If you have insight into why you obtained the results you did for the strategies, that might be publishable? Great job!

    Note: the app is currently available at http://stromquistcake.appspot.com/

  • Fantasy sports draft
    Repo
    fdfantasysports
    Abstract
    In this paper, we describe two modified Knaster’s Sealed Bids procedures to facilitate a fair player draft. One such procedure is a round based player allocation draft with caps on the amount a bidder can bid each item in a round. An additional approach auctions slots for a draft with point allocations carrying over in between rounds.
    Report
    PDF
    Comments
    Great job and interesting problem. You might want to look at the other groups' work that did draft-related problems. If the problem of receiving players of a certain kind (e.g., quarterback) is hard maybe your approaches could work for teams where players are more uniform, such as volleyball?

    For the plots that show proportionality, there appear to be 5 bidders, so 20% would be the nominal proportional value for each, correct? Another way to read the data is that you are showing the perecentage of a proportional share. Great job!

  • fair course seat allocation
    Repo
    sunwind
    Abstract
    Nowadays, university students usually facing with the problem of course choosing. It’s not only about which courses to choose, it’s also about by what strategy one can get into the courses that he/she chooses. Usually most course choosing systems is obeying the rule that first come first get. This seems not so fair and makes every student to choose course as early as possible. The student may do not have a good look at the courses he/she chooses. After the learning of cake cutting course, we come up with the idea to improve the course choosing system. We have designed a new algorithm for this. Our algorithm is a combine of Ann & Ben divorce algorithm and Knaster’s procedure. And the goal is to make the course choosing system more fair and make everyone happier. And by analyzing the result of the new course choosing system, we find that the more rounds we use this system, the more fair it will be.
    Report
    PDF
    Comments
    I am unclear as to what you mean by the Ann and Ben divorce algorithm. Ann and Ben is just an example. What is the algorithm you are using?

    For your results, how is it possible that T (the denominator in U/T) is anything but 1000?

    You say your approach is not envy-free, but where do you measure envy?

  • Fair pizza toppings
    Repo
    thunderraptors
    Abstract
    Our project goal was to determine an efficient and equitable solution for the distribution of pizza toppings for a group of people with different pizza topping preferences. The algorithm can be used for more than just pizza toppings as long as it makes sense to distribute them in a similar manner. The algorithm we used to solve this problem was a modified version of the Fisher Market Clearing algorithm that returned a normalized vector of products.
    Report
    PDF
    Comments
    Nice work, and great problem. I have a hard time interpreting the output of your program, but your write-up is fairly clear. I don't understand why ties are so problematic. Cigarette butt pizza topping? Yuck.
  • bandwidth division
    Repo
    propertydivision
    Abstract
    Our project mainly focuses on dividing the indivisible properties. This method is applied in many situation of the real life such as: divorce, inheritance, etc. We try to find the best method which will help to divide properties to certain number of players so that it is fair share and envy-free situation. After the group discussion, we decide to set up the scenario where roommates in the apartment share and use internet for specify time slot as they want and win through bet. If person A wants to have specified time slot, A needs to bet and wins the time slot. In order for person A to get the specified time slot which he desires, he needs to trade it with something (in this project, he needs to pay by cashes for others). If there is a time slot where people want to use at the same time, bandwidth will be share equally to people in the apartment. The internet bandwidth is divided based on the probabilities from the bet between people.
    Report
    PDF
    Comments
    Nice work, good analysis of what you did. How did your friends (the ones who provided the data) like your results?
  • Task assignment
    Repo
    penguin
    Abstract
    Our project involves investigating how the cake cutting algorithms we learned in class can be applied to project and task division in a work environment. A project involves many sub-tasks that come with time and monetary costs. Business and Information Technology (IT) teams may have different preferences about which tasks take priority and about how to split the tasks across several projects. Additionally, teams need to determine how to split the tasks among development groups and ensure everyone is getting a fair share of the work. Our aim is to analyze the distribution of work among projects and development groups utilizing modified One Cut Suffices (OCS) and Moving Knife (MK) cake cutting algorithms.
    Report
    PDF
    Comments
    It's great you could use real-world data, and the approach and results are interesting. The experiments are well done. It may be difficult to take priorities into account, but a Fisher-type setting might help. Nice work!
  • Fair assignment of course seats
    Repo
    fairschedule
    Abstract
    Our project was about redesigning a course selection system to fairly distribute seats in classes for students, primarily in a post-secondary setting. The system assumes that all students are granted seats in the courses they need to complete their graduation requirements and the remaining seats in all classes are then distributed to students based on the students’ submitted preferences. Our system assumes that each student gets a fixed number of points to use to assign value to each of their chosen elective classes. The system is preliminary and in order to put it into use by an actual institution would require additional levels of complexity to be built in, including schedule dependency.
    Report
    PDF
    Comments
    No abstract as required, took first paragraph. Code executes but does not produce required output. Report lacks data, experimentation, analysis. What is the connection of the report to cake cutting algorithms or ideas?
  • Inheritance case study
    Repo
    none, by agreement
    Abstract
    I conduct a case study of an inheritance problem in which the heirs designed an original fair- division procedure to allocate furniture and household items among 13 participants. I compare their procedure to Knaster’s Procedure of Sealed Bids, a First Price Auction, a Second Price Auction, and a variation of the Adjusted Winner Procedure using normative metrics of proportionality, envy-freeness, stability, equitability, and efficiency as well as positive metrics including manipulability, collusion, and financial fairness. I evaluate each mechanism in accordance with the traits most valued by the participants.
    Report
    PDF
    Comments
    A well-done study of an actual problem with real data, nicely documented. Great work!
  • Exact solutions for continuous algorithms, and an SU allocation problem.
    Repo
    shanecarr
    Abstract
    The naive implementations of continuous algorithms estimates [sic] cuts to epsilon precision in time proportional to the number of players, the complexity of their preferences, and the negative logarithm of epsilon. We document here a method of computing an exact solution to single moving-knife algorithms in time proportional to only the number of players and the complexity of their preferences.
    Report
    PDF
    Comments
    You did two projects, but the first one is not well evaluated. How much closer is your solution on average to the naive one? How much faster?

    For the second project, you dismissed cake-cutting algorithms without trying them, implemented a bang-per-buck approach, but did not compare it with anything else. The web page code for this part has something to do with pizza, quiche, etc., but is not documented in your report.

    While I believe there may be good work here, you did not follow the specification for the project which makes it difficult for me to evaluate what you did.

  • Framework for mapping problems to cake-cutting
    Repo
    cakery
    Abstract
    In observing the various algorithms proposed for dividing resources fairly among two or more parties, one question seemed to occur over and over again: how exactly does this map onto a real world problem. Ideally the algorithms would provide a framework for adapting their themselves to the various types of division in the real world, however they usually stop short at simple examples. In this paper I present cakery, a generic framework that eases the translation process of real world problems while still delivering the results each algorithm guarantees.
    Report
    PDF
    Comments
    You developed a nice body of code that I wish I could have made available to the class for this semester. The implementation using the two preference representations is nice and the analysis is well done.
  • Game theory applied to player behavior in fair division
    Repo
    jake
    Abstract
    Many of the algorithms we studied for fair division either implicitly or explicitly assumed that players would adopt certain strategies that then led to the proportional or envy free outcome of the algorithm. A number of times during the semester, however, the rationality / optimality of these strategies was called in to question, and in at least one case shown to be at least slightly suboptimal. In my project, I seek to take a few of the algorithms (Divide and Choose, Brams' algorithm, Moving Knife) we studied and represent them as normal form games, and then solve them using a game theoretic approach that does not make assumptions about players' strategies, rather assuming only that players behave rationally. I demonstrate that such a strategy agnostic version of divide and choose is slightly strongly proportional even with open preferences whenever at least one strongly proportional cut exists. I also demonstrate by analyzing a strategy agnostic version of Brams' algorithm that the original version of Brams' algorithm cannot guarantee proportionality if players know each others' preferences.
    Report
    PDF
    Comments
    There appear to be some nice results here but I don't have time before turning in grades to verify them. I would have preferred a smaller focus with more experimentation on data (random or not). But this does open up interesting ideas for future work and experimentation.

    I will read the theorems and proofs over break and revise this write-up then.

  • Repo
    cooper
    Abstract
    We wanted to approach the problem of how to fairly give people internet bandwidth in the times they desire it most. More specifically given peoples preferences over a 24 hr interval (valued per hour) we attempted to find a horizontal “slice” of the bandwidth that reflected a “fair” (proportional) division.
    Report
    PDF
    Comments
    Interesting project, well documented. Nice experimental study and validation.

    The plots on page 6 are for the performance of your algorithm. By what method did you fit your data to the quadratic shown there?

    The last player gets so much more bandwidth than the others, so this could be made fair by randomizing who goes last, or you could redistribute the last player's extra bandwidth to the others perhaps?

  • Dividing chores fairly
    Repo
    sachertorte
    Abstract
    Dividing chores household chores is a fairly common problem. Frequently, people complain that they have to do more work than other members of the household. Unlike some situations, monetary compensation, such as in Adjusted Winner or Knaster’s Sealed Bids, is not really appropriate since chores don’t really have a well-defined value (Cytron, Lectures 14 and 16). Since chores are repeated every week, my algorithm adjusts future assignments to compensate for the fact that an equitable assignment is not necessarily possible. Through this adjustment it is possible to make the allocation equitable at least in the long term. Furthermore, the algorithm is designed to try to find a proportional solution. Through testing on randomly generated data and a realistic use scenario, the algorithm is shown to be reasonably successful at making repeated fair allocations.
    Report
    PDF
    Comments
    Nice job! Are the data on page 7 (Table 5) from real people? Thank you for documenting how to run your code to obtain the data you show. You say it's unfortunate that an equitable solution was found, but that's not so lamentable. Also if people tire of doing the same chore week after week, their preferences can change which makes re-running your algorithm a good idea.
  • Assigning chores to 3 or more people
    Repo
    veliuscake
    Abstract
    My project is about assigning household chores to 3 or more people using the Last Diminisher algorithm.
    Report
    PDF
    Comments
    The project lacks a one paragraph abstract as required. Interesting project! On page 6, a low sum means less work, right? I like the honesty of your conclusions. Also your observation about inconsistent post-evaluation shows how difficult it can be to apply these algorithms in real life. The abstract chore may have a different value then the chore once it is really assigned to a person. Also, a given chore's value may change once it is assigned along with other chores to the same person.

    I didn't see that you measured envy but if you have any data on that and want to add it, I can repost your report.