Author name cluster

Changyuan Yu

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.

5 papers

1 author row

NeurIPS Conference 2025 Conference Paper

Beyond Last-Click: An Optimal Mechanism for Ad Attribution

Nan An
Weian Li
Qi Qi
Changyuan Yu
Liang Zhang

Accurate attribution for multiple platforms is critical for evaluating performance-based advertising. However, existing attribution methods rely heavily on the heuristic methods, e. g. , Last-Click Mechanism (LCM) which always allocates the attribution to the platform with the latest report, lacking theoretical guarantees for attribution accuracy. In this work, we propose a novel theoretical model for the advertising attribution problem, in which we aim to design the optimal dominant strategy incentive compatible (DSIC) mechanisms and evaluate their performance. We first show that LCM is not DSIC and performs poorly in terms of accuracy and fairness. To address this limitation, we introduce the Peer-Validated Mechanism (PVM), a DSIC mechanism in which a platform's attribution depends solely on the reports of other platforms. We then examine the accuracy of PVM across both homogeneous and heterogeneous settings, and provide provable accuracy bounds for each case. Notably, we show that PVM is the optimal DSIC mechanism in the homogeneous setting. Finally, numerical experiments are conducted to show that PVM consistently outperforms LCM in terms of attribution accuracy and fairness.

PDF Details

AAAI Conference 2025 Conference Paper

On Designing the Optimal Integrated Ad Auction in E-commerce Platforms

Yuchao Ma
Weian Li
Yuhan Wang
Zitian Guo
Yuejia Dou
Qi Qi
Changyuan Yu

Currently, e-commerce platforms integrate ads and organic content into a mixed list for users. While platforms seek to maximize profit from advertisers, organic items enhance user experience. To ensure long-term development, platforms aim to design mechanisms that optimize both revenue and user satisfaction. Current methods rank ads and organic items separately before integrating them. Even if each part is locally optimal, the combined result may not be globally optimal. In this paper, we come up with the Joint Integrated Regret Network (JINTER Net). Unlike traditional methods, which pre-order ads and organic items separately, JINTER Net directly selects from the combined set of candidate ads and organic items to generate an optimal list. This approach aims to optimally balance platform revenue and user experience while satisfying approximate dominant strategy incentive compatibility and individual rationality. We validate the effectiveness of JINTER Net using both synthetic data and real dataset, and our experimental results show that it significantly outperforms baseline models across multiple metrics.

PDF Details DOI

TCS Journal 2023 Journal Article

Optimally integrating ad auction into e-commerce platforms

Weian Li
Qi Qi
Changjun Wang
Changyuan Yu

Advertising becomes one of the most popular ways of monetizing an online transaction platform. Usually, sponsored advertisements are posted on the most attractive positions to enhance the number of clicks. However, multiple e-commerce platforms are aware that this action may hurt the search experience of users, even though it can bring more incomes. To balance the advertising revenue and the user experience loss caused by advertisements, most e-commerce platforms choose fixing some areas for advertisements and adopting some restrictions on the number of ads, such as a fixed number K of ads or one advertisement for every N organic searched results. Different from these common rules of treating the allocation of ads separately (from the arrangements of the organic searched items), in this work we build up an integrated system with mixed arrangements of advertisements and organic items. We focus on the design of truthful mechanisms to properly list the advertisements and organic items and optimally trade off the instant revenue and the user experience. Furthermore, for different settings and practical requirements, we extend our optimal truthful allocation mechanisms to cater for these realistic conditions. Finally, we exert several experiments to verify the improvement of our mechanism compared to the common-used advertising mechanism.

Details DOI

TCS Journal 2009 Journal Article

A 5 + ϵ -approximation algorithm for minimum weighted dominating set in unit disk graph

Decheng Dai
Changyuan Yu

We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5 + ϵ, improving the previous best result of 6 + ϵ in [Yaochun Huang, Xiaofeng Gao, Zhao Zhang, Weili Wu, A better constant-factor approximation for weighted dominating set in unit disk graph, J. Comb. Optim. (ISSN: 1382-6905) (2008) 1573–2886. (Print) (Online)]. Combining the common technique used in the above mentioned reference, we can compute a minimum weight connected dominating set with approximation ratio 9 + ϵ, beating the previous best result of 10 + ϵ in the same work.

Details DOI

TCS Journal 2009 Journal Article

Truthful mechanisms for two-range-values variant of unrelated scheduling

Changyuan Yu

In this paper, we consider a restricted variant of the scheduling problem, where the machines are the strategic players. For this multi-parameter mechanism design problem, the only known truthful mechanisms use task independent allocation algorithms and only have approximation ratio O ( m ) [N. Nisan, A. Ronen. Algorithmic mechanism design (extended abstract), in: STOC’99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1999. pp. 129–140; A. Mu’alem, M. Schapira, Setting lower bounds on truthfulness: Extended abstract, in: SODA’07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007, pp. 1143–1152; P. Lu, C. Yu, An improved randomized truthful mechanism for scheduling unrelated machines, in: 25th International Symposium on Theoretical Aspects of Computer Science, STACS, 2008, pp. 527–538; P. Lu, C. Yu, Randomized truthful mechanisms for scheduling unrelated machines, in: C. H. Papadimitriou, S. Zhang (Eds.), Proceedings of WINE, in: Lecture Notes in Computer Science, vol. 5385, Springer, 2008, pp. 402–413]. Lavi and Swamy first use the cycle monotone condition and design a 3-approximation truthful mechanism for a two value variant in [R. Lavi, C. Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, in: EC’07: Proceedings of the 8th ACM conference on Electronic commerce, ACM, New York, NY, USA, 2007, pp. 252–261], where the processing time of task j on machine i, say t i j, can only be either a lower value L j or a higher value H j. We consider a generalized variant, where t i j lies in [ L j, L j ( 1 + ϵ ) ] ⋃ [ H j, H j ( 1 + ϵ ) ] and ϵ is a parameter satisfying some condition. We consider two special cases, case A when H j / L j > 2, ∀ j and case B when H j / L j ≤ 2, ∀ j, and give randomized truthful mechanisms with approximation ratio 4 ( 1 + ϵ ) for both cases. Based on these two cases’ results, we are also able to deal with the general case of our two-range-values scheduling problem. We use a combination of two mechanisms, which is also a novel method in mechanism design for scheduling problems, and finally we give a randomized truthful mechanism with approximation ratio 7 ( 1 + ϵ ). Although the generalization seems a little incremental, we actually use a very novel technique in the key step of proving truthfulness for case A, as well as a new mechanism scheme for case B. Besides, the results in this paper are the first truthful mechanisms with constant approximation ratios when a machine (player) can report infinitely possible values, which is quite different from the two value variant, in which only finite values are available. Furthermore, together with Lavi and Swamy’s work, our results suggest that such a task-dependent approach can really do much better for the scheduling unrelated machines problem.

Details DOI