14

This isn't a complete answer, but it's an incomplete one. Some background and related lit for those who aren't familiar -- A nice property would be envy-freeness, in which no player would like to trade with another after the mechanism is complete. Unfortunately, for indivisible goods and no money we can see that this is impossible (there might be one good ...


9

Mechanism design is basically just algorithm design, where you don't control the inputs: instead, you assume that the inputs are controlled by different agents, who each have their own set of feasible actions, and their own utility function over outcomes, and are acting to maximize their own utility (and not yours, as the mechanism designer). So you are ...


7

Much of the white elephant gift exchange experience is also controlled by random selection. A popular variation includes the rule that the first picks last, but that is not always included in the rule. This takes the unfair advantage of being randomly selected first out of the equation. Another rule requires that there are no direct "steal-backs" in the ...


2

I think I've gotten part of the answer. The above statement actually says that for any truthful mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for truthful mechanisms only, then by the Myerson's Lemma the payment rule must be in that form.


2

What we did this year was restrict the people you could steal from so that the later players didn't have as large an advantage. So the $n$ players sat in a circle and they could only steal along edges of a graph $G$. Picking $G$ to be reasonably expansive is enough to "mix" the gifts; the simple expander graph we used is to assign players 1 through $n$, and ...


1

the calculation of $\mathcal{SW}_{-D_i}$ and $\mathcal{SW}_{-C_i^\mathcal{K}}$ is incorrect. There are still $\mathcal{K}$ items to be allocated in both allocations, so for node $D$, the first is 20+19+17+11+10 and the second is 20+19+17+14+11. So D's payment is 10. p.s. there is a typo in one of the constraints for the two allocations, which is updated in ...


1

Great answer. I just want to add that the problem you posed seems to require a solution like Nash equilibrium or a Evolutionary stable strategy. That does not typically come under mechanism design. Its more basic game theory where everything (the game) is well defined and you find the equilibrium outcome. Mechanism design moves in the other way. Given you ...


Only top voted, non community-wiki answers of a minimum length are eligible