Weiran Shen

AAAI Conference 2026 Conference Paper

The Power of Initial Investigation in Audit Games

• Ren Liu
• Weiran Shen

Audit games are an important variant of the Stackelberg security game, a widely studied game-theoretic model over the past years. It has been acknowledged that a pre-audit phase can notably enhance the audit's efficiency by informing and directing the following audit procedures. In this paper, we model the above process with a two-stage audit game. The game encompasses two stages: an investigation stage where the auditor gathers information about potential policy breaches, and an audit stage where the auditor allocates the audit resources based on the investigation results. We formulate the problem as a set of mathematical programs. Due to the non-convexity of the programs, we consider a restricted strategy space and show that the optimal strategy in the restricted space can be determined by solving a polynomial number of convex optimization problems. Finally, we conduct extensive experiments to evaluate the effect of introducing the initial investigation stage and our algorithm. Our experiments show that even a small budget for the initial investigations can significantly enhance the defender's utility.

IJCAI Conference 2025 Conference Paper

Public Signaling in Markets with Information Asymmetry Using a Limited Number of Signals

• Xu Zhao
• Ren Liu
• Weiran Shen

Consider a market with a seller and many buyers. The seller has a kind of item for sale to the buyers. The items have a quality and each buyer has a private type. The quality is only known to the seller, and the buyers only have a prior belief of the quality. A third party (e. g. , intermediaries or product reviewers) is able to reveal information about the actual quality by using a so-called signaling scheme. After receiving the information, buyers can update their beliefs accordingly and decide whether to buy the items. We consider the third party's problem of maximizing the purchasing probability by sending signals. However, the optimal signaling scheme has implementation issues, as the number of signals in the optimal scheme is the same as the number of buyer types, which can be exceedingly large or even infinite. We therefore investigate whether a finite and limited set of signals could still approximate the performance of the optimal signaling scheme. Unfortunately, our results show that with a finite number of signals, no signaling scheme can achieve a certain fraction of the performance of the optimal signaling scheme. This limitation persists even with the regularity or the monotone hazard rate assumption. Nevertheless, we identify a mild technical condition under which the third party can approximate the optimal performance within a constant factor by employing only two signals. We also conduct extensive experiments to substantiate our theoretic results. These experiments compare the performance of using a small signal set across different value distributions. Despite the negative results, our experiment results show that using only a small number of signals is able to achieve a fairly reasonable performance in average cases.

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.

ICAPS Conference 2024 Conference Paper

A Fast Algorithm for k-Memory Messaging Scheme Design in Dynamic Environments with Uncertainty

• Zhikang Fan 0001
• Weiran Shen

We study the problem of designing the optimal k-memory messaging scheme in a dynamic environment. Specifically, a sender, who can perfectly observe the state of a dynamic environment but cannot take actions, aims to persuade an uninformed, far-sighted receiver to take actions to maximize the long-term utility of the sender, by sending messages. We focus on k-memory messaging schemes, i. e. , at each time step, the sender

TCS Journal 2024 Journal Article

A mechanism design approach for multi-party machine learning

• Mengjing Chen
• Yang Liu
• Weiran Shen
• Yiheng Shen
• Pingzhong Tang
• Qiang Yang

In a multi-party machine learning system, different parties cooperate on optimizing towards better models by sharing data in a privacy-preserving way. A major challenge in learning is the incentive issue. For example, if there is competition among the parties, one may strategically hide their data to prevent other parties from getting better models. In this paper, we study the problem through the lens of mechanism design and incorporate the features of multi-party learning in our setting. First, each agent's valuation has externalities that depend on others' types and actions. Second, each agent can only misreport a type lower than his true type, but not the other way round. We provide the optimal truthful mechanism in the separable utility setting, as well as necessary and sufficient conditions for truthful mechanisms in general cases. Finally, we propose an algorithm to find the desirable mechanism that is truthful, individually rational, efficient and weakly budget-balanced, and analyze the computational complexity of the algorithm.

