  We study the problem of mechanism design for allocating a set of indivisible
items among agents with private preferences on items. We are interested in such
a mechanism that is strategyproof (where agents' best strategy is to report
their true preferences) and is expected to ensure fairness and efficiency to a
certain degree. We first present an impossibility result that a deterministic
mechanism does not exist that is strategyproof, fair and efficient for
allocating indivisible chores. We then utilize randomness to overcome the
strong impossibility. For allocating indivisible chores, we propose a
randomized mechanism that is strategyproof in expectation as well as ex-ante
and ex-post (best of both worlds) fair and efficient. For allocating mixed
items, where an item can be a good (i.e., with a positive utility) for one
agent but a chore (i.e., a with negative utility) for another, we propose a
randomized mechanism that is strategyproof in expectation with best of both
worlds fairness and efficiency when there are two agents.
