109 lines
3.8 KiB
TeX
109 lines
3.8 KiB
TeX
\documentclass{beamer}
|
|
|
|
\usetheme{Slides}
|
|
\usepackage{algo}
|
|
\usepackage{soul}
|
|
% \usepackage{cancel}
|
|
\newcommand{\munepsfig}[3][scale=1.0]{% <===============================
|
|
\begin{figure}[!htbp]
|
|
\centering
|
|
\vspace{2mm}
|
|
\setlength{\fboxrule}{#3} % <===================================
|
|
\framebox{\includegraphics[#1]{#2.png}} % <=====================
|
|
\label{fig:#2}
|
|
\end{figure}
|
|
}
|
|
|
|
\title[Incentive allocation]{Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints}
|
|
\date{August 30, 2025}
|
|
\author{\underline{Yu Cong}, Chao Xu, Yi Zhou}
|
|
\institute[UESTC]{University of Electronic Science and Technology of China}
|
|
% \AtBeginSection[]{
|
|
% \frame{\frametitle{Outline}\tableofcontents[currentsection,
|
|
% subsectionstyle=show/show/shaded]}
|
|
% }
|
|
|
|
|
|
\begin{document}
|
|
\begin{frame}[plain]
|
|
\titlepage
|
|
\scriptsize 34th International Joint Conference on Artificial Intelligence (IJCAI25)
|
|
\end{frame}
|
|
|
|
% introduce the problem. 3 things: trade-off curve, approximation, general constraints
|
|
|
|
\begin{frame}{Incentive allocation with constraints}
|
|
A ride sharing company wants to send riders promotional coupons in the hope of more rides.
|
|
|
|
% each agent gets at most 1 coupon.
|
|
\begin{figure}
|
|
\includegraphics[width=.7\textwidth]{image/chatgpt.png}
|
|
|
|
\scriptsize Image courtesy: ChatGPT-5
|
|
\end{figure}
|
|
|
|
\end{frame}
|
|
|
|
\begin{frame}{Multiple-choice knapsack}
|
|
\textbf{Input}: $n$ sets of coupons $K_1,\dots,K_n$. Each coupon $e\in K_i$ has a non-negative cost $c_e\in \Z_+$ and value $v_e\in \Z_+$. A positive budget $b\in \Z_+$.
|
|
|
|
\textbf{Output}: A subset of coupons $K$ that maximizes the total value $\sum_{e\in K} v_e$ while satisfying \textcolor{Red}{$|K\cap K_i|\leq 1$} and $\sum_{e\in K} c_e\leq b$.
|
|
|
|
\vspace{1em}
|
|
\pause
|
|
|
|
Three problems with this formulation:
|
|
\begin{enumerate}
|
|
\item Finding the exact optimum is NP-hard. So we consider solving it approximately.
|
|
\item Companies may run multiple campaigns at the same time. So a trade-off curve between budget and profit will be useful.
|
|
\item The multiple-choice constraint \textcolor{Red}{$|K\cap K_i|\leq 1$} is too strong for real-world applications.
|
|
\end{enumerate}
|
|
|
|
\end{frame}
|
|
|
|
\begin{frame}{Linear programming relaxation}
|
|
% \textcolor{gray}{
|
|
\textbf{Input}: $n$ sets of coupons $K_1,\dots,K_n$. Each coupon $e\in K_i$ has a non-negative cost $c_e\in \Z_+$ and value $v_e\in \Z_+$. \st{A positive budget $b\in \Z_+$.}
|
|
% }
|
|
\pause
|
|
\begin{equation*}
|
|
\begin{aligned}
|
|
\tau(b)= \max_x& & v\cdot x& & &\\
|
|
s.t.& & c\cdot x&\leq b & &\\
|
|
& & \mathcolor{Plum}{x_{K_i}}&\mathcolor{Plum}{\in P_{K_i}} & &\forall i\in [n]\\
|
|
\end{aligned}
|
|
\end{equation*}
|
|
|
|
\textbf{Output}: function $\tau(b)$ for $b\in (0,+\infty)$.
|
|
\pause
|
|
|
|
We focus on 2 kinds of constraints of \textcolor{Plum}{$x_{K_i}\in P_{K_i}$}.
|
|
\begin{enumerate}
|
|
\item Cardinality. \textcolor{Plum}{$x_{K_i}\in P_{K_i}$}→ $\sum_{e\in K_i}x_e\leq p$.
|
|
\item Matroid. \textcolor{Plum}{$x_{K_i}\in P_{K_i}$}→ $x_{K_i}$ is in the base polytope of a matroid $M_i$.
|
|
\end{enumerate}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Results}
|
|
We compute the curve $\tau(b)$ fast.
|
|
\begin{theorem}
|
|
Consider an incentive allocation problem with a total of $m$ incentives.
|
|
The trade-off curve is a piecewise linear concave function with $k$ breakpoints.
|
|
\begin{itemize}
|
|
\item Cardinality constraint.
|
|
$k=O(mp^{1/3})$ and $\tau$ can be computed in $O((k+m)\log m)$ time.
|
|
\item Matroid constraint. $k=O(mr^{1/3})$ and $\tau$ can be computed in $O(Tk+k\log m)$ time.
|
|
\end{itemize}
|
|
\end{theorem}
|
|
\end{frame}
|
|
|
|
\begin{frame}[plain]
|
|
\centering
|
|
\Large \textit{Let's discuss this in detail at my poster!}
|
|
|
|
\munepsfig[width=.8\linewidth]{image/poster}{1pt}
|
|
% \begin{figure}
|
|
% \includegraphics[width=0.8\linewidth]{image/poster.png}
|
|
% \end{figure}
|
|
\end{frame}
|
|
\end{document} |