Sesión Matemática Discreta

Martes 17 de septiembre

Horario	Título	Expositor/a
9:40 ~ 10:00	The stability of nonstationary Markov strategies in a dynamic resource game with heterogeneous discounting	Luis Alcalá
10:00 ~ 10:20	Manipulaciones Obvias y la Regla Uniforme	Roberto Pablo Arribillaga
10:20 ~ 10:40	Caracterización Axiomática de reglas de asignación en el problema de la mochila	Dalma Yamila Veron
10:40 ~ 11:00	Un modelado matemático para estudiar las propiedades de las cadenas globales de composición de servicios	Juan Marcos Tripolone

Horario	Título	Expositor/a
14:30 ~ 15:10	Comparación de Algoritmos de asignación de bienes indivisibles.	Agustín Alvarez
15:10 ~ 15:30	Dominancia y Estructura de los Conjuntos Estables Von Neumann-Morgenstern en Mercados de Matching Uno a Uno	Andrés Mauricio Lucero Quevedo
15:30 ~ 15:50	Operaciones de reticulado para el conjunto estable en mercados bilaterales sustituibles mediante dinámicas de reequilibrio	Noelia Juarez
16:20 ~ 16:40	Mecanismos de asignación eficiente en mercados muchos a muchos dinámicos	Adriana del Valle Amieva Rodriguez
16:40 ~ 17:00	LP-approach for substitutable preferences in matching markets	Pablo Neme
17:00 ~ 17:20	Not obviously manipulable allotment rules	Agustín Bonifacio

Miércoles 18 de septiembre

Horario	Título	Expositor/a
9:40 ~ 10:00	Funciones simétricas y t-diseños esféricos en $\mathbb{R}^2$	Federico Nicolás Martínez
10:00 ~ 10:20	Gaps en polinomios ciclotómicos binarios	Antonio Cafure
10:20 ~ 11:00	Matrices EP relativas a una isometría parcial	David Eduardo Ferreyra

Horario	Título	Expositor/a
14:30 ~ 14:50	La inversa de grupo $m$-débil relativa a un peso Hermitiano	Valentina Orquera
14:50 ~ 15:10	La inversa $m$-WC respecto a un peso Hermitiano	Paola Moas
15:10 ~ 15:30	Inversas $G$-Drazin $W$-ponderadas laterales y órdenes parciales matriciales	María Luz Llanes
15:30 ~ 15:50	Una nueva extensión de la inversa Core a matrices de índice arbitrario	Vanina Grisel Negro
16:20 ~ 16:40	Evolución de autómatas celulares permutacionales	Diego Luis Alberto
16:40 ~ 17:00	Coloreando los caminos de un árbol	Pablo De Caria Di Fonzo
17:00 ~ 17:20	Contando la cantidad de PEDs en algunas clases de grafos	Camilo Vera
17:20 ~ 17:40	Efecto de operaciones de vértices en asociaedros de grafos	Ana Gargantini

Jueves 19 de septiembre

Horario	Título	Expositor/a
9:40 ~ 10:00	Complejidad computacional de algunos problemas de modificación a grafos de intervalos.	Aldana Ayelén Alcantar
10:00 ~ 10:20	Hacia una caracterización de los grafos balanceados dentro de la clase de grafos coclaw-free	Lucía Busolini
10:20 ~ 10:40	Sobre una generalización de grafos distancia regular, autovectores constantes y autovalores lineales	Ezequiel Dratman
10:40 ~ 11:00	Sobre el radio espectral de los grafos bipartitos con signo no balanceados	Luciano N. Grippo

Horario	Título	Expositor/a
14:30 ~ 14:50	Propiedad de 1-persistencia en la relajación clique del poliedro de conjuntos estables.	Lucía Moroni
14:50 ~ 15:10	A New Formula for the Determinant of a Graph	Daniel A. Jaume
15:10 ~ 15:30	$P_3$-convexidad en el grafo complemento del grafo generalizado de Kneser	Agustina Victoria Ledezma

Viernes 20 de septiembre

Horario	Título	Expositor/a
9:40 ~ 10:00	About of the determinant K\H{o}nig-Egerv\'{a}ry graphs with a perfect matching	Gonzalo Molina
10:00 ~ 10:20	About the determinant of graph with perfect matching	Diego G. Martinez
10:20 ~ 10:40	Subdivisiones impares en grafos de Kneser	Adrian Pastine
10:40 ~ 11:00	A new elemental proof of K\H{o}nig's Theorem	Kevin D. Pereyra

Horario	Título	Expositor/a
14:30 ~ 14:50	Matrices de suma por fila en grupos diedrales generalizados	María Valentina Soldera Ruiz
14:50 ~ 15:10	A Combinatorial core-nilpotent decomposition of unicyclic graphs	Micaela Vega
15:10 ~ 15:30	About unimodularity of barbells graphs	Cristian Panelo

Charlas invitadas

Martes 17 de septiembre, 14:30 ~ 15:10

Comparación de Algoritmos de asignación de bienes indivisibles.

Agustín Alvarez

Universidad Nacional de General Sarmiento, Instituto de Ciencias, Los Polvorines, Provincia de Buenos Aires, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Cómo repartir un conjunto de bienes indivisibles (artículos, no plata) entre un grupo de personas no es un problema sencillo. Las personas podrían ser un grupo de hermanas que heredan un conjunto de bienes, o un matrimonio que se divorcia, o países en conflicto por un conjunto de recursos. Pensando en las hermanas que heredan, cada hermana valora los bienes según su propia subjetividad y se desea tener un método que reparta los bienes de manera que todas queden satisfechas con el reparto. Hay definidas distintas medidas de justicia y funciones de bienestar para medir cuán buenos son los repartos de este tipo y lo deseable suele ser proponer algoritmos de reparto que se desempeñen bien respecto a estas medidas o cuantificadores. Proponemos un método de asignación y lo comparamos a través de simulaciones con otros algoritmos conocidos. A su vez, para casos de pocos agentes y pocos artículos también comparamos con métodos exhaustivos que logran, de existir, repartos proporcionales o repartos sin envidia, observando en qué proporción de casos no se logran estos repartos justos con el algoritmo propuesto y los conocidos. También comparamos con métodos exhaustivos que maximizan medidas de bienestar como el Bienestar de Nash o el igualitario, observando la pérdida con los otros algoritmos en este sentido. El objetivo de realizar esta comparación es elegir un método de asignación que sea computable tanto en casos de pocos herederos y pocos agentes como cuando estas cantidades son moderadas o grandes y que su comportamiento sea bueno o aceptable en los casos en que se puede comparar con algoritmos exhaustivos. Programar dicho método dentro de una aplicación Shiny para brindar una herramienta de reparto de bienes indivisibles para posibles usuarios interesados.

Es un problema bastante similar al de repartir bienes, el de repartir un conjunto de tareas entre trabajadores, donde cada uno valora las tareas según su percepción. También se estudia este problema y se propone un método de reparto de tareas.

