Sesión Matemática DiscretaCaracterización Axiomática de reglas de asignación en el problema de la mochila
Dalma Yamila Veron
Instituto de Matemática Aplicada San Luis (UNSL-CONICET), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
\begin{document} \section{Resumen} En el problema de la mochila, un grupo de agentes busca llenar una mochila con varios bienes. Se debe considerar dos cuestiones. La primera, ampliamente estudiada en la literatura, es decidir que art\'iculos seleccionar para introducir en la mochila. La segunda cuesti\'on, no tan estudiada, es dividir los ingresos totales entre los agentes que participan.\\ Existen distintos tipos de algoritmos que resuelven el primero de estos problemas. En este caso estudiaremos dos algoritmos, que si bien no son eficiente, son muy sencillo y ampliamente conocidos en la literatura. Luego, proponemos una regla de reparto asociada a cada algoritmo.\\ Primero, consideremos un problema $P=(N,M,W,w,p)$ , donde $N$ es el conjunto de agentes, $M$ el conjunto de bienes, $W$ el tamaño de la mochila, $w_{j}$ es el tamaño del objeto $j$ y $ p_{j}^{i}$ es la ganancia que obtiene el agente $i$ cuando el bien $j$ es introducido en la mochila.\\ Adem\'as para cualquier problema $P$, el conjunto de asignaciones factibles es definido como
\begin{center} $\mathcal F (P)=\{(x_{j})_{j\in M}\in\mathbb{R}_{+}^{M}:\sum _{j\in M}x_{j}\leq W\}$ \end{center}
La idea del primer algoritmo, denominado algoritmo voraz dividido (Greedy-Split Algorithm), es comenzar con una mochila vac\'ia y simplemente revisar los elementos que est\'an en orden decreciente de eficiencia , agregando cada elemento en consideraci\'on a la mochila sin exceder su capacidad.\\ Se define la regla asociada a dicho algoritmo como $f^{*}=(\varphi ^{*},r^{*})$, donde $\varphi ^{*}$ ordena los elementos de manera decreciente de eficiencia, es decir \begin{center} $\left. \frac{p_{1}}{w_{1}}\geq ...\geq \frac{p_{s-1}}{w_{s-1}}\geq \frac{% p_{s}}{w_{s}}\geq ...\right. $\] \end{center} en el cual $s$ se determina por \begin{center} $\sum_{k= 1}^{s-1}w_{k}\leq W \lt \sum_{k= 1}^{s}w_{k}$ \end{center} y $(\varphi_{j}^{*}(P))_{j\in M}\in \mathcal F$, donde \begin{center}
$\varphi_{j}^{*}(P) =\begin{cases} \begin{array}{rcl} 1& si& j\leq s-1 \\ 0& si& j \gt s-1 \end{array} \end{cases} $\\ \end{center} Para un agente $i$ en el problema $P$, la regla de reparto se define como:
\begin{center} $ r_{i}^{\ast }(P)=\sum\limits_{j\in M}p_{j}^{i}\varphi _{j}^{\ast }(P)$
\bigskip \end{center}
La idea del segundo algoritmo , denominado algoritmo voraz (Greedy Algorithm), se define como $f^{G}=(\varphi ^{G},r^{G})$. Es muy similar a la del algoritmo anterior, pero si el elemento $j$ no entra, se verifica si los siguientes objetos, por ejemplo, $j+1$ o $j+2$ \ pueden entran en la mochila.\\
Adem\'as del orden nombrado, se debe tener en cuenta otro orden, que es el orden de ingreso a la mochila, es decir \begin{center} $\left. j_{1},j_{2},...,j_{r}\right. $ \end{center}
donde $j_{1}$ indica el primer objeto que es colocado en la mochila que no necesariamente es el primer objeto del orden por eficiencia por que este podria no entrar.\\ Por otro lado, para un agente $i$ en el problema $P$, la regla de reparto se define como:
\begin{center} $ r_{i}^{G }(P)=\sum\limits_{j\in M}p_{j}^{i}\varphi _{j}^{G }(P)$
\bigskip \end{center} Desde un enfoque axiom\'atico de la teor\'ia de juego y la elecci\'on social, se introduce algunas propiedades que caracterizan estos algoritmos y se realiza una comparaci\'on de los mismos.\\ En este trabajo se demuestra que $f^{*}$ es la \'unica regla que satisface Maximum aspirations ,Weak independence of irrelevant goods, Minimal efficient, Conditional null solution y Composition up.\\ De manera conjetural, se considera que $f^{G}$ es la \'unica regla que satisface M\'{a}ximum aspirations,Independence of relevant goods, Minimal efficient y No advantage splitting .\\ Y por \'ultimo, a modo de comparaci\'on, se muestra la siguiente tabla
\begin{table}[h] \centering \begin{tabular}{ | c | c | c |} \hline $ \textbf{Axiomas} & \textbf{$f^{*}$} & \textbf{$f^{G}$} \\ \hline Maximum aspirations & \checkmark & \checkmark \\ \hline Weak independence of irrelevant goods & \checkmark & \checkmark \\ \hline Minimal efficient & \checkmark & \checkmark\\ \hline Conditional null solution & \checkmark & \times \\ \hline Composition up & \checkmark & \times \\ \hline Independence of relevant goods & \checkmark &\checkmark \\ \hline No advantage splitting & \checkmark &\checkmark \\ \hline Independence of irrelevant goods & \times & \checkmark\\ \hline Outcast condition & \checkmark &\checkmark \\ \hline Arrow's Choice Axiom & \checkmark & \times \\ \hline Quality over Quantity &\checkmark & \checkmark \\ \hline \end{tabular}
\end{table}$ \end{document}