Strategy-proof truthfulness in mechanism design with interdependent valuations

Abstract

Social choice problems arise frequently in our daily life, where each agent has its own private information (i.e., a type), and all involved agents must agree on one particular outcome in spite of their conflicting preferences over the possible outcomes of the problem. Mechanism design is a general methodology for solving social choice problems by designing mechanisms where agents will be truthful (i.e., report their true types) through eliminating any incentives agents may have from strategic misreporting. Classical mechanism design assumes that an agent's value of any outcome depends only on its type. However in many situations, an agent's value of an outcome depends on the true types of other agents in addition to its own type. In such problems where agents have interdependent valuations, only efficient mechanisms that achieve truthful in ex-post incentive compatibility (i.e., an agent reports its true type only if other agents are rational and reporting truthfully) exist. Efficient strategy-proof mechanisms that achieve the strongest and most preferable form of truthfulness (i.e., an agent reports its true type even if other agents are strategically misreporting their types and/or behaving irrationally) have not been proposed yet for any domain when valuations are interdependent, and when such mechanisms are possible is the research question of this thesis. Unlike classical mechanism design, strategy-proof mechanisms for interdependent valuations can only be provided for a particular domain, because the interdependencies between the agents' valuations vary depending on the problem, and this directly affects how strategy-proofness is established. In this thesis, we focus our attention on the interdependent task allocation and prediction markets problems, and we provide possibility and impossibility results regarding the design of efficient and strategy-proof mechanisms along with other desirable properties. First, we study the interdependent task allocation (ITA) problem where a set of tasks with predefined dependencies is to be assigned to self-interested agents based on what they report about their privately known capabilities and costs. We consider here the possibility that tasks may fail during their executions, which imposes interdependencies between the agents' valuations. We show that efficient and strategy-proof mechanisms exist for a class of ITA problems where an agent's privately known cost for performing a task is factorized into a privately known duration in which the agent can perform that task and a publicly known cost per time unit. For ITA problems where agents have private costs, we show that it is impossible to achieve strategy-proofness by using a single allocation round, and then we present reassignment-based mechanisms that achieve strategy-proofness by reassigning failing tasks. For each ITA model - either with private durations or costs, we investigate the assumptions under which the mechanism operates without outside subsidy and makes a profit. Second, we study prediction markets, which are often used to aggregate the agents' beliefs concerning a future event. Participating agents are paid based on the accuracy of their reports when compared to the realized outcome. If agents find incentives to hide, postpone reporting, and/or strategically misreport their beliefs, then the accuracy of such aggregated information may be in question. We present a belief model where agents can influence each other beliefs, and hence, influence each other reports. Given our belief model, we show that current prediction markets (e.g., market scoring rules, cost function based markets) assume that an agent will report its belief truthfully under restrictive assumptions, i.e., agents are reporting in a predefined order, each agent can participate only once, and each agent is assuming that other agents influence its belief in a positive way (i.e., increase its expected value). We present novel strategy-proof prediction markets where an agent will report its belief truthfully while dismissing all the previous assumptions. However, the marker maker needs to make additional payments compared to already existing markets. We show that our proposed markets achieve strategy-proofness while maintaining the minimum possible worst-case loss for the market maker. Show more