Algorítmica y Complejidad Computacional. Mecanismos, mercados, plataformas, algoritmos.

1. Hace unos días he recibido unos comentarios de un amable lector en relación a una entrada del año pasado sobre el Premio Nobel de Economía, concedido a investigadores que descubrieron Algoritmos que resolvían problemas de intercambio económico dónde no había posibilidad de aplicar el mecanismo de precios (ojo, estos mismos algoritmos se podrían aplicar también en casos dónde si hay mecanismo de precios).

Uno lee muchos papers académicos a lo largo del año y es un poco escéptico con la retórica introductoria habitual (en general en inglés) que aparece en muchos de ellos, que en  realidad son puramente teóricos: “esta investigación tiene múltiples aplicaciones prácticas bla bla bla…”, muy alejada de la realidad y que en ocasiones sólo busca tranquilizar a los financiadores  de la investigación, sean públicos o privados, que deben de justificar la asignación de fondos.

No digo que estos papers no sean interesantes (si pensase que no lo son no los leería), ni que no deban financiarse con dinero público o privado. Lo que no me parece del todo correcto es dar gato por liebre: dicha retórica sobra, salvo que sea verdad y en ocasiones, muchas, no lo es. Esto, teniendo en cuenta el crédito público que tienen los académicos es irresponsable, pues nunca se sabe quien puede leerlos y cómo puede actuar de acuerdo con dichas afirmaciones. En fin, que cada cual haga uso de su crédito cómo le venga en gana.

A lo que iba: para mi grata sorpresa, este lector que contactó conmigo  a través de la sección de comentarios, estaba utilizando uno de estos algoritmos nobelizados para resolver un problema práctico de su organización (que no se cual es, pero si aplicaba estas técnicas algorítmicas me imagino que debe de tener un tamaño considerable).

2. Por otra parte hay un campo emergente de publicación académica que se encuentra en la intersección entre Economía  (microeconomía),  E-commerceTeoría de Juegos y Algorítmica / Complejidad Computacional. No se si llamarlo Campo Interdisciplinar o Academic No Man´s Land.  En cualquier caso, en él podrían incluirse las publicaciones nobelizadas y otras sobre las que  he leído recientemente y que quiero reseñar aquí.

Por ejemplo, recientemente la Game Theory Society ha concedido un premio a los siguientes papers (de 2007 los dos) que, sin duda ninguna sí tienen múltiples aplicaciones prácticas en el campo de las Subastas On-Line de Anuncios.

Personalmente no tengo muy claro si el uso de la teoría de juegos en casos en los que agentes que participan en el intercambio son humanos es pertinente, pero sí parece serlo en casos en los que se trata de intercambios automatizados:

–Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz, “Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords,” American Economic Review 97, pages 242-259, 2007,

y

–Hal R. Varian, “Position Auctions,” International Journal of Industrial Organization 25, pages 1163-1178, 2007,

Copiamos literalmente la justificación de motivos emitida por el Comité para la concesión del Premio.

A very significant body of research at the interface of game theory and computer science concerns the design of automated mechanisms for economic transactions, which typically take place on the internet. A prime example are advertisements that search engines such as Google, Bing or Yahoo! place next to the results of internet searches for a given keyword. When a user clicks on such an ad, the search engine receives money from the advertiser. The payment is determined by an auction mechanism that computes the available advertisement “slots” to the bids which are dynamically provided by the bidders for each keyword search.

EOS and Varian (independently) analyzed an auction format known as the “generalized second price auction”, a term coined by EOS, which is now used by the major search engines. Their work is of unparalleled theoretical and practical influence. At the time of this writing, it has attracted over 1,400 combined citations (about 800 for EOS and 600 for Varian) and the two articles are by far the most influential papers in the area.

The design of market mechanisms that are implemented algorithmically represents a most fruitful interaction of game theory and computer science. The work of EOS and Varian has spawned research – and, also significantly, attractive jobs for economic and computing theorists – to an extent that they clearly deserve the Prize.

