Speaker:
Irinel Dragan
Title:
On Semivalues and TU games on matroids
Abstract:
Recently, Bilbao ([1]} has introduced a Shapley value for transferable
utility games on combinatorial structures like matroids and convex
geometries. In the case of matroids, we see that the usual property of
each component of the payoff, to depend on all values of the characteristic
function does not hold. Therefore, we
felt that an alternative definition which is correcting this fact is
appropriate, and
this is what we intend to do in the present paper, starting from t
he Semivalues of cooperative TU games.
The Semivalues were introduced by Dubey, Neyman and Weber by a system of
axioms for general cooperative games ([4]). In the case of cooperative
TU games
they obtained a formula for Semivalues which can be taken as a definition.
The formula shows a family of values depending on a vector of weights;
for particular
weights is obtained the Shapley value, the famous value due to
L.S.Shapley ([7]).
It is easy to show that the unique Semivalue which is efficient is the
Shapley value.
We show an algebraic proof of this fact (Theorem 1), which suggests an
alternative definition for the Shapley value on matroids.
The matroids were introduced by Whitney ([9]) and the body of knowledge
connected
to this combinatorial concept has been further developed into a
subject ([8]). Here
we need only one of the many definitions of the matroids ([6]).
We need also our
earlier result, giving the power game of a TU game relative to
a Semivalue ([2]).
The class of Semivalues on matroids is formally defined as the
Semivalues of games
which have a given characteristic function on the matroid, with
zero values on the
dependent sets of the matroid. As the grand coalition does not
belong in general to
the set of independent sets, except in the case of the free monoid,
the usual definition
of the efficiency has no meaning. We introduce a matroid-efficiency
concept, which
looks similar to Bilbao's efficiency, but has a more general meaning,
and by using
this type of efficiency we get a family of Semivalues depending on one
parameter
(Theorem 2). A unique value is obtained, which has the highest efficiency
level and
this is a generalization of the Shapley value (Theorem 3).
An example shows that this
is different of the Bilbao's value, however the Bilbao's value is
a value obtained from
the same matroid-efficiency for a lower level of efficiency.
We prove that the new
Shapley value has the dummy player property for some type of
matroids (Theorem 4).
As the Semivalues on matroids have a potential, the new value
has a potential of Hart/
Mas-Colell type ([5]) and also what we call a recursive definition
and a Shapley blue-
print property (Theorems 5,6, and 7), ([3]). A few results from
Matroid theory and
from Game theory are presented in order to make the paper self
contained.
References.
[1] Bilbao, J.M., (2000), Cooperative games on combinatorial structures,
Kluwer Academic, Boston/Dordrecht/London.
[2] Dragan,I., (2002), On the inverse problem for Semivalues of
cooperative TU games, TR # 348, Univ. Texas at Arlington, April 2002.
[3] Dragan,I., (1999), Potential, Balanced contributions,
Recursion formula, Shapley
blueprint properties of values of cooperative TU games, in H.DeSwart
(ed.), Proceedings of the Conference on Logic, Game Theory and
Social Choice, Tilburg Univ. Press, Tilburg, pp.57-67.
[4] Dubey,P., Neyman,A., and Weber,R.J., (1981), Value theory without efficiency, Math. O.R., 6, pp.122-128.
[5] Hart,S., and Mas-Colell,A., (1989), Potential, value and consistency, Econometrica, 57, pp.589-614.
[6] von Randow,R., (1975), Introduction to the theory of matroids, Springer, Berlin.
[7]
Shapley,L.S., (1953), A value for n-person games, Ann.Math.Studies, no.28, pp.307-317
[8]
Welsh,D.J.A., (1976), Matroid theory, Academic Press, London.
[9]
Whitney, H., (1935), On the abstract properties of linear dependence, American journal
of mathematics 57, pp.509-533.
|
Speaker:
Ira Gessel
Title: P-partitions
Abstract:
An ordinary partition of n with k parts is a weakly decreasing sequence of
positive integers with sum k. In the late 19th century, Percy MacMahon,
studied plane partitions, in which the parts are arranged in a rectangle
and decrease in rows and columns. For example,
42211
433
211
is a plane partition of 24. An ordinary partition may be viewed as an
order-reversing map from a chain to the totally ordered set of nonnegative
integers, and a plane partition may similarly be viewed as an order
reversing map from a product of two chains to the nonnegative integers.
The general theory of P-partitions considers order-reversing (or
order-preserving maps) from an arbitrary finite partially ordered set P to
a totally ordered set. The fundamental result in the theory of
P-partitions is a close connection between P-partitions and the set of
extensions of P to a total order.
The descents of a permutation of 1, 2, ... , n are the positions where one
number is immediately followed by a smaller number. For example, the
descents of the permutation 4 1 3 5 2 correspond to 4 > 1 and 5 > 2. If we
take our poset P to be an arbitrary partial order on {1, 2, ... , n} the
extensions of P to a total order may be identified with permutations of
{1, 2, ... , n}, and the theory of P-partitions helps in counting these
permutations by descents.
I will describe some applications of P-partitions to permutation
enumeration, and specifically to Eulerian numbers, Simon Newcomb's
problem, Stirling numbers, and descent algebras.
|
Speaker:
Illya Hicks
Title: Theoretical and Practical Applications of Branch
Decompositions
Abstract:
The notion of branch decompositions and its connectivity invariant,
branchwidth, were used by Robertson and Seymour to prove the Graph
Minors Theorem, formally known as Wagner's Conjecture. In addition,
theoretical computer scientists have shown that some NP-hard problems
can be solved when modeled on graphs with bounded branchwidth.
Thus, branch decompositions have both theoretical and practical
applications. In this talk, we will
explore some of the numerous applications of branch decompositions. In
particular, we will discuss algorithms to construct branch
decompositions and the usage of branch decompositions to solve
certain NP-hard problems like TSP, minor containment, and constructing
optimal branch decompositions
for general graphs.
|
Speaker:
Michal Karonski
Title: Irregular Assignments
Abstract:
A weighting of the edges of a graph with integer weights gives
rise to a weighting of the vertices, the weight of a vertex being
the sum of the weights of its incident edges.
An assignment of positive integer weights to the edges of a simple
graph $G$ is called irregular if the weighted degrees of the
vertices are all different. The irregularity strength
is the maximal weight, minimized over all irregular
assignments.
In the first part of my talk I shall discuss some recent results
on irregularity strength of graphs, in particular of regular
graphs and trees.
An assignment of positive integer weights to the edges of a simple
graph $G$ is called locally irregular if the weighted
degrees of adjacent vertices are different. Obviously, such vertex
weighting induce a proper coloring of the graph. In this context,
the following question has been raised: Is it possible to weight
the edges of any connected graph with at least three vertices,
with the integers {1,2,3}, such that the resultant vertex
weighting is a proper coloring? In the second part of my talk I
will offer two pieces of information in relation to the
above question:
first, that a weighting is possible for $3$-colorable graphs, and
secondly that, if real, rather than just integer, weights are
permitted, then a finite
number of weights suffices for all graphs.
The talk is based on joint work with Alan Frieze, Mike Ferrara,
Ron Gould, Tomasz Luczak, Florian Pfender and Andrew Thomason.
|
Speaker:
D. T. Lee
Title:
Power Domination Problem in Graphs
Abstract:
We consider a variation of graph-theoretic domination problem that
arises in monitoring an electric power system of its voltage and current
states at loads and branches of the power system respectively.
To monitor or observe an electric power system by placing as few phase
measurement units as possible is closely related to the famous vertex
cover problem and domination problem in graph theory. A set S is a
power dominating set (PDS) of a graph G=(V,E), if every vertex and
every edge in the graph modeling a power system are observed following
certain observation rules of power system monitoring. The minimum
cardinality of a PDS of a graph G is the power domination number of G.
We shall show that the problem of finding the power domination number
for split graphs, a subclass of chordal graphs, is NP-complete. We thus
consider this problem for a subclass of chordal graphs, i.e., interval
graphs. Specifically we shall present a linear time algorithm
for finding the minimum PDS of an interval graph, if the interval
model of the graph is provided and the endpoints of the intervals are
given sorted. We also extend the result to the class of circular-arc graphs.
Some open problems will be given in this presentation.
Joint work with Chung-Shou Liao,
Institute of Information Science, Academia Sinica, Taiwan
|
Speaker:
Benny Sudakov
Title: Solving extremal problems using stability approach
Abstract:
In this talk we discuss a "stability approach" for solving
extremal problems. Roughly speaking, it can be described as follows. In
order to show that given configuration is a unique optimum for an extremal
problem, we first prove an approximate structure theorem for all
constructions whose value is close to the optimum and then use this
theorem to show that any imperfection in the structure must lead to a
suboptimal configuration. To illustrate this strategy, we discuss three
recent results in which stability approach was used to answer a question
of Erdos-Rothschild and to resolve two conjectures of Sos and Frankl.
All the results in this talk are co-authored with P. Keevash and the first
one is in addition co-authored with N. Alon and J. Balogh.
|
Speaker:
Tandy Warnow
Title:Graph-theoretic algorithms for phylogeny reconstruction
Abstract:
Phylogenies are evolutionary trees, and phylogeny reconstruction
plays an important role in both biology and historical linguistics.
In this talk I will present some new methods for reconstructing
phylogenies that rely upon very pretty graph theory. In particular,
I will present the "triangulating colored graphs Problem" and
show how it is related to reconstructing phylogenies in
historical linguistics.
|
Speaker:
Xingxing Yu
Title: Independent trees in graphs
Abstract:
In 1984, Itai and Rodeh proposed a multi-tree approach to
reliability in distributed networks. A fault-tolerant communication
scheme can be designed for a network if we are able to find rooted spanning
trees which are independent. Two rooted spanning trees are independent if,
for each vertex, the paths in the trees from that vertex to the root are
internally disjoint. The main problem of interest is whether
every k-connected graph contains k pairwise independent spanning trees.
Itai and Rodeh solved the problem for k=2. Cheryian and
Maheshwari, and independently, Itai and Zehavi, solved the problem for k=3.
The case k=4 is important in a number of aspects, and Huck solved it for
planar graphs. In this talk, I will outline a solution to the problem for all
4-connected graphs.
This includes a decomposition result of 4-connected graphs,
and a cubic algorithm for finding 4 independent spanning trees in
a 4-connected graph.
Connection to other graph theory problems will also be discussed.
|
|
