Speakers and abstracts

Clemens Puppe and Attila Tasnadi, Axiomatic Districting

We study the districting problem from an axiomatic point of view in a framework with two parties, deterministic voter preferences and geographical constraints. The axioms are normatively motivated and reflect a notion of fairness to voters. Our main result is an “impossibility” theorem demonstrating that all anonymous districting rules are necessarily complex in the sense that they either use information beyond the mere number of districts won by the parties, or they violate an appealing consistency requirement according to which an acceptable districting rule should induce an acceptable districting of appropriate subregions.

Lars Ehlers and Alexander Westkamp, Strategy-Proof Tie-Breaking:

We study a general class of priority-based allocation problems with weak priority orders. Our aim is to identify tractable conditions on priority structures that guarantee the existence of a strategy-proof mechanism that always chooses an agent-optimal stable, or constrained efficient, matching.  The existence of such mechanisms is known for strict priority structures (Dubins and Freedman, 1981; Roth, 1982) and simple ownership priority structures (Abdulkadiroglu and Sonmez, 1999). Weak priority structures are perfectly pairwise variable if for any pair of distinct agents i and j, there exists an object for which i has strictly higher priority than j. Our main result shows that out of the whole class of perfectly pairwise variable priority structures a strategy-proof and constrained efficient mechanism could potentially exist only for three types of priority structures: Strict, simple ownership, or simple exclusion priority structures, where for each object there is at most one agent who has strictly lower priority than any other agent.

Bettina Klaus and Jonathan Newton, Stochastic Stability in Assignment Problems:

In a dynamic model of assignment problems, small deviations suffice to move between stable outcomes. This result is used to obtain no-selection and almost-no-selection results under the stochastic stability concept for uniform and payoff-dependent errors. There is no-selection of partner or payoff under uniform errors, nor for agents with multiple optimal partners under payoff-dependent errors. There can be selection of payoff for agents with a unique optimal partner under payoff-dependent errors. However, when every agent has a unique optimal partner, almost-no-selection is obtained.

Baharak Rastegari, Size Versus Truthfulness in the House Allocation Problem:

We study the House Allocation problem (also known as the Assignment problem), i.e., the problem of allocating a set of objects among a set of agents, where each agent has ordinal preferences (possibly involving ties) over a subset of the objects.  We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings.  It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2.  We thus consider randomized mechanisms.  We give the first explicit extensions of the classical Random Serial Dictatorship Mechanism (RSDM) to the case where preference lists can include ties.  We thus obtain a universally truthful randomized mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of e/(e-1).  The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching.  

Jay Sethuraman, Rationing Problems in Bipartite Networks:

In the bipartite rationing problem, a set of agents share a single resource available in different types, each agent has a claim over only a subset of the resource-types, and these claims overlap in arbitrary fashion. The goal is to divide fairly the various types
of resource between the claimants, when resources are in short supply. When there is single type of resource, this is the standard rationing problem, which has been studied extensively in the economics literature. Some popular solutions to this problem include
the proportional, uniform gains, and uniform losses methods. We consider various generalizations of these methods to the network context, and characterize the solutions using compelling axioms used in the economics literature on rationing. I will focus on two standard requirements – truthfulness and consistency – and discuss ways of extending standard rationing methods to the network setting while satisfying these properties. (Based on joint work with Herve Moulin, Shyam Chandramouli, Olivier Bochet, and Rahmi Ilkilic.)

Serge Galam, From Majority Rule Voting to Democratic Dictatorship:

The stability of a leadership against a growing internal opposition is studied in bottom up hierarchical organizations. Using a very simple model with bottom-up majority rule voting, the dynamics of power distribution at the various hierarchical levels is calculated within a probabilistic framework. Given a leadership at the top, the opposition weight from the hierarchy bottom is shown to fall off quickly while climbingup the hierarchy. It reaches zero after only a few hierarchical levels. Accordingly, an opposition can grow steadily from few percents up to seventy seven percents with no change at the elected top level. However and in contrast, from one election to another, less than one percent additional shift at the bottom level can drive a drastic and brutal change at the top. In addition to analytical formulas, results from a large scale simulation are presented. The results may provide some new insight on last century’s Eastern European communist collapse. S. Galam, Sociophysics : A Physicist’s Modeling of Psycho-political Phenomena, Springer (2012) S. Galam, The Drastic Outcomes from Voting Alliances in Three-Party Democratic Voting (1990 -> 2013), Journal of Statistical Physics, 151 (2013)  46-68

Friedrich Pukelsheim, Negative Voting Weights in the Former Electoral System for the German Bundestag:

Formerly the election system for the Bundestag admitted an effect of non-monotonicity:  more votes could result in fewer seats.  In the talk I recount the history of this effect, and describe its removal in the 2013 amendment of the Federal Election Law.

Flip Klijn and Ayse Yazici, A Many-to-Many “Rural Hospital Theorem”:

We show that the full version of the so-called “rural hospital theorem” generalizes to many-to-many matching problems where agents on both sides of the problem have substitutable and weakly separable preferences. We reinforce our result by showing that when agents’ preferences satisfy substitutability, the domain of weakly separable preferences is also maximal for the rural hospital theorem to hold.

David Cantala and Szilvia Papai, Reasonably and Securely Stable Matching:

We are interested in stability concepts that are weaker than the standard stability concept in the context of matching agents to objects on a one-to-one basis, when the objects are matched to agents based on strict priorities for each object. The standard stability concept is the usual core stability which rules out justified envy objections, and it is well-known that in this setting stability and efficiency cannot be reconciled. If we insist on efficiency and consider stability secondary, then we must consider weaker notions of stability that are compatible with efficiency for arbitrary strict priorities. We consider two such weaker notions of stability in this paper. Reasonable Stability allows for justified envy objections if there is a counter-objection of the same type, and Secure Stability allows for justified envy objections if there is a counter-objection by an agent who has a higher priority for the object than the objecting agent does. Our results indicate that the DA-TTC rule, which takes the agent-optimal stable matching as endowments and applies Gale’s Top Trading Cycle rule to them, stands out as the best matching rule that satisfies our criteria.     

Albin Erlanson and  Karol Szwagrzak, Strategy-Proof Package Assignment:

We examine the strategy-proof allocation of multiple divisible and indivisible resources; an  application is the assignment of packages of tasks, workloads, and compensations among the  members of an organization. We find that any allocation mechanism obtained by maximizing a separably concave function over a polyhedral extension of the set of Pareto-efficient allocations is strategy-proof. Moreover, these are the only strategy-proof and unanimous mechanisms satisfying a coherence property and responding well to changes in the availability of resources. These mechanisms generalize the parametric rationing mechanisms (Peyton Young, 1987, Mathematics of Operations Research 12 (3), 397-414.), some of which date back to the Babylonian Talmud.

Felix Brandt and Christian Geist, Finding Strategyproof Social Choice Functions via SAT Solving:

A promising direction in computational social choice is to address open research problems using computer-aided proving techniques. In conjunction with SAT solving, this approach has been shown to be viable in the context of classic impossibility theorems such as Arrow’s impossibility as well as axiomatizations of preference extensions. In this presentation, we demonstrate that it can also be applied to the more complex notion of strategyproofness for irresolute social choice functions. These types of problems, however, require a more evolved encoding as otherwise the search space rapidly becomes much too large. We present an efficient encoding for translating such problems to SAT and leverage this encoding to prove new results about strategyproofness with respect to Kelly’s and Fishburn’s preference extensions. For example, we show that no Pareto-optimal majoritarian social choice function satisfies Fishburn-strategyproofness.