RUI: Combinatorial Fixed Point Theorems, Polytopes, and Fair Division

SuDMS-0301129“RUI：组合不动点定理、多面体和公平分割“提案摘要研究者先前的工作已经将组合拓扑和离散几何的方法引入到数理经济学中某些“公平分割”问题的研究中。 目前的建议将支持这些方法背后的数学的发展和几个组合问题的解决方案，已从经济问题的动机，包括：（1）新的组合不动点定理的发展，（2）相关的单纯算法，和（3）研究最小三角剖分和最小单纯覆盖的多面体。 更广泛的影响，拟议的工作包括其跨学科的应用，以支持群体决策的谈判，并积极参与和培训的大学生在拟议的研究。非正式地说，一个“公平划分”的问题是关于寻找方法，划分一组货物之间的球员在这样一种方式，每个人都可以满意根据某种公平的概念。 这一点引起了经济学家、政治学家和博弈论家的兴趣，它经常引发有趣的数学问题。 这类问题的可能解决方案通常是一个高维多面体（多面体），人们通常可以通过将多面体分成许多块（四面体）来找到解决方案，并以玩家偏好为指导的方式在多面体中行走。 因此，数学上的多面体如何可以建立从它的四面体积木使用思想从三个领域（组合学，拓扑学和离散几何学）将直接应用于涉及人类战略和决策的社会科学中的重要问题。该奖项由数学科学部和社会，行为，和经济科学作为数学科学优先领域的一部分。

Abstract for Proposal of SuDMS-0301129"RUI: Combinatorial fixed point theorems, polytopes, and fair division"The investigator's prior work has introduced methods from combinatorialtopology and discrete geometry to the study of certain "fair division" questions in mathematical economics. The current proposal will supportthe development of the mathematics behind these methods and the solutionof several combinatorial questions that have been motivated from economicproblems, including: (1) the development of new combinatorial fixed pointtheorems, (2) associated simplicial algorithms, and (3) the study ofminimal triangulations and minimal simplicial covers of polytopes. Broader impacts of the proposed work include its interdisciplinaryapplication to negotiation support for group decision making, and theactive participation and training of undergraduates in the proposedresearch.Informally speaking, a "fair division" problem is concerned with findingmethods for dividing a set of goods among players in such a way thateveryone can be satisfied according to some notion of fairness. Thistopic is of interest to economists, political scientists, and gametheorists, and it often motivates interesting mathematical questions. The set of possible solutions in such problems is often a polyhedron ofhigh dimension (a polytope), and one can usually find a solution bybreaking the polytope into many pieces (tetrahedra), and walking aroundthe polytope in a way that is guided by player preferences. Thus themathematics of how polytopes can be built up from its tetrahedral buildingblocks using ideas from three areas (combinatorics, topology, and discretegeometry) will have direct application to important problems in the socialsciences involving human strategy and decision making.This award is being jointly funded by the Division of Mathematical Sciences and the Directorate of Social, Behavioral, and Economic Science as part of the Mathematics Sciences Priority Area.