1st International Conference on Game Theory for Networks

Research Article

Combinatorial agency with audits

  • @INPROCEEDINGS{10.1109/GAMENETS.2009.5137423,
        author={Raphael Eidenbenz and Stefan  Schmid},
        title={Combinatorial agency with audits},
        proceedings={1st International Conference on Game Theory for Networks},
  • Raphael Eidenbenz
    Stefan Schmid
    Year: 2009
    Combinatorial agency with audits
    DOI: 10.1109/GAMENETS.2009.5137423
Raphael Eidenbenz1,*, Stefan Schmid2,*
  • 1: Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland
  • 2: Chair for Efficient Algorithms Computer Science Department, TU Munich, Germany
*Contact email: eidenbenz@tik.ee.ethz.ch, schmiste@in.tum.de


This paper studies the question of how to overcome inefficiencies due to hidden actions in a rational milieu, such as a grid computing system with open clientele. We consider the so-called principal-agent model known from economic theory, where the members (or agents) of a distributed system collaborate in complex ways. We adopt the perspective of the principal and investigate auditing mechanisms that incentivize participants to contribute more to a common project. As conducting audits might be costly, the principal must balance the tradeoff between low auditing costs and the level of incentives offered to the participants to exert high effort. We present optimal solutions for this optimization problem in scenarios, where the project success either depends on all, on any or on the majority of the participants succeeding in their subtask. In the first case, we further find that with an increasing principal valuation, there is exactly one transition point where the optimal choices for achieving the maximal principal utility switch. Compared to a combinatorial agency without the leverage of audits, this transition occurs earlier.