Problemes de repartiment just i un joc de taula

• Natàlia Castellana ^[1]
  1. [1] Universitat Autònoma de Barcelona

     Universitat Autònoma de Barcelona

     Barcelona, España

     
• Localización: NouBiaix: revista de la FEEMCAT i la SCM, ISSN-e 2014-7104, ISSN 1133-4282, Nº. 40, 2017, págs. 6-22
• Idioma: catalán
• Enlaces
  • Texto completo
• Resumen
  • català

    En ciències socials i polítiques apareixen problemes de repartiment. Donats uns béns (divisibles o no), un es pregunta si existeix un repartiment just d’aquests entre uns participants. No busquem repartiments proporcionals, sinó que tothom estigui content amb el que té. Un concepte clau és el de repartiment sense enveja sota certes hipòtesis. Els problemes clàssics d’aquesta mena són els de repartir un pastís, però n’hi ha d’altres com el de repartir equips, habitacions, tasques...

    Donarem un parell d’exemples d’aquest tipus de problemes i com un lema aparentment innocent és la clau per provar l’existència de solucions: és el lema de Sperner. Aquest lema és molt rellevant per donar una demostració constructiva del conegut teorema del punt fix de Brouwer. I acabem amb una part lúdica: el joc del HEX.

  • English

    In political and social sciences, a fair division problem is a problem of dividing a set of goods or resources between several people, such that each person receives his/her due share. We are not interested in proportional division but in envy-free division, in which every partner is satisfied with his share and feels that his allocated share is at least as good as any other. Classical problems of this type are cutting cake and rental divisions. We present a couple of examples whose solution is based on a combinatorial lemma:

    Sperner’s lemma. The results also provide constructive proof of Brouwer’s Fixed Point Theorem. We conclude with an application to a table game: HEX.

• Referencias bibliográficas
  • Brouwer, L.E.J. (1912). Über Abbildung von Mannigfaltigkeiten. Math. Ann., 71, 97-115.
  • Knaster, B., Kuratowski, C., Mazurkiewicz, S. (1929). Ein Beweis des Fixpuntktsatzes für n-dimensionale Simplexe. Fund. Math, 14(1), 132-137.
  • Matoušek, J., Ziegler, G., Björner, A. (2014). Around Brouwer’s fixed point theorem, arXiv:1409.7890.
  • Simmons, F., Su, F. (2003). Consensus-halving via theorems of Borsuk-Ulam and Tucker. Math. Social Sci., 45, 15-25.
  • Sperner, E. (1928). Neuer beweis für die invarianz der dimensionszahl und des gebietes. Abh. Math. Sem. Univ. Hamburg, 6, 265-272.
  • Su, F. (1999). Rental Harmony: Sperner’s Lemma in Fair Division. Amer. Math. Monthly, 106, 930-942.