Finalmente se crea una aplicación Shiny para que los usuarios interesados puedan utilizar libremente esta herramienta en cualquiera de los tipos de reparto.

Algunos trabajos importantes del área se incluyen en las referencias.

Referencias

[1] Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., . . . & Wu, X. (2023). Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322, 103965.

[2] Lipton, R. J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allo- cations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (pp. 125-131).

[3] Plaut, B., & Roughgarden, T. (2020). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2), 1039-1068.

[4] Akrami, H., Alon, N., Chaudhury, B. R., Garg, J., Mehlhorn, K., & Mehta, R. (2022). EFX allocations: Simplifications and improvements. arXiv preprint arXiv:2205.07638.

Ver PDF

Miércoles 18 de septiembre, 10:20 ~ 11:00

Matrices EP relativas a una isometría parcial

David Eduardo Ferreyra

Universidad Nacional de Río Cuarto, CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Una matriz $A\in \mathbb{C}^{n\times n}$ es EP (o rango-Hermitiana) si su espacio columna coincide con el espacio columna de su traspuesta conjugada $A^*$. Este tipo de matrices es muy importante en la teoría matricial e incluye matriciales especiales como los proyectores ortogonales, las matrices Hermitianas, anti-Hermitianas, unitarias, normales y por supuesto las no singulares. Las matrices EP tienen índice a lo sumo uno, esto es, $\mathcal{R}(A)=\mathcal{R}(A^2)$, donde $\mathcal{R}(\cdot)$ indica el espacio columna de la matriz. Dicha limitación condujo a diferentes extensiones para el caso de matrices cuadradas de índice arbitrario [4,8] como así también a la teoría de operadores y/o anillos abstractos [3,9]. Sin embargo, para el caso rectangular se han obtenido muy pocos resultados [10].

En esta charla, se presentará la idea de $T$-EP matriz que involucra una matriz rectangular $A\in \mathbb{C}^{m\times n}$ relativa a una isometría parcial $T\in \mathbb{C}^{m\times n}$, es decir, $T=TT^*T$. A partir de ciertas descomposiciones simultáneas de $A$ y $T$, basadas en las descomposición SVD y la descomposición de Hartwig-Spindelböck, se presentan diferentes propiedades y caracterizaciones de las $T$-EP matrices, muchas de las cuales involucran la clásica inversa de Moore-Penrose. Entre las caracterizaciones más destacadas se puede mencionar la siguiente:$A$ es $T$-EP si y sólo si $TA^{\dagger}A=AA^{\dagger}T$ y $\mathcal{R}(A^*)\subseteq \mathcal{R}(T^*)$, donde $A^{\dagger}$ simboliza la inversa de Moore-Penrose de $A$.

Este enfoque está inspirado en [7] , donde se desarrolla una teoría espectral para matrices rectangulares y se introduce el concepto de $*$-ortogonalidad entre dos matrices $A,B\in \mathbb{C}^{m\times n}$, a saber, $A^*B=0$ y $BA^*=0$. De esta manera se extienden muchos resultados conocidos en el caso cuadrado como los obtenidos en [1,2]. Si hay tiempo, se hará un ligero interludio al problema de la suma de dos matrices de la misma clase. Más precisamente, ¿cuándo la suma de dos matrices $T$-EP resulta nuevamente $T$-EP? Su conexión con ciertos resultados de $*$-ortogonalidad, sumas paralelas y matrices rango disjuntas serán mencionados [5,6].

Este trabajo está parcialmente subvencionado por la Universidad Nacional de Río Cuarto (PPI 18/C634) y CONICET (PIBAA 28720210100658CO).

Trabajo en conjunto con: Saroj Malik (School of Liberal Studies, Ambedkar University, India).

Referencias

[1] Baksalary, O.M., Trenkler, G.: Characterizations of EP, normal and Hermitian matrices. Linear Multilinear Algebra 56, 299–304 (2008).

[2] Cheng, S., Tian, Y.: Two sets of new characterizations for normal and EP matrices. Linear Algebra Appl. 375, 181–195 (2003).

[3] Djordjevic, D.S.: Characterizations of normal, hyponormal and EP operators. J. Math. Anal. Appl. 329, 1181–1190 (2007).

[4] Ferreyra, D.E., Levis, F.E., Priori, A.N., Thome, N.: Extending EP matrices by means of recent generalized inverses. Aequat. Math. 98, 921–939 (2024).

[5] Ferreyra D.E., Malik S.B.: Relative EP matrices, Rev. Real Acad. Cienc. Exactas Fis. Nat. Ser. A-Mat. 116, 69 (2022).

[6] Ferreyra D.E, Malik, S.B.: Core and strongly core orthogonal matrices. Linear Multilinear Algebra 70 (20), 5052-5067 (2022).

[7] Hestenes, M.R.: Relative Hermitian matrices. Pacific J. Math. 11, 224–245 (1961).

[8] Malik, S.B., Rueda, L., Thome, N.: The class of m-EP and m-normal matrices. Linear Multilinear Algebra 64(11), 2119–2132 (2016).

[9] Mosic, D., Djordjevic, D.S., Koliha, J.J.: EP elements in rings. Linear Algebra Appl. 431, 527–535 (2009).

[10] Tian, Y., Wang, H.: Characterizations of EP matrices and weighted-EP matrices. Linear Algebra Appl. 434(5), 1295–1318 (2011).

Ver PDF

Resúmenes

Martes 17 de septiembre, 9:40 ~ 10:00

The stability of nonstationary Markov strategies in a dynamic resource game with heterogeneous discounting

Luis Alcalá

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.

In this paper, we study the stability of nonstationary Markov strategies in a two-player dynamic resource game with heterogeneous discount factors and infinite horizon, originally developed by Levhari and Mirman [1]. It is well known that this game has a unique Markov-perfect equilibrium (MPE) in stationary strategies that is also globally stable. We analyze several consequences of enlarging the strategy spaces of the players to include Markov nonstationary strategies. In particular, we prove the following: 1. The MPE in stationary strategies is the limit of a sequence of nonstationary equilibria for the finite horizon game as the horizon tends to infinity; 2. The MPE in stationary strategies is also an MPE in nonstationary strategies, but it is both locally and globally unstable; 3. There are two asymptotic equilibria where the consumption of one player converges to zero and the consumption of the other player is maximized in the limit. Both of these equilibria are saddle-path stable; and 4. There is a continuum of asymptotic equilibria where the consumption of both players converge to zero and the limiting stock is maximized, which are locally stable. However, these equilibria may not satisfy a terminal condition for dynamic problems with unbounded payoffs, which is both necessary and sufficient for optimality, as has been recently shown by Wiszniewska-Matyszkiel [2], and Wiszniewska-Matyszkiel and Singh [3].

Referencias

