The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

Kousha   Etessami; Kristoffer Arnsfelt Hansen; Peter Bro Miltersen; Troels Bjerre    Sørensen

doi:10.1007/978-3-662-44803-8_20

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

Kousha Etessami, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Abstract

Mining user behavior patterns in social networks is of great importance in user behavior analysis, targeted marketing, churn prediction and other applications. However, less effort has been made to study the evolution of user behavior in social communities. In particular, users join and leave communities over time. How to automatically detect the online community transitions of individual users is a research problem of immense practical value yet with great technical challenges. In this paper, we propose an algorithm based on the Minimum Description Length (MDL) principle to trace the evolution of community transition of individual users, adaptive to the noisy behavior. Experiments on real data sets demonstrate the efficiency and effectiveness of our proposed method.

Original language	English
Title of host publication	Algorithmic Game Theory : 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings
Editors	Ron Lavi
Number of pages	13
Publisher	Springer VS
Publication date	Jun 2014
Pages	231-243
ISBN (Print)	978-3-662-44802-1
ISBN (Electronic)	978-3-662-44803-8
DOIs	https://doi.org/10.1007/978-3-662-44803-8_20
Publication status	Published - Jun 2014
Event	Symposium on Algorithmic Game Theory - Haifa, Israel Duration: 30 Sept 2014 → 2 Oct 2014 Conference number: 7

Conference

Conference	Symposium on Algorithmic Game Theory
Number	7
Country/Territory	Israel
City	Haifa
Period	30/09/2014 → 02/10/2014

Series	Lecture Notes in Computer Science
Volume	8768
ISSN	0302-9743

Access to Document

10.1007/978-3-662-44803-8_20

Cite this

Etessami, K., Hansen, K. A., Miltersen, P. B., & Sørensen , T. B. (2014). The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. In R. Lavi (Ed.), Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings (pp. 231-243 ). Springer VS. https://doi.org/10.1007/978-3-662-44803-8_20

Etessami, Kousha ; Hansen, Kristoffer Arnsfelt ; Miltersen, Peter Bro et al. / The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. editor / Ron Lavi. Springer VS, 2014. pp. 231-243 (Lecture Notes in Computer Science, Vol. 8768).

@inproceedings{4f61b03ab39f4c95abc2c7171d767512,

title = "The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form",

abstract = "Mining user behavior patterns in social networks is of great importance in user behavior analysis, targeted marketing, churn prediction and other applications. However, less effort has been made to study the evolution of user behavior in social communities. In particular, users join and leave communities over time. How to automatically detect the online community transitions of individual users is a research problem of immense practical value yet with great technical challenges. In this paper, we propose an algorithm based on the Minimum Description Length (MDL) principle to trace the evolution of community transition of individual users, adaptive to the noisy behavior. Experiments on real data sets demonstrate the efficiency and effectiveness of our proposed method.",

author = "Kousha Etessami and Hansen, {Kristoffer Arnsfelt} and Miltersen, {Peter Bro} and S{\o}rensen, {Troels Bjerre}",

year = "2014",

month = jun,

doi = "10.1007/978-3-662-44803-8_20",

language = "English",

isbn = "978-3-662-44802-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer VS",

pages = "231--243 ",

editor = "{ Lavi}, {Ron }",

booktitle = "Algorithmic Game Theory",

note = "Symposium on Algorithmic Game Theory ; Conference date: 30-09-2014 Through 02-10-2014",

}

Etessami, K, Hansen, KA , Miltersen, PB & Sørensen , TB 2014, The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. in R Lavi (ed.), Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. Springer VS, Lecture Notes in Computer Science, vol. 8768, pp. 231-243 , Symposium on Algorithmic Game Theory, Haifa, Israel, 30/09/2014. https://doi.org/10.1007/978-3-662-44803-8_20

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. / Etessami, Kousha ; Hansen, Kristoffer Arnsfelt ; Miltersen, Peter Bro et al.
Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. ed. / Ron Lavi. Springer VS, 2014. p. 231-243 (Lecture Notes in Computer Science, Vol. 8768).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

AU - Etessami, Kousha

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Sørensen , Troels Bjerre

N1 - Conference code: 7

PY - 2014/6

Y1 - 2014/6

N2 - Mining user behavior patterns in social networks is of great importance in user behavior analysis, targeted marketing, churn prediction and other applications. However, less effort has been made to study the evolution of user behavior in social communities. In particular, users join and leave communities over time. How to automatically detect the online community transitions of individual users is a research problem of immense practical value yet with great technical challenges. In this paper, we propose an algorithm based on the Minimum Description Length (MDL) principle to trace the evolution of community transition of individual users, adaptive to the noisy behavior. Experiments on real data sets demonstrate the efficiency and effectiveness of our proposed method.

AB - Mining user behavior patterns in social networks is of great importance in user behavior analysis, targeted marketing, churn prediction and other applications. However, less effort has been made to study the evolution of user behavior in social communities. In particular, users join and leave communities over time. How to automatically detect the online community transitions of individual users is a research problem of immense practical value yet with great technical challenges. In this paper, we propose an algorithm based on the Minimum Description Length (MDL) principle to trace the evolution of community transition of individual users, adaptive to the noisy behavior. Experiments on real data sets demonstrate the efficiency and effectiveness of our proposed method.

U2 - 10.1007/978-3-662-44803-8_20

DO - 10.1007/978-3-662-44803-8_20

M3 - Article in proceedings

SN - 978-3-662-44802-1

T3 - Lecture Notes in Computer Science

SP - 231

EP - 243

BT - Algorithmic Game Theory

A2 - Lavi, Ron

PB - Springer VS

T2 - Symposium on Algorithmic Game Theory

Y2 - 30 September 2014 through 2 October 2014

ER -

Etessami K, Hansen KA , Miltersen PB, Sørensen TB. The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. In Lavi R, editor, Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings. Springer VS. 2014. p. 231-243 . (Lecture Notes in Computer Science, Vol. 8768). doi: 10.1007/978-3-662-44803-8_20

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form

Abstract

Conference

Access to Document

Fingerprint

Cite this