Algorithmic mechanism design | EPFL Graph Search

Algorithmic mechanism design (AMD) lies at the intersection of economic game theory, optimization, and computer science. The prototypical problem in mechanism design is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social welfare maximization. Algorithmic mechanism design differs from classical economic mechanism design in several respects. It typically employs the analytic tools of theoretical computer science, such as worst case analysis and approximation ratios, in contrast to classical mechanism design in economics which often makes distributional assumptions about the agents. It also considers computational constraints to be of central importance: mechanisms that cannot be efficiently implemented in polynomial time are not considered to be viable solutions to a mechanism design problem. This often, for examp

Challenges in Algorithmic Mechanism Design

Paul David Dütting

This thesis addresses three challenges in algorithmic mechanism design, which seeks to devise computationally efficient mechanisms consisting of an outcome rule and a payment rule that implement desirable outcomes in strategic equilibrium. The first challenge that we address is the design of expressive mechanisms, i.e., mechanisms that allow the participating agents to express rich preferences. We focus on multi-item auc- tions with unit demand. For this setting we present the most expressive polynomial-time mechanism known to date that is incentive compatible for non-degenerate inputs. This mech- anism can, e.g., be used in ad auctions with per-click and per-impression valuations and it can handle a large variety of soft and hard budget constraints. The second challenge that we consider is the analysis of simplicity-expressiveness tradeoffs. We develop tools for analyzing how simplification, i.e., restricting the message space, affects the set of equilibria of a mechanism. We use these tools to analyze two representative settings, sponsored search auctions and combinatorial auctions. We find that in both cases simplifica- tion can be beneficial, either by ruling out undesirable equilibria or by promoting desirable ones. In the case of sponsored search auctions our analysis leads to a strong argument in favor of the mechanism that is used by all major search engines. Finally, and this is the third challenge, we consider the design of approximately strategyproof mechanisms. We present a framework that exploits a remarkably close connection between discriminant-based classification and the design of strategyproof mechanisms. For a given algorithmically specified outcome rule our framework finds a payment rule that makes the resulting mechanism maximally strategyproof. We support our theoretical findings by applying our framework to a multi-minded combinatorial auction with a greedy outcome rule and to an assignment problem with egalitarian outcome rule.

EPFL2013

M-DPOP: Faithful distributed implementation of efficient social choice problems

Boi Faltings, David C. Parkes, Adrian Petcu

In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information-revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authority that we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i's payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents. On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank.

2008

EBSD coupled to SEM in situ annealing for assessing recrystallization and grain growth mechanisms in pure tantalum

Roland Logé

An in situ annealing stage has been developed in-house and integrated in the chamber of a Scanning Electron Microscope equipped with an Electron BackScattered Diffraction system. Based on the Joule effect, this device can reach the temperature of 1200°C at heating rates up to 100°C/s, avoiding microstructural evolutions during heating. A high-purity tantalum deformed sample has been annealed at variable temperature in the range 750°C-1030°C, and classical mechanisms of microstructural evolutions such as recrystallization and grain coarsening phenomena have been observed. Quantitative measurements of grain growth rates provide an estimate of the mean grain boundary mobility, which is consistent with the value estimated from physical parameters reported for that material. In situ annealing therefore appears to be suited for complementing bulk measurements at relatively high temperatures, in the context of recrystallization and grain growth in such a single-phase material. © 2013 The Authors Journal of Microscopy © 2013 Royal Microscopical Society.