[1] Levhari D. and Mirman L.J. (1980) ``The Great Fish War: An example using a dynamic Cournot-Nash solution,'' Bell Journal of Economics, 11(1):322-334.

[2] Wiszniewska-Matyszkiel A. (2011) ``On the terminal condition for the Bellman equation for dynamic optimization with an infinite horizon,'' Applied Mathematics Letters, 24, 943--949.

[3] Wiszniewska-Matyszkiel A. and Singh R. (2021) ``Necessity of the terminal condition in the infinite horizon dynamic optimization problems with unbounded payoff,'' Automatica, 123,109332.

Ver PDF

Martes 17 de septiembre, 10:00 ~ 10:20

Manipulaciones Obvias y la Regla Uniforme

Roberto Pablo Arribillaga

Instituto de Matemática Aplicada San Luis (UNSL-CONICET) - Departamento de Matemática (UNSL) , Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

En el problema de la asignación de un bien infinitamente divisible entre agentes cuyas preferencias son unimodales, demostramos que la regla uniforme es la única regla de asignación que satisface eficiencia, consistencia, garantía de división equitativa y no manipulabilidad obvia.

Ampliación:

En la teoría de la asignación de recursos, particularmente cuando se trata de un bien completamente divisible, es esencial encontrar reglas de asignación que sean justas y eficientes. En este contexto, consideramos una situación donde varios agentes tienen preferencias unimodales, es decir, cada agente tiene una única cantidad ideal de la mercancía que prefiere más que cualquier otra cantidad y conforme se aleja de esa cantidad su situación empeora.

La regla uniforme se refiere a un método de asignación que propone un reparto lo más igualitario popsible de manera de hacer un repato eficiente.

Nuestro análisis muestra que esta regla uniforme es la única que cumple simultáneamente con los siguientes criterios:

Eficiencia: La asignación debe maximizar el bienestar total, es decir, no debe haber manera de reorganizar la distribución para que al menos un agente esté mejor sin que otro esté peor.

Consistencia: Si aplicamos la regla a un subconjunto de agentes con el bien asignada a ese subconjunto, la asignación resultante debe ser coherente con la asignación original.

Garantía de división equitativa: Cada agente debe recibir el reparto igualitario si este es su cantidad ideal.

No manipulabilidad obvia: No debe ser posible para un agente mejorar su asignación reportando falsamente sus preferencias de manera obvia.

Estos criterios aseguran que la regla de asignación no solo es justa y eficiente, sino también robusta ante intentos de manipulación y consistente en diferentes escenarios de asignación. La conclusión de que solo la regla uniforme satisface todos estos criterios simultáneamente es significativa, ya que proporciona una base teórica sólida para su uso en diversas aplicaciones prácticas de asignación de recursos.

Trabajo en conjunto con: Agustín Bonifacio (Instituto de Matemática Aplicada San Luis (UNSL-CONICET) - Departamento de Matemática (UNSL) ).

Referencias

[1] SPRUMONT, Y. (1991): “The division problem with single-peaked preferences: a charac- terization of the uniform allocation rule,” Econometrica, 509–519.

[2] THOMSON, W. (1994): “Consistent solutions to the problem of fair division when prefer- ences are single-peaked,” Journal of Economic Theory, 63, 219–245. 6

[3] TROYAN, P. AND T. MORRILL (2020): “Obvious manipulations,” Journal of Economic The- ory, 185, 104970. 25

[4] CHING, S. (1994): “An alternative characterization of the uniform rule,” Social Choice and Welfare, 11, 131–136.

[5] ARRIBILLAGA, R. P. AND A. G. BONIFACIO (2024): “Obvious manipulations of tops-only voting rules,” Games and Economic Behavior, 143, 12–24

Ver PDF

Martes 17 de septiembre, 10:20 ~ 10:40

Caracterizació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}

Ver PDF

Martes 17 de septiembre, 10:40 ~ 11:00

Un modelado matemático para estudiar las propiedades de las cadenas globales de composición de servicios

Juan Marcos Tripolone

Universidad de Congreso, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Esta comunicación se refiere a los modelos de asignación aplicados a la cadena internacional de contratos de outsourcing para composición de servicios. Las cadenas globales de valor tienen como objetivo capilarizar los procesos de captación y subcontratación de recursos (offshoring/outsourcing/staffing), y al mismo tiempo, mitigar o gestionar los riesgos de externalización hacia abajo en la cadena.

Estos riesgos incluyen la desactivación del contrato, el despido abrupto de un determinado trabajador (por bajo desempeño o por una nueva oferta laboral) entre otros, lo que motiva que la cadena de subcontratación crezca indefinidamente.

Este artículo aborda matemáticamente desde los Juegos de Asignación, la Teoría de Contratos, la Teoría de Retículos y los conjuntos ordenados el esquema de contratación en grandes cadenas de contratistas, proponiendo algunas propiedades clave para estudiar su comportamiento a través de un plexo de teoremas.

Para acometer este objetivo, el abordaje propuesto incluye:

A. El diseño de una estructura reticular multinivel que representa la cadena de composición de servicios, con nodos de contratación en diferentes niveles representando contratistas y subcontratistas, en donde se evidencia la relación de asignación.

B. Morfismos de asignación de contratos entre los agentes de la cadena, con sus propiedades y caracterización.

Aspectos destacados de la investigación:

1. La cadena de contratación en los mercados de subcontratación se modela como un juego de emparejamiento de muchos a muchos representable mediante retículos.

2. Se desarrolla un álgebra de asignaciones contractuales con teoremas que demuestran las propiedades algebraicas y topológicas de las cadenas de subcontratación.

3. Se propone el diseño de una plataforma digital para emparejar contratistas y subcontratistas utilizando algoritmos basados en preferencias.

4. Se demuestra la existencia de asignaciones estables y optimalidad para contratistas en cadenas de subcontratación finitas con preferencias estrictas.

5. Se establecen resultados acerca de niveles de complejidad, mostrando que el cálculo de la distancia a la estabilidad es NP-difícil.

6. Se aplica la teoría de categorías para analizar las propiedades estructurales de los pooles de composición de servicios y las asignaciones de recursos humanos.

Introducción:

Se pretenden modelar las cadenas de subcontratación en mercados de outsourcing como juegos de emparejamiento múltiple representables por retículos. Se desarrolla un álgebra de asignaciones contractuales y se propone el diseño de una plataforma digital para emparejar contratistas y subcontratistas.

