Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents - Agent-Mediated Electronic Commerce - page 84

We have chosen the self-interested network flow domain, because in this case
we were able to find a mechanism that was tractable in its computational prop-
erties, and also had good results in the sense of being budget-balanced. This
domain demonstrates that by using a very simple payment scheme we can cre-
ate a significant gap between the amount of work the mechanism performs (in
this case a simple poly-time algorithm) and the amount of work an agent is re-
quired to perform in order to find a beneficial manipulation (in this case solving
an NP-hard problem). We believe further research can find domains in which
the mechanism is required to perform harder work (e.g., solving an NP-hard
problem by approximation), and manipulations are completely intractable. It
may be possible to achieve budget-balance while retaining a stronger notion of
strategy-resistance, even in this domain. Also, it may be possible to find other
valuable tradeoffs in other domains. It remains an open problem to characterize
the domains in which using computational complexity in this way is possible, and
to find domains in which a stronger sense of strategy-resistance can be achieved.
References
1. Green, J., Laffont, J.J.: Characterization of satisfactory mechanisms for the revela-
tion of preferences for public goods. Econometrica 45 (2) (1977) 427-38
2. Hurwicz, L.: On the existence of allocation systems whose manipulative Nash equi-
libria are pareto-optimal. In: 3rd World Congress of the Econometric Society (Un-
published). (1975)
3. Conitzer, V., Sandholm, T.: Universal voting protocol tweaks to make manipulation
hard. In: Proceedings of the Eighteenth International Joint Conference on Artificial
Intelligence (IJCAI), Acapulco, Mexico (2003) 781-788
4. Bartholdi, J.J.: The computational diculty of manipulating an election. Social
Choice and Welfare 6 (3) (1989) 227-241
5. Conitzer, V., Sandholm, T.: Computing shapley values, manipulating value division
schemes, and checking core membership in multi-issue domains. In: Proceedings of
the 19th National Conference on Artificial Intelligence (AAAI), San Jose, California,
USA (2004) 219-225
6. Shapley, L.S.: A value for n-person games. Contributions to the Theory of Games
(1953) 31-40
7. Sandholm, T., Lesser, V.R.: Coalitions among computationally bounded agents.
Artificial Intelligence 94 (1-2) (1997) 99-137
8. Sanghvi, S., Parkes, D.C.: Hard-to-manipulate combinatorial auctions. Technical
report, Harvard University (2004)
9. Lavi, R., Mu'alem, A., Nisan, N.: Towards a characterization of truthful combi-
natorial auctions (extended abstract). In: Proceedings of the 44th Annual IEEE
Symposium on Foundations of Computer Science (FOCS). (2003)