Project Ideas

  1. Practical voting applications. Consider a problem where you think voting can give a good solution. For example, deciding where to go for dinner. Create a voting website application or smartphone application implementing your solution.
  2. Empirical study of manipulating voting rules. We have seen several greedy algorithms for finding manipulations in voting. Pick a voting rule and design new manipulation algorithms. See "An Empirical Study of Borda Manipulation."
  3. Strategy-proof voting rules for restricted domains. While voting are generally manipulable with unrestricted preference profiles, voting rules can be strategy-proof on restricted domains. Perform a survey of these domains.
  4. Voting and mechanism design. The Stackelberg voting game we discussed is superficially similar to a random serial dictatorship, the unique strategy-proof mechanism in many settings. Compare these mechanisms, when are they the same, when different? Does one offer more possibilities than the other?
  5. Paper reviews and voting. Deciding which papers to publish in a peer-reviewed journal or conference is a difficult decision. No single person reads all the papers and additional constraints, like sufficient variety, may be imposed. Suggest a voting model for this domain.
  6. Ranking and sybils. Online review systems and user-generated sites often suffer from sybils. How can sybils distort these systems?
  7. Contiguous cake cutting. In cake cutting it's often assumed a person is happy with many pieces of the cake, but usually everyone receives one piece. How do cake cutting results change when we assume a person can only receive one contiguous piece?
  8. Efficiency and truthfulness in cake cutting. There are few truthful cake cutting algorithms. Can you quantify how much efficiency must be given up to obtain truthfulness?
  9. Allocation of computational resources. Cake cutting is often described as a model for the allocation of a resource like time on a computing cluster. Pick a resource allocation problem and propose an a new allocation mechanism. Evaluate your result either analytically or experimentally.
  10. The rent partition problem. Suppose you and some friends rent a heterogenous apartment and need to decide how to split the rent. Survey the existing literature on this problem and propose a new solution.
  11. Pie cutting. Pies are cut differently from cakes. How and why is cutting a pie different from cutting a cake? What's a problem better modeled by pie cutting instead of cake cutting?
  12. Preferences and crowdsourcing. Design and run an Amazon Mechanical Turk experiment to efficiently learn the preferences of the crowd.