El mercado de recursos humanos (RRHH), especialmente en sectores empresariales como el de las tecnologías de la información o la construcción, presenta a menudo una importante cadena de contratistas y subcontratistas de distintos niveles, para cubrir vacantes en proyectos relevantes (como desarrollos de sistemas informáticos de gran envergadura o grandes obras públicas de construcción). Por ejemplo, cuando una empresa contratista que licita un proyecto (en el que se debe asignar una determinada cantidad de personal mediante un modelo de negocio de externalización) contrata o asigna dicho proyecto a otra empresa, ésta es considerada como contratista directo (contratista de nivel 1, o 1-contratista). Si el 1-contratista subcontrata parcialmente algunos de estos recursos humanos a otra empresa, esta nueva empresa es un subcontratista (contratista de nivel 2, o 2-contratista). Esta cadena de contratación puede extenderse y generalizarse a la empresa contratista n-ésima (contratista de nivel n, o n-contratista).

Juegos de asignación de muchos a muchos en la composición de servicios:

Situaciones de muchos a muchos como el desafío de asignar talento humano en proyectos de empresas son cada vez más comunes en extensas cadenas globales de empresas contratantes producidas por la formación de equipos de recursos humanos aplicados a proyectos de tecnologías de la información u otros sectores similares de la economía del conocimiento y los servicios profesionales exportables.

Esto motiva extender los modelos de emparejamiento de trabajadores a instituciones (muchos a uno) a casos en los que distintos trabajadores pertenecientes a una o más empresas contratantes son asignados a distintos proyectos de varias empresas contratantes (muchos a muchos). Este trabajo propone soluciones algebraicas y computacionales al desafío.

Algebrización de la cadena de contratación:

Para simplificar el modelo, consideramos que la empresa contratante $A_0$ sólo oferta un único proyecto, y los elementos de este conjunto representan los recursos humanos (propios o subcontratados) asignados al proyecto. A efectos de generalización, consideraremos aquí que la empresa contratista $A_0$ equivale al propio proyecto en estudio.

Sin embargo, al extender este modelo a múltiples proyectos multicontratistas que subcontratan múltiples recursos humanos a múltiples subcontratistas, se obtiene un modelo de asignación de muchos a muchos en el mercado del talento humano. Para estos casos, se puede denotar genéricamente como $A_{ij} \subseteq A_i$ el j-ésimo proyecto de $A_i$, y ampliar lo aquí expuesto. Este modelo se vuelve aún más complejo si se pueden asignar trabajadores a tiempo parcial (por lo que un solo trabajador podría ser asignado a más de un proyecto de más de una empresa).

Sea $A_0$ la empresa contratante dueña del proyecto, y $A_{i \in I}$ empresas contratistas de la misma cadena de contratación, $I = \{1, 2, 3, ..., n\}; I \subset N\}$. Sean estas empresas A1 el contratista directo de $A_0$ (es decir, contratista de A0, o 1-contratista), $A_2$ contratista de $A_1$ (subcontratista de $A_0$ o 2-contratista), $A_3$ contratista de $A_2$ (subsubcontratista de $A_0$ o 3-contratista), ..., $A_n$ contratista de $A_{n-1}$ (n-contratista).

$A_0 =$ $'$Empresa contratante$'$ = $\{a_{01}, a_{02}, ..., a_{0x}, a_{11}, a_{12}, ..., a_{1b}, a_{21}, a_{22}, ..., a_{2b}, a_{31}, a_{32}, ..., a_{3c}, ..., a_{n1}, a_{n2}, ..., a_{nm}\}$

$A_1 =$ $'$Contratista directo (1-contractor)$'$ = $\{a_{11}, a_{12}, ..., a_{1b}, a_{21}, a_{22}, ..., a_{2b}, a_{31}, a_{32}, ..., a_{3c}, ..., a_{n1}, a_{n2}, ..., a_{nm}\}$

$A_2 =$ $'$Subcontratista (2-contractor)$'$ = $\{a_{21}, a_{22}, ..., a_{2b}, a_{31}, a_{32}, ..., a_{3c}, ..., a_{n1}, a_{n2}, ..., a_{nm}\}$

$A_3 =$ $'$Sub-subcontratista (3-contractor)$'$ = $\{a_{31}, a_{32}, ..., a_{3c}, ..., a_{n1}, a_{n2}, ..., a_{nm}\}$

$A_n =$ $'$Sub-...-subcontratista (n-contractor)$'$ = $\{a_{n1}, a_{n2}, ..., a_{nm}\}$

Cadena simple de contratación:

$A_n \subseteq A_{n-1} \subseteq ... \subseteq A_i \subseteq ... \subseteq A_3 \subseteq A_2 \subseteq A_1 \subseteq A_0$ $\forall$ $i \in I = \{1, 2, ..., n\}$

$A_n \cup A_{n-1} \cup ... \cup A_i \cup ... \cup A_3 \cup A_2 \cup A_1 = A_0$ $\forall$ $i \in I = \{1, 2, ..., n\}$

Un espacio métrico definido por el nivel de contrato:

Con el desarrollo anterior se constituye el espacio métrico $(\wp{P}(C \cup S), \delta(A_i, A_j))$, $A_i, A_j \in \wp{P}(C \cup S)$, donde $C \cup S$ es el universo de contratistas para una cadena de contratación.

Definición. Función de distancia entre niveles de contratación:

Sean $A_i, A_j, A_k$ empresas pertenecientes a una única cadena de contratación (hilo único) tal que $A_i, A_j, A_k \subseteq C \cup S$ $(A_i, A_j, A_k \in \wp(C \cup S))$ y sea $\delta: \wp(C \cup S) \times \wp(C \cup S) \rightarrow \mathbb{N}$ / $\delta(A_i, A_j) = |i - j|$, donde $i$ (j) representa el nivel de profundidad del agente i (j) en la cadena contractual. $\Rightarrow$

(i) $\delta(A_i, A_i) = 0$

(ii) $\delta(A_i, A_j) \gt 0~ \forall A \neq B$

(iii) $\delta(A_i, A_j) = \delta(A_j, A_i)$

(iv) $\delta(A_i, A_k) \leq \delta(A_i, A_j) + \delta(A_j, A_k) ~\forall A_i, A_j, A_k \in C \cup S$

$\therefore \delta(A_i, A_j)$ es una función distancia de $\wp(C \cup S)$ entre los conjuntos $A_i, A_j, A_k\in C \cup S$.

Cadena de composición simplificada:

Se presentan a continuación algunas definiciones útiles para modelar un hilo completo o cadena de contratación para la composición de servicios agregados.

\textbf{Principal inicial}. Sean las empresas $A_0, A_1, A_2, A_3$ tales que $A_0$ contrata a $A_1$ para su proyecto, para lo cual $A_1$ subcontrata a $A_2$, que a su vez subcontrata a $A_3$ para el mismo fin. Formalizamos a la empresa contratante principal y dueña del proyecto como el conjunto $A_0$ de proyectos ofrecidos a licitación a su red de contratistas. A su vez, X es un conjunto de asignaciones con contratos factibles para ejecutar el proyecto de $A_0$.

Contratos factibles para el proyecto licitado. Sea X el conjunto de asignaciones posibles por contratos al proyecto $A_0$, considerando que la empresa $A_0$ podría asignar algunos de sus propios empleados a este u otros proyectos.

