Zihe Wang

AAAI Conference 2026 Conference Paper

Pacing Equilibria in Second-Price Auctions with Few Buyers

• Yonglei Yan
• Zihe Wang
• Zhengyang Liu

We present a polynomial-time algorithm for exactly computing second-price pacing equilibria (SPPE) in auction markets with a constant number of buyers. SPPE plays a central role in modern advertising auctions; however, computing or even approximating it is PPAD-hard in general. To overcome this computational barrier in the restricted setting, we adopt the cell-decomposition method. Specifically, we partition the solution space into polynomially many cells, each defined by hyperplanes corresponding to a fixed ordering of buyers’ scaled valuations across goods. Within each cell, the equilibrium computation reduces to solving a constant number of linear programs. Notably, our algorithm can also efficiently identify equilibria that optimize key objectives such as revenue or social welfare. To the best of our knowledge, this is the first algorithm that efficiently computes an exact SPPE for a simple and natural class of second-price pacing games.

AAMAS Conference 2025 Conference Paper

Environmental Policies within Cournot Oligopoly

• Liang Shan
• Zhengyang Liu
• Haoqiang Huang
• Zihe Wang

We consider how to effectively regulate environmental policies with clear penalties and rewards, through a game-theoretical point of view. To this end, we use social welfare as the primary metric for evaluation. We demonstrate that the best possible social welfare can be achieved through policies that incorporate both linear taxation and subsidies in a Cournot competition model. To make it constructive, we propose efficient algorithms to find optimal policies in a Cournot competition model. Our work can be seen as the first step towards obtaining the optimal environmental policy through the lens of computation.

AIJ Journal 2025 Journal Article

On the design of truthful mechanisms for the capacitated facility location problem with two and more facilities

• Gennaro Auricchio
• Zihe Wang
• Jie Zhang

In this paper, we explore the Mechanism Design aspects of the m-Capacitated Facility Location Problem (m-CFLP) on a line, focusing on two frameworks. In the first framework, the number of facilities is arbitrary, all facilities share the same capacity, and the number of agents matches the total capacity of the facilities. In the second framework, we need to locate two facilities, each with a capacity equal to at least half the number of agents. For both frameworks, we propose truthful mechanisms with bounded approximation ratios in terms of Social Cost (SC) and Maximum Cost (MC). When m > 2, our results stand in contrast to the impossibility results known for the classical m-Facility Location Problem, where capacity constraints are absent. Moreover, all the proposed mechanisms are optimal with respect to MC and either optimal or near-optimal with respect to the SC among anonymous mechanisms. We then establish lower bounds on the approximation ratios that any truthful and deterministic mechanism achieves with respect to SC and MC for both frameworks. Lastly, we run several numerical experiments to empirically evaluate the performances of our mechanisms with respect to the SC or the MC. Our empirical analysis shows that our proposed mechanisms outperform all previously proposed mechanisms applicable in this setting.

IJCAI Conference 2025 Conference Paper

Stackelberg vs. Nash in the Lottery Colonel Blotto Game

• Yan Liu
• Bonan Ni
• Weiran Shen
• Zihe Wang
• Jie Zhang

Resource competition problems are often modeled using Colonel Blotto games, where players take simultaneous actions. However, many real-world scenarios involve sequential decision-making rather than simultaneous moves. To model these dynamics, we represent the Lottery Colonel Blotto game as a Stackelberg game, in which one player, the leader, commits to a strategy first, and the other player, the follower, responds. We derive the Stackelberg equilibrium for this game, formulating the leader's strategy as a bi-level optimization problem. To solve this, we develop a constructive method based on iterative game reductions, which allows us to efficiently compute the leader’s optimal commitment strategy in polynomial time. Additionally, we identify the conditions under which the Stackelberg equilibrium coincides with the Nash equilibrium. Specifically, this occurs when the budget ratio between the leader and the follower equals a certain threshold, which we can calculate in closed form. In some instances, we observe that when the leader’s budget exceeds this threshold, both players achieve higher utilities in the Stackelberg equilibrium compared to the Nash equilibrium. Lastly, we show that, in the best case, the leader can achieve an infinite utility improvement by making an optimal first move compared to the Nash equilibrium.