AIJ Journal 2024 Journal Article

An extensive study of security games with strategic informants

• Weiran Shen
• Minbiao Han
• Weizhe Chen
• Taoan Huang
• Rohit Singh
• Haifeng Xu
• Fei Fang

Over the past years, game-theoretic modeling for security and public safety issues (also known as security games) have attracted intensive research attention and have been successfully deployed in many real-world applications for fighting, e. g. , illegal poaching, fishing and urban crimes. However, few existing works consider how information from local communities would affect the structure of these games. In this paper, we systematically investigate how a new type of players – strategic informants who are from local communities and may observe and report upcoming attacks – affects the classic defender-attacker security interactions. Characterized by a private type, each informant has a utility structure that drives their strategic behaviors. For situations with a single informant, we capture the problem as a 3-player extensive-form game and develop a novel solution concept, Strong Stackelberg-perfect Bayesian equilibrium, for the game. To find an optimal defender strategy, we establish that though the informant can have infinitely many types in general, there always exists an optimal defense plan using only a linear number of patrol strategies; this succinct characterization then enables us to efficiently solve the game via linear programming. For situations with multiple informants, we show that there is also an optimal defense plan with only a linear number of patrol strategies that admits a simple structure based on plurality voting among multiple informants. Finally, we conduct extensive experiments to study the effect of the strategic informants and demonstrate the efficiency of our algorithm. Our experiments show that the existence of such informants significantly increases the defender's utility. Even though the informants exhibit strategic behaviors, the information they supply holds great value as defensive resources. Compared to existing works, our study leads to a deeper understanding on the role of informants in such defender-attacker interactions.

IJCAI Conference 2024 Conference Paper

Optimal Auction Design with User Coupons in Advertising Systems

• Xiaodong Liu
• Zhikang Fan
• Yiming Ding
• Yuan Guo
• Lihua Zhang
• Changcheng Li
• Dongying Kong
• Han Li

Online advertising is a major revenue source for most Internet companies. The advertising opportunities are usually sold to advertisers through auctions that take into account the bids of the advertisers and the click-through rates (CTRs) and the conversion rates (CVRs) of the users. Standard auction design theory perceives both the CTRs and the CVRs as constants. We consider a new auction mechanism that offers coupons to users when displaying the ads. Such coupons allow the user to buy the advertisers' products or services at a lower price, which increases both the CTRs and the CVRs of the ads. In this paper, we formulate the problem mathematically and perform a systematic analysis. We characterize the set of individually rational and incentive compatible mechanisms in our setting. Based on the characterization, we identify the optimal strategy of offering coupons that maximizes the platform's expected revenue. We also conduct extensive experiments on both synthetic data and industrial data. Our experiment results show that our mechanism significantly improves both the revenue and welfare of the platform, thereby creating a win-win situation for all parties including the platform, the advertisers, and the user.

AAAI Conference 2024 Conference Paper

Simultaneous Optimization of Bid Shading and Internal Auction for Demand-Side Platforms

• Yadong Xu
• Bonan Ni
• Weiran Shen
• Xun Wang
• Zichen Wang
• Yinsong Xue
• Pingzhong Tang

Online advertising has been one of the most important sources for industry's growth, where the demand-side platforms (DSP) play an important role via bidding to the ad exchanges on behalf of their advertiser clients. Since more and more ad exchanges have shifted from second to first price auctions, it is challenging for DSPs to adjust bidding strategy in the volatile environment. Recent studies on bid shading in first-price auctions may have limited performance due to relatively strong hypotheses about winning probability distribution. Moreover, these studies do not consider the incentive of advertiser clients, which can be crucial for a reliable advertising platform. In this work, we consider both the optimization of bid shading technique and the design of internal auction which is ex-post incentive compatible (IC) for the management of a DSP. Firstly, we prove that the joint design of bid shading and ex-post IC auction can be reduced to choosing one monotone bid function for each advertiser without loss of optimality. Then we propose a parameterized neural network to implement the monotone bid functions. With well-designed surrogate loss, the objective can be optimized in an end-to-end manner. Finally, our experimental results demonstrate the effectiveness and superiority of our algorithm.

