The Shapley value for shortest path games

In this paper shortest path games are considered. The transportation of a good in a network has costs and benet too. The problem is to divide the prot of the transportation among the players. Fragnelli et al (2000) introduce the class of shortest path games, which coincides with the class of monotone games. They also give a characterization of the Shapley value on this class of games. In this paper we consider further four characterizations of the Shapley value (Shapley (1953)'s, Young (1985)'s, Chun (1989)'s, and van den Brink (2001)'s axiomatizations), and conclude that all the mentioned axiomatizations are valid for shortest path games. Fragnelli et al (2000)'s axioms are based on the graph behind the problem, in this paper we do not consider graph specic axioms, we take TU axioms only, that is, we consider all shortest path problems and we take the view of abstract decision maker who focuses rather on the abstract problem than on the concrete situations.

The Shapley value for shortest path games

In this paper shortest path games are considered. The transportation of a good in a network has costs and benet too. The problem is to divide the prot of the transportation among the players. Fragnelli et al (2000) introduce the class of shortest path games, which coincides with the class of monotone games. They also give a characterization of the Shapley value on this class of games. In this paper we consider further four characterizations of the Shapley value (Shapley (1953)'s, Young (1985)'s, Chun (1989)'s, and van den Brink (2001)'s axiomatizations), and conclude that all the mentioned axiomatizations are valid for shortest path games. Fragnelli et al (2000)'s axioms are based on the graph behind the problem, in this paper we do not consider graph specic axioms, we take TU axioms only, that is, we consider all shortest path problems and we take the view of abstract decision maker who focuses rather on the abstract problem than on the concrete situations.

Optimal redistricting under geographical constraints: Why "pack and crack" does not work

We show that optimal partisan redistricting with geographical constraints is a computationally intractable (NP-complete) problem. In particular, even when voter's preferences are deterministic, a solution is generally not obtained by concentrating opponent's supporters in \unwinnable" districts ("packing") and spreading one's own supporters evenly among the other districts in order to produce many slight marginal wins ("cracking").

A computational approach to unbiased districting

In the context of discrete districting problems with geographical constraints, we demonstrate that determining an (ex post) unbiased districting, which requires that the number of representatives of a party should be proportional to its share of votes, turns out to be a computationally intractable (NP-complete) problem. This raises doubts as to whether an independent jury will be able to come up with a “fair” redistricting plan in case of a large population, that is, there is no guarantee for finding an unbiased districting (even if such exists). We also show that, in the absence of geographical constraints, an unbiased districting can be implemented by a simple alternating-move game among the two parties.

Existence of Pure Strategy Nash Equilibrium in Bertrand-Edgeworth Oligopolies

This article is searching for necessary and sufficient conditions which are to be imposed on the demand curve to guarantee the existence of pure strategy Nash equilibrium in a Bertrand-Edgeworth game with capacity constraints.

Does timing of decisions in a mixed duopoly matter?

We determine the endogenous order of moves in a mixed pricesetting duopoly. In contrast to the existing literature on mixed oligopolies we establish the payo equivalence of the games with an exogenously given order of moves if the most plausible equilibrium is realized in the market. Hence, in this case it does not matter whether one becomes a leader or a follower. We also establish that replacing a private firm by a public firm in the standard Bertrand-Edgeworth game with capacity constraints increases social welfare and that a pure-strategy equilibrium always exists.

Optimal partisan districting on planar geographies

We show that optimal partisan districting in the plane with geographical constraints is an NP-complete problem.