TCS Journal 2025 Journal Article

Striking the balance: Optimizing pricing schemes for time-sensitive buyers

• Zhengyang Liu
• Liang Shan
• Zihe Wang

This study explores the fundamental trade-off between time and money in pricing strategies. Specifically, we investigate the optimization of pricing schemes tailored for identical items, catering to heterogeneous, time-sensitive buyers. Our analysis aims to determine the optimal pricing scheme, which is achieved through the development of an efficient algorithm within a Bayesian framework. Notably, our findings elucidate the relationship between the loss of buyers’ wasted time and the corresponding impact on the seller’s revenue. Additionally, we conduct a comparative evaluation of two types of pricing schemes, namely the k-step function and fixed pricing, shedding light on their respective efficacy in revenue. Furthermore, we delve into the underlying mechanics of the optimal pricing scheme under a general setting, offering closed form expressions over the product distribution. Through illustrative examples, we highlight how the positive correlation between the valuation of the item and the cost per unit time could help increase revenue.

NeurIPS Conference 2025 Conference Paper

Universally Invariant Learning in Equivariant GNNs

• Jiacheng Cen
• Anyi Li
• Ning Lin
• Tingyang Xu
• Yu Rong
• Deli Zhao
• Zihe Wang
• Wenbing Huang

Equivariant Graph Neural Networks (GNNs) have demonstrated significant success across various applications. To achieve completeness---that is, the universal approximation property over the space of equivariant functions---the network must effectively capture the intricate multi-body interactions among different nodes. Prior methods attain this via deeper architectures, augmented body orders, or increased degrees of steerable features, often at high computational cost and without polynomial-time solutions. In this work, we present a theoretically grounded framework for constructing complete equivariant GNNs that is both efficient and practical. We prove that a complete equivariant GNN can be achieved through two key components: 1) a complete scalar function, referred to as the canonical form of the geometric graph; and 2) a full-rank steerable basis set. Leveraging this finding, we propose an efficient algorithm for constructing complete equivariant GNNs based on two common models: EGNN and TFN. Empirical results demonstrate that our model demonstrates superior completeness and excellent performance with only a few layers, thereby significantly reducing computational overhead while maintaining strong practical efficacy.

NeurIPS Conference 2024 Conference Paper

Are High-Degree Representations Really Unnecessary in Equivariant Graph Neural Networks?

• Jiacheng Cen
• Anyi Li
• Ning Lin
• Yuxiang Ren
• Zihe Wang
• Wenbing Huang

Equivariant Graph Neural Networks (GNNs) that incorporate E(3) symmetry have achieved significant success in various scientific applications. As one of the most successful models, EGNN leverages a simple scalarization technique to perform equivariant message passing over only Cartesian vectors (i. e. , 1st-degree steerable vectors), enjoying greater efficiency and efficacy compared to equivariant GNNs using higher-degree steerable vectors. This success suggests that higher-degree representations might be unnecessary. In this paper, we disprove this hypothesis by exploring the expressivity of equivariant GNNs on symmetric structures, including $k$-fold rotations and regular polyhedra. We theoretically demonstrate that equivariant GNNs will always degenerate to a zero function if the degree of the output representations is fixed to 1 or other specific values. Based on this theoretical insight, we propose HEGNN, a high-degree version of EGNN to increase the expressivity by incorporating high-degree steerable vectors while maintaining EGNN's efficiency through the scalarization trick. Our extensive experiments demonstrate that HEGNN not only aligns with our theoretical analyses on toy datasets consisting of symmetric structures, but also shows substantial improvements on more complicated datasets such as $N$-body and MD17. Our theoretical findings and empirical results potentially open up new possibilities for the research of equivariant GNNs.

AAAI Conference 2024 Conference Paper

Cost Minimization for Equilibrium Transition

• Haoqiang Huang
• Zihe Wang
• Zhide Wei
• Jie Zhang

