Mixed strategies in combinatorial agency

DOI10.1613/JAIR.2961MaRDI QIDQ3579358zbMATH OpenOpenAlexFDO

Authors Moshe Babaioff, Michal Feldman, Noam Nisan

Publication date 6 August 2010

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3837

zbMATH Keywords

Nash equilibriumcommunication networks

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42) Network design and communication in computer systems (68M10)

Abstract: In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic combinatorial agency model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principals gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.

Recommendations

• Combinatorial agency
• Computing optimal contracts in combinatorial agencies
• Free-riding and free-labor in combinatorial agency
• Effort Games and the Price of Myopia
• Combinatorial agency of threshold functions

Cited in

(15)

• Designing menus of contracts efficiently: the power of randomization
• Combinatorial agency
• Algorithms and mechanisms for procuring services with uncertain durations using redundancy
• On the Existence of Low-Rank Explanations for Mixed Strategy Behavior
• scientific article; zbMATH DE number 2209529 (Why is no real title available?)
• Free-riding and free-labor in combinatorial agency
• Computing optimal contracts in combinatorial agencies
• Combinatorial agency of threshold functions
• Verifiable crowd computing: coping with bounded rationality
• Learning approximately optimal contracts
• Fault tolerant mechanism design
• Crowd computing as a cooperation problem: An evolutionary approach
• Multi-agent contracts
• Learning approximately optimal contracts
• Bayesian agency: linear versus tractable contracts

This page was built for publication: Mixed strategies in combinatorial agency

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579358)