共查询到20条相似文献,搜索用时 15 毫秒
1.
Xiaotie Deng Toshihide Ibaraki Hiroshi Nagamochi Wenan Zang 《Mathematical Programming》2000,87(3):441-452
Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by
solving a combinatorial optimization problem on the resources collectively owned by this subset. A solution of the game is
in the core if no subset of players is able to gain advantage by breaking away from this collective decision of all players.
The game is totally balanced if and only if the core is non-empty for every induced subgame of it.?We study the total balancedness
of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete characterization
for the total balancedness. For the packing and covering games [3], we completely clarify the relationship between the related
primal/dual linear programs for the corresponding games to be totally balanced. Our work opens up the question of fully characterizing
the combinatorial structures of totally balanced packing and covering games, for which we present some interesting examples:
the totally balanced matching, vertex cover, and minimum coloring games.
Received: November 5, 1998 / Accepted: September 8, 1999?Published online February 23, 2000 相似文献
2.
On the core of ordered submodular cost games 总被引:5,自引:0,他引:5
A general ordertheoretic linear programming model for the study of matroid-type greedy algorithms is introduced. The primal restrictions are given by so-called weakly increasing submodular functions on antichains. The LP-dual is solved by a Monge-type greedy algorithm. The model offers a direct combinatorial explanation for many integrality results in discrete optimization. In particular, the submodular intersection theorem of Edmonds and Giles is seen to extend to the case with a rooted forest as underlying structure. The core of associated polyhedra is introduced and applications to the existence of the core in cooperative game theory are discussed. Received: November 2, 1995 / Accepted: September 15, 1999?Published online February 23, 2000 相似文献
3.
Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving
network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle
canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and
the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems,
Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial
minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining
both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems.
Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999 相似文献
4.
In this paper we introduce the ℬ-prenucleolus for a transferable utility game (N,v), where ℬ⊆2
N
. The ℬ-prenucleolus is a straightforward generalization of the ordinary prenucleolus, where only the coalitions in ℬ determine
the outcome. We impose a combinatorial structure on the collection ℬ which enables us to compute the ℬ-prenucleolus in ?(n
3|ℬ|) time. The algorithm can be used for computing the nucleolus of several classes of games, among which is the class of
minimum cost spanning tree games.
Received: September 4, 1995 / Accepted: May 5, 1997?Published online June 8, 2000 相似文献
5.
We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume
that for any submodular function f: ?→R on a distributive lattice ?⊆2
V
with ?,V∈? and f(?)=0 and for any vector x∈R
V
where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|2) times, the descent method finds a sequence of subsets Z
1,Z
2,···,Z
k
of V such that f(Z
1)>f(Z
2)>···>f(Z
k
)=min{f(Y) | Y∈?}, where k is O(|V|2). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient
membership algorithms.
Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001 相似文献
6.
A model of taxation for cooperativen-person games is introduced where proper coalitions Are taxed proportionally to their value. Games with non-empty core under taxation at rate-balanced. Sharp bounds on in matching games (not necessarily bipartite) graphs are estabLished. Upper and lower bounds on the smallest in bin packing games are derived and euclidean random TSP games are seen to be, with high probability,-balanced for0.06. 相似文献
7.
We describe an O(n
4
hmin{logU,n
2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp
capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails
scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity
δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary
slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular
function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along
minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s
algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running
time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the
first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.
Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001 相似文献
8.
Given a linear transformation L:?
n
→?
n
and a matrix Q∈?
n
, where ?
n
is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,?
n
+,Q) over the cone ?
n
+ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R
n×n
, we consider the linear transformation L
A
:?
n
→?
n
defined by L
A
(X):=AX+XA
T
and show that the P- and Q-properties for L
A
are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov.
Received: March 1999 / Accepted: November 1999?Published online April 20, 2000 相似文献
9.
In this paper we consider a two-person zero-sum discounted stochastic game with ARAT structure and formulate the problem of
computing a pair of pure optimal stationary strategies and the corresponding value vector of such a game as a vertical linear
complementarity problem. We show that Cottle-Dantzig’s algorithm (a generalization of Lemke’s algorithm) can solve this problem
under a mild assumption.
Received July 8, 1998 / Revised version received April 16, 1999? Published online September 15, 1999 相似文献
10.
Henk Norde 《Mathematical Programming》1999,85(1):35-49
Received April 21, 1995 / Revised version received June 12, 1998 Published online November 24, 1998 相似文献
11.
In a fuzzy cooperative game the players may choose to partially participate in a coalition. A fuzzy coalition consists of
a group of participating players along with their participation level. The characteristic function of a fuzzy game specifies
the worth of each such coalition. This paper introduces well-known properties of classical cooperative games to the theory
of fuzzy games, and studies their interrelations. It deals with convex games, exact games, games with a large core, extendable
games and games with a stable core. 相似文献
12.
Received May 15, 1995 / Revised version received May 20, 1998 Published online October 21, 1998 相似文献
13.
Marion Scheepers 《Archive for Mathematical Logic》1999,38(2):103-122
For X a separable metric space and an infinite ordinal, consider the following three games of length : In ONE chooses in inning an –cover of X; TWO responds with a . TWO wins if is an –cover of X; ONE wins otherwise. In ONE chooses in inning a subset of which has the zero function in its closure, and TWO responds with a function . TWO wins if is in the closure of ; otherwise, ONE wins. In ONE chooses in inning a dense subset of , and TWO responds with a . TWO wins if is dense in ; otherwise, ONE wins. After a brief survey we prove:
1. If is minimal such that TWO has a winning strategy in , then is additively indecomposable (Theorem 4)
2. For countable and minimal such that TWO has a winning strategy in on X, the following statements are equivalent (Theorem 9):
a) TWO has a winning strategy in on .
b) TWO has a winning strategy in on .
3. The Continuum Hypothesis implies that there is an uncountable set X of real numbers such that TWO has a winning strategy in on X (Theorem 10).
Received: 14 February 1997 相似文献
14.
We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with
k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values.
Received: August 2001 / Accepted: January 2002?Published online March 27, 2002 相似文献
15.
16.
This paper is about set packing relaxations of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and set
packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines
carry over to the problems under investigation.
Received: September 1997 / Accepted: November 1999?Published online June 8, 2000 相似文献
17.
Tamás Solymosi 《International Journal of Game Theory》2002,31(1):1-11
It is well known that in three-person transferable-utility cooperative games the bargaining set ℳi
1 and the core coincide for any coalition structure, provided the latter solution is not empty. In contrast, five-person totally-balanced
games are discussed in the literature in which the bargaining set ℳi
1 (for the grand coalition) is larger then the core. This paper answers the equivalence question in the remaining four-person
case. We prove that in any four-person game and for arbitrary coalition structure, whenever the core is not empty, it coincides
with the bargaining set ℳi
1. Our discussion employs a generalization of balancedness to games with coalition structures.
Received: August 2001/Revised version: April 2002 相似文献
18.
We introduce a new class of totally balanced cooperative TU games, namely p-additive games. It is inspired by the class of inventory games that arises from inventory situations with temporary discounts
(Toledo Ph.D. thesis, Universidad Miguel Hernández de Elche, 2002) and contains the class of inventory cost games (Meca et al. Math. Methods Oper. Res. 57:481–493, 2003). It is shown that every p-additive game and its corresponding subgames have a nonempty core. We also focus on studying the character of concave or
convex and monotone p-additive games. In addition, the modified SOC-rule is proposed as a solution for p-additive games. This solution is suitable for p-additive games, since it is a core-allocation which can be reached through a population monotonic allocation scheme. Moreover,
two characterizations of the modified SOC-rule are provided.
This work was partially supported by the Spanish Ministry of Education and Science and Generalitat Valenciana (grants MTM2005-09184-C02-02,
ACOMP06/040, CSD2006-00032). Authors acknowledge valuable comments made by the Editor and the referee. 相似文献
19.
Fabrizio Germano 《International Journal of Game Theory》2006,34(4):561-581
Equivalence classes of normal form games are defined using the discontinuities of correspondences of standard equilibrium concepts like correlated, Nash, and robust equilibrium, or risk dominance and rationalizability. Resulting equivalence classes are fully characterized and compared across different equilibrium concepts for 2 × 2 games; larger games are also studied. It is argued that the procedure leads to broad and game-theoretically meaningful distinctions of games as well as to alternative ways of representing, comparing and testing equilibrium concepts. 相似文献
20.
In this paper, we relate several questions about cutting planes to a fundamental problem in the geometry of numbers, namely,
the closest vector problem. Using this connection we show that the dominance, membership and validity problems are NP-complete
for Chvátal and split cuts.
Received: August 28, 2001 / Accepted: March 2002?Published online May 8, 2002 相似文献