-
The work we present in this paper initiated the formal study of fractional
hedonic games, coalition formation games in which the utility of a player is
the average value he ascribes to the members of his coalition. Among other
settings, this covers situations in which players only distinguish between
friends and non-friends and desire to be in a coalition in which the fraction
of friends is maximal. Fractional hedonic games thus not only constitute a
natural class of succinctly representable coalition formation games, but also
provide an interesting framework for network clustering. We propose a number of
conditions under which the core of fractional hedonic games is non-empty and
provide algorithms for computing a core stable outcome. By contrast, we show
that the core may be empty in other cases, and that it is computationally hard
in general to decide non-emptiness of the core.
-
We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean
Space with arbitrary dimension $d$ where $n$ transportation requests are picked
i.i.d. with a separate origin-destination pair for each object to be moved.
First, we consider the problem from the customer perspective where the
objective is to compute a plan for transporting the objects such that the
Euclidean distance traveled by the vehicles when carrying objects is minimized.
We develop a polynomial time asymptotically optimal algorithm for vehicles with
capacity $o(\sqrt[2d]{n})$ for this case. This result also holds imposing LIFO
constraints for loading and unloading objects. Secondly, we extend our
algorithm to the classical single-vehicle PDP where the objective is to
minimize the total distance traveled by the vehicle and present results
indicating that the extended algorithm is asymptotically optimal for a fixed
vehicle capacity if the origins and destinations are picked i.i.d. using the
same distribution.
-
Consider a situation with $n$ agents or players where some of the players
form a coalition with a certain collective objective. Simple games are used to
model systems that can decide whether coalitions are successful (winning) or
not (losing). A simple game can be viewed as a monotone boolean function. The
dimension of a simple game is the smallest positive integer $d$ such that the
simple game can be expressed as the intersection of $d$ threshold functions
where each threshold function uses a threshold and $n$ weights. Taylor and
Zwicker have shown that $d$ is bounded from above by the number of maximal
losing coalitions. We present two new upper bounds both containing the
Taylor/Zwicker-bound as a special case. The Taylor/Zwicker-bound imply an upper
bound of ${n \choose n/2}$. We improve this upper bound significantly by
showing constructively that $d$ is bounded from above by the cardinality of any
binary covering code with length $n$ and covering radius $1$. This result
supplements a recent result where Olsen et al. showed how to construct simple
games with dimension $|C|$ for any binary constant weight SECDED code $C$ with
length $n$. Our result represents a major step in the attempt to close the
dimensionality gap for simple games.
-
Voting is a commonly applied method for the aggregation of the preferences of
multiple agents into a joint decision. If preferences are binary, i.e., "yes"
and "no", every voting system can be described by a (monotone) Boolean function
$\chi\colon\{0,1\}^n\rightarrow \{0,1\}$. However, its naive encoding needs
$2^n$ bits. The subclass of threshold functions, which is sufficient for
homogeneous agents, allows a more succinct representation using $n$ weights and
one threshold. For heterogeneous agents, one can represent $\chi$ as an
intersection of $k$ threshold functions. Taylor and Zwicker have constructed a
sequence of examples requiring $k\ge 2^{\frac{n}{2}-1}$ and provided a
construction guaranteeing $k\le {n\choose {\lfloor n/2\rfloor}}\in 2^{n-o(n)}$.
The magnitude of the worst-case situation was thought to be determined by
Elkind et al.~in 2008, but the analysis unfortunately turned out to be wrong.
Here we uncover a relation to coding theory that allows the determination of
the minimum number $k$ for a subclass of voting systems. As an application, we
give a construction for $k\ge 2^{n-o(n)}$, i.e., there is no gain from a
representation complexity point of view.
-
This paper studies the complexity of computing a representation of a simple
game as the intersection (union) of weighted majority games, as well as, the
dimension or the codimension. We also present some examples with linear
dimension and exponential codimension with respect to the number of players.
-
In this work we consider the problem of maximizing the PageRank of a given
target node in a graph by adding $k$ new links. We consider the case that the
new links must point to the given target node (backlinks). Previous work shows
that this problem has no fully polynomial time approximation schemes unless
$P=NP$. We present a polynomial time algorithm yielding a PageRank value within
a constant factor from the optimal. We also consider the naive algorithm where
we choose backlinks from nodes with high PageRank values compared to the
outdegree and show that the naive algorithm performs much worse on certain
graphs compared to the constant factor approximation scheme.
-
Using a one-dimensional jellium model and standard beam theory we calculate
the spring constant of a vibrating nanowire cantilever. By using the asymptotic
energy eigenvalues of the standing electron waves over the nanometer-sized
cross-section area, the change in the grand canonical potential is calculated
and hence the force and the spring constant. As the wire is bent more electron
states fits in its cross section. This has an impact on the spring"constant"
which oscillates slightly with the bending of the wire. In this way we obtain
an amplitude-dependent resonance frequency of the oscillations that should be
detectable.
-
Simple games cover voting systems in which a single alternative, such as a
bill or an amendment, is pitted against the status quo. A simple game or a
yes-no voting system is a set of rules that specifies exactly which collections
of ``yea'' votes yield passage of the issue at hand. A collection of ``yea''
voters forms a winning coalition.
We are interested on performing a complexity analysis of problems on such
games depending on the game representation. We consider four natural explicit
representations, winning, loosing, minimal winning, and maximal loosing. We
first analyze the computational complexity of obtaining a particular
representation of a simple game from a different one. We show that some cases
this transformation can be done in polynomial time while the others require
exponential time. The second question is classifying the complexity for testing
whether a game is simple or weighted. We show that for the four types of
representation both problem can be solved in polynomial time. Finally, we
provide results on the complexity of testing whether a simple game or a
weighted game is of a special type. In this way, we analyze strongness,
properness, decisiveness and homogeneity, which are desirable properties to be
fulfilled for a simple game.