Using nash implementation to achieve better frugality ratios

Chien Chung Huang; Ming-Yang Kao; Xiang Yang Li; Weizhao Wang

doi:10.1007/978-3-540-77120-3_34

Using nash implementation to achieve better frugality ratios

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

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
Publisher	Springer Verlag
Pages	377-389
Number of pages	13
ISBN (Print)	9783540771180
DOIs	https://doi.org/10.1007/978-3-540-77120-3_34
State	Published - 2007
Event	18th International Symposium on Algorithms and Computation, ISAAC 2007 - Sendai, Japan Duration: Dec 17 2007 → Dec 19 2007

Publication series

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

Other

Other	18th International Symposium on Algorithms and Computation, ISAAC 2007
Country/Territory	Japan
City	Sendai
Period	12/17/07 → 12/19/07

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-77120-3_34

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). Springer Verlag. https://doi.org/10.1007/978-3-540-77120-3_34

Huang, Chien Chung ; Kao, Ming-Yang ; Li, Xiang Yang et al. / Using nash implementation to achieve better frugality ratios. Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. Springer Verlag, 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",

doi = "10.1007/978-3-540-77120-3_34",

language = "English (US)",

isbn = "9783540771180",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "377--389",

booktitle = "Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings",

note = "18th International Symposium on Algorithms and Computation, ISAAC 2007 ; Conference date: 17-12-2007 Through 19-12-2007",

}

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, Springer Verlag, pp. 377-389, 18th International Symposium on Algorithms and Computation, ISAAC 2007, Sendai, Japan, 12/17/07. https://doi.org/10.1007/978-3-540-77120-3_34

Using nash implementation to achieve better frugality ratios. / Huang, Chien Chung; Kao, Ming-Yang; Li, Xiang Yang et al.
Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. Springer Verlag, 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 proceeding › Conference 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

Y1 - 2007

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

U2 - 10.1007/978-3-540-77120-3_34

DO - 10.1007/978-3-540-77120-3_34

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

PB - Springer Verlag

T2 - 18th International Symposium on Algorithms and Computation, ISAAC 2007

Y2 - 17 December 2007 through 19 December 2007

ER -

Huang CC, Kao MY, Li XY, Wang W. Using nash implementation to achieve better frugality ratios. In Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings. Springer Verlag. 2007. p. 377-389. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-77120-3_34

Using nash implementation to achieve better frugality ratios

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this