Author name cluster

Yukun Cheng

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

AAMAS Conference 2026 Conference Paper

Learning Truthful Mechanisms without Discretization

Yunxuan Ma
Steven (Siqiang) Wang
Zhijian Duan
Yukun Cheng
Xiaotie Deng

This paper introduces TEDI (Truthful, Expressive, and Dimension- Insensitiveapproach), thefirstdiscretization-freealgorithmtolearn truthful mechanisms. Existing learning-based algorithms rely on discretization of outcome spaces to ensure truthfulness, which suffers from inefficiency as problem size increases. To address this limitation, we formalize the concept of pricing rules, defined as functions that map outcomes to prices. We then parameterize pricing rules using Partial GroupMax Network, a novel network architecture designed to universally approximate partial convex functions. To enable optimization, we develop two training techniques: covariance trick and continuous sampling, to derive unbiased gradient estimators compatible with first-order optimization. Together, these design choices ensure the truthfulness, expressiveness and dimension-insensitivity of TEDI, and our experiments show that it consistently outperforms state-of-the-art methods in medium-tolarge scale problems. 1

PDF

IJCAI Conference 2025 Conference Paper

Game Theory Meets Large Language Models: A Systematic Survey

Haoran Sun
Yusen Wu
Yukun Cheng
Xu Chu

Game theory establishes a fundamental framework for analyzing strategic interactions among rational decision-makers. The rapid advancement of large language models (LLMs) has sparked extensive research exploring the intersection of these two fields. Specifically, game-theoretic methods are being applied to evaluate and enhance LLM capabilities, while LLMs themselves are reshaping classic game models. This paper presents a comprehensive survey of the intersection of these fields, exploring a bidirectional relationship from three perspectives: (1) Establishing standardized game-based benchmarks for evaluating LLM behavior; (2) Leveraging game-theoretic methods to improve LLM performance through algorithmic innovations; (3) Characterizing the societal impacts of LLMs through game modeling. Among these three aspects, we also highlight how the equilibrium analysis for traditional game models is impacted by LLMs' advanced language understanding, which in turn extends the study of game theory. Finally, we identify key challenges and future research directions, assessing their feasibility based on the current state of the field. By bridging theoretical rigor with emerging AI capabilities, this survey aims to foster interdisciplinary collaboration and drive progress in this evolving research area.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Optimal Mechanism Design for Crowdfunding of Public Goods

Yukun Cheng
Xiaotie Deng
Baqiao Quan

Mechanisms for crowdfunding public goods are essential for ensuring that societies can collectively benefit from public goods. Unlike previous researches on crowdfunding for public goods, which focused on binary outcomes—either full provision or none at all, this paper proposes an auction framework to examine the partial provision of public goods, based on the funds raised, with the goal of maximizing the final investment amount. We develop truthful investment mechanisms that achieve the (approximate) optimal expected investment amount across different models, taking into account the number of agents.

PDF

AAMAS Conference 2023 Conference Paper

Altruism, Collectivism and Egalitarianism: On a Variety of Prosocial Behaviors in Binary Networked Public Goods Games

Jichen Li
Xiaotie Deng
Yukun Cheng
Yuqi Pan
Xuanzhi Xia
Zongjun Yang
Jan Xie

Binary Networked public goods (BNPG) game consists of a network 𝐺 = (𝑉, 𝐸) with n players residing as nodes in a network and making a YES/NO decision to invest a public project. Examples of such public projects include face mask wearing during a pandemic, crime reporting and vaccination, etc. Most of the conventional modes of BNPG games solely posit egoism as the motivation of players: they only care about their own benefits. However, a series of real-world examples show that people have a wide range of prosocial behaviors in making decisions. To address this property, we introduce a novel extension of BNPG games to account for three kinds of prosocial motivations: altruism, collectivism, and egalitarianism. We revise utility functions to reflect different prosocial motivations with respect to the welfare of others, mediated by a prosocial graph. We develop computational complexity results to decide the existence of pure strategy Nash equilibrium in these models, for cases where the prosocial graph is a tree, a clique or a general network. We further discuss the Prosocial Network Modification (PNM) problem, in which a principal can change the network structure within a budget constraint, to induce a given strategy profile with respect to an equilibrium. For all three types of PNM problems, we completely characterize their corresponding computational complexity results.

PDF

TCS Journal 2023 Journal Article

Decision on block size in blockchain systems by evolutionary equilibrium analysis

Jinmian Chen
Yukun Cheng
Zhiqi Xu
Yan Cao

By using the PoW protocol, mining pools compete to successfully mine blocks to pursue rewards. Generally, the reward from a mined block includes the fixed block subsidies and the time-varying transaction fees. The latter are offered by the senders whose transactions are packaged into blocks and are increasing with the block size being larger. However, the larger block size brings the longer latency, resulting in a smaller probability of successfully mining. Therefore, decision on the optimal block size of a block to trade off two factors above mentioned is a complex and crucial problem for the mining pools. In this paper, we model the repeated mining competition dynamics among mining pools as an evolutionary game, in which each mining pool has two strategies: following the upper bound of block size B ¯, or selecting a block size smaller than B ¯. Because of the bounded rationality, each mining pool pursues its evolutionary stable strategy (ESS) on block size by continuous learning and adjustments during the whole mining process. A framework is built for the general evolutionary game, based on which we then explore the existence and stability of the ESSs for a case of two mining pools. Numerical experiments using the real Bitcoin data are conducted to demonstrate the theoretical results in this paper.

Details DOI

TCS Journal 2021 Journal Article

Approximation algorithms for spherical k-means problem using local search scheme

Dongmei Zhang
Yukun Cheng
Min Li
Yishui Wang
Dachuan Xu

In the spherical k-means problem (SKMP), which is a well-studied clustering problem in text mining, we are given an n-point set D in d-dimensional unit sphere S d, and an integer k ≤ n. The goal is to find a center subset S ⊂ S d with | S | ≤ k that minimizes the sum of cosine dissimilarity measure for each point in D to the nearest center. We prove that any γ-approximation algorithm for the k-means problem (KMP) can be adapted to the SKMP with 2γ-approximation ratio. It follows that there is a local search ( 18 + ϵ ) -approximation algorithm for the SKMP, by leveraging the classical local search ( 9 + ϵ ) -approximation algorithm for the KMP. Therefore, an interesting problem arises, that is whether there exists an approximation algorithm using local search scheme directly for the SKMP. In this paper, we present a local search approximation algorithm for the SKMP and prove its performance guarantee is ( 2 ( 4 + 7 ) + ϵ ). We also conduct numerical computation to show the efficiency of the local search approximation algorithm by single-swap operation in the end.

Details DOI

IJCAI Conference 2016 Conference Paper

Truthfulness of a Proportional Sharing Mechanism in Resource Exchange

Yukun Cheng
Xiaotie Deng
Qi Qi
Xiang Yan

In this paper, we consider the popular proportional sharing mechanism and discuss the incentives and opportunities of an agent to lie for personal gains in resource exchange game. The main result is a proof that an agent manipulating the proportional sharing mechanism by misreporting its resource amount will not benefit its own utility eventually. This result establishes a strategic stability property of the resource exchange protocol. We further illustrate and confirm the result via network examples.

PDF Details

TCS Journal 2013 Journal Article

Strategy-proof approximation mechanisms for an obnoxious facility game on networks

Yukun Cheng
Wei Yu
Guochuan Zhang

We study a new facility game, namely, an obnoxious facility game, on a network where the facility is undesirable and all agents try to be as far away from the facility as possible. The following process is considered: at first the agents declare their locations, then, given these bids, a mechanism selects a place on the network to locate the facility. The aim of the mechanism is to maximize the obnoxious social welfare, i. e. , the total distance between the agents and the facility. The objective of each agent is to maximize his/her utility, i. e. , the distance from the facility. Thus an agent may lie if, by doing so, he/she can get strictly more benefit. We are interested in mechanisms without money to decide the facility location so that the obnoxious social welfare is maximized and all agents are enforced to report their true locations. In this paper we give a first attempt at this game on different networks. Our main results are the following. When the network is a path, we show a 3-approximation group strategy-proof deterministic mechanism which is best possible if the facility can only take one of the endpoints on the path, and a group strategy-proof randomized mechanism with tight approximation ratio of 3 2. When the networks are a circle (known as a ring in the case of computer networks) and a tree, we propose two group strategy-proof deterministic mechanisms that each provides the approximation ratio of 3. Furthermore, when all agents are on a general network, we propose a 4-approximation group strategy-proof deterministic mechanism and a 2-approximation group strategy-proof randomized mechanism.

Details DOI

TCS Journal 2010 Journal Article

The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers

Yukun Cheng
Liying Kang
Changhong Lu

In this paper we consider the pos/neg-weighted median problem on a tree graph where the customers are modeled as continua subtrees. We address the discrete and continuous models, i. e. , the subtrees’ boundary points are all vertices, or possibly inner points of an edge, respectively. We consider two different objective functions. If we minimize the overall sum of the minimum weighted distances of the subtrees from the facilities, there exists an optimal solution satisfying a generalized vertex optimality property, e. g. , there is an optimal solution such that all facilities are located at vertices or the boundary points of the subtrees. Based on this property we devise a polynomial time algorithm for the pos/neg-weighted 1-median problem on a tree with subtree-shaped customers.

Details DOI