IJCAI Conference 2023 Conference Paper

Auto-bidding with Budget and ROI Constrained Buyers

• Xiaodong Liu
• Weiran Shen

In online advertising markets, an increasing number of advertisers are adopting auto-bidders to buy advertising slots. This tool simplifies the process of optimizing bids based on various financial constraints. In our study, we focus on second-price auctions where bidders have both private budget and private ROI (return on investment) constraints. We formulate the auto-bidding system design problem as a mathematical program and analyze the auto-bidders' bidding strategy under such constraints. We demonstrate that our design ensures truthfulness, i. e. , among all pure and mixed strategies, always reporting the truthful budget and ROI is an optimal strategy for the bidders. Although the program is non-convex, we provide a fast algorithm to compute the optimal bidding strategy for the bidders based on our analysis. We also study the welfare and provide a lower bound for the PoA (price of anarchy). Moreover, we prove that if all bidders utilize our auto-bidding system, a Bayesian Nash equilibrium exists. We provide a sufficient condition under which the iterated best response process converges to such an equilibrium. Finally, we conduct extensive experiments to empirically evaluate the effectiveness of our design.

ICLR Conference 2023 Conference Paper

Deep Generative Modeling on Limited Data with Regularization by Nontransferable Pre-trained Models

• Yong Zhong
• Hongtao Liu
• Xiaodong Liu
• Fan Bao
• Weiran Shen
• Chongxuan Li

Deep generative models (DGMs) are data-eager because learning a complex model on limited data suffers from a large variance and easily overfits. Inspired by the classical perspective of the bias-variance tradeoff, we propose regularized deep generative model (Reg-DGM), which leverages a nontransferable pre-trained model to reduce the variance of generative modeling with limited data. Formally, Reg-DGM optimizes a weighted sum of a certain divergence and the expectation of an energy function, where the divergence is between the data and the model distributions, and the energy function is defined by the pre-trained model w.r.t. the model distribution. We analyze a simple yet representative Gaussian-fitting case to demonstrate how the weighting hyperparameter trades off the bias and the variance. Theoretically, we characterize the existence and the uniqueness of the global minimum of Reg-DGM in a non-parametric setting and prove its convergence with neural networks trained by gradient-based methods. Empirically, with various pre-trained feature extractors and a data-dependent energy function, Reg-DGM consistently improves the generation performance of strong DGMs with limited data and achieves competitive results to the state-of-the-art methods. Our implementation is available at https://github.com/ML-GSAI/Reg-ADA-APA.

IJCAI Conference 2023 Conference Paper

Revenue Maximization Mechanisms for an Uninformed Mediator with Communication Abilities

• Zhikang Fan
• Weiran Shen

Consider a market where a seller owns an item for sale and a buyer wants to purchase it. Each player has private information, known as their type. It can be costly and difficult for the players to reach an agreement through direct communication. However, with a mediator as a trusted third party, both players can communicate privately with the mediator without worrying about leaking too much or too little information. The mediator can design and commit to a multi-round communication protocol for both players, in which they update their beliefs about the other player's type. The mediator cannot force the players to trade but can influence their behaviors by sending messages to them. We study the problem of designing revenue-maximizing mechanisms for the mediator. We show that the mediator can, without loss of generality, focus on a set of direct and incentive-compatible mechanisms. We then formulate this problem as a mathematical program and provide an optimal solution in closed form under a regularity condition. Our mechanism is simple and has a threshold structure. We also discuss some interesting properties of the optimal mechanism, such as situations where the mediator may lose money.

AAMAS Conference 2023 Conference Paper

Revenue Maximization Mechanisms for an Uninformed Mediator with Communication Abilities

• Zhikang Fan
• Weiran Shen