3. El otro paper que quería reseñar tiene más un aroma a Complejidad Computacional.

Título: Understanding Incentives: Mechanism Design becomes Algorithm.

El abstract es muy técnico y no dirá mucho al no iniciado. Por eso lo omitimos. En cambio algunas partes de la introducción si son más accesibles y pueden poner al lector en contexto sobre el tipo de cuestiones que se investigan en este No Man´s Land.

Extracto.

Mechanism design is the problem of optimizing an objective subject to “rational inputs.” The difference to algorithm design is that the inputs to the objective are not known, but are owned by rational agents who need to be provided incentives in order to share enough information about their inputs such that the desired objective can be optimized. The question that arises is how much this added complexity degrades our ability to optimize objectives, namely 

How much more computationally difficult is mechanism design for a certain objective compared to algorithm design for the same objective?

This question has been at the forefront of algorithmic mechanism design, starting already with the seminal work of Nisan and Ronen [27]. In a non-Bayesian setting, i.e. when no prior distributional information is known about the inputs, we now have strong separation results between algorithm and mechanism design. Indeed, a sequence of recent breakthroughs [28, 8, 21, 23] has culminated in combinatorial auction settings where welfare can be optimized computationally efficiently to within a constant factor for “honest inputs,” but it cannot be computationally efficiently optimized to within a polynomial factor for “rational inputs,” subject to well-believed complexity theoretic assumptions. Besides, the work of Nisan and Ronen studied the problem of minimizing makespan on unrelated machines, which can be well-approximated for honest machines, but whose approximability for rational machines still remains unknown.

In a Bayesian world, where every input is drawn from some known distribution, algorithm and mechanism design appear more tightly connected. Indeed, a sequence of surprising works [26, 25, 4] have established that mechanism design for welfare optimization in an arbitrary environment1 can be computationally efficiently reduced to algorithm design in the same environment, in an approximation-preserving way. A similar reduction has been recently discovered for the revenue objective [11, 12] in the case of additive bidders.  Here, mechanism design for revenue optimization in an arbitrary additive environment (computationally efficiently) reduces to algorithm design for virtual welfare optimization in the same environment, in an approximation-preserving manner. The natural question is whether such mechanism- to algorithm-design reduction is achievable for general bidder types (i.e. beyond additive) and general objectives (i.e. beyond revenue and welfare). This is what we achieve in this paper.

Es  curioso que en el intercambio con el amable lector precisamente salió el tema de que información estaba disponible para los agentes y cómo variaba el campo de aplicaciones de estos algoritmos.

4. Cómo se ve en todos estos papers, en este Academic No Man´s Land, hay una cierta graduación entre dos extremos, el agente autómata que meramente ejecuta algoritmos (con unos determinados requisitos de disponibilidad de información) y el agente humano que, en contexto de intercambio o de cualquier otro tipo de interacción, puede comportarse de manera racional o no, según le venga en gana en ese mismísimo momento (todos somos testigos a diario de esto :-)). Entre estos dos extremos un agente artificial dotado de una cierta racionalidad (¿ qué es ser racional ?), capaz de actuar con eficacia en el contexto de determinados mecanismos de intercambio automatizado.

Cómo se ve, aunque soy de los que piensa que no hay un más allá del ser humano sí creo que la aparición de este tipo de agentes artificiales no sometidos a imperativos biológicos es muy interesante para una teoría de la  racionalidad.

Cuando digo que no hay más allá quiero decir que opino que no seremos capaces de diseñar inteligencias artificiales:

— universales / multiuso,

–eficientes desde el punto de vista energético y viables desde el punto de vista económico, es decir cuyo coste de producción y mantenimiento sea menor que el de un ser humano.

superiores a la del ser humano; aunque seguramente sí iguales. Dicho de otra manera, el ser humano es la cota superior de la racionalidad. Por eso mismo a veces se puede permitir el lujo de la irracionalidad.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: