DROPS

Document

Extended Abstract

DOI: 10.4230/LIPIcs.ITCS.2025.49

Confusion Matrix Design for Downstream Decision-Making (Extended Abstract)

Authors: Yiding Feng and Wei Tang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

We initiate the study of confusion matrix design. In this problem, an algorithm designer needs to generate a machine learning model (for a classification task from contexts to labels) which makes predictions for a population of downstream decision makers. The prediction accuracy of the machine learning model is characterized by its confusion matrix, which is a stochastic matrix where each entry encodes the probability of predicting the true label to another label. Each downstream decision maker faces a separate optimization task and will decide his binary action based on his own context, realized prediction given his context, and the confusion matrix selected by the algorithm designer. Decision makers are heterogeneous, as they may hold different contexts. Both the decision makers and the algorithm designer will obtain utilities that are determined by the actions the decision makers take, and their true labels. The goal of the algorithm designer is to design a public confusion matrix that is used for all decision makers subject to some feasibility constraints in order to maximize her net utility. We consider a general class of net utility functions, which could be a combination of both decision makers' utilities and the algorithm designer’s utility. Classic outcome-independent utility and utilitarian/Nash/egalitarian social welfare are all special cases of our net utility formulation. We study the above problem through an information design framework, where we view training machine learning model as designing an information structure (signaling scheme) subject to some specific constraints motivated by the machine learning literature. By building the connection to the public persuasion with heterogeneous priors, we design convex programming-based algorithms that compute the optimal confusion matrix subject to (i) post-processing constraints and (ii) receiver operating characteristic (ROC) constraints in polynomial time, respectively. Besides the computational results, we also obtain analytical structural results and numerical results for the special cases of outcome-independent utility and social-aware utility, by utilizing the convex programming-based characterization of the optimal confusion matrix.

Cite as

Yiding Feng and Wei Tang. Confusion Matrix Design for Downstream Decision-Making (Extended Abstract). In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, p. 49:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ITCS.2025.49,
  author =	{Feng, Yiding and Tang, Wei},
  title =	{{Confusion Matrix Design for Downstream Decision-Making}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{49:1--49:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.49},
  URN =		{urn:nbn:de:0030-drops-226779},
  doi =		{10.4230/LIPIcs.ITCS.2025.49},
  annote =	{Keywords: Confusion Matrix, Downstream Decision-making, Public Persuasion, Human-AI Interaction, Information Design}
}

Document

Extended Abstract

DOI: 10.4230/LIPIcs.ITCS.2021.88

Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)

Authors: Yiding Feng and Rad Niazadeh

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

In several applications of real-time matching of demand to supply in online marketplaces, the platform can allow for some latency to batch the demand and improve the matching’s efficiency. Motivated by these scenarios, we study the optimal trade-off between batching and inefficiency in online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems, where online vertices arrive in K batches. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratios known for the online variant of these problems [Mehta et al., 2007; Aggarwal et al., 2011]. Our main technique is using a family of convex-programming based matchings that distribute the demand in a particularly balanced way among supply in different stages. More precisely, we identify a sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers of the optimal matching linear program to form this family. By providing structural decompositions of the underlying graph using the optimal solutions of these convex programs, we develop a new multi-stage primal-dual framework to analyze the fractional multi-stage algorithm that returns the corresponding regularized optimal matching in each stage (by solving the stage’s convex program). We further show a matching upper-bound by providing an unweighted instance of the problem in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios.

Cite as

Yiding Feng and Rad Niazadeh. Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, p. 88:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ITCS.2021.88,
  author =	{Feng, Yiding and Niazadeh, Rad},
  title =	{{Batching and Optimal Multi-Stage Bipartite Allocations}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{88:1--88:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.88},
  URN =		{urn:nbn:de:0030-drops-136272},
  doi =		{10.4230/LIPIcs.ITCS.2021.88},
  annote =	{Keywords: Online Bipartite Matching, Primal-Dual Analysis, Multi-stage Allocation, Batching}
}

Search Results

Documents authored by Feng, Yiding

Confusion Matrix Design for Downstream Decision-Making (Extended Abstract)

Abstract

Cite as

Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message