Efficiency of Truthful and Symmetric Mechanisms in One-sided Matching

Adamczyk, Marek; Sankowski, Piotr; Zhang, Qiang
We study the efficiency (in terms of social welfare) of truthful and symmetric mechanisms in one-sided matching problems with \{$\backslash$em dichotomous preferences\} and \{$\backslash$em normalized von Neumann-Morgenstern preferences\}. We are particularly interested in the well-known \{$\backslash$em Random Serial Dictatorship\} mechanism. For dichotomous preferences, we first show that truthful, symmetric and optimal mechanisms exist if intractable mechanisms are allowed. We then provide a connection to online bipartite matching. Using this connection, it is possible to design truthful, symmetric and tractable mechanisms that extract \$0.69\$ of the maximum social welfare, which works under assumption that agents are not adversarial. Without this assumption, we show that Random Serial Dictatorship always returns an assignment in which the expected social welfare is at least a third of the maximum social welfare. For normalized von Neumann-Morgenstern preferences, we show that Random Serial Dictatorship always returns an assignment in which the expected social welfare is at least \$\backslash frac\{1\}\{e\}\backslash frac\{\backslash nu(\backslash opt)\^{}2\}\{n\}\$, where \$\backslash nu(\backslash opt)\$ is the maximum social welfare and \$n\$ is the number of both agents and items. On the hardness side, we show that no truthful mechanism can achieve a social welfare better than \$\backslash frac\{\backslash nu(\backslash opt)\^{}2\}\{n\}\$.
Research areas:
Year:
2014
Type of Publication:
Article
Journal:
Lecture Notes in Computer Science
Volume:
8768
Pages:
13-24
ISSN:
1611-3349
Hits: 5086

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information