Kangning Wang 0001

SODA Conference 2025 Conference Paper

Majorized Bayesian Persuasion and Fair Selection

• Siddhartha Banerjee
• Kamesh Munagala
• Yiheng Shen 0001
• Kangning Wang 0001

STOC Conference 2025 Conference Paper

Six Candidates Suffice to Win a Voter Majority

• Moses Charikar
• Alexandra Lassota
• Prasanna Ramakrishnan
• Adrian Vetta
• Kangning Wang 0001

A cornerstone of social choice theory is Condorcet’s paradox which says that in an election where n voters rank m candidates it is possible that, no matter which candidate is declared the winner, a majority of voters would have preferred an alternative candidate. Instead, can we always choose a small committee of winning candidates that is preferred to any alternative candidate by a majority of voters? Elkind, Lang, and Saffidine raised this question and called such a committee a Condorcet winning set . They showed that winning sets of size 2 may not exist, but sets of size logarithmic in the number of candidates always do. In this work, we show that Condorcet winning sets of size 6 always exist, regardless of the number of candidates or the number of voters. More generally, we show that if α/1 − lnα ≥ 2/ k + 1, then there always exists a committee of size k such that less than an α fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all k ≥ 2. Our proof uses the probabilistic method and the minimax theorem, inspired by recent work on approximately stable committee selection . We construct a distribution over committees that performs sufficiently well (when compared against any candidate on any small subset of the voters) so that this distribution must contain a committee with the desired property in its support.

SODA Conference 2024 Conference Paper

Breaking the Metric Voting Distortion Barrier

• Moses Charikar
• Kangning Wang 0001
• Prasanna Ramakrishnan
• Hongxun Wu

SODA Conference 2024 Conference Paper

Fair Price Discrimination

• Siddhartha Banerjee
• Kamesh Munagala
• Yiheng Shen 0001
• Kangning Wang 0001

A seller is pricing identical copies of a good to a stream of unit-demand buyers. Each buyer has a value on the good as his private information. The seller only knows the empirical value distribution of the buyer population and chooses the revenue-optimal price. We consider a widely studied third-degree price discrimination model where an information intermediary with perfect knowledge of the arriving buyer's value sends a signal to the seller, hence changing the seller's posterior and inducing the seller to set a personalized posted price. Prior work of Bergemann, Brooks, and Morris (American Economic Review, 2015) has shown the existence of a signaling scheme that preserves seller revenue, while always selling the item, hence maximizing consumer surplus. In a departure from prior work, we ask whether the consumer surplus generated is fairly distributed among buyers with different values. To this end, we aim to maximize functions of buyers’ welfare that reward more balanced surplus allocations. Our main result is the surprising existence of a novel signaling scheme that simultaneously 8-approximates all welfare functions that are non-negative, monotonically increasing, symmetric, and concave, compared with any other signaling scheme. Classical examples of such welfare functions include the utilitarian social welfare, the Nash welfare, and the max-min welfare. Such a guarantee cannot be given by consumer-surplus-maximizing schemes — which are the ones typically studied in the literature. In addition, our scheme is socially efficient, and has the fairness property that buyers with higher values enjoy higher expected surplus, which is not always the case for existing schemes. * The full version of the paper can be accessed at https: //arxiv. org/abs/2305. 07006.

SODA Conference 2024 Conference Paper

Prior-Independent Auctions for Heterogeneous Bidders

• Guru Guruganesh
• Aranyak Mehta
• Di Wang 0005
• Kangning Wang 0001

SODA Conference 2023 Conference Paper

Optimal Pricing Schemes for an Impatient Buyer

• Yuan Deng
• Jieming Mao
• Balasubramanian Sivan
• Kangning Wang 0001

A patient seller aims to sell a good to an impatient buyer (i. e. , one who discounts utility over time). The buyer will remain in the market for a period of time T, and her private value is drawn from a publicly known distribution. What is the revenue-optimal pricing-curve (sequence of (price, time) pairs) for the seller? Is randomization of help here? Is the revenue-optimal pricing-curve computable in polynomial time? We answer these questions in this paper. We give an efficient algorithm for computing the revenue-optimal pricing curve. We show that pricing curves, that post a price at each point of time and let the buyer pick her utility maximizing time to buy, are revenue-optimal among a much broader class of sequential lottery mechanisms: namely, mechanisms that allow the seller to post a menu of lotteries at each point of time cannot get any higher revenue than pricing curves. We also show that the even broader class of mechanisms that allow the menu of lotteries to be adaptively set, can earn strictly higher revenue than that of pricing curves, and the revenue gap can be as big as the support size of the buyer's value distribution. * The full version of the paper can be accessed at https: //arxiv. org/abs/2106. 02149.

SODA Conference 2022 Conference Paper

Approximate Core for Committee Selection via Multilinear Extension and Market Clearing

• Kamesh Munagala
• Yiheng Shen 0001
• Kangning Wang 0001
• Zhiyi Wang

Motivated by civic problems such as participatory budgeting and multiwinner elections, we consider the problem of public good allocation: Given a set of indivisible projects (or candidates) of different sizes, and voters with different monotone utility functions over subsets of these candidates, the goal is to choose a budget-constrained subset of these candidates (or a committee) that provides fair utility to the voters. The notion of fairness we adopt is that of core stability from cooperative game theory: No subset of voters should be able to choose another blocking committee of proportionally smaller size that provides strictly larger utility to all voters that deviate. The core provides a strong notion of fairness, subsuming other notions that have been widely studied in computational social choice. It is well-known that an exact core need not exist even when utility functions of the voters are additive across candidates. We therefore relax the problem to allow approximation: Voters can only deviate to the blocking committee if after they choose any extra candidate (called an additament ), their utility still increases by an α factor. If no blocking committee exists under this definition, we call this an α -core. Our main result is that an α -core, for α < 67. 37, always exists when utilities of the voters are arbitrary monotone submodular functions, and this can be computed in polynomial time. This result improves to α < 9. 27 for additive utilities, albeit without the polynomial time guarantee. Our results are a significant improvement over prior work that only shows logarithmic approximations for the case of additive utilities. We complement our results with a lower bound of α > 1. 015 for submodular utilities, and a lower bound of any function in the number of voters and candidates for general monotone utilities.

STOC Conference 2022 Conference Paper

Approximately efficient bilateral trade

• Yuan Deng
• Jieming Mao
• Balasubramanian Sivan
• Kangning Wang 0001

We study bilateral trade between two strategic agents. The celebrated result of Myerson and Satterthwaite states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be efficient. I.e., no mechanism with these properties can guarantee a trade whenever buyer value exceeds seller cost. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, namely a constant fraction of the gains-from-trade attainable whenever buyer’s value weakly exceeds seller’s cost. In this work, we positively resolve this long-standing open question on constant-factor approximation, mentioned in several previous works, using a simple mechanism that obtains a 1/8.23 ≈ 0.121 fraction of the first-best.

STOC Conference 2020 Conference Paper

Approximately stable committee selection

• Zhihao Jiang
• Kamesh Munagala
• Kangning Wang 0001

In the committee selection problem, we are given m candidates, and n voters. Candidates can have different weights. A committee is a subset of candidates, and its weight is the sum of weights of its candidates. Each voter expresses an ordinal ranking over all possible committees. The only assumption we make on preferences is monotonicity: If S ⊆ S ′ are two committees, then any voter weakly prefers S ′ to S . We study a general notion of group fairness via stability: A committee of given total weight K is stable if no coalition of voters can deviate and choose a committee of proportional weight, so that all these voters strictly prefer the new committee to the existing one. Extending this notion to approximation, for parameter c ≥ 1, a committee S of weight K is said to be c -approximately stable if for any other committee S ′ of weight K ′, the fraction of voters that strictly prefer S ′ to S is strictly less than c K ′/ K . When c = 1, this condition is equivalent to classical core stability. The question we ask is: Does a c -approximately stable committee of weight at most any given value K always exist for constant c ? It is relatively easy to show that there exist monotone preferences for which c ≥ 2. However, even for simple and widely studied preference structures, a non-trivial upper bound on c has been elusive. In this paper, we show that c = O (1) for all monotone preference structures. Our proof proceeds via showing an existence result for a randomized notion of stability, and iteratively rounding the resulting fractional solution.