Research Interests

#1. Game Theory

Currently, my research interests focus on algorithmic game theory and social choice theory in general. In particular, I am working on the problem of resource fair division, which could be stated as that, there is a set of (indivisible/divisible) resources M and a set of agents A, how to fairly allocate the resources to the agents when each agent has a personal preference towards different parts of the resources.

The problem sounds simple and the model is clean. However, this problem is not a kind of child's play at all. It is a classical problem in economics, mathematics, and computer science. Please refer to the article "Cake Cutting: Not Just Child's Play" written by Prof. Ariel Procassia for more background on this problem.

In my opinion,  this problem is pretty interesting from the perspective of mathematics and mechanism design. The basic model is clean and many classical techniques like Round-robin, and envy-graph are pretty novel. Currently, I am curious about the following problems,

Although envy-free allocation does not always exist in the setting of indivisible items, it is quite intriguing to study the existence of variations of it.  The most challenging one is EFX (envy-freeness up to any item). There are many existing papers on it, but no one completely solves it, even for four agents. It is shown that existing methods, like envy-graph, case-study, etc, all have limitations for this problem. I am interested in finding some novel techniques for this problem.

Another interesting fairness notion for me is what we call doubly-EFc/PROP-c in our paper "Fair Division with Allocator's Preference [WINE'23]". There are two preference profiles, and we are required to find an allocation that is fair under each profile. This model can be motivated in various ways, e.g., there is a set of couples, and we want to find an allocation that is fair for each couple, and there is an allocator, and we want to find an allocation that is fair for both allocator and agents, etc. I love this problem much not only because of the model. Classical methods do not work in this setting and we adopt novel techniques in our paper. However, they still cannot fully show the existence of this notion and we even cannot provide a counter-example. I am curious whether a doubly-EF1 allocation always exists. If the answer is yes, it would sound pretty amazing to me!

When I introduced fair division to researchers of other fields, the problem asked most was, "Where and how can fair division be applied in the real world?" I would like to list some scenarios to them (like public resource allocation, computation resource allocation, etc), but sometimes they are not convinced. The reasons I conjectured are that: 

a. Most application scenarios are simple, and people may not believe we indeed require such complicated mechanisms stated in many papers; 

b. Although fairness sounds make sense in many scenarios (like computation resource allocation), many companies do not think highly of fairness and prefer efficiency; 

c. The mechanisms proposed in many papers are difficult to understand by external people, which makes them not rarely implemented. Besides, although some mechanisms have beautiful complexity analysis, they may not run fast in real.

Based on the above reasons, I would say, how to push fair division into the real world, in my opinion, shares equal importance with theoretical analysis. In particular,  currently, I am interested in designing some fast methods that output an approximately fair allocation fast.

#2. Programming Languages

Besides the theory direction, I also hold some interest in program analysis/verification.  I tried to design some static analysis methods to find bugs within C programs during my undergraduate study. Besides, I also enjoy the process of writing Coq proofs. However, I have to admit that, the optimization of program analysis at the algorithm level is currently limited. Most works turn to optimizing program analysis from the perspective of computer systems (like parallelization, database, time optimization at the expense of memory, etc). 

Despite this, I have a slight preference for the theoretical work of programming languages. In particular, now I am interested in the following problems,

#3. Game Theory + X?

I also have a great interest in using some Programming/Software Engineering skills to benefit the development of theory direction. Some ideas came to my mind are that, whether we could use static analysis methods (like fuzzing) to detect potential strategic behaviors to help design truthful mechanisms. 

Besides, inspired by the recent work "Cutting the Cake: A Language for Fair Division", I am curious whether we could design some programming languages for other game theory problems.