共查询到20条相似文献,搜索用时 78 毫秒
1.
In the context of coalition formation games a player evaluates a partition on the basis of the set she belongs to. For this
evaluation to be possible, players are supposed to have preferences over sets to which they could belong. In this paper, we
suggest two extensions of preferences over individuals to preferences over sets. For the first one, derived from the most
preferred member of a set, it is shown that a strict core partition always exists if the original preferences are strict and
a simple algorithm for the computation of one strict core partition is derived. This algorithm turns out to be strategy proof.
The second extension, based on the least preferred member of a set, produces solutions very similar to those for the stable
roommates problem.
Received August 1998/Final version June 20, 2000 相似文献
2.
Minimizing risk models in stochastic shortest path problems 总被引:1,自引:0,他引:1
Yoshio Ohtsubo 《Mathematical Methods of Operations Research》2003,57(1):79-88
3.
Edward M. Bolger 《International Journal of Game Theory》2000,29(1):93-99
In Bolger [1993], an efficient value was obtained for a class of games called games with n players and r alternatives. In these games, each of the n players must choose one and only one of the r alternatives. This value can be used to determine a player’s “a priori” value in such a game. In this paper, we show that
the value has a consistency property similar to the “consistency” for TU games in Hart/Mas-Colell [1989] and we present a
set of axioms (including consistency) which characterizes this value.
The games considered in this paper differ from the multi-choice games considered by Hsiao and Raghavan [1993]. They consider
games in which the actions of the players are ordered in the sense that, if i >j, then action i carries more “weight” than action j.
These games also differ from partition function games in that the worth of a coalition depends not only on the partitioning
of the players but also on the action chosen by each subset of the partition.
Received: April 1994/final version: June 1999 相似文献
4.
We define a convex extension of a lower semi-continuous function to be a convex function that is identical to the given function
over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions
under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex
extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest
convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving
convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited
by various underestimators of $x/y$ over a rectangle and prove that the extensions theory provides convex relaxations that
are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms.
Received: December 2000 / Accepted: May 2002 Published online: September 5, 2002
RID="*"
ID="*" The research was funded in part by a Computational Science and Engineering Fellowship to M.T., and NSF CAREER award
(DMI 95-02722) and NSF/Lucent Technologies Industrial Ecology Fellowship (NSF award BES 98-73586) to N.V.S.
Key words. convex hulls and envelopes – multilinear functions – disjunctive programming – global optimization 相似文献
5.
6.
7.
8.
In this work we analyze the paper “Brimberg, J. (1995): The Fermat-Weber location problem revisited. Mathematical Programming 71, 71–76” which claims to close the question on the conjecture posed by Chandrasekaran and Tamir in 1989 on the convergence
of the Weiszfeld algorithm. Some counterexamples are shown to the proofs showed in Brimberg’s paper.
Received: January 1999 / Accepted: December 2001?Published online April 12, 2002
RID="*"
ID="*"Partially supported by PB/11/FS/97 of Fundación Séneca of the Comunidad Autónoma de la Región de Murcia
RID="**"
ID="**"Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica (I+I+D), project TIC2000-1750-C06-06
RID="*"
RID="**" 相似文献
9.
Dedicated to the Memory of Paul Erdős
We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b - 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan,
and Szegedy (1992) to this model, we construct families of explicit functions for which bits of communication are required to find the "missing bit", where n is the length of each player's input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities
(in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable
from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the
basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer
jumping function.
Received November 12, 1998
RID="*"
ID="*" Supported in part by NSA grant MSPR-96G-184.
RID="†"
ID="†" Supported in part by an NSF Graduate Fellowship. 相似文献
10.
Sigal Leviatan 《International Journal of Game Theory》2003,31(3):383-410
The consistent value is an extension of the Shapley value to the class of games with non-transferable utility.? In this paper,
the consistent value will be characterized for market games with a continuum of players of two types. We will show that for
such games the consistent value need not belong to the core, and provide conditions under which there is equivalence between
the two concepts.
Received: October 1998
RID="*"
ID="*" This thesis was completed under the supervision of Professor Sergiu Hart, The Center for Rationality and Interactive
Decision Theory, Department of Mathematics, Department of Economics, The Hebrew University of Jerusalem. I would like to thank
Professor Hart for introducing me to this area of research, for his help and guidance, and, especially, for all his patience.? I
would also like to thank Michael Borns for improving the style, and an anonymous referee for helpful comments. 相似文献
11.
Alison Watts 《International Journal of Game Theory》2007,35(4):505-519
A model of group formation is presented such that the number of groups is fixed, and a person can only join a group if the
group’s members approve the person’s joining. Agents have either local status preferences (each agent wants to be the highest
status agent in his group) or global status preferences (each agent wants to join the highest status group that she can join).
For both preference types, conditions are provided which guarantee the existence of a segregated stable partition such that
similar people are grouped together, and conditions are provided which guarantee the existence of an integrated stable partition
such that dissimilar people are grouped together. Additionally, in a dynamic framework we show that if a new empty group is
added to a segregated stable partition, then integration may occur. 相似文献
12.
Closed kernel systems of the coalition matrix turn out to correspond to cones of games on which the core correspondence is
additive and on which the related barycentric solution is additive, stable and continuous. Different perfect cones corresponding
to closed kernel systems are described.
Received: December 2001/Revised: July 2002
RID="*"
ID="*" This note contains the new results, which were presented by the first author in an invited lecture at the XIV Italian
Meeting on Game Theory and Applications in Ischia, July 2001. The lecture was dedicated to Irinel Dragan on the occasion of
his seventieth birthday. 相似文献
13.
14.
Christof Külske 《Probability Theory and Related Fields》2001,119(1):1-30
Can the joint measures of quenched disordered lattice spin models (with finite range) on the product of spin-space and disorder-space
be represented as (suitably generalized) Gibbs measures of an “annealed system”? - We prove that there is always a potential
(depending on both spin and disorder variables) that converges absolutely on a set of full measure w.r.t. the joint measure
(“weak Gibbsianness”). This “positive” result is surprising when contrasted with the results of a previous paper [K6], where
we investigated the measure of the set of discontinuity points of the conditional expectations (investigation of “a.s. Gibbsianness”).
In particular we gave natural “negative” examples where this set is even of measure one (including the random field Ising
model). Further we discuss conditions giving the convergence of vacuum potentials and conditions for the decay of the joint
potential in terms of the decay of the disorder average over certain quenched correlations. We apply them to various examples.
From this one typically expects the existence of a potential that decays superpolynomially outside a set of measure zero.
Our proof uses a martingale argument that allows to cut (an infinite-volume analogue of) the quenched free energy into local
pieces, along with generalizations of Kozlov's constructions.
Received: 11 November 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000
RID="*"
ID="*" Work supported by the DFG Schwerpunkt `Wechselwirkende stochastische Systeme hoher Komplexit?t' 相似文献
15.
We provide an axiomatic foundation of the expected utility preferences over lotteries on roles in simple superadditive games
represented by the two main power indices, the Shapley-Shubik index and the Banzhaf index, when they are interpreted as von
Neumann-Morgenstern utility functions. Our axioms admit meaningful interpretations in the setting proposed by Roth in terms
of different attitudes toward risk involving roles in collective decision procedures under the veil of ignorance. In particular,
an illuminating interpretation of `efficiency', up to now missing in this set up, as well as of the corresponding axiom for
the Banzhaf index, is provided.
November 7, 2002
RID="*"
ID="*" We want to thank M. Maschler, J. M. Zarzuelo and two referees for their comments. This research has been supported
by the IVIE, and by the DGES of the Spanish Ministerio de Educación y Cultura, under project PB96-0247. The first author also
acknowledges the financial support from the Ramón y Cajal Program initiated by the Spanish MCyT. 相似文献
16.
Sergei. S. Goncharov Valentina. S. Harizanov Julia. F. Knight Charles F. D. McCoy 《Archive for Mathematical Logic》2003,42(3):279-291
Let 𝒜 be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of 𝒜 in
which the image of R (?R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on 𝒜 and R, a necessary and sufficient condition for the existence of a computable copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.).
Received: 4 February 2001 Published online: 5 November 2002
RID="*"
ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899.
RID="*"
ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899.
RID="*"
ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. 相似文献
17.
Noritsugu Nakanishi 《International Journal of Game Theory》2009,38(2):249-261
We examine an n-player prisoners’ dilemma game in which only individual deviations are allowed, while coalitional deviations (even non-binding
ones) are not, and every player is assumed to be sufficiently farsighted to understand not only the direct outcome of his
own deviation but also the ultimate outcome resulting from a chain of subsequent deviations by other players. We show that
there exists a unique, noncooperative farsighted stable set (NFSS) and that it supports at least one (partially and/or fully)
cooperative outcome, which is individually rational and Pareto-efficient. We provide a sufficient condition for full cooperation.
Further, we discuss the relationship between NFSS and other “stable set” concepts such as the (myopic) von Neumann–Morgenstern
stable set, Harsanyi (1974)’s strictly stable set, Chwe (1994)’s largest consistent set, and the cooperative farsighted stable
set examined by Suzuki and Muto (2005).
The author is very grateful to Professor Eiichi Miyagawa, the editor and the associate editor of this journal for their insightful
comments and suggestions. He also acknowledges the financial support of Japan Society for the Promotion of Science [Grant-in-Aid
for Scientific Research (C), No. 18530175]. 相似文献
18.
This paper examines the role communication between players might serve in enabling them to reach an agreement on the future
play of a repeated game. The property of the communication process that we focus on is the amount of time it takes to complete.
We characterize the effects of such communication processes indirectly by determining the set of agreements they may yield.
A weak and a strong criterion are introduced to describe sets of agreements that are “stable” in the sense that players would
follow the current agreement and not seek to reach a new agreement. We show that as players become extremely patient, strongly
stable sets converge to Pareto efficient singletons. We apply the stability criteria to Prisoner’s Dilemmas and show how the
unique strongly stable set reflects asymmetries in the players’ stage-game payoffs. Finally, we model the communication process
as a Rubinstein alternating-offer bargaining game and demonstrate that the resulting agreements help characterize the strongly
stable set for a general class of communication mechanisms.
Received January 1998/final version June 1999 相似文献
19.
This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively
substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine
inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how
the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given.
Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method.
Received: April 23, 2001 / Accepted: May 2002
Published online: March 21, 2003
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="*"
ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt.
RID="#"
ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET
program TMR ERB FMRX-CT98-0202.
Mathematics Subject Classification (1991): 90C10 相似文献
20.
Milan Horniaček 《International Journal of Game Theory》2008,37(2):235-249
We analyze conditions under which negotiated agreements are efficient from the point of view of every possible coalition of
negotiators. The negotiators have lexicographic preferences over agreements they reach. Their utility is the first criterion.
The coalition reaching an agreement is the second criterion. In the analyzed non-cooperative discrete time bargaining game
Γ the players bargain about the choice from the sets of utility vectors feasible for coalitions in a given NTU game (N, V). If Γ has a Markov perfect equilibrium, then the set of equilibrium utility vectors in Markov perfect equilibria in it equals
the core of (N, V).
I thank an anonymous referee, an anonymous Associate Editor, and the Editor for their comments that helped me to improve the
paper. The research reported in this paper was supported by the Grant VEGA 1/1223/04 of the Ministry of Education of the Slovak
Republic. 相似文献