Consider a market where a seller owns an item for sale and a buyer wants to buy an item, and both players have a private type. We study the problem of designing revenue-maximizing mechanisms for a mediator who has no private information but can privately communicate with players. We show that the mediator can, without loss of generality, focus on the set of direct and incentive-compatible mechanisms. Then we formulate this problem as a mathematical program. Moreover, we give an optimal solution to the optimization problem in closed form under certain technical conditions.

NeurIPS Conference 2022 Conference Paper

Inverse Game Theory for Stackelberg Games: the Blessing of Bounded Rationality

• Jibang Wu
• Weiran Shen
• Fei Fang
• Haifeng Xu

Optimizing strategic decisions (a. k. a. computing equilibrium) is key to the success of many non-cooperative multi-agent applications. However, in many real-world situations, we may face the exact opposite of this game-theoretic problem --- instead of prescribing equilibrium of a given game, we may directly observe the agents' equilibrium behaviors but want to infer the underlying parameters of an unknown game. This research question, also known as inverse game theory, has been studied in multiple recent works in the context of Stackelberg games. Unfortunately, existing works exhibit quite negative results, showing statistical hardness and computational hardness, assuming follower's perfectly rational behaviors. Our work relaxes the perfect rationality agent assumption to the classic quantal response model, a more realistic behavior model of bounded rationality. Interestingly, we show that the smooth property brought by such bounded rationality model actually leads to provably more efficient learning of the follower utility parameters in general Stackelberg games. Systematic empirical experiments on synthesized games confirm our theoretical results and further suggest its robustness beyond the strict quantal response model.

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.

AIJ Journal 2021 Journal Article

Coalitional permutation manipulations in the Gale-Shapley algorithm

• Weiran Shen
• Yuan Deng
• Pingzhong Tang

In this paper, we consider permutation manipulations by any subset of women in the men-proposing version of the Gale-Shapley algorithm. This paper is motivated by the college admissions process in China. Our results also answer an open problem on what can be achieved by permutation manipulations. We present an efficient algorithm to find a strategy profile such that the induced matching is stable and Pareto-optimal (in the set of all achievable stable matchings) while the strategy profile itself is inconspicuous. Surprisingly, we show that such a strategy profile actually forms a Nash equilibrium of the manipulation game. In the end, we show that it is NP-complete to find a manipulation that is strictly better for all members of the coalition. This result demonstrates a sharp contrast between weakly better off outcomes and strictly better-off outcomes.

AAAI Conference 2021 Conference Paper

Coupon Design in Advertising Systems

• Weiran Shen
• Pingzhong Tang
• Xun Wang
• Yadong Xu
• Xiwang Yang

Online platforms sell advertisements via auctions (e. g. , VCG and GSP auction) and revenue maximization is one of the most important tasks for them. Many revenue increment methods are proposed, like reserve pricing, boosting, coupons and so on. The novelty of coupons rests on the fact that coupons are optional for advertisers while the others are compulsory. Recent studies on coupons have limited applications in advertising systems because they only focus on second price auctions and do not consider the combination with other methods. In this work, we study the coupon design problem for revenue maximization in the widely used VCG auction. Firstly, we examine the bidder strategies in the VCG auction with coupons. Secondly, we cast the coupon design problem into a learning framework and propose corresponding algorithms using the properties of VCG auction. Then we further study how to combine coupons with reserve pricing in our framework. Finally, extensive experiments are conducted to demonstrate the effectiveness of our algorithms based on both synthetic data and industrial data.

AAAI Conference 2020 Conference Paper

Reinforcement Mechanism Design: With Applications to Dynamic Pricing in Sponsored Search Auctions

• Weiran Shen
• Binghui Peng
• Hanpeng Liu
• Michael Zhang
• Ruohan Qian
• Yan Hong
• Zhi Guo
• Zongyao Ding

In many social systems in which individuals and organizations interact with each other, there can be no easy laws to govern the rules of the environment, and agents’ payoffs are often influenced by other agents’ actions. We examine such a social system in the setting of sponsored search auctions and tackle the search engine’s dynamic pricing problem by combining the tools from both mechanism design and the AI domain. In this setting, the environment not only changes over time, but also behaves strategically. Over repeated interactions with bidders, the search engine can dynamically change the reserve prices and determine the optimal strategy that maximizes the profit. We first train a buyer behavior model, with a real bidding data set from a major search engine, that predicts bids given information disclosed by the search engine and the bidders’ performance data from previous rounds. We then formulate the dynamic pricing problem as an MDP and apply a reinforcement-based algorithm that optimizes reserve prices over time. Experiments demonstrate that our model outperforms static optimization strategies including the ones that are currently in use as well as several other dynamic ones.

IJCAI Conference 2020 Conference Paper

When to Follow the Tip: Security Games with Strategic Informants

• Weiran Shen
• Weizhe Chen
• Taoan Huang
• Rohit Singh
• Fei Fang

Although security games have attracted intensive research attention over the past years, few existing works consider how information from local communities would affect the game. In this paper, we introduce a new player -- a strategic informant, who can observe and report upcoming attacks -- to the defender-attacker security game setting. Characterized by a private type, the informant has his utility structure that leads to his strategic behaviors. We model the game as a 3-player extensive-form game and propose a novel solution concept of Strong Stackelberg-perfect Bayesian equilibrium. To compute the optimal defender strategy, we first show that although the informant can have infinitely many types in general, the optimal defense plan can only include a finite (exponential) number of different patrol strategies. We then prove that there exists a defense plan with only a linear number of patrol strategies that achieve the optimal defender's utility, which significantly reduces the computational burden and allows us to solve the game in polynomial time using linear programming. Finally, we conduct extensive experiments to show the effect of the strategic informant and demonstrate the effectiveness of our algorithm.

AAMAS Conference 2019 Conference Paper

Automated Mechanism Design via Neural Networks

• Weiran Shen
• Pingzhong Tang
• Song Zuo

Using AI approaches to automatically design mechanisms has been a central research mission at the interface of AI and economics. Previous approaches that attempt to design revenue optimal auctions for the multi-dimensional settings fall short in at least one of the three aspects: 1) representation — search in a space that probably does not even contain the optimal mechanism; 2) exactness — finding a mechanism that is either not truthful or far from optimal; 3) domain dependence — need a different design for different environment settings. To resolve the three difficulties, in this paper, we put forward a unified neural network based framework that automatically learns to design revenue optimal mechanisms. Our framework consists of a mechanism network that takes an input distribution for training and outputs a mechanism, as well as a buyer network that takes a mechanism as input and output an action. Such a separation in design mitigates the difficulty to impose incentive compatibility constraints on the mechanism, by making it a rational choice of the buyer. As a result, our framework easily overcomes the previously mentioned difficulty in incorporating IC constraints and always returns exactly incentive compatible mechanisms. We then applied our framework to a number of multi-item auction design settings, for a few of which the theoretically optimal mechanisms are unknown. We then go on to theoretically prove that the mechanisms found by our framework are indeed optimal.

AAMAS Conference 2019 Conference Paper

Buyer Signaling Games in Auctions

• Weiran Shen
• Pingzhong Tang
• Yulong Zeng

We consider an auction setting where a seller sells one item to several buyers. Before a buyer’s type is realized, he can commit himself to a so-called signal scheme. Mathematically, a signal scheme can be regarded as a linear decomposition of his prior type distribution into a probability distribution over a set of posterior distributions, each of which the seller can use a revenue optimal auction tailored for that distribution. It is known, from the literature of Bayes persuasion, that such signal schemes can lead to utility increase for both the seller and the buyers. Our goal, is to analyze how a buyer should signal his distribution, given that other buyers may also signal their distributions. In other words, we want to find an equilibrium profile of signal schemes. We obtain the closed-form solution for the single buyer case with regular distributions, and the multiple buyers case with symmetric type distributions under certain conditions. To prove our technique results, we also obtain some interesting intermediate results. In particular, we show that, if each buyer’s signal scheme is to decompose his prior distribution into a set of posteriors that has the same virtual value function (in the exact sense of Myerson’s virtual value function), his expected utility is equal to his utility in a first price auction game where his bidding function is always his virtual value function. Furthermore, perhaps surprisingly, we show that, certain distributions, including the uniform distribution, satisfy the property that every buyer’s optimal signal scheme is indeed to decompose the prior into a set of posteriors that has the same virtual value function. As a result, we give the closed-form of an equilibrium profile of signal schemes for these cases.

