6
$\begingroup$

Background

I have (rather recently) dabbled in game theory. I need it to design an algorithm to share chores. Obviously this is a kind of cake-cutting problem. So far, I have fought my way through An Introduction to Game Theory by Martin J. Osborne, but I'm still feel far from comfortable with it. I have a solid foundation in calculus, know how to deal with ODEs and PDEs (but I try to avoid them if I can. :)) And yes, I'm not a mathematician, I"m an engineer.

Problem

The 'cake' needs to be split among $k\geq 2$ players. The twist is that valuation of the players is not finitely additive, it has a maximum i.e. there is an amount of cake that they will find more valuable than a larger amount (kind of being afraid of overeating $-$ or being on a diet).

Question

Does anybody know of a starting point to how tackle this? (Efficient or equitable solutions would be the most interesting.) All the resources I found, treat only the finitely additive case. I would also be grateful for any freely downloadable material.

EDIT: I'm looking for efficient and/or equitable ways of splitting the cake, regardless of the protocol to achieve it. If there also is a protocol for that, the better for me. :)

  • 0
    Just because it's game theory doesn't mean that you should keep us guessing what the question is :-) Are you looking for a particular protocol for cutting the cake? Or do you have a particular protocol in mind and are looking for optimal/equilibrium strategies for the eaters under that protocol? Or are you just looking for efficient or equitable divisions of the cake, independent of protocols for achieving them?2012-10-14
  • 0
    @joriki: I edited the question. Hope that ends the guessing game. `:)`2012-10-14
  • 0
    You haven't specified a valuation for the eaters -- are you just generally interested in methods for finding efficient and/or equitable divisions that work if the valuations aren't additive, or do you want to find an efficient and/or equitable division for a particular valuation?2012-10-14
  • 0
    @joriki: The valuation is random, but known, subject to this non-additivity condition (i.e. has 1 maximum).2012-10-14
  • 0
    You may have better luck describing it as a "compensation" problem, rather than cake cutting. For discrete problems (finitely many chores) the math involved is very engineery, some Lagrange multipliers and stuff. I believe I've read Econ papers where special sorts of non-additive utility functions were considered.2012-10-14
  • 0
    @JackSchmidt: That's very likely: there are compensation schemes, where extra time is not paid proportionally to discourage employees from doing more than a desired limit (e.g. avoid overproduction). Do you have any links? That could be an answer and I'd certainly upvote it!2012-10-14
  • 0
    @CountZero: done. Definitely don't accept my answer, as it just (1) recommends a (cheap, good) book and an easy technique, (2) confirms what you already know, and (3) gives you one more search term "unimodal" to help out.2012-10-14

4 Answers 4