In this paper, we delve into the problem of using monetary incentives to encourage players to shift from an initial Nash equilibrium to a more favorable one within a game. Our main focus revolves around computing the minimum reward required to facilitate this equilibrium transition. The game involves a single row player who possesses m strategies and k column players, each endowed with n strategies. Our findings reveal that determining whether the minimum reward is zero is NP-complete, and computing the minimum reward becomes APX-hard. Nonetheless, we bring some positive news, as this problem can be efficiently handled if either k or n is a fixed constant. Furthermore, we have devised an approximation algorithm with an additive error that runs in polynomial time. Lastly, we explore a specific case wherein the utility functions exhibit single-peaked characteristics, and we successfully demonstrate that the optimal reward can be computed in polynomial time.

IJCAI Conference 2024 Conference Paper

Facility Location Problems with Capacity Constraints: Two Facilities and Beyond

• Gennaro Auricchio
• Zihe Wang
• Jie Zhang

In this paper, we investigate the Mechanism Design aspects of the m-Capacitated Facility Location Problem (m-CFLP) on a line. We focus on two frameworks. In the first framework, the number of facilities is arbitrary, all facilities have the same capacity, and the number of agents is equal to the total capacity of all facilities. In the second framework, we aim to place two facilities, each with a capacity of at least half of the total agents. For both of these frameworks, we propose truthful mechanisms with bounded approximation ratios with respect to the Social Cost (SC) and the Maximum Cost (MC). When m>2, the result sharply contrasts with the impossibility results known for the classic m-Facility Location Problem, where capacity constraints are not considered. Furthermore, all our mechanisms are optimal with respect to the MC and optimal or nearly optimal with respect to the SC among anonymous mechanisms. For both frameworks, we provide a lower bound on the approximation ratio that any truthful and deterministic mechanism can achieve with respect to the SC and MC.

NeurIPS Conference 2024 Conference Paper

MLLM-CompBench: A Comparative Reasoning Benchmark for Multimodal LLMs

• Jihyung Kil
• Zheda Mai
• Justin Lee
• Arpita Chowdhury
• Zihe Wang
• Kerrie Cheng
• Lemeng Wang
• Ye Liu

The ability to compare objects, scenes, or situations is crucial for effective decision-making and problem-solving in everyday life. For instance, comparing the freshness of apples enables better choices during grocery shopping, while comparing sofa designs helps optimize the aesthetics of our living space. Despite its significance, the comparative capability is largely unexplored in artificial general intelligence (AGI). In this paper, we introduce MLLM-CompBench, a benchmark designed to evaluate the comparative reasoning capability of multimodal large language models (MLLMs). MLLM-CompBench mines and pairs images through visually oriented questions covering eight dimensions of relative comparison: visual attribute, existence, state, emotion, temporality, spatiality, quantity, and quality. We curate a collection of around 40K image pairs using metadata from diverse vision datasets and CLIP similarity scores. These image pairs span a broad array of visual domains, including animals, fashion, sports, and both outdoor and indoor scenes. The questions are carefully crafted to discern relative characteristics between two images and are labeled by human annotators for accuracy and relevance. We use MLLM-CompBench to evaluate recent MLLMs, including GPT-4V(ision), Gemini-Pro, and LLaVA-1. 6. Our results reveal notable shortcomings in their comparative abilities. We believe MLLM-CompBench not only sheds light on these limitations but also establishes a solid foundation for future enhancements in the comparative capability of MLLMs.

AAMAS Conference 2023 Conference Paper

Node Conversion Optimization in Multi-hop Influence Networks

• Jie Zhang
• Yuezhou Lv
• Zihe Wang