IJCAI Conference 2019 Conference Paper

Dispatching Through Pricing: Modeling Ride-Sharing and Designing Dynamic Prices

• Mengjing Chen
• Weiran Shen
• Pingzhong Tang
• Song Zuo

Over the past few years, ride-sharing has emerged as an effective way to relieve traffic congestion. A key problem for the ride-sharing platforms is to come up with a revenue-optimal (or GMV-optimal) pricing scheme and a vehicle dispatching policy that incorporate geographic and temporal information. In this paper, we aim to tackle this problem via an economic approach. Modeled naively, the underlying optimization problem may be non-convex and thus hard to solve. To this end, we use a so-called ``ironing'' technique to convert the problem into an equivalent convex optimization one via a clean Markov decision process (MDP) formulation, where the states are the driver distributions and the decision variables are the prices for each pair of locations. Our main finding is an efficient algorithm that computes the exact revenue-optimal (or GMV-optimal) randomized pricing scheme, which naturally induces the accompany vehicle dispatching policy. We also conduct empirical evaluations of our solution through real data of a major ride-sharing platform and show its advantages over fixed pricing schemes as well as several prevalent surge-based pricing schemes.

AAAI Conference 2019 Conference Paper

Learning Optimal Strategies to Commit To

• Binghui Peng
• Weiran Shen
• Pingzhong Tang
• Song Zuo

Over the past decades, various theories and algorithms have been developed under the framework of Stackelberg games and part of these innovations have been fielded under the scenarios of national security defenses and wildlife protections. However, one of the remaining difficulties in the literature is that most of theoretical works assume full information of the payoff matrices, while in applications, the leader often has no prior knowledge about the follower’s payoff matrix, but may gain information about the follower’s utility function through repeated interactions. In this paper, we study the problem of learning the optimal leader strategy in Stackelberg (security) games and develop novel algorithms as well as new hardness results.

ICML Conference 2019 Conference Paper

Learning to Clear the Market

• Weiran Shen
• Sébastien Lahaie
• Renato Paes Leme

The problem of market clearing is to set a price for an item such that quantity demanded equals quantity supplied. In this work, we cast the problem of predicting clearing prices into a learning framework and use the resulting models to perform revenue optimization in auctions and markets with contextual information. The economic intuition behind market clearing allows us to obtain fine-grained control over the aggressiveness of the resulting pricing policy, grounded in theory. To evaluate our approach, we fit a model of clearing prices over a massive dataset of bids in display ad auctions from a major ad exchange. The learned prices outperform other modeling techniques in the literature in terms of revenue and efficiency trade-offs. Because of the convex nature of the clearing loss function, the convergence rate of our method is as fast as linear regression.

AAMAS Conference 2018 Conference Paper

A Closed-Form Characterization of Buyer Signaling Schemes in Monopoly Pricing

• Weiran Shen
• Pingzhong Tang
• Yulong Zeng

