New Faculty Member, Ribeiro, Wins ACM SIGMETRICS Best Paper Award

07-12-2016
Writer(s): Staff Reports

Purdue Assistant Professor Bruno Ribeiro receives the ACM SIGMETRICS 2016 Best Paper Award for the work titled, “On the Duration and Intensity of Competitions in Nonlinear Polya Urn Processes with Fitness.”

Prof. Ribeiro and his co-authors, Daniel Figueiredo (Federal University of Rio de Janeiro, Brazil) Bo Jiang and Don Towsley (UMass Amherst) set forth to investigate a mathematical model that is used to describe phenomena such as wealth inequality can be attributed to the difference in individuals’ skills or mostly luck.

“In the competition for resources, “cumulative advantage” refers to the notion that accumulated resources foster the accumulation of further resources—a phenomenon that is widely used to explain the accumulation of wealth, customers, online followers, and paper citations,” Ribeiro explained. “The oldest and arguably the simplest mathematical model to embody this general principle is the Polya urn process, which finds applications in economics, biology, social and computer sciences, and machine learning under various names such as preferential attachment, “rich get richer,” the Matthew effect, path-dependent increasing returns, Chinese restaurant process, and processes with feedback,” he added.

The Polya urn model originated in 1923 with the work of Eggenberger and Polya. A general version of the model incorporates skill and nonlinear cumulative advantage attractiveness. Skill (fitness) refers to the inherent ability of agents to accumulate resources while nonlinearity refers to chances of accumulating further resources that are sub/super-linear in the amount of resources already accumulated.

Ribeiro’s and co-authors work provides the first full characterization of key metrics such as the duration and intensity of competitions in this foundational model. “For instance, for both linear and super-linear cumulative advantage competitions we show that within finite horizons there are many competition instances where the most skilled individual gathers less wealth than a less skilled individual, thus demonstrating that luck frequently trumps skill. Interestingly, in super-linear competitions, durations are heavy tailed with a slope does not depend on the difference in skill between the competitors, showing the extreme role of luck over skill in the outcome,” Ribeiro explained.

Ribeiro expects these results will shed light on the mechanisms of resource accumulation in a variety of disciplines, hopefully ensuring that new systems are designed so that skill does play a greater role in resource accumulation than luck.

The ACM SIGMETRICS 2016 Conference was held at the Congress Center of Antibes Juan-les-Pins, France from June 14-18. SIGMETRICS and Performance, held jointly this year, are respectively the flagship conferences of the Association for Computing Machinery (ACM) special interest group for the computer systems performance evaluation community and the International Federation for Information Processing (IFIP) working group WG7.3 on performance modeling and analysis.