Yun Kuen CHEUNG (Marco) 張潤權
Email: [AT] cims [DOT] nyu [DOT] edu

PhD candidate at Courant Institute of Mathematical Sciences, New York University; Department: Computer Science
MPhil at HKUST; Department: Mathematics (worked in Theoretical Computer Science Lab)
BSc at HKUST; Major: Mathematics, Physics; Minor: Information and Technology (almost equal to Computer Science)

Main Page

I will graduate by Summer 2014.

NEW (Nov 13, 2013):I have put full versions of my papers in Research and Publications.

I am a fifth year PhD candidate in Computer Science Department, Courant Institute of Mathematical Sciences, New York University. My advisor is Prof. Richard Cole. My research interest lies in algorithm analysis, algorithmic game theory and computational economics. I will give more details of my research below.

My current research focuses on market equilibrium computation problems; one of our aims is to explain why equilibria are often reached (approximately) in real world from an algorithmic perspective. We study a price-udpate dynamic called tatonnement, in which price updates are distributed. In the recent work with Richard Cole and Nikhil Devanur, we show that for Fisher markets with any CES utility functions, tatonnement is equivalent to gradient descent on some convex potential function. We show that the potential function satisfies 'strong sandwiching property', which is a generalization of strong convexity (on standard metric) to Bregman divergence (a kind of asymmetric metric), in order to show that tatonnement attains linear convergence rate. Beyond the standard continuous and discrete synchronous tatonnements, we are working on asynchronous tatonnement too.

I am also interested in other equilibrium computation problems; Nash equilibrium is one of them. Erick Chastain and I have shown that a broad class of multiplicative weight dynamics fail to converge (in empirical average) to the Nash equilibrium of some symmetric Rock-Paper-Scissors games, even with the assumption that both players have the same initial mixed strategies. In our proof, we use arithmetic tools developed in dynamical system theory to show existence of heteroclinic cycle: the multiplicative weight dynamic stays near different saddle equilibria for exponentially increasing periods of time.

I am also following closely on literatures on mechanism design, and I am working on some problems in this area.

When I did my MPhil degree in Hong Kong University of Science and Technology, I was fortunate to have Prof. Mordecai Golin as advisor. In my MPhil thesis, I used Mellin transform technique to solve some divide-and-conquer type recurrences exactly, which gives exact formula on varies types of weighted digital sums that appear in different algorithm analysis problems. Prof. Philippe Flajolet told me in a private communication that the technique can become a standard analytical approach for comparing practical algorithms, e.g. sorting and searching. I welcome input from researchers working on developing practical algorithms.

For more details of my research and publications, click here.