We revisit the problem of designing optimal, individually rational matching mechanisms (in
a general sense, allowing for cycles in directed graphs), where each player — who is associated
with a subset of vertices — matches as many of his own vertices when he opts into the matching
mechanism as when he opts out. We offer a new perspective on this problem by considering an
arbitrary graph, but assuming that vertices are associated with players at random. Our main
result asserts that, under certain conditions, any fixed optimal matching is likely to be individually
rational up to lowerorder terms. We also show that a simple and practical mechanism is
(fully) individually rational, and likely to be optimal up to lowerorder terms. We discuss the
implications of our results for market design in general, and kidney exchange in particular.
more »
« less
IncentiveCompatible Kidney Exchange in a Slightly SemiRandom Model
Motivated by kidney exchange, we study the following mechanismdesign problem: On a directed graph (of transplant compatibilities among patientdonor pairs), the mechanism must select a simple path (a chain of transplantations) starting at a distinguished vertex (an altruistic donor) such that the total length of this path is as large as possible (a maximum number of patients receive a kidney). However, the mechanism does not have direct access to the graph. Instead, the vertices are partitioned over multiple players (hospitals), and each player reports a subset of her vertices to the mechanism. In particular, a player may strategically omit vertices to increase how many of her vertices lie on the path returned by the mechanism. Our objective is to find mechanisms that limit incentives for such manipulation while producing long paths. Unfortunately, in worstcase instances, competing with the overall longest path is impossible while incentivizing (approximate) truthfulness, i.e., requiring that hiding nodes cannot increase a player's utility by more than a factor of 1 + o(1). We therefore adopt a semirandom model where o(n) random edges are added to worstcase instances. While it remains impossible for truthful mechanisms to compete with the overall longest path, we give a truthful mechanism that competes with a weaker but nontrivial benchmark: the length of any path whose subpaths within each player have a minimum average length. In fact, our mechanism satisfies even a stronger notion of truthfulness, which we call matchingtime incentive compatibility. This notion of truthfulness requires that each player not only reports her nodes truthfully but also does not stop the returned path at any of her nodes in order to divert it to a continuation inside her own subgraph.
more »
« less
 Award ID(s):
 1733556
 NSFPAR ID:
 10288576
 Date Published:
 Journal Name:
 ACM Conference on Economics and Computation
 Volume:
 21
 Page Range / eLocation ID:
 138 to 156
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the problem of distributed corruption detection in networks. In this model each node of a directed graph is either truthful or corrupt. Each node reports the type (truthful or corrupt) of each of its outneighbors. If it is truthful, it reports the truth, whereas if it is corrupt, it reports adversarially. This model, first considered by Preparata, Metze and Chien in 1967, motivated by the desire to identify the faulty components of a digital system by having the other components checking them, became known as the PMC model. The main known results for this model characterize networks in which all corrupt (that is, faulty) nodes can be identified, when there is a known upper bound on their number. We are interested in networks in which a large fraction of the nodes can be classified. It is known that in the PMC model, in order to identify all corrupt nodes when their number is t, all indegrees have to be at least t. In contrast, we show that in d regulargraphs with strong expansion properties, a 1  O(1/d) fraction of the corrupt nodes, and a 1  O(1/d) fraction of the truthful nodes can be identified, whenever there is a majority of truthful nodes. We also observe that if the graph is very far from being a good expander, namely, if the deletion of a small set of nodes splits the graph into small components, then no corruption detection is possible even if most of the nodes are truthful. Finally we discuss the algorithmic aspects and the computational hardness of the problem.more » « less

Peer prediction aims to incentivize truthful reports from agents whose reports cannot be assessed with any objective ground truthful information. In the multitask setting where each agent is asked multiple questions, a sequence of mechanisms have been proposed which are truthful — truthtelling is guaranteed to be an equilibrium, or even better, informed truthful — truthtelling is guaranteed to be one of the bestpaid equilibria. However, these guarantees assume agents’ strategies are restricted to be taskindependent: an agent’s report on a task is not affected by her information about other tasks. We provide the first discussion on how to design (informed) truthful mechanisms for taskdependent strategies, which allows the agents to report based on all her information on the assigned tasks. We call such stronger mechanisms (informed) omnitruthful. In particular, we propose the jointdisjoint task framework, a new paradigm which builds upon the previous penaltybonus task framework. First, we show a natural reduction from mechanisms in the penaltybonus task framework to mechanisms in the jointdisjoint task framework that maps every truthful mechanism to an omnitruthful mechanism. Such a reduction is nontrivial as we show that current penaltybonus task mechanisms are not, in general, omnitruthful. Second, for a stronger truthful guarantee, we design the matching agreement (MA) mechanism which is informed omnitruthful. Finally, for the MA mechanism in the detailfree setting where no prior knowledge is assumed, we show how many tasks are required to (approximately) retain the truthful guarantees.more » « less

null (Ed.)Peer prediction mechanisms incentivize agents to truthfully report their signals even in the absence of verification by comparing agents’ reports with those of their peers. In the detailfree multitask setting, agents are asked to respond to multiple independent and identically distributed tasks, and the mechanism does not know the prior distribution of agents’ signals. The goal is to provide an epsilonstrongly truthful mechanism where truthtelling rewards agents “strictly” more than any other strategy profile (with epsilon additive error) even for heterogeneous agents, and to do so while requiring as few tasks as possible. We design a family of mechanisms with a scoring function that maps a pair of reports to a score. The mechanism is strongly truthful if the scoring function is “prior ideal”. Moreover, the mechanism is epsilonstrongly truthful as long as the scoring function used is sufficiently close to the ideal scoring function. This reduces the above mechanism design problem to a learning problem – specifically learning an ideal scoring function. Because learning the prior distribution is sufficient (but not necessary) to learn the scoring function, we can apply standard learning theory techniques that leverage side information about the prior (e.g., that it is close to some parametric model). Furthermore, we derive a variational representation of an ideal scoring function and reduce the learning problem into an empirical risk minimization. We leverage this reduction to obtain very general results for peer prediction in the multitask setting. Specifically, Sample Complexity. We show how to derive good bounds on the number of tasks required for different types of priors–in some cases exponentially improving previous results. In particular, we can upper bound the required number of tasks for parametric models with bounded learning complexity. Furthermore, our reduction applies to myriad continuous signal space settings. To the best of our knowledge, this is the first peerprediction mechanism on continuous signals designed for the multitask setting. Connection to Machine Learning. We show how to turn a softpredictor of an agent’s signals (given the other agents’ signals) into a mechanism. This allows the practical use of machine learning algorithms that give good results even when many agents provide noisy information. Stronger Properties. In the finite setting, we obtain strongly truthful mechanisms for any stochastically relevant prior. Prior works either only apply to more restrictive settings, or achieve a weaker notion of truthfulness (informed truthfulness).more » « less

Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is βstretch if π is a simple (nonselfintersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the subcurve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the βstretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a βstretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a βstretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NPcomplete. We complement this result by giving a quasipolynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log V (G))), and s, t ∈ V (G), outputs a βstretch path between s and t, if a (1 − ε)βstretch path between s and t exists in the drawing.more » « less