NDLI: Truthful germs are contagious: a local to global characterization of truthfulness

Please wait, while we are loading the content...

Natural language generation for sponsored-search advertisements

Truthful germs are contagious: a local to global characterization of truthfulness

Posted prices vs. negotiations: an asymptotic analysis

Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions

A sufficient condition for voting rules to be frequently manipulable

Altruism, selfishness, and spite in traffic routing

Self-financed wagering mechanisms for forecasting

Better redistribution with inefficient allocation in multi-unit auctions with unit demand

Uncoordinated two-sided matching markets

Strategic network formation with structural holes

Optimizing query rewrites for keyword-based advertising

Mechanism design over discrete domains

Item pricing for revenue maximization

On the communication requirements of verifying the VCG outcome

Generalized scoring rules and the frequency of coalitional manipulability

Behavioral experiments in networked trade

Permutation betting markets: singleton betting with extra information

Efficiency and redistribution in dynamic mechanism design

Fast convergence to nearly optimal solutions in potential games

On the windfall of friendship: inoculation strategies on social networks

Optimal bidding in stochastic budget constrained slot auctions

On characterizations of truthful mechanisms for combinatorial auctions and scheduling

Optimal envy-free pricing with metric substitutability

Informational overhead of incentive compatibility

Incentives for expressing opinions in online polls

Security and insurance management in networks with heterogeneous agents

Complexity of combinatorial market makers

A visual interface for critiquing-based recommender systems

Fault tolerance in large games

Strong regularities in online peer production

Monotonicity and implementability: extended abstract

Information revelation and random entry in sequential ascending auctions

Eliciting properties of probability distributions

Non-myopic strategies in prediction markets

Popularity, novelty and attention

Predicting trusts among users of online communities: an epinions case study

The complexity of forecast testing: abstract

Crowdsourcing and knowledge sharing: strategic user behavior on taskcn

Truthful germs are contagious: a local to global characterization of truthfulness

Content Provider	ACM Digital Library
Author	Kleinberg, Robert Archer, Aaron
Abstract	We study the question of how to easily recognize whether a social choice function f from an abstract type space to a set of outcomes is truthful, i.e. implementable by a truthful mechanism. In particular, if the restriction of f to every "simple" subset of the type space is truthful, does it imply that f is truthful? Saks and Yu proved one such theorem: when the set of outcomes is finite and the type space is convex, a function f is truthful if its restriction to every 2-element subset of the type space is truthful, a condition called weak monotonicity. This characterization fails for infinite outcome sets. We provide a local-to-global characterization theorem for any set of outcomes (including infinite sets) and any convex space of types (including infinite-dimensional ones): a function f is truthful if its restriction to every sufficiently small 2-D neighborhood about each point is truthful. More precisely, f is truthful if and only if it satisfies local weak monotonicity and is vortex-free, meaning that the loop integral of f over every sufficiently small triangle vanishes. Our results apply equally well to multiple solution concepts, including dominant strategies, Nash and Bayes-Nash equilibrium, and to both deterministic and randomized mechanisms. When the type space is not convex, we show that f is truthful if and only if it extends to a truthful function on the convex hull of the original type space. We use our characterization theorem to give a simple alternate derivation of the Saks-Yu theorem. Generalizing this, we give a sufficient condition for constructing a truthful function by "stitching together" truthful subfunctions on different subsets of the domain.
Starting Page	21
Ending Page	30
Page Count	10
File Format	PDF
ISBN	9781605581699
DOI	10.1145/1386790.1386796
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-07-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Truthful Weak monotonicity Mechanism design Vortex-free
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Weak monotonicity suffices for truthfulness on convex domains

Weak monotonicity suffices for truthfulness on convex domains (2005)

Alternatives to truthfulness are hard to recognize (2008)

Truthful assignment without money

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity

Brief announcement: universally truthful secondary spectrum auctions

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity

An algorithm composition scheme preserving monotonicity

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity (2007)

Truthful germs are contagious: a local to global characterization of truthfulness

Similar Documents

Weak monotonicity suffices for truthfulness on convex domains

Weak monotonicity suffices for truthfulness on convex domains (2005)

Alternatives to truthfulness are hard to recognize (2008)

Truthful assignment without money

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity

Brief announcement: universally truthful secondary spectrum auctions

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity

An algorithm composition scheme preserving monotonicity

Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity (2007)

Truthful germs are contagious: a local to global characterization of truthfulness