188 lines
8.2 KiB
TeX
188 lines
8.2 KiB
TeX
%--A0 beamer slide-------------------------------------------------------------
|
|
\documentclass[final]{beamer}
|
|
\usepackage[orientation=portrait,size=a0,
|
|
scale=1.5 % font scale factor
|
|
]{beamerposter}
|
|
|
|
\geometry{
|
|
hmargin=2.5cm, % little modification of margins
|
|
}
|
|
\usepackage{lipsum}
|
|
\usepackage{MnSymbol}
|
|
\usepackage{multirow}
|
|
\usepackage{booktabs}
|
|
\usepackage{soul}
|
|
\usepackage{graphicx}
|
|
\usepackage{natbib}
|
|
\usepackage{bibentry}
|
|
% \usepackage{hyperref}[colorlinks=true,urlcolor=Blue,citecolor=Green,linkcolor=BrickRed,unicode]
|
|
|
|
\DeclareMathOperator*{\conv}{conv}
|
|
|
|
\linespread{1.15}
|
|
%
|
|
%==The poster style============================================================
|
|
\usetheme{Poster}
|
|
|
|
%==Title, date and authors of the poster=======================================
|
|
\title
|
|
[34th International Joint Conference on Artificial Intelligence (IJCAI25), Guangzhou, China] % Conference
|
|
{ % Poster title
|
|
\#2001 \; Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints
|
|
}
|
|
|
|
\author{\texorpdfstring{\underline{Yu Cong}}{Yu Cong}, Chao Xu, Yi Zhou}
|
|
\institute[UESTC]{University of Electronic Science and Technology of China}
|
|
|
|
\date{\today}
|
|
|
|
|
|
|
|
\begin{document}
|
|
% larger font
|
|
\large
|
|
|
|
\begin{frame}[t]
|
|
\vspace{-3cm}
|
|
\begin{multicols}{2}
|
|
|
|
\section{Problem}
|
|
We consider the incentive allocation problem with additional constraints.
|
|
|
|
\textbf{Input}: A set of coupons $E=\bigcupdot_i E_i$, where each coupon $e\in E$ has a value and a cost $v_e,c_e\in \mathbb{Z}_+$. Budget $B\in \mathbb{Z}_+$. Constraints $\mathcal F_i$ on each subset $E_i$.
|
|
|
|
\textcolor{Gray}{
|
|
\textbf{Output}: A subset $X\subset E$ of coupons that maximizes the total value $\sum_{e\in X}v_e$ while satisfying the budget constraint $\sum_{e\in X}c_e\leq B$ and additional constraints $X\cap E_i\in \mathcal F_i$.
|
|
}
|
|
|
|
This problem is NP-hard. Consider its LP relaxation.
|
|
\begin{equation*}\label{LP}
|
|
\begin{aligned}
|
|
\tau(B)=\max_x&\; & v\cdot x& & & \\
|
|
s.t.&\; & c \cdot x &\leq B & &\\
|
|
& & x_{E_i}&\in \conv(\mathcal{F}_i) & &\;\forall i\in [n]\\
|
|
& & x&\in [0,1]^m & &
|
|
\end{aligned}
|
|
\end{equation*}
|
|
\textbf{Output}: The entire curve $\tau(B)$ for $B\in [0,\infty)$.
|
|
|
|
We consider 3 cases of additional constraints $x_{E_i}\in \mathcal{F}_i$ :
|
|
\begin{enumerate}
|
|
\item Multiple-choice. $\sum\limits_{e\in E_i}x_e\leq 1$;
|
|
\item Cardinality. $\sum\limits_{e\in E_i}x_e\leq p$;
|
|
\item Matroid. $x_{E_i}\in \text{independence polytope of a matroid}$.
|
|
\end{enumerate}
|
|
|
|
\section{Existing works \& Comparison}
|
|
|
|
\begin{table}[!htb]
|
|
\centering
|
|
\small
|
|
\begin{tabular}{cccc}
|
|
Constraint Type & Result & Fixed budget & Trade-off curve \\
|
|
\bottomrule
|
|
\hline
|
|
\multirow{3}{*}{Multiple Choice}& \cite{Dyer84,ZEMEL1984123}& $O(m)$ & - \\
|
|
&\cite{10.1109/ITSC55140.2022.9922143} & - & $O(m\log m)$ \\
|
|
& \textcolor{OrangeRed}{this paper} & - & $O(m\log m)$ \\
|
|
\hline
|
|
\multirow{4}{*}{Cardinality}& \cite{DavidPisinger} & $O(m\log VC)$ & -\\
|
|
& \cite{DavidPisinger} & $O(mp+nB)$ & - \\
|
|
& \cite{minimaxoptimization} & $O(m\log m)$ & - \\
|
|
& \textcolor{OrangeRed}{this paper} & - & $O((k+m)\log m)$ \\
|
|
\hline
|
|
\multirow{3}{*}{Matroid}& \cite{CAMERINI1984157} & $O(m^2 + T \log m)$ & -\\
|
|
& \cite{minimaxoptimization} & $O(T \log m)$ & - \\
|
|
& \textcolor{OrangeRed}{this paper} & - & $O(Tk+k\log m)$\\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\caption{Comparison of algorithms for incentive allocation: $m$ is the total number of incentives, $M$ is the maximum number of incentives over each agent, $p$ is the max rank of the matroid constraint over each agent, or the limit in the cardinality constraint. $V$ and $C$ is the maximum value and cost of the incentives, respectively. $B$ is the budget. $k=O(mp^{1/3})$ is the number of breakpoints of the trade-off curve. $T$ is the time complexity of matroid optimum base algorithm.}
|
|
\label{runtimetable}
|
|
\end{table}
|
|
|
|
\section{Methods}
|
|
The idea is to take advantage of the independence among the constraints $\mathcal{F}_i$ and reduce the optimization problem to one in computational geometry.
|
|
|
|
\textcolor{DarkOrchid}{\textit{Signature Function.}} Let $f_i(\lambda) = \max\{(v_{E_i}-\lambda c_{E_i}) x | x\in \conv(\mathcal F_i) \}$ be the signature function of agent $i$. The signature function is piecewise-linar and convex.
|
|
|
|
\textcolor{DarkOrchid}{\textit{Lagrangian Dual.}} The Lagrangian dual of LP\autoref{LP} is therefore
|
|
\begin{equation*}
|
|
\label{eq:Lagrangiandual}
|
|
\begin{aligned}
|
|
\min_{\lambda} \left( B\lambda+\sum_i f_i(\lambda)\right).
|
|
\end{aligned}
|
|
\end{equation*}
|
|
|
|
\begin{theorem}[4]\large
|
|
$\tau(B)$ is piecewise-linear and concave.
|
|
\end{theorem}
|
|
|
|
Computing $\tau(B)$ is straightforward if $f_i(\lambda)$ is known.
|
|
|
|
\subsection{Finding $f_i(\lambda)$}
|
|
\textcolor{DarkOrchid}{\textit{Cardinality constraint.}}
|
|
For fixed $\lambda$, computing $f_i(\lambda) = \max\{(v_{E_i}-\lambda c_{E_i})x \mid \mathbf{1}\cdot x \leq p\}$ is the same as finding the $p$ largest coupons with respect to the weights $v_e - \lambda c_e$. If $\lambda$ is not fixed, this is computing the \emph{$k$-level} of univariate linear functions.
|
|
\begin{figure}[htb]
|
|
\begin{minipage}[c]{0.6\linewidth} % Minipage for the image
|
|
\centering
|
|
\includegraphics[width=\linewidth]{image/klevel_black.pdf} % Replace with your image
|
|
\end{minipage}
|
|
\hfill % Optional: Adds horizontal space between minipages
|
|
\begin{minipage}[c]{0.39\linewidth} % Minipage for the caption
|
|
\caption{The bold line forms a $2$-level in the line arrangement.}
|
|
\label{fig:klevel}
|
|
\end{minipage}
|
|
\end{figure}
|
|
|
|
\textcolor{DarkOrchid}{\textit{Matroid constraint.}}
|
|
For fixed $\lambda$ under matroid constraints, computing the signature function is equivalent to finding the optimum-weight base in a matroid.
|
|
However, the matroid generalization of $k$-level problem is significantly harder. We use Eisner-Severance method to compute the curve.
|
|
\section{Computational results}
|
|
|
|
\begin{table}[!ht]
|
|
\small
|
|
\centering
|
|
\begin{tabular}{ccccccccc}
|
|
\toprule
|
|
\multirow{2}*{$m$} & \multicolumn{2}{c}{$p=20$} & \multicolumn{2}{c}{$p=40$} & \multicolumn{2}{c}{$p=2000$} & \multicolumn{2}{c}{$p=m/5$}\\
|
|
\cmidrule(lr){2-3} \cmidrule(lr){4-5} \cmidrule(lr){6-7} \cmidrule(lr){8-9}
|
|
& scan & opt & scan & opt & scan & opt & scan & opt\\
|
|
\midrule
|
|
$1\times 10^3$ & 0.000 & 0.000 & 0.000 & 0.001 & - & - & 0.003& 0.002 \\
|
|
$5\times 10^3$ & 0.003 & 0.005 & 0.006 & 0.005 & 0.137 & 0.027 & 0.091& 0.02\\
|
|
$1\times 10^4$ & 0.008 & 0.010 & 0.014 & 0.012 & 0.384 & 0.048 & 0.384 & 0.048\\
|
|
$5\times 10^4$ & 0.043 & 0.089 & 0.080 & 0.087 & 2.634 & 0.187 & 9.531& 0.326\\
|
|
$1\times 10^5$ & 0.094 & 0.216 & 0.173 & 0.223 & 5.795 & 0.397 & 38.275& 1.222\\
|
|
$5\times 10^5$ & 0.528 & 2.911 & 0.937 & 2.952 & 33.760 & 3.398 & TLE & 10.500 \\
|
|
$1\times 10^6$ & 1.147 & 7.291 & 1.989 & 7.140 & 72.485 & 7.604 & TLE & 23.203\\
|
|
$1\times 10^7$ & 12.994 & 100.512 & 23.863 & 101.675 & TLE & 101.775 & TLE & 133.974\\
|
|
|
|
% \bottomrule
|
|
% \end{tabular}
|
|
% \begin{tabular}{ccccc}
|
|
% % \toprule
|
|
% \multirow{2}*{$m$} & \multicolumn{2}{c}{$p=2000$} & \multicolumn{2}{c}{$p=m/5$}\\
|
|
% \cmidrule(lr){2-3} \cmidrule(lr){4-5}
|
|
% & scan & opt & scan & opt \\
|
|
% \midrule
|
|
% $1\times 10^3$ & - & - & 0.003& 0.002 \\
|
|
% $5\times 10^3$ & 0.137 & 0.027 & 0.091& 0.02\\
|
|
% $1\times 10^4$ & 0.384 & 0.048 & 0.384 & 0.048\\
|
|
% $5\times 10^4$ & 2.634 & 0.187 & 9.531& 0.326\\
|
|
% $1\times 10^5$ & 5.795 & 0.397 & 38.275& 1.222\\
|
|
% $5\times 10^5$ & 33.760 & 3.398 & TLE & 10.500 \\
|
|
% $1\times 10^6$ & 72.485 & 7.604 & TLE & 23.203\\
|
|
% $1\times 10^7$ & TLE & 101.775 & TLE & 133.974\\
|
|
|
|
\bottomrule
|
|
\end{tabular}
|
|
\caption{The time (in seconds) to compute the breakpoints on the signature function under cardinality constraint using the optimum $p$-level algorithm (opt) and the scan line algorithm (scan).}
|
|
\label{tab:klevel}
|
|
\end{table}
|
|
|
|
\bibliographystyle{plainnat}
|
|
\nobibliography{ijcai25}
|
|
\end{multicols}
|
|
\end{frame}
|
|
\end{document}
|