5 Search Results for "Wang, Kangning"

Document
DOI: 10.4230/LIPIcs.FORC.2026.14
Fair Multi-Agent Persuasion with Submodular Constraints

Authors: Yannan Bai, Kamesh Munagala, Yiheng Shen, and Davidson Zhu

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
We study the problem of selection in the context of Bayesian persuasion. We are given multiple agents with hidden values (or quality scores), to whom resources must be allocated by a welfare-maximizing decision-maker. An intermediary with knowledge of the agents' values seeks to influence the outcome of the selection by designing informative signals and providing tie-breaking policies, so that when the receiver maximizes welfare over the resulting posteriors, the expected utilities of the agents (where utility is defined as allocation times value) achieve certain fairness properties. The fairness measure we will use is majorization, which simultaneously approximately maximizes all symmetric, monotone, concave functions of the utilities. We consider the general setting where the allocation to the agents needs to respect arbitrary submodular constraints, as given by the corresponding polymatroid. We present a signaling policy that achieves a logarithmically approximate majorized policy in this setting, assuming the receiver is a (1+ε) approximate welfare maximizer. The approximation ratio is almost best possible, and that significantly outperforms generic results that only yield linear approximations. A key component of our result is a structural characterization showing that the vector of agent utilities for a given signaling policy defines the base polytope of a different polymatroid, a result that may be of independent interest. In addition, we show that an arbitrarily good additive approximation to this vector can be produced in (weakly) polynomial time via the multiplicative weights update method.
Cite as