We consider a setting where a revenue maximizing monopolist sells a single item to a buyer. A mediator first collects the buyer’s value and can reveal extra information about the buyer’s value by sending signals. Mathematically, a signal scheme can be thought of as a decomposition of the prior value distribution into a linear combination of posterior value distributions, and based on each of them, the monopolist separately posts a price. According to the theory of Bayesian persuasion, a well-designed signal scheme can lead to utility improvements for both the monopolist and the buyer. We put forward a novel technique to analyze the effects of signal schemes of the mediator. Using this technique, we are able to construct explicitly a closed-form solution, and thus characterize the set of seller-buyer utility pairs achievable by any signal scheme, for any prior type distribution. Our result generalizes a well-known result by Bergemann et. al. , who derive a characterization for the same problem but only restricted to the discrete distribution case. Similar to the result derived by Bergermann et. al. , we show that the set of seller and buyer utility pairs achievable form a triangle: any point within the triangle can be achieved by an explicitly constructed signal scheme and any point outside the triangle cannot be achievable by any such scheme. Our result is obtained by establishing the endpoints of the triangle: one corresponds to the point where the buyer obtains the highest utility among all schemes, another corresponds to the point where the buyer obtains zero utility and the seller has the lowest possible revenue, and the third corresponds to the point where the buyer has zero utility while the seller extracts full social surplus. We then prove that the triangle described fully characterizes all possible signal schemes.

AAMAS Conference 2018 Conference Paper

Buyer-Optimal Distribution

• Weiran Shen
• Pingzhong Tang
• Yulong Zeng

We consider the problem of how a buyer can optimize his utility if he can choose his own valuation distribution in a prior-dependent auction, such as the revenue-optimal auction [18]. The problem is motivated by and equivalent to a type of the market segmentation problem [3], where a principal tries to select a subset of agents (i. e. , a market segment) from the set of all agents, each with a constant valuation, to attend a posted price auction for selling multiple identical items, in order to maximize the total utilities of the agents selected into the market segment. Our results are closed-form solutions in both the single buyer case as well as the multi-buyer case where several buyers best response to each other. Interestingly, in the two-buyer case, essentially all commitments that satisfy a certain condition are equilibria.

AAAI Conference 2018 Conference Paper

Coalition Manipulation of Gale-Shapley Algorithm

• Weiran Shen
• Pingzhong Tang
• Yuan Deng

It is well-known that the Gale-Shapley algorithm is not truthful for all agents. Previous studies in this category concentrate on manipulations using incomplete preference lists by a single woman and by the set of all women. Little is known about manipulations by a subset of women. In this paper, we consider manipulations by any subset of women with arbitrary preferences. We show that a strong Nash equilibrium of the induced manipulation game always exists among the manipulators and the equilibrium outcome is unique and Pareto-dominant. In addition, the set of matchings achievable by manipulations has a lattice structure. We also examine the super-strong Nash equilibrium in the end.

AAMAS Conference 2018 Conference Paper

Coalitional Permutation Manipulations in the Gale-Shapley Algorithm

• Yuan Deng
• Weiran Shen
• Pingzhong Tang

In this paper, we consider permutation manipulations by any subset of women in the Gale-Shapley algorithm. This paper is motivated by the college admissions process in China. Our results also answer an open problem on what can be achieved by permutation manipulations. We present an efficient algorithm to find a strategy profile such that the induced matching is stable and Pareto-optimal while the strategy profile itself is inconspicuous. Surprisingly, we show that such a strategy profile actually forms a Nash equilibrium of the manipulation game. In the end, we show that it is NP-complete to find a manipulation that is strictly better for all members of the coalition. This result demonstrates a sharp contrast between weakly better-off outcomes and strictly better-off outcomes.

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.

AAMAS Conference 2017 Conference Paper

Hotelling-Downs Model with Limited Attraction

• Weiran Shen
• Zihe Wang

AAMAS Conference 2017 Conference Paper

Practical versus Optimal Mechanisms

• Weiran Shen
• Pingzhong Tang

Designing simple mechanisms with desirable revenue guarantees has become a major research agenda in the economics and computation community. However, few mechanisms have been actually applied in industry. In this paper, we aim to bridge the gap between the “simple versus optimal” theory and practice, and propose a class of parameterized mechanisms, tailored for the sponsored search auction settings. Our mechanisms can balance different objectives by simple parameter tuning, yet at the same time guarantee near optimal revenue in both theoretical and practical senses.