ﻻ يوجد ملخص باللغة العربية
We provide a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces. The key technical barrier preventing exact incentive compatibility in prior black-box reductions is that repairing violations of incentive constraints requires understanding the distribution of the mechanisms output, which is typically #P-hard to compute. Reductions that instead estimate the output distribution by sampling inevitably suffer from sampling error, which typically precludes exact incentive compatibility. We overcome this barrier by employing and generalizing the computational model in the literature on $textit{Bernoulli factories}$. In a Bernoulli factory problem, one is given a function mapping the bias of an input coin to that of an output coin, and the challenge is to efficiently simulate the output coin given only sample access to the input coin. This is the key ingredient in designing an incentive compatible mechanism for bipartite matching, which can be used to make the approximately incentive compatible reduction of Hartline et al. (2015) exactly incentive compatible.
The study of approximate mechanism design for facility location problems has been in the center of research at the intersection of artificial intelligence and economics for the last decades, largely due to its practical importance in various domains,
Game theory is often used as a tool to analyze decentralized systems and their properties, in particular, blockchains. In this note, we take the opposite view. We argue that blockchains can and should be used to implement economic mechanisms because
We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function $g$ from the $n$-dimensional hypercube to the bounded interval $[-1,1]$, and
We study Bayesian automated mechanism design in unstructured dynamic environments, where a principal repeatedly interacts with an agent, and takes actions based on the strategic agents report of the current state of the world. Both the principal and
Complex networks tend to display communities which are groups of nodes cohesively connected among themselves in one group and sparsely connected to the remainder of the network. Detecting such communities is an important computational problem, since