Reducing Interaction Cost: A Mechanism Deisgn Approach

[摘要] In this thesis we study the problem of requiring self-interestedagents needto interact with some centralized mechanism wherethis interaction is costly. To improve their utility, agents may choose to interactwith emph{neighbours} in order to coordinate their actions,potentially resulting in savings with respect to total interactioncosts for all involved.We highlight the issues that arise in sucha setting for the mechanism as well as for the agents.We use a mechanism-design approach to study this problem and present a model for self-interested agents to form groups with neighbours in order toreduce the total interaction cost.Our model focuses on twoaspects: reward-distribution and cost-sharing.We look at twoscenarios for reward-distribution mechanisms and proposed acore-stable payoff as well as a fair payoff mechanism. We then propose a cost-sharing mechanism that agents can use to coordinate and reducetheir interaction costs.We prove this mechanism to be incentive-compatible,cost-recovery and fair. We also discuss how agents might form groups in order to save on cost.We study how our final outcome (the total percentage of savings as a group) depends on the agents;; interaction topology andanalyze different topologies.In addition we carry out experimentswhich further validate our proposal.

[发布机构] University of Waterloo

[关键词] Computer Science