In this paper, we study scenarios such as diffusion of innovations in a social system and belief propagation in social choice decisionmaking, which can be captured by a social influence network. In such networks, nodes are distributed and are connected by links between them. Nodes have two different states, 𝑠 and 𝑟. They can change from state 𝑠 to state 𝑟, but not backward [24]. Nodes are interested in changing to state 𝑟 only if a sufficient number of their neighbors change to state 𝑟. In many scenarios, it is desired to design local decision algorithms that guarantee this feature, termed as the safety of node conversion. We design optimal algorithms that maximize the number of nodes that change to state 𝑟. In particular, we assume that each node can observe its neighbors up to a distance of 𝑘 from itself, which introduces complexity to the setting that each node can only observe its immediate neighbors, i. e. , 𝑘 = 1. Moreover, we consider the models that nodes have the same threshold or different thresholds under which their conversion from 𝑠 to 𝑟 is safe. We first present the optimal algorithm for the uniform threshold model and establish its optimality by characterizing a monotonicity property. We then generalize the algorithm to maximize node conversion when they have different threshold values. The monotonicity properties and insights on nodes’ recursive reasoning of their neighbors’ status may be of independent interest.

AAAI Conference 2023 Conference Paper

Optimal Pricing Schemes for Identical Items with Time-Sensitive Buyers

• Zhengyang Liu
• Liang Shan
• Zihe Wang

Time or money? That is a question! In this paper, we consider this dilemma in the pricing regime, in which we try to find the optimal pricing scheme for identical items with heterogenous time-sensitive buyers. We characterize the revenue-optimal solution and propose an efficient algorithm to find it in a Bayesian setting. Our results also demonstrate the tight ratio between the value of wasted time and the seller's revenue, as well as that of two common-used pricing schemes, the k-step function and the fixed pricing. To explore the nature of the optimal scheme in the general setting, we present the closed forms over the product distribution and show by examples that positive correlation between the valuation of the item and the cost per unit time could help increase revenue. To the best of our knowledge, it is the first step towards understanding the impact of the time factor as a part of the buyer cost in pricing problems, in the computational view.

IJCAI Conference 2022 Conference Paper

Optimal Anonymous Independent Reward Scheme Design

• Mengjing Chen
• Pingzhong Tang
• Zihe Wang
• Shenke Xiao
• Xiwang Yang

We consider designing reward schemes that incentivize agents to create high-quality content (e. g. , videos, images, text, ideas). The problem is at the center of a real-world application where the goal is to optimize the overall quality of generated content on user-generated content platforms. We focus on anonymous independent reward schemes (AIRS) that only take the quality of an agent's content as input. We prove the general problem is NP-hard. If the cost function is convex, we show the optimal AIRS can be formulated as a convex optimization problem and propose an efficient algorithm to solve it. Next, we explore the optimal linear reward scheme and prove it has a 1/2-approximation ratio, and the ratio is tight. Lastly, we show the proportional scheme can be arbitrarily bad compared to AIRS.

TCS Journal 2022 Journal Article

Optimal pricing policy design for selling cost-reducing innovation in Cournot games

• Mengjing Chen
• Haoqiang Huang
• Weiran Shen
• Pingzhong Tang
• Zihe Wang
• Jie Zhang

In a marketplace where a number of firms produce and sell a homogeneous product, an innovator develops cost-cutting manufacturing technology and decides to sell it to various firms in the form of a license for profit. Given the innovator's license pricing policy, each firm independently decides whether to purchase the innovation license and how many products to produce. To put it simply, the firms are then in a Cournot market in which the product price is a decreasing function of the total amount of the product on the market. Both the innovator and the firms are acting out of self-interest and look to maximize their utilities. We consider the problem of designing optimal pricing policies for the innovator. A pricing policy could be in the form of a one-off upfront fee, a per-unit royalty fee, or a hybrid of both. Building upon the results of Segal [1], we first show that in a properly designed pricing policy, it is a strictly dominant strategy for the firms to accept the pricing policy, and that this constitutes the unique Nash equilibrium of the game. For the hybrid-fee policy, we devise an algorithm that computes the optimal price in time O ( n 3 ), where n is the number of firms. For the royalty-fee policy, we show that the problem is captured by convex quadratic programming and can be solved in time O ( n 6 L 2 ), where L is the number of input bits. For the upfront-fee policy, we show the optimal policy problem is NP-complete and we devise an FPTAS algorithm. Moreover, we compare the revenue achievable through the above three pricing policies when all firms are identical.

