Grant: Discovery Grants Program - Individual

This proposal highlights three sets of open questions, all reflecting the interactions of finite orderings. Discrete Fair Division When and how can individuals with different preferences can jointly allocate something ?fairly?? This venerable yet easily understood mathematical problem has many potential applications, for example to negotiation and budgeting. The continuous allocation problem (?cake division?) has been well researched, but relatively little is known about allocating a set of indivisible objects, such as hard candies or paintings. The usual objectives are envy-freeness (no-one strictly prefers someone else?s portion) and Pareto-optimality (any other allocation would be less preferable for someone). The AL algorithm was recently proposed and linked to a theorem specifying exactly when a complete, Pareto-optimal, envy-free two-person allocation exists. But this theorem depends on a particular definition of envy-freeness, and does not indicate what to do when AL breaks down. One idea is to extend AL by combining it with a non-simultaneous algorithm like Undercut. Extension beyond two persons is another important goal. Computational studies can reveal vulnerabilities to insincere (untruthful) behaviour. Multi-Winner Electoral Systems The recent proliferation of electoral systems is probably due to the internet, where new ballots and counting rules have been invented and adopted. One theme of this program is multi-winner elections, for the most part a ?new frontier.? For such elections, approval voting, though designed for single-winner elections, is a natural procedure; the voter is asked to vote for every candidate he or she approves. An article on multi-winner elections in Handbook on Approval Voting distinguished elections in which the number of winners is known in advance from those in which the number of winners is determined from the ballots. Examples of the latter include Hall of Fame and short-listing elections. Properties of multi-winner procedures for approval ballots, such as the Next-Two Rule, are not well understood, and whether ""optimal"" systems exist is an open question. Another direction of research passes beyond approval ballots to yes-no ballots, in which voters support, oppose, or abstain on each candidate. The Handbook article generated considerable demand for this extension, which can be tested on real datasets. Graph Model This system for modelling and analyzing strategic conflicts has been applied to environmental, political, economic, and military conflicts. Its computer implementation (beta version) is widely used to understand interacting decisions with multidimensional implications. The graph model methodology is simple and flexible, yet nuanced enough to give insights into conflicts with many independent decision-makers (DMs). A model is always in one of finitely many states; DMs, who have different capabilities and preferences, control state changes. A natural prediction of outcome is an equilibrium, or a state that is stable for all DMs. A graph model is not a game, as mixed strategies cannot be evaluated since preferences are given as orderings but, despite its simplicity, it has proven surprisingly useful. One plan to develop the graph model methodology is to address an inverse problem: Is it possible to fill in missing preference information so as to create a desired equilibrium? This answer would guide ?third party? interveners, such as those who apparently averted war in the Euphrates basin several times. A second project is to explore the structure of graph models with a common DM in conflict with local DMs who care only about their local outcomes. For example, the government of China has several local conflicts over south-north (Yangtze to Yellow) water diversions.