2026-08-17T10:29:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:205 2024-03-06T11:06:05Z ddc:004 open_access

A Network Approach to Bayes-Nash Incentive Compatible Mechanisms Müller, Rudolf Perea, Andres Wolf, Sascha compact representation of games congestion games local-effect games action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio This paper provides a characterization of Bayes-Nash incentive compatible mechanisms in settings where agents have one-dimensional or multi-dimensional types, quasi-linear utility functions and interdependent valuations. The characterization is derived in terms of conditions for the underlying allocation function. We do this by making a link to network theory and building complete directed graphs for agents type spaces. We show that an allocation rule is Bayes-Nash incentive compatible if and only if these graphs have no negative, finite cycles. In the case of one-dimensional types and given certain properties for agents valuation functions, we show that this condition reduces to the absence of negative 2-cycles. In the case of multi-dimensional types and given a linearity requirement on the valuation functions, we show that this condition reduces to the absence of negative 2-cycles and an integratebility condition on the valuation functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rudolf Müller and Andres Perea and Sascha Wolf 2005 Is Part Of Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.05011.4 urn:nbn:de:0030-drops-2056 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.4 eng https://creativecommons.org/licenses/by/4.0/legalcode