AAAI Conference 2020 Conference Paper

Bounded Incentives in Manipulating the Probabilistic Serial Rule

• Zihe Wang
• Zhide Wei
• Jie Zhang

The Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem. However, Probabilistic Serial is not incentive-compatible, thereby these desirable properties only hold for the agents’ declared preferences, rather than their genuine preferences. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism and would subvert the very foundation of adopting the mechanism in practice. In this paper, we characterize the extent to which an individual agent can increase its utility by strategic manipulation. We show that the incentive ratio of the mechanism is 3 2. That is, no agent can misreport its preferences such that its utility becomes more than 1. 5 times of what it is when reports truthfully. This ratio is a worst-case guarantee by allowing an agent to have complete information about other agents’ reports and to figure out the best response strategy even if it is computationally intractable in general. To complement this worst-case study, we further evaluate an agent’s utility gain on average by experiments. The experiments show that an agent’ incentive in manipulating the rule is very limited. These results shed some light on the robustness of Probabilistic Serial against strategic manipulation, which is one step further than knowing that it is not incentive-compatible.

AAAI Conference 2020 Conference Paper

Optimal Common Contract with Heterogeneous Agents

• Shenke Xiao
• Zihe Wang
• Mengjing Chen
• Pingzhong Tang
• Xiwang Yang

We consider the principal-agent problem with heterogeneous agents. Previous works assume that the principal signs independent incentive contracts with every agent to make them invest more efforts on the tasks. However, in many circumstances, these contracts need to be identical for the sake of fairness. We investigate the optimal common contract problem. To our knowledge, this is the first attempt to consider this natural and important generalization. We first show this problem is NP-complete. Then we provide a dynamic programming algorithm to compute the optimal contract in O(n2 m) time, where n, m are the number of agents and actions, under the assumption that the agents’ cost functions obey increasing difference property. At last, we generalize the setting such that each agent can choose to directly produce a reward in [0, 1]. We provide an O(log n)-approximate algorithm for this generalization.

AAAI Conference 2019 Conference Paper

Making Money from What You Know – How to Sell Information?

• Shani Alkoby
• Zihe Wang
• David Sarne
• Pingzhong Tang

Information plays a key role in many decision situations. The rapid advancement in communication technologies makes information providers more accessible, and various information providing platforms can be found nowadays, most of which are strategic in the sense that their goal is to maximize the providers’ expected profit. In this paper, we consider the common problem of a strategic information provider offering prospective buyers information which can disambiguate uncertainties the buyers have, which can be valuable for their decision making. Unlike prior work, we do not limit the information provider’s strategy to price setting but rather enable her flexibility over the way information is sold, specifically enabling querying about specific outcomes and the elimination of a subset of non-true world states alongside the traditional approach of disclosing the true world state. We prove that for the case where the buyer is self-interested (and the information provider does not know the true world state beforehand) all three methods (i. e. , disclosing the true worldstate value, offering to check a specific value, and eliminating a random value) are equivalent, yielding the same expected profit to the information provider. For the case where buyers are human subjects, using an extensive set of experiments we show that the methods result in substantially different outcomes. Furthermore, using standard machine learning techniques the information provider can rather accurately predict the performance of the different methods for new problem settings, hence substantially increase profit.

IJCAI Conference 2018 Conference Paper

Ex-post IR Dynamic Auctions with Cost-per-Action Payments

• Weiran Shen
• Zihe Wang
• Song Zuo

Motivated by online ad auctions, we consider a repeated auction between one seller and many buyers, where each buyer only has an estimation of her value in each period until she actually receives the item in that period. The seller is allowed to conduct a dynamic auction but must guarantee ex-post individual rationality. In this paper, we use a structure that we call credit accounts to enable a general reduction from any incentive compatible and ex-ante individual rational dynamic auction to an approximate incentive compatible and ex-post individually rational dynamic auction with credit accounts. Our reduction obtains stronger individual rationality guarantees at the cost of weaker incentive compatibility. Surprisingly, our reduction works without any common knowledge assumption. Finally, as a complement to our reduction, we prove that there is no non-trivial auction that is exactly incentive compatible and ex-post individually rational under this setting.

AAMAS Conference 2018 Conference Paper

Ex-post IR Dynamic Auctions with Cost-per-action Payments

• Weiran Shen
• Zihe Wang
• Song Zuo

Consider a repeated auction between one seller and many buyers, where each buyer only has an estimation of her value in each period until she actually receives the item in that period. The seller is allowed to conduct a dynamic auction to sell the items but must guarantee ex-post individual rationality. In other words, if the buyer realized that her value of the item she just received was zero, she did not need to pay anything. Unlike the clicks on the ads, these actions are private information only observable by the buyers (advertisers). Hence they may have incentives to misreport the user actions, because they can pay less under cost-per-action payment schemes with ex-post individual rationality guarantees. In this paper, we use a structure that we call credit accounts to enable a general reduction from any incentive compatible and ex-ante individual rational dynamic auction to an approximate incentive compatible and ex-post individually rational dynamic auction with credit accounts. Our reduction can obtain stronger individual rationality guarantees at of the cost of weaker incentive compatibility. Surprisingly, our reduction works without making any common knowledge assumptions. Finally, as a complement to our reduction, we prove that there is no non-trivial auction that is exactly incentive compatible and ex-post individually rational under this setting.

AAAI Conference 2017 Conference Paper

Computational Issues in Time-Inconsistent Planning

• Pingzhong Tang
• Yifeng Teng
• Zihe Wang
• Shenke Xiao
• Yichong Xu

Time-inconsistency refers to a paradox in decision making where agents exhibit inconsistent behaviors over time. Examples are procrastination where agents tend to postpone easy tasks, and abandonments where agents start a plan and quit in the middle. To capture such behaviors and to quantify inefficiency caused by such behaviors, Kleinberg and Oren (2014) propose a graph model with a certain cost structure and initiate the study of several interesting computation problems: 1) cost ratio: the worst ratio between the actual cost of the agent and the optimal cost, over all the graph instances; 2) motivating subgraph: how to motivate the agent to reach the goal by deleting nodes and edges; 3) Intermediate rewards: how to incentivize agents to reach the goal by placing intermediate rewards. Kleinberg and Oren give partial answers to these questions, but the main problems are open. In this paper, we give answers to all three open problems. First, we show a tight upper bound of cost ratio for graphs, and confirm the conjecture by Kleinberg and Oren that Akerlof’s structure is indeed the worst case for cost ratio. Second, we prove that finding a motivating subgraph is NP-hard, showing that it is generally inefficient to motivate agents by deleting nodes and edges in the graph. Last but not least, we show that computing a strategy to place minimum amount of total reward is also NP-hard and we provide a 2napproximation algorithm.

AAMAS Conference 2017 Conference Paper

Hotelling-Downs Model with Limited Attraction

• Weiran Shen
• Zihe Wang

IJCAI Conference 2015 Conference Paper

Optimal Auctions for Partially Rational Bidders

• Zihe Wang
• Pingzhong Tang

We investigate the problem of revenue optimal mechanism design [Myerson, 1981] under the context of the partial rationality model, where buyers randomize between two modes: rational and irrational. When a buyer is irrational (can be thought of as lazy), he acts according to certain fixed strategies, such as bidding his true valuation. The seller cannot observe the buyer’s valuation, or his rationality mode, but treat them as random variables from known distributions. The seller’s goal is to design a single-shot auction that maximizes her expected revenue. A minor generalization as it may seem, our findings are in sharp contrast to Myerson’s theory on the standard rational bidder case. In particular, we show that, even for the simplest setting with one buyer, direct value revelation loses generality. However, we do show that, in terms of revenue, the optimal value-revelation and type-revelation mechanisms are equivalent. In addition, the posted-price mechanism is no longer optimal. In fact, the more complicated the mechanism, the higher the revenue. For the case where there are multiple bidders with IID uniform valuations, we show that when the irrational buyers are truthful, first price auction yields more revenue than second price auction.