Using nash implementation to achieve better frugality ratios

Chien Chung Huang*, Ming-Yang Kao, Xiang Yang Li, Weizhao Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Most of the recent works on algorithmic mechanism design exploit the solution concept of dominant strategy equilibria. Such work designs a proper payment scheme so that selfish agents maximize their utility by truthfully revealing their types. It has been pointed out that these truthful mechanisms, the famous among them being the VCG mechanisms, often incur high payments and fruglity ratios. In this work, we exploit the solution concept of Nash implementation to overcome this problem. Our mechanisms induce a set of Nash equilibria so that selfish agents have incentive to act based on a Nash equilibrium. We prove that our mechanisms enjoy substantial advantages over the truthful mechanisms in terms of payment and frugality.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
Pages377-389
Number of pages13
StatePublished - Dec 1 2007
Event18th International Symposium on Algorithms and Computation, ISAAC 2007 - Sendai, Japan
Duration: Dec 17 2007Dec 19 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4835 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Symposium on Algorithms and Computation, ISAAC 2007
CountryJapan
CitySendai
Period12/17/0712/19/07

Fingerprint

Solution Concepts
Nash Equilibrium
Algorithmic Mechanism Design
Incentives
Maximise
Strategy
Design

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Huang, C. C., Kao, M-Y., Li, X. Y., & Wang, W. (2007). Using nash implementation to achieve better frugality ratios. In Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings (pp. 377-389). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4835 LNCS).
Huang, Chien Chung ; Kao, Ming-Yang ; Li, Xiang Yang ; Wang, Weizhao. / Using nash implementation to achieve better frugality ratios. Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. 2007. pp. 377-389 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{b365f78231ea49f38d428d0b3dd839fe,
title = "Using nash implementation to achieve better frugality ratios",
abstract = "Most of the recent works on algorithmic mechanism design exploit the solution concept of dominant strategy equilibria. Such work designs a proper payment scheme so that selfish agents maximize their utility by truthfully revealing their types. It has been pointed out that these truthful mechanisms, the famous among them being the VCG mechanisms, often incur high payments and fruglity ratios. In this work, we exploit the solution concept of Nash implementation to overcome this problem. Our mechanisms induce a set of Nash equilibria so that selfish agents have incentive to act based on a Nash equilibrium. We prove that our mechanisms enjoy substantial advantages over the truthful mechanisms in terms of payment and frugality.",
author = "Huang, {Chien Chung} and Ming-Yang Kao and Li, {Xiang Yang} and Weizhao Wang",
year = "2007",
month = "12",
day = "1",
language = "English (US)",
isbn = "9783540771180",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "377--389",
booktitle = "Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings",

}

Huang, CC, Kao, M-Y, Li, XY & Wang, W 2007, Using nash implementation to achieve better frugality ratios. in Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4835 LNCS, pp. 377-389, 18th International Symposium on Algorithms and Computation, ISAAC 2007, Sendai, Japan, 12/17/07.

Using nash implementation to achieve better frugality ratios. / Huang, Chien Chung; Kao, Ming-Yang; Li, Xiang Yang; Wang, Weizhao.

Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. 2007. p. 377-389 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4835 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Using nash implementation to achieve better frugality ratios

AU - Huang, Chien Chung

AU - Kao, Ming-Yang

AU - Li, Xiang Yang

AU - Wang, Weizhao

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Most of the recent works on algorithmic mechanism design exploit the solution concept of dominant strategy equilibria. Such work designs a proper payment scheme so that selfish agents maximize their utility by truthfully revealing their types. It has been pointed out that these truthful mechanisms, the famous among them being the VCG mechanisms, often incur high payments and fruglity ratios. In this work, we exploit the solution concept of Nash implementation to overcome this problem. Our mechanisms induce a set of Nash equilibria so that selfish agents have incentive to act based on a Nash equilibrium. We prove that our mechanisms enjoy substantial advantages over the truthful mechanisms in terms of payment and frugality.

AB - Most of the recent works on algorithmic mechanism design exploit the solution concept of dominant strategy equilibria. Such work designs a proper payment scheme so that selfish agents maximize their utility by truthfully revealing their types. It has been pointed out that these truthful mechanisms, the famous among them being the VCG mechanisms, often incur high payments and fruglity ratios. In this work, we exploit the solution concept of Nash implementation to overcome this problem. Our mechanisms induce a set of Nash equilibria so that selfish agents have incentive to act based on a Nash equilibrium. We prove that our mechanisms enjoy substantial advantages over the truthful mechanisms in terms of payment and frugality.

UR - http://www.scopus.com/inward/record.url?scp=38349011627&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38349011627&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:38349011627

SN - 9783540771180

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 377

EP - 389

BT - Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings

ER -

Huang CC, Kao M-Y, Li XY, Wang W. Using nash implementation to achieve better frugality ratios. In Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. 2007. p. 377-389. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).