30 citations · 102 across the 19 of their papers we have counts for
15 papers · 1 filter
MEV Makes Everyone Happy under Greedy Sequencing Rule
Yuhao Li, Mengqian Zhang, Jichen Li +3
Trading through decentralized exchanges (DEXs) has become crucial in today's blockchain ecosystem, enabling users to swap tokens efficiently and automatically. However, the capacit…
On Convergence Lemma and Convergence Stability for Piecewise Analytic Functions
Xiaotie Deng, Hanyu Li, Ningyuan Li
In this work, a convergence lemma for function being finite compositions of analytic mappings and the maximum operator is proved. The lemma shows that the set of -stationary…
A Context-Integrated Transformer-Based Neural Network for Auction Design
Zhijian Duan, Jingwu Tang, Yutong Yin +4
One of the central problems in auction design is developing an incentive-compatible mechanism that maximizes the auctioneer's expected revenue. While theoretical approaches have en…
Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions
Xiaotie Deng, Xinyan Hu, Tao Lin +1
The convergence properties of learning dynamics in repeated auctions is a timely and important question, with numerous applications in, e.g., online advertising markets. This work…
On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games
Xiaotie Deng, Ningyuan Li, David Mguni +2
Similar to the role of Markov decision processes in reinforcement learning, Stochastic Games (SGs) lay the foundation for the study of multi-agent reinforcement learning (MARL) and…
A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling
Xiaotie Deng, Ron Lavi, Tao Lin +3
The Empirical Revenue Maximization (ERM) is one of the most important price learning algorithms in auction design: as the literature shows it can learn approximately optimal reserv…
Finding Mixed Strategy Nash Equilibrium for Continuous Games through Deep Learning
Zehao Dou, Xiang Yan, Dongge Wang +1
Nash equilibrium has long been a desired solution concept in multi-player games, especially for those on continuous strategy spaces, which have attracted a rapidly growing amount o…
Smoothed and Average-case Approximation Ratios of Mechanisms: Beyond the Worst-case Analysis
Xiaotie Deng, Yansong Gao, Jie Zhang
The approximation ratio has become one of the dominant measures in mechanism design problems. In light of analysis of algorithms, we define the \emph{smoothed approximation ratio}…
Power-Law Distributions in a Two-sided Market and Net Neutrality
Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou
"Net neutrality" often refers to the policy dictating that an Internet service provider (ISP) cannot charge content providers (CPs) for delivering their content to consumers. Many…
Pricing Ad Slots with Consecutive Multi-unit Demand
Xiaotie Deng, Paul Goldberg, Yang Sun +2
We consider the optimal pricing problem for a model of the rich media advertisement market, as well as other related applications. In this market, there are multiple buyers (advert…
On Revenue Maximization with Sharp Multi-Unit Demands
Ning Chen, Xiaotie Deng, Paul. W. Goldberg +1
We consider markets consisting of a set of indivisible items, and buyers that have {\em sharp} multi-unit demand. This means that each buyer wants a specific number of it…
On Nash Dynamics of Matching Market Equilibria
Ning Chen, Xiaotie Deng
In this paper, we study the Nash dynamics of strategic interplays of n buyers in a matching market setup by a seller, the market maker. Taking the standard market equilibrium appro…
Competitive Equilibria in Matching Markets with Budgets
Ning Chen, Xiaotie Deng, Arpita Ghosh
We study competitive equilibria in the classic Shapley-Shubik assignment model with indivisible goods and unit-demand buyers, with budget constraints: buyers can specify a maximum…
On the Complexity of Envy-Free Cake Cutting
Xiaotie Deng, Qi Qi, Amin Saberi
We study the envy-free cake-cutting problem for players with cuts, for both the oracle function model and the polynomial time function model. For the former, we derive a…
Settling the Complexity of Computing Two-Player Nash Equilibria
Xi Chen, Xiaotie Deng, Shang-Hua Teng
We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the comp…