\textbf{Contratistas y subcontratistas asignados}. Sea $A_{0_X}$ el subconjunto de $A_0$ que contiene a los recursos humanos propios (directos) que $A_0$ asignó a su proyecto unidos a $A_{1_X}$, que es el subconjunto de $A_1$ que contiene agentes (personas o empresas) subcontratados por $A_1$ para el proyecto de $A_0$, que subcontrata a $A_{2_X}$, subconjunto de $A_2$ definido que contiene agentes (personas o empresas) subcontratados por $A_2$ para asignar al equipo que $A_1$ reunió para el proyecto de $A_0$, finalizando la cadena con $A_{3_X}$ el subconjunto de $A_3$ definido como el conjunto de recursos humanos (solo personas, ya que en este ejemplo $A_3$ está en el último nivel de contratación) subcontratados por $A_3$ para asignarlos al equipo que $A_2$ reunió para proporcionar recursos humanos a la empresa $A_1$, que a su vez reunió el equipo final de contratistas indirectos y subcontratistas, junto a los recursos humanos propios que A0 asignó a su proyecto.

Asumiendo que todos los elementos (conjuntos unitarios de personas o conjuntos de empresas subcontratistas) de $A_{0_X}, A_{1_X}, A_{2_X}$ y $A_{3_X}$ sean aceptables por $A_0$ para ser asignados a su proyecto, y considerando $A_{0_X}$ como el conjunto de todos los recursos humanos asignables al proyecto de A0 en la cadena, se puede construir una estructura compuesta por el conjunto $A_0$ ordenado por la operación de subconjunto (poset).

$A_{3_X} = \{a_{3_{x_1}}, a_{3_{x_2}}, ..., a_{3_{x_o}}\} \subseteq A_3$

$(A_{3_X} \in \wp(A_{3}), |A_{3_X}| = o)$

$A_{2_X} = \{a_{3_{x_1}}, a_{3_{x_2}}, ..., a_{3_{x_o}}, a_{2_{x_1}}, a_{2_{x_2}}, ..., a_{2_{x_l}}\} \subseteq A_2$

$(A_{2_X} \in \wp(A_{2}), |A_{2_X}| = |A_{3_X}| + l = o + l)$

$A_{1_X} = \{a_{3_{x_1}}, a_{3_{x_2}}, ..., a_{3_{x_o}}, a_{2_{x_1}}, a_{2_{x_2}}, ..., a_{2_{x_l}}, a_{1_{x_1}}, a_{1_{x_2}}, ..., a_{1_{x_m}}\} \subseteq A_1$

$(A_{1_X} \in \wp(A_{1}), |A_{1_X}| = |A_{3_X}| + |A_{2_X}| + m = o + l + m)$

$A_{0_X} = \{a_{3_{x_1}}, ..., a_{3_{x_o}}, a_{2_{x_1}}, a_{2_{x_2}}, ..., a_{2_{x_l}}, a_{1_{x_1}}, a_{1_{x_2}}, ..., a_{1_{x_m}}, a_{0_{x_1}}, a_{0_{x_2}}, ..., a_{0_{x_n}}\} \subseteq A_0$

$(A_{0_X} \in \wp(A_0), |A_{0_X}| = |A_{3_X}| + |A_{2_X}| + |A_{1_X}| + n = o + l + m + n)$

$\therefore \langle \wp(A_0), \subseteq \rangle: A_{3_X} \subseteq A_{2_X} \subseteq A_{1_X} \subseteq A_{0_X}$

Retículos en el mercado de contratistas:

Utilizando la relación de orden definida por la operación de subconjunto, es posible construir la red que representa la cadena formada en el poset $\langle \wp(A_{0_X}), \subseteq \rangle$ como sigue.

Hilos de contratación de primer orden: $A_{0_X}$

Hilos de contratación de segundo orden:

$A_{8_X} \subseteq A_{0_X}$

Hilos de contratación de tercer orden:

$\{a_{0_{x_1}}\} \subseteq A_{8_X} \subseteq A_{0_X}$

$A_{3_X} \subseteq A_{1_X} \subseteq A_{0_X}$

$A_{4_X} \subseteq A_{1_X} \subseteq A_{0_X}$

$A_{7_X} \subseteq A_{2_X} \subseteq A_{0_X}$

Hilos de contratación de cuarto orden:

$A_{5_X} \subseteq A_{6_X} \subseteq A_{2_X} \subseteq A_{0_X}$

Competencia y preferencias en los mercados de recursos humanos:

Sean $A_0, A_1, A_2 y A_3$ empresas que desean contratar respectivamente $q_{A_0}, q_{A_1}$, $q_{A_2}$ y $q_{A_3}$ recursos humanos con el mismo perfil profesional, y sea H el conjunto de trabajadores $h_r$ que cumplen con el perfil especificado. Después de evaluar a cada $h_r, A_0, A_1, A_2$ y $A_3$ podrían construir las siguientes relaciones de preferencia ejemplificativas (descartando de ellas a los candidatos que decidieron rechazar), y hacer una oferta de trabajo considerando las tarifas $r_0$, $r_1$, $r_2$ y $r_3$ a cada trabajador, ordenados del más preferido al menos preferido, suponiendo que cada empresa intentó contratar la suficiente cantidad de trabajadores para cubrir su cuota requerida.

$H = \{h_1, h_2, h_3, h_4, h_5, h_6, h_7, h_8, h_9\}$

$h_3 \succeq_{A_0} h_5 \succeq_{A_0} h_9 \succeq_{A_0} h_7 \succeq_{A_0} h_2; q_{A_0} = 5$

$h_1 \succeq_{A_1} h_3 \succeq_{A_1} h_5 \succeq_{A_1} h_9 \succeq_{A_1} h_7 \succeq_{A_1} h_2; q_{A_1} = 4$

$h_3 \succeq_{A_2} h_1 \succeq_{A_2} h_8 \succeq_{A_2} h_5 \succeq_{A_2} h_9 \succeq_{A_2} h_7 \succeq_{A_2} h_2; q_{A_2} = 6$

$h_8 \succeq_{A_3} h_5 \succeq_{A_3} h_9 \succeq_{A_3} h_1 \succeq_{A_3} h_7 \succeq_{A_3} h_2; q_{A_3} = 3$

$A_0$ realizará una oferta laboral a: $O_{A_0} = \{h_3, h_5, h_9, h_7, h_2\}$

$A_1$ realizará una oferta laboral a: $O_{A_1} = \{h_1, h_3, h_5, h_9\}$

$A_2$ realizará una oferta laboral a: $O_{A_2} = \{h_3, h_1, h_8, h_5, h_9, h_7\}$

$A_3$ realizará una oferta laboral a: $O_{A_3} = \{h_8, h_5, h_9\}$

