Project Guidelines and Due Dates
(See note on the front page about exposition papers. Experimental papers can be done in pairs, and in groups of three by approval. Theory papers can be done in pairs with approval.)
Wednesday 11/4 Project Proposals due in class (2 pages, max.)
Monday 12/7 Brief Project Presentations 1-2:30, MD 221
Friday 12/11 Projects due at noon to Ann Marie King in MD 133, and by email to shailij@eecs (if in electronic form).
For project proposals, students must include the following four sections for non-exposition papers:
- Describe at a high level what you will do and how does it relate to the material covered in class? Citations to related work and a description about how your proposed work relates.
- Define the exact problem you will be studying as carefully and completely as you can. E.g. if a theory problem - give a concrete problem definition. If an experimental problem, what code will you write, what simulations will you run, and what graphs will you generate?
- State the concrete first two steps in moving forward with your project. What could you start tomorrow?
- What is unclear to you? What can we help with? (E.g., did you find a related literature, do you need help with scoping the work, is there something that you're confused about?)
For an exposition paper, what are the two papers you will study and which two technical results in those papers will you describe? How are the papers related to the class, and to each other? Why do you find the papers interesting?
Project Ideas
- Exposition paper on theoretical developments post Milgrom-Hatfield on the generalized matching problem
- Exposition paper on computational aspects of matching problems.
- Experimental study of alternate HBS course allocation mechanisms.
- Combinatorial house markets (e.g., combinatorial TTC algorithms).
- Experimental study of the ex ante efficiency of "futures" market vs. constant spot favor existing market (Kurino's paper).
- Dynamic house allocation with trading between agents and time varying preferences.
- Dynamic house allocation with weaker "acceptability" constraints.
- Development of effective bidding languages for preferences for generalized matching or dynamic house problems.
- Scrip systems: Develop a model of scrip systems in which the "demand side" model is more nuanced, e.g. with non-stationarities and with some types preferring some types of workers over others.
- Scrip systems: Develop alternate methods to discouage hoarding, e.g. through mandating a certain level of work by all agents.
- Scrip systems: Consider strategies in which agents seek to affect the monetary sypply, and thereby manipulate the system.
- Scrip systems: Develop and study a set of behavioral strategies that are applicable to real-world scrip systems and/or develop applications of the scrip system model.
- Scrip systems: Extend the scrip system model to one in which there are different types of work and agents can express value for different kinds of work.
- Scrip systems: Study the wealth distribution effects of the scrip system equilibrium in terms of how it depends on attributes of agent types (e.g., do agents twice as preferred have more or less money on average?)
- Sybilproofness vs. costly sybils. Can you construct and analyze protocols in a model of costly sybils rather than a model of sybilproofness?
- In class we discussed the "sybilproof" concept in a number of different contexts. Survey the literature and provide a detailed critique of the literature. What assumptions are unrealistic? What are the directions for future work in each area?
- The discussion of distributed accounting for dynamic transaction systems falls under the category of a distributed system in which we need users to track the quality and quantity of goods and services exchanged. Formulate this as a dynamic mechanism design problem.
- Pick an online system (Turk, p2p networks, eBay, Amazon, etc.) and critique the reputation and recommendation system used. Point out some inefficiency in the system and suggest how this can be remedied through appropriately designed incentives.
- Provide a model capturing how trust networks grow over time, coupled with simulations. Does this shine light on the informativeness limitations of something like shortest path vs. page rank?
- What happens to the theory of kidney exchanges when there is preference for small cycles, since small cycles might be more likely to have successful exchanges. Can a variation of the TTCC algorithm be used?
- In class it was mentioned that list exchanges put O recipients on the list at a disadvantage. Can you suggest alternate ways of dealing with list exchanges that do not put O recipients at a disadvantage.
- Can you implement a scrip system between hospitals to encourage them to truthfully report their entire donor-patient set?
- The Aperjis et al. paper has a relatively "snapshot" view of a dynamic system. Can we bring the model closer to a dynamic model and then think about analyzing efficiency in such a model?
- The model of Aperjis et al. also seems to assume that the demand for a file is constant, however, in practice this is not often the case. Incorporate a reaonsable model of demand into the model of Aperjis et al.
- Give a very thorough critique of PACE. We already mentioned a number of ideas in class. Can you continue this critique?
- The model of Aperjis et al. has no consideration for malicious users even though this can be a problem in practice. Can you modify the model of Aperjis et. al. to consider attacks by malicious users?
- Analyze the GAG of an online kidney exchange model (perhaps limiting the life of a kidney-donor pair to two periods) by leveraging the insights in the work discussed from Chapter 3 of the survey about the effect of moving from 2 to 3 to cycle lengths on the number of trades.
- The Awasthi and Sandholm paper works with a rather simple model. Can you incorporate more richness into their model and perform a similar style analysis. Some possible extensions include: prioritization of cycles via weights, including type dependency and/or history dependency, incorporate a disutility of waiting, incorporate a wait list, etc.
- In class we mentioned critiques of the "Regrets" algorithm to the online kidney problem. Take these considerations into account as you reapply "Regrets" to the online kidney problem.
- Study dynamic auction mechanisms under alternate models of temporal preferences, for example a discounting model.
- Develop analogs to the "self-correction" idea for other online algorithms, such as Regrets or Expectation.