Yannan Bai, Kamesh Munagala, Yiheng Shen, and Davidson Zhu. Fair Multi-Agent Persuasion with Submodular Constraints. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.FORC.2026.14,
  author =	{Bai, Yannan and Munagala, Kamesh and Shen, Yiheng and Zhu, Davidson},
  title =	{{Fair Multi-Agent Persuasion with Submodular Constraints}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.14},
  URN =		{urn:nbn:de:0030-drops-259872},
  doi =		{10.4230/LIPIcs.FORC.2026.14},
  annote =	{Keywords: Bayesian Persuasion, Fair Division, Submodular Optimization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.26
Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice

Authors: Guangya Cai

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study the problem of finding a fair linear scoring function over (numerical) attributes for top-k selection, ensuring fairness through a proportional representation constraint on the protected group. Existing algorithms do not scale efficiently, particularly in higher dimensions. Our hardness analysis shows that in more than two dimensions, no algorithm is likely to scale efficiently with respect to dataset size, and the computational complexity is likely to grow rapidly with dimensionality. However, the hardness results also provide key insights guiding algorithm design, leading to our two-pronged solution: (1) For small k, our analysis reveals a gap in the hardness barrier. By addressing various engineering challenges, including achieving efficient parallelism, we turn this potential of efficiency into an optimized geometry-based algorithm delivering substantial performance gains. (2) For large k, where the hardness is robust, we employ a practically efficient optimization-based algorithm which, despite being theoretically worse, achieves superior real-world performance. Experimental evaluations on real-world datasets then explore scenarios where worst-case behavior does not manifest, identifying areas critical to practical performance. Our solution achieves speedups of up to several orders of magnitude compared to the state of the art, an efficiency made possible through a tight integration of hardness analysis, algorithm design, practical engineering, and empirical evaluation.
Cite as

Guangya Cai. Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cai:LIPIcs.SoCG.2026.26,
  author =	{Cai, Guangya},
  title =	{{Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.26},
  URN =		{urn:nbn:de:0030-drops-258320},
  doi =		{10.4230/LIPIcs.SoCG.2026.26},
  annote =	{Keywords: Fairness, Top-k, Integration}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.105
Interactive Communication in Bilateral Trade

Authors: Jieming Mao, Renato Paes Leme, and Kangning Wang

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case of a one-round communication protocol. We define message complexity corresponding to the minimum number of interactive rounds necessary to achieve the best possible outcome. Our main result is that for bilateral trade, agents don't stop talking until they reach an efficient outcome: Either agents achieve an efficient allocation in finitely many rounds of communication; or the optimal communication protocol has infinite number of rounds. We show an important class of bilateral trade settings where efficient allocation is achievable with a small number of rounds of communication.
Cite as

Jieming Mao, Renato Paes Leme, and Kangning Wang. Interactive Communication in Bilateral Trade. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 105:1-105:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mao_et_al:LIPIcs.ITCS.2022.105,
  author =	{Mao, Jieming and Paes Leme, Renato and Wang, Kangning},
  title =	{{Interactive Communication in Bilateral Trade}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{105:1--105:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.105},
  URN =		{urn:nbn:de:0030-drops-157014},
  doi =		{10.4230/LIPIcs.ITCS.2022.105},
  annote =	{Keywords: Bayesian persuasion, bilateral trade, information design}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.74
Online Stochastic Matching with Edge Arrivals

Authors: Nick Gravin, Zhihao Gavin Tang, and Kangning Wang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by Gamlath et al., who showed that no online policy is better than the straightforward greedy algorithm, i.e., no online algorithm has a worst-case competitive ratio better than 0.5. In this work, we consider the bipartite matching problem with edge arrivals in a natural stochastic framework, i.e., Bayesian setting where each edge of the graph is independently realized according to a known probability distribution. We focus on a natural class of prune & greedy online policies motivated by practical considerations from a multitude of online matching platforms. Any prune & greedy algorithm consists of two stages: first, it decreases the probabilities of some edges in the stochastic instance and then runs greedy algorithm on the pruned graph. We propose prune & greedy algorithms that are 0.552-competitive on the instances that can be pruned to a 2-regular stochastic bipartite graph, and 0.503-competitive on arbitrary stochastic bipartite graphs. The algorithms and our analysis significantly deviate from the prior work. We first obtain analytically manageable lower bound on the size of the matching, which leads to a non-linear optimization problem. We further reduce this problem to a continuous optimization with a constant number of parameters that can be solved using standard software tools.
Cite as

Nick Gravin, Zhihao Gavin Tang, and Kangning Wang. Online Stochastic Matching with Edge Arrivals. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 74:1-74:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gravin_et_al:LIPIcs.ICALP.2021.74,
  author =	{Gravin, Nick and Tang, Zhihao Gavin and Wang, Kangning},
  title =	{{Online Stochastic Matching with Edge Arrivals}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{74:1--74:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.74},
  URN =		{urn:nbn:de:0030-drops-141438},
  doi =		{10.4230/LIPIcs.ICALP.2021.74},
  annote =	{Keywords: online matching, graph algorithms, prophet inequality}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.11
k-Regret Minimizing Set: Efficient Algorithms and Hardness

Authors: Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
We study the k-regret minimizing query (k-RMS), which is a useful operator for supporting multi-criteria decision-making. Given two integers k and r, a k-RMS returns r tuples from the database which minimize the k-regret ratio, defined as one minus the worst ratio between the k-th maximum utility score among all tuples in the database and the maximum utility score of the r tuples returned. A solution set contains only r tuples, enjoying the benefits of both top-k queries and skyline queries. Proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of k-RMS in the following aspects. First, we develop efficient algorithms for k-RMS (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones. Second, we show that k-RMS is NP-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of k-RMS, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger.
Cite as

Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan. k-Regret Minimizing Set: Efficient Algorithms and Hardness. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ICDT.2017.11,
  author =	{Cao, Wei and Li, Jian and Wang, Haitao and Wang, Kangning and Wang, Ruosong and Chi-Wing Wong, Raymond and Zhan, Wei},
  title =	{{k-Regret Minimizing Set: Efficient Algorithms and Hardness}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.11},
  URN =		{urn:nbn:de:0030-drops-70569},
  doi =		{10.4230/LIPIcs.ICDT.2017.11},
  annote =	{Keywords: multi-criteria decision-making, regret minimizing set, top-k query}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 1 2022
  • 1 2021
  • 1 2017

  • Refine by Author
  • 3 Wang, Kangning
  • 1 Bai, Yannan
  • 1 Cai, Guangya
  • 1 Cao, Wei
  • 1 Chi-Wing Wong, Raymond
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 1 Information systems → Top-k retrieval in databases
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Algorithmic game theory and mechanism design
  • 1 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Bayesian Persuasion
  • 1 Bayesian persuasion
  • 1 Fair Division
  • 1 Fairness
  • 1 Integration
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact