Commitment and extortion

ABSTRACT

Making commitments, e.g., through promises and threats, enables a player to exploit the strengths of his own strategic position as well as the weaknesses of that of his opponents. Which commitments a player can make with credibility depends on the circumstances. In some, a player can only commit to the performance of an action, in others, he can commit himself conditionally on the actions of the other players. Some situations even allow for commitments on commitments or for commitments to randomized actions. We explore the formal properties of these types of (conditional) commitment and their interrelationships. So as to preclude inconsistencies among conditional commitments, we assume an order in which the players make their commitments. Central to our analyses is the notion of an extortion, which we define, for a given order of the players, as a profile that contains, for each player, an optimal commitment given the commitments of the players that committed earlier. On this basis, we investigate for different commitment types whether it is advantageous to commit earlier rather than later, and how the outcomes obtained through extortions relate to backward induction and Pareto efficiency.

References

1. A. K. Chopra and M. Singh. Contextualizing commitment protocols. In Proceedings of the 5th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1345--1352. ACM Press, 2006.
2. V. Conitzer and T. Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce (ACM-EC), pages 82--90. ACM Press, 2006.
3. J. C. Harsanyi. A simplified bargaining model for the n-person cooperative game. International Economic Review, 4(2):194--220, 1963.
4. R. D. Luce and H. Raiffa. Games and Decisions: Introduction and Critical Survey. Wiley, 1957.
5. J. Nash. Two-person cooperative games. Econometrica, 21:128--140, 1953.
6. M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
7. D. Samet. How to commit to cooperation, 2005. Invited talk at the 4th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
8. T. Sandholm and V. Lesser. Leveled-commitment contracting. A backtracking instrument for multiagent systems. AI Magazine, 23(3):89--100, 2002.
9. T. C. Schelling. The Strategy of Conflict. Harvard University Press, 1960.
10. R. Selten. Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit. Zeitschrift für die gesamte Staatswissenschaft, 121:301--324, 1965.
11. M. P. Singh. An ontology for commitments in multiagent systems: Toward a unification of normative concepts. Artificial Intelligence and Law, 7(1):97--113, 1999.
12. M. Tennenholtz. Program equilibrium. Games and Economic Behavior, 49:363--373, 2004.
13. E. van Damme and S. Hurkens. Commitment robust equilibria and endogenous timing. Games and Economic Behavior, 15:290--311, 1996.
14. J. von Neumann and O. Morgenstern. The Theory of Games and Economic Behavior. Princeton University Press, 1944.
15. H. von Stackelberg. Marktform und Gleichgewicht. Julius Springer Verlag, 1934.
16. B. von Stengel and S. Zamir. Leadership with commitment to mixed strategies. CDAM Research Report LSE-CDAM-2004-01, London School of Economics, 2003.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence