Xiaotie Deng - Selected Publications#

Fixed point computation: Characterization of PPAD and PPA by Sperner triangle on Euclid-ean Plane and on Mobius Strip.

1. Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi and Zeying Xu. Understand-ing PPA-completeness. 31st Conference on Computational Complexity (CCC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.

2. Xiaotie Deng, Qi Qi, Amin Saberi and Jie Zhang. Discrete Fixed Points: Models, Complexities, and Applications. Math. Oper. Res. 36(4): 636-652, 2011.

3. Chen, Xi and Xiaotie Deng. On the Complexity of 2D Discrete Fixed Point Problem. Theoretical Computer Science, 410(44): 4448-4456, 2009.

On the information manipulation in auction and market equilibrium by agent with private value distribution and private utility function.

4. Xiaotie Deng, Tao Lin and Tao Xiao: Private Data Manipulation in Optimal Sponsored Search Auction, WWW 2020.

5. Xiaotie Deng, Keyu Zhu and Tao Xiao: Learn to Play Maximum Revenue Auction. IEEE Transactions on Cloud Computing 7(4): 1057-1067, 2019.

6. Cheng, Yukun, Xiaotie Deng, Yifan Pi and Xiang Yan. Can Bandwidth Sharing Be Truthful? In The 8th International Symposium on Algorithmic Game Theory (SAGT): pp.190-202, Saarbrücken, Germany, September 28-30, 2015.

7. Ning Chen, Xiaotie Deng and Jie Zhang. How Profitable Are Strategic Behaviors in a Market? Proceedings of19th Annual European Symposium (ESA): pp. 106-118, Saarbrücken, Germany, September 5-9, 2011.

Classical works in algorithmic game theory

8. Deng, Xiaotie, and Christos H. Papadimitriou. On the Complexity of Cooperative Solution Concepts. Mathematics of Operations Research 19(2): 257-266, 1994.

9. X. Deng, C. Papadimitriou and S. Safra. On the Complexity of Equilibria. 34th ACM Symposium on Theory of Computing (ACM STOC): 67-71, (2002).

10. X. Chen and X. Deng, Settling the Complexity of Two-Player Nash-Equilibrium. 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 261-272, Berkeley, CA, USA, 2006 (Best Paper Award) (journal version: X. Chen, X. Deng and S. Teng: Settling the Complexity of Computing Two-player Nash Equilibria. Journal of the ACM, 56(3), May 2009)

Total number of citations: 8383, H-index 46 (https://scholar.google.com/citations?hl=en&user=OBUwP_oAAAAJ)