Considerando $\succeq_H$ como la relación de preferencia que los candidatos $h_r \in H$ tienen sobre las vacantes ofrecidas por las empresas $A_0, A_1, A_2, A_3$, se deduce que este problema de asignación tiene un orden dual, y por tanto, puede construirse a partir de las empresas que prefieren a los trabajadores evaluados.

$\succeq_ {A_0 \cup A_1 \cup A_2 \cup A_3}: A_0 \cup A_1 \cup A_2 \cup A_3 \rightarrow H$,

o desde su orden dual:

$\succeq_H: H \rightarrow A_0 \cup A_1 \cup A_2 \cup A_3$,

donde se verifica que:

$\succeq_ {A_0 \cup A_1 \cup A_2 \cup A_3} \circ \succeq_H$ = $\succeq_H^{-1} \circ \succeq_{A_0 \cup A_1 \cup A_2 \cup A_3}^{- 1 }$

Generalizando, el conjunto de alternativas posibles para los trabajadores $h_r$, representa todas las ofertas de trabajo disponibles de todas las empresas $A_i$:

$X_h = \bigcup A_i$

$\succeq_ {\bigcup A_i} \circ \succeq_H$ = $\succeq_H^{-1} \circ \succeq_{\bigcup A_i}^{- 1 }$

La cadena de contratación modelada mediante morfismos de matching:

Es posible generalizar la composición de servicios $\mu = \displaystyle\circ_{i=1}^{n} \mu_i$ como una única relación de asignación (es decir, simplemente $\mu$), si asumimos que todos los contratos intervinientes en todos los i niveles de la cadena de contratantes, tanto entre personas (consideradas como singletons) y empresas como entre las propias empresas, se llevan a cabo mediante contratos de naturaleza equivalente. Esta relación de asignación tiene propiedades interesantes que se desarrollarán en el apartado de teoremas. Ahora construiremos una tabla genérica para la relación de contratación $\mu$ con el fin de definirla formalmente.

Definición. Relación de contratación. Definimos $\mu_i$ como el i-ésimo morfismo de asignación (aplicación intercompañía que preserva la estructura interna de la cadena contractual) entre los conjuntos que representan a cada empresa contratante, donde i es un índice que identifica la profundidad en la cadena de contratación. Formalmente:

Sea $C \cup S$ el universo de contratistas factibles (tanto individuos como empresas) y $\mu$ la relación contractual entre ellos tal que:

$\mu: \wp(C \cup S) \rightarrow \wp(A_0)$

$x \rightarrow \mu(x) $

$\{a_{01}\} \mu A_0$

$\{a_{0x}\} \mu A_0$

$A_1 \mu A_0$

$\{a_{11}\} \mu A_1$

$\{a_{1b}\} \mu A_1$

$A_2 \mu A_1$

$\{a_{21}\} \mu A_2 $

$\{a_{2b}\} \mu A_2$

$A_n \mu A_{n-1}$

$\{a_{nm}\} \mu A_n$

Modelado preliminar:

Se define el universo de contratistas como $C \cup S$, donde $C$ son los contratistas directos y $S$ los subcontratistas. La relación de contratación se denota como $\mu$.

Álgebra de asignaciones contractuales:

Se define la operación de asignación contractual $\mu$ con las siguientes propiedades:

Transitividad: $A_2\mu A_1, A_1\mu A_0 \Rightarrow A_2\mu A_0$

Simetría: $A_1\mu_1 A_0 \Leftrightarrow A_0\mu_1 A_1$

Asociatividad: $(A_2\mu A_1)\mu A_0 = A_2\mu(A_1\mu A_0)$

Retículos de preferencias:

Se demuestra que las preferencias de las empresas sobre los subcontratistas forman un retículo.

Teorema. Si cada empresa contratista define una relación de preferencia sobre el conjunto de subcontratistas potenciales, entonces estas relaciones de preferencia forman un retículo.

Composición de servicios en pools:

Se define un pool de servicios como una tripleta $(A, q, p)$, donde $A$ es el conjunto de agentes, $q$ la cantidad de recursos humanos y $p$ la tarifa.

La operación de unión de pools se define como:

$(A_1, q_1, p_1) \oplus (A_2, q_2, p_2) = (A_1 \cup A_2, q_1 + q_2, \max(p_1, p_2))$

Asignaciones estables:

Se demuestra la existencia de asignaciones estables en cadenas de subcontratación finitas con preferencias estrictas.

Teorema. En una cadena de subcontratación finita con preferencias estrictas, siempre existe al menos una asignación estable.

Complejidad computacional:

Se establece que calcular la distancia a la estabilidad es un problema NP-duro.

Teorema. Calcular la distancia a la estabilidad para una asignación dada en una cadena de subcontratación es un problema NP-duro.

Propiedades de los retículos contractuales:

Existencia de un espacio métrico en la cadena

Cerradura del álgebra de asignaciones contractuales

Elemento neutro del álgebra de asignación contractual

Composición de morfismos de asignación

Asociatividad en la cadena de morfismos de asignación

Elemento identidad en los morfismos de asignación

Existencia de un retículo de preferencias

Morfismo de retículos inducido por una asignación

Existencia de un retículo de asignaciones estables

Preservación de estabilidad y optimalidad en servicios

Plenitud y fidelidad de funtores

Funtor adjunto izquierdo al funtor de intersección

Categoría monoidal en pooles de servicios

Axioma 1: Asociatividad

Axioma 2: Unidad

Axioma 3: Coherencia

Cerradura de categoría de pooles de RRHH

Conclusiones:

El modelo propuesto permite abordar proyectos de desarrollo de software con múltiples niveles de subcontratación, optimizando las asignaciones en plataformas de freelancing. Se sugieren futuras líneas de investigación en la maximización del valor para agentes intermediarios y en el diseño de mercados de talento en línea.

Referencias

[1] Blair, C. (1988). The lattice structure of the set of stable matchings with Multiple Partners. Mathematics of Operations Research, 13, 619–628.

[2] Risma, E. (2015). A deferred acceptance algorithm with contracts. Journal of Dynamics and Games, 2, 289-302.

[3] Risma, E. (2015). Binary operations and lattice structure for a model of matching with contracts. Mathematical Social Sciences, 73, 6-12.

[4] Ostrovsky, M. (2008). Stability in Supply Chain Networks. American Economic Review, 98:3, 897–923.

[5] Teytelboym, A. (2014). Trading networks with bilateral contracts. ISER Seminar Series, 18.

[6] Echenique, F. and Oviedo, J. (2006). A theory of stability in many-to-many matching markets. Theoretical Economics, 1, 233–273.

[7] Gale, D. and Shapley, L. (1962). College admissions and the stability of marriage. American Math Monthly, 69, 9–15.

[8] Gusfield, D. and Irving, R. (1989). The Stable Marriage Problem: Structure and Algorithms. Cambridge: MIT press.

[9] Hatfield, J. and Milgrom, P. (2005). Matching with contracts. The American Economic Review, 95, 913–935.

[10] Hatfield, J. and Kominers, S. (2012). Contract design and stability in many to many matching. Working paper.

Ver PDF

Martes 17 de septiembre, 14:30 ~ 15:10

Comparación de Algoritmos de asignación de bienes indivisibles.

Agustín Alvarez

Universidad Nacional de General Sarmiento, Instituto de Ciencias, Los Polvorines, Provincia de Buenos Aires, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Finalmente se crea una aplicación Shiny para que los usuarios interesados puedan utilizar libremente esta herramienta en cualquiera de los tipos de reparto.

Algunos trabajos importantes del área se incluyen en las referencias.

Referencias

[3] Plaut, B., & Roughgarden, T. (2020). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2), 1039-1068.

[4] Akrami, H., Alon, N., Chaudhury, B. R., Garg, J., Mehlhorn, K., & Mehta, R. (2022). EFX allocations: Simplifications and improvements. arXiv preprint arXiv:2205.07638.

Ver PDF

Martes 17 de septiembre, 15:10 ~ 15:30

Dominancia y Estructura de los Conjuntos Estables Von Neumann-Morgenstern en Mercados de Matching Uno a Uno

Andrés Mauricio Lucero Quevedo

Universidad Nacional de San Luis - Instituto de Matemática Aplicada San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

En la literatura de juegos cooperativos, Von Neumann y Morgenstern (1944) introdujeron el concepto de conjunto estable Von Neumann-Morgenstern. En el presente trabajo, estudiaremos el mencionado concepto de solución en un mercado de matching bilateral uno a uno (literatura de teoría de juegos no cooperativos), específicamente las relaciones de dominancia entre los elementos (es decir, los matchings) que pertenecen y no pertenecen a los conjuntos estables Von Neumann-Morgenstern. Además, a través de este estudio, construiremos conjuntos ordenados de agentes del mercado, que permitirán probar en el marco de los conjuntos estables Von Neumann-Morgenstern, dos resultados clásicos de la literatura conocidos para el core de un mercado uno a uno: (i) El conjunto formado por todos los conjuntos estables Von Neumann-Morgenstern de un mercado uno a uno es no vacío; (ii) para cualesquiera dos matching en un conjunto estable Von Neumann-Morgenstern, la join es también un elemento del conjunto estable Von Neumann-Morgenstern (por simetría, el resultado paralelo también vale para la meet).

Ver PDF

Martes 17 de septiembre, 15:30 ~ 15:50

Operaciones de reticulado para el conjunto estable en mercados bilaterales sustituibles mediante dinámicas de reequilibrio

Noelia Juarez

Universidad Nacional de San Luis, Instituto de Matemática Aplicada San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

En este trabajo, calculamos las operaciones de reticulado del conjunto estable (por parejas) en mercados bilaterales en los que sólo se impone la sustituibilidad en las funciones de elección de los agentes. Para ello, utilizamos operadores de Tarski definidos en los reticulados de las asignaciones trabajador-cuasi-estable y firma-cuasi-estable. Estos operadores modelan la dinámica de las cadenas de despidos y vacantes, respectivamente. En primer lugar, calculamos las operaciones de reticulado en el modelo muchos- a-uno. A continuación, ampliamos estas operaciones a un modelo de muchos-a-muchos con funciones de elección sustituibles en ambos lados del mercado.

Trabajo en conjunto con: Agustín G. Bonifacio (UNSL, IMASL, Argentina) y Paola Manasero (UNSL, IMASL, Argentina).

Ver PDF

Martes 17 de septiembre, 16:20 ~ 16:40

Mecanismos de asignación eficiente en mercados muchos a muchos dinámicos

Adriana del Valle Amieva Rodriguez

Universidad Nacional de San Luis. Instituto de Matematica Aplicada San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

En este trabajo, analizamos la asignación de docentes a escuelas en un mercado muchos-a-muchos donde la variable temporal tiene un rol fundamental. Adaptamos un concepto de estabilidad a estos mercados y presentamos un mecanismo que calcula una asignación estable de forma dinámica, obteniendo resultados eficientes dentro del conjunto de asignaciones dinámicamente estables. No obstante, es posible encontrar asignaciones no dinámicamente estables que sean más eficientes para los trabajadores. Para estos casos, proponemos un mecanismo que calcula la asignación más eficiente fuera del conjunto de asignaciones dinámicamente estables.

Trabajo en conjunto con: Pablo Neme (Universidad Nacional de San Luis, Argentina) y Agustín Bonifacio (Universidad Nacional de San Luis, Argentina).

Ver PDF

Martes 17 de septiembre, 16:40 ~ 17:00

LP-approach for substitutable preferences in matching markets

Pablo Neme

UNSL-IMASL, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

En este trabajo estudiamos un modelo de matching muchos a uno con preferencias sustituibles. Presentamos una descomposición a un modelo uno a uno y un programa lineal cuyas soluciones enteras se corresponden con el conjunto de matching estables.

Trabajo en conjunto con: Jorge Oviedo (UNSL-IMASL,Argentina) y Marcelo Fernandez (John Hopkins University, EEUU).

Ver PDF

Martes 17 de septiembre, 17:00 ~ 17:20

Not obviously manipulable allotment rules

Agustín Bonifacio

Universidad Nacional de San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

In the problem of allocating a single non-disposable commodity among agents whose preferences are single-peaked, we study a weakening of strategy-proofness called not obvious manipulability (NOM). If agents are cognitively limited, then NOM is sufficient to describe their strategic behavior. We characterize a large family of own-peak-only rules that satisfy efficiency, NOM, and a minimal fairness condition. We call these rules "simple". In economies with excess demand, simple rules fully satiate agents whose peak amount is less than or equal to equal division and assign, to each remaining agent, an amount between equal division and his peak. In economies with excess supply, simple rules are defined symmetrically. These rules can be thought of as a two-step procedure that involves solving a claims problem. We also show that the single-plateaued domain is maximal for the characterizing properties of simple rules. Therefore, even though replacing strategy-proofness with NOM greatly expands the family of admissible rules, the maximal domain of preferences involved remains basically unaltered.

Trabajo en conjunto con: Pablo Arribillaga (Universidad Nacional de San Luis, Argentina).

Referencias

[1] ARRIBILLAGA, R. P. AND A. G. BONIFACIO (2024): “Obvious manipulations of tops-only voting rules,” Games and Economic Behavior, 143, 12–24.

[2] BARBERÀ, S., M. O. JACKSON, AND A. NEME (1997): “Strategy-proof allotment rules,” Games and Economic Behavior, 18, 1–21.

[3] CHING, S. AND S. SERIZAWA (1998): “A maximal domain for the existence of strategyproof rules,” Journal of Economic Theory, 78, 157–166.

[4] MASSÓ, J. AND A. NEME (2001): “Maximal domain of preferences in the division problem,” Games and Economic Behavior, 37, 367–387.

[5] ORTEGA, J. AND E. SEGAL-HALEVI (2022): “Obvious manipulations in cake-cutting,” Social Choice and Welfare, 1–20.

[6] SPRUMONT, Y. (1991): “The division problem with single-peaked preferences: a characterization of the uniform allocation rule,” Econometrica, 509–519.

[7] TROYAN, P. AND T. MORRILL (2020): “Obvious manipulations,” Journal of Economic Theory, 185, 104970.

Ver PDF

Miércoles 18 de septiembre, 9:40 ~ 10:00

Funciones simétricas y t-diseños esféricos en $\mathbb{R}^2$

Federico Nicolás Martínez

Universidad Nacional de San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Un subconjunto finito $X$ de $S^{n−1}$ in $\mathbb{R}^n$ es un $t-$diseño esférico si para cualquier polinomio $f (x) = f (x_1 , . . . , x_n )$ de grado a lo sumo $t$, el valor de la integral de $f(x)$ sobre $S^{n−1}$ dividido por el volumen de $S^{n−1}$ es igual al promedio de $f(x)$ en $X$. Intuitivamente, podemos decir que los puntos de $X$ están distribuidos de manera "óptima" en la esfera. Los $t$-diseños esféricos fueron introducidos en {\bf[DGS]} y son objeto de interés en diversas áreas de la matemática (ver también {\bf[BB]}).

En el caso $n=2$ los elementos del diseño pueden verse como números complejos de módulo 1 y podemos dar la siguiente definición equivalente: para $n,t\in\mathbb{N}$, $n\geq t+1$, el conjunto $X=\{z_1,\dots,z_n\}\subset S^1$ es un $t$-diseño esférico si y sólo si $\sigma_i( z_1,\dots,z_n)=0$ para $i=1,\dots,t$, donde $\sigma_i$ es la $i-$ésima función simétrica de los elementos de $X$. De esta forma podemos estudiar los $t$-diseños por medio de los coeficientes de los polinomios que tienen por raíces a sus elementos.

Así, las raíces enésimas de un número complejo de módulo 1 son un $t$-diseño esférico si $n \gt t$ al igual que uniones de conjuntos de este tipo (eg. la unión de raíces cúbicas y cuartas de respectivos números complejos de módulo 1 forman un 2-diseño esférico de 7 elementos, al igual que raíces séptimas de un tal número). Diseños obtenidos de esta forma se dicen de ``tipo grupo'' y son todos los $t$-diseños para $t+1\leq n\leq 2t+2$ mientras que, para $n\geq 2t+3$ existen, además, no numerables $t$-diseños de ``tipo no grupo'' (ver {\bf[H]}).

En {\bf[M]}, dados $k$ puntos en $S^1$ satisfaciendo ciertas condiciones determinadas por medio de sus funciones simétricas, se introduce un método para construir $t$-diseños esféricos en $\mathbb{R}^2$ con $2t+k$ elementos. Dichas condiciones también clarifican la naturaleza de los diseños de tipo grupo y dan una descripción geométrica del conjunto de los $t$-diseños esféricos en términos del $\sigma$-espacio.

\bigskip

{\bf Referencias}

{\bf [BB]}E. Bannai; E. Bannai. A survey on spherical designs and algebraic combinatorics on spheres. {\it European Journal of Combinatorics}, 30:1392–1425, 2009.

{\bf[DGS]} P. Delsarte; J. M. Goethals; J. J. Seidel. Spherical codes and designs. {\it Geometriae Dedicata}, 6:363–388, 1977.

{\bf[H]} Y. Hong. On spherical t-designs in $\mathbb{R}^2$ . {\it European Jounal of Combinatorics}, 3(3):255–258, 1982.

{\bf[M]} F. Martínez. Simmetric functions and spherical $t$-designs in $\mathbb{R}^2$. {\it Codes, Designs and Criptography}, 90:2563-2581, 2022.

Ver PDF

Miércoles 18 de septiembre, 10:00 ~ 10:20

Gaps en polinomios ciclotómicos binarios

Antonio Cafure

Universidad Nacional de General Sarmiento, CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

El conjunto de gaps de un polinomio dado por su representación densa es el conjunto de las distancias entre las potencias de monomios no nulos consecutivos. El máximo gap de un polinomio es el máximo de este conjunto.

En este contexto, el estudio de los gaps de los polinomios ciclotómicos ha cobrado relevancia en los últimos años como consecuencia de las aplicaciones a problemas de criptografía ([1], [2]). El primer caso importante de estudio es el caso de los polinomios ciclotómicos binarios. Un polinomio ciclotómico $\Phi_{n}$ se dice binario si $n = p q$, con $p \lt q$ números primos. Es sabido que el máximo gap de $\Phi_{p q}$ es igual a $p-1$ y que la cantidad de estos gaps es igual a $2\lfloor q/p \rfloor$ ([1], [2]). De todos modos queda aún por determinar el conjunto completo de gaps de $\Phi_{pq}$.

En esta comunicación presentaremos los dos resultados que siguen.

El primero de ellos da cuenta del segundo gap de $\Phi_{pq}$. En efecto, mostramos que si $3 \lt p \lt q$ son primos impares y $r \gt 0$ es el resto de $q$ módulo $p$, entonces el segundo gap de $\Phi_{pq}$ es igual al máximo entre $p-r-1$ y $r-1$.

El segundo resultado proporciona una caracterización combinatoria de los sucesivos gaps de $\Phi_{pq}$ cuando $ q \equiv \pm 1 \mod p$. En particular, implica el de [3] sobre la existencia de gaps de todas las longitudes.

Para obtener estos resultados apelamos a la interpretación de los polinomios ciclotómicos binarios en términos de una concatenación de palabras sobre el alfabeto $\{-1,0,1\}$ que introdujimos en nuestro trabajo [4].

Trabajo en conjunto con: Eda Cesaratto (Universidad Nacional de General Sarmiento, CONICET, Argentina).

Referencias

[1] Hong, H.; Lee, E.; Lee, H.; Park, C. Maximum gap in (inverse) cyclotomic polynomial. J. Number Theory 132, No. 10, 2297-2315 (2012).

[2] Zhang, B. Remarks on the maximum gap in binary cyclotomic polynomials. Bull. Math. Soc. Sci. Math. Roum., Nouv. Sér. 59(107), No. 1, 109-115 (2016).

[3] Camburu, O.; Ciolan, E.; Luca, F.; Moree, P.; Shparlinski, I. Cyclotomic coefficients: gaps and jumps. J. Number Theory 163, 211-237 (2016).

[4] Cafure, A.; Cesaratto, E. Binary cyclotomic polynomials: representation via words and algorithms. Lecroq, Thierry (ed.) et al., Combinatorics on words. 13th international conference, WORDS 2021, Rouen, France, September 13–17, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12847, 65-77 (2021).