Thesis
|
Estévez-Fernández, A. (2006)
"Cooperative behavior, competition and operations research", PhD thesis,
Tilburg University, The Netherlands.
(
Abstract)
(CentER Ph.D. Thesis Series)
|
Game theory is the mathematical tool to study
cooperation and competition. Since the beginnings of operations research and game theory both fields
have been closely related. This thesis further investigates this relationship. Costs or rewards
sharing problems arising from scheduling problems, traveling salesman problems and project management
are investigated within the framework of game theory. Refinements of the set of optimal solutions of
linear programming problems are studied by making use of the relationship betweenof linear
programming problems, linear complementarity problems, and matrix games. Finally, competitive
environments, i.e. bimatrix games for which some appealing properties of matrix games are kept, are
analyzed. |
|
|
Publications
-
Lazarova, E., Borm, P., and Estévez-Fernández, A.
(2016) "Transfers and exchange-stability in two-sided matching problems" Theory and Decision 81, 53-71.
(Previously TI 2014-086/II)
(Abstract)
|
In this paper we consider one-to-many matching problems
where the preferences of the agents involved are represented by monetary reward functions.
We characterize Pareto optimal matchings by means of contractually exchange stability and
matchings of maximum total reward by means of compensation exchange stability. To
conclude, we show that in going from an initial matching to a matching of maximum total
reward, one can always provide a compensation schedule that will be ex-post stable in
the sense that there will be no subset of agents who can all by deviation obtain a higher
reward. The proof of this result uses the fact that the core of an associated
compensation matching game with constraints is nonempty. |
|
-
Sánchez, E., Borm, P., Estévez-Fernández, A., Fiestras-Janeiro, M.G., and Mosquera, M.A.
(2015) "k-core covers and the core", Mathematical Methods of Operations Research
81, 147-167.
(Abstract)
(Previously TI 2013-177/II )
|
This paper extends the notion of individual minimal
rights for a transferable utility game (TU-game) to coalitional minimal rights using
minimal balanced families of a specific type, thus defining a corresponding minimal
rights game. It is shown that the core of a TU-game coincides with the core of the
corresponding minimal rights game. Moreover, the paper introduces the notion of the
k-core cover as an extension of the core cover. The k-core cover of a
TU-game consists of all efficient payoff vectors for which the total joint payoff for any
coalition of size at most k is bounded from above by the value of this coalition
in the corresponding dual game, and from below by the value of this coalition in the
corresponding minimal rights game. It is shown that the core of a TU-game with player
set N coincides with the ⌊|N|/2⌋-core
cover. Furthermore, full characterizations of games for which a k-core
cover is nonempty and for which a k-core cover coincides with the core are
provided. |
|
-
Van den Brink, R., Estévez-Fernández, A., van der Laan, G., and Moes, N. (2014)
"Independence of downstream and upstream benefits in river water allocation problems", Social Choice and Welfare 43, 173-194.
(Abstract)
(Previously TI 2011-128/1)
|
We consider the problem of sharing
water among agents located along a river.Each agent has quasi-linear preferences over river water
and money, where the benefit of consuming an amount of water is given by a continuous and concave
benefit function. A solution to the problem efficiently distributes the river water over the
agents and wastes no money. We introduce a number of (independence) axioms to characterize two new
and two existing solutions. We apply the solutions to the particular case that every agent has
constant marginal benefit of one up to a satiation point and marginal benefit of zero thereafter.
In this case we find that two of the solutions (one existing and one new) can be implemented
without monetary transfers between the agents. |
|
-
Estévez-Fernández, A. and Reijnierse, H. (2014)
"On the core of cost-revenue games: minimum cost spanning tree games with revenues", European Journal of Operational Research 237, 606-616.
(Abstract)
(Previously TI 12-101/II)
|
In this paper, we analyze cost sharing problems arising from a general service by
explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with
transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value
of a coalition is defined as the maximum net profit that the coalition may obtain by means of cooperation. As a result, a coalition
may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of c
ost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service
under consideration to all its members, it is shown that a cost-revenue game has a non-empty core for any vector of revenues if,
and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games
with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum
cost spanning tree game with revenues has a non-empty core. Furthermore, we provide an example of a minimum cost spanning tree game
with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost). |
|
-
Estévez-Fernández, A., Borm, P., and Hamers, H. (2012) "A note on passepartout problems",
International Game Theory Review 14 (2), 1250013 (9 pages).
(Abstract)
(Previously TI 2010-031/1 and,
originally, "The museum pass game and its value "revisited"",
CentER DP 2004-07)
|
This note provides a methodological
contribution to the allocation of joint revenues obtained from passepartouts. In a passepartout
system a group of service providers offers a passepartout that allows its owners the use of
specified services for an unlimited number of times during a fixed period of time. The
corresponding allocation problem is then how to share the total joint revenues of the passepartout
system adequately among the service providers. Arguments are provided to model a passepartout
problem within the framework of bankruptcy and context-specific properties are considered in order
to select an appropriate allocation rule. |
|
-
Estévez-Fernández, A., Fiestras-Janeiro, M.G., Mosquera, M.A.,
Sánchez, E. (2012) "A bankruptcy approach to the core cover",
Mathematical Methods of Operations Research 76, 343-359.
(Abstract)
(Previously TI 2012-012/1)
|
In this paper we establish a
relationship between the core cover of a compromise admissible game and the core of a particular
bankruptcy game: the core cover of a compromise admissible game is, indeed, a translation of the
set of coalitional stable allocations captured by an associated bankruptcy game. Moreover, we
analyze the combinatorial complexity of the core cover and, consequently, of the core of a
compromise stable game. |
|
-
Estévez-Fernández, A. (2012) "New characterizations for largeness of the core ",
Games and Economic Behavior 76 160-180.
(Abstract) (Previously
TI 2011-086/1)
|
In this paper, we provide three new
characterizations of largeness of the core. The first characterization of largeness of the core is
based on minimal covers of the grand coalition and associated inequalities. The second
characterization shows the relation between the bases that provide core elements of the game and
the bases that provide core elements of the games that are obtained from the original one by
increasing the value of the grand coalition. The third characterization of largeness of the core
is based on the idea that if a base of the grand coalition does not provide a core element of the
game, it should not provide a core element of a game which differs from the original one only by
an increase of the value of the grand coalition. Based on these new characterizations, we show the
equivalence between largeness of the core and stability of the core for games with at most 5
players and we revise some results on the literature concerning largeness of the core. |
|
-
Estévez-Fernández, A. (2012)
"A game theoretical approach to sharing penalties and rewards in projects",
European Journal of Operational Research 216, 647-657.
(Abstract) (Previously
TI 2009-090/1)
|
This paper analyzes situations in which a project
consisting of several activities is not realized according to plan. If the project is expedited, a
reward arises. Analogously, a penalty arises if the project is delayed. This paper considers the
case of arbitrary monotonic reward and penalty functions on the total expedition and delay,
respectively. Attention is focused on how to divide the total reward (penalty) among the
activities: the core of a corresponding cooperative project game determines a set of stable
allocations of the total reward (penalty). In the definition of project games,surplus (cost)
sharing mechanisms are used to take into account the specific characteristics of the reward
(penalty) function at hand. It turns outs that project games are related to bankruptcy and
taxation games. This relation allows us to establish the nonemptiness of the core of project games.
|
|
-
Apt, K., Estévez-Fernández, A. (2009)
"Sequential pivotal mechanisms for public project problems", in:
Algorithmic Game Theory (Eds. Mavronicolas, M. and Papadoupoulou, V.G.), 85-96.
(Abstract)
(Link)
|
It is well-known that for several natural decision
problems no budget balanced Groves mechanisms exist. This has motivated recent research on
designing variants of feasible Groves mechanisms (termed as ‘redistribution of VCG
(Vickrey-Clarke-Groves) payments’) that generate reduced deficit. With this in mind, we
study sequential mechanisms and consider optimal strategies that could reduce the deficit
resulting under the simultaneous mechanism. We show that such strategies exist for the sequential
pivotal mechanism of the well-known public project problem. We also exhibit an optimal strategy
with the property that a maximal social welfare is generated when each player follows it. Finally,
we show that these strategies can be achieved by an implementation in Nash equilibrium.
|
|
-
Borm, P., Estévez-Fernández, A., and Fiestras-Janiero, M.G. (2009)
"Competitive environments and protective behaviour",
Games and Economic Behavior 67, 245-252.
(Abstract) (Previously
CentER DP 2006-43)
|
The class of two-person competition
games is introduced and analyzed. For any game in this class the set of Nash equilibria is convex
and all Nash equilibria lead to the same payoff vector. Competition games are compared to other
competitive environments such as unilaterally competitive games and rivalry games. Moreover,
protective behaviour within competitive environments is analyzed. For matrix games it is known
that protective strategies profiles exactly correspond to proper equilibria. It is shown that this
result can be extended to the class of unilaterally competitive games. |
|
-
Estévez-Fernández, A., Borm, P., Meertens, M., and Reijnierse,
H. (2009) "On the core of routing games with revenues",
International Journal of Game Theory 38, 291-304.
(Abstract) (Previously
CentER DP 2006-63)
|
Traveling salesman problems with
revenues form a generalization of traveling salesman problems. Here, next to travel costs an
explicit revenue is generated by visiting a city. We analyze routing problems with revenues, where
a predetermined route on all cities determines the tours along subgroups. Corresponding routing
games with revenues are analyzed. It is shown that these games have a nonempty core and a complete
description of the core is provided. |
|
Estévez-Fernández, A., Mosquera. M.A., Borm, P., and Hamers, H. (2008) "Proportionate flow shop games",
Journal of Scheduling 11, 433-447.
(Abstract) (Previously
CentER DP 2006-63)
|
In a proportionate flow shop problem
several jobs have to be processed through a fixed sequence of machines and the processing time of
each job is equal on all machines. By identifying jobs with agents, whose costs linearly depend on
the completion time of their jobs, and assuming an initial processing order on the jobs, we face
two problems: the first one is how to obtain an optimal order that minimizes the total processing
cost, the second one is how to allocate the cost savings obtained by ordering the jobs optimally.
In this paper we focus on the allocation problem. PFS games are defined as cooperative games
associated to proportionate flow shop problems. It is seen that PFS games have a nonempty core.
Moreover, it is shown that PFS games are convex if the jobs are initially ordered in decreasing
urgency. For this case an explicit game independent expression for the Shapley value is provided.
|
|
-
Estévez-Fernández, A., Borm, P., Calleja, P., and Hamers, H. (2008) "Sequencing games with repeated players",
Annals of Operations Research 158, 189-203.
(Abstract) (Previously
CentER DP 2004-128)
|
Two classes of one machine
sequencing situations are considered in which each job corresponds to exactly one player but a
player may have more than one job to be processed, so called RP (repeated player) sequencing
situations. In max-RP sequencing situations it is assumed that each player's cost function is
linear with respect to the maximum completion time of his jobs, whereas in min-RP sequencing
situations the cost functions are linear with respect to the minimum completion times. For both
classes, following explicit procedures to go from the initial processing order to an optimal order
for the coalition of all players, equal gain splitting rules are defined. It is shown that these
rules lead to core elements of the associated RP sequencing games. Moreover, it is seen that
min-RP sequencing games are convex. |
|
-
Estévez-Fernández, A., Borm, P., and Hamers, H. (2007)
"Project games", International Journal of Game Theory 36, 149-176.
(Abstract) (Previously
CentER DP 2005-91)
|
This paper studies situations in
which a project consisting of several activities is not executed as planned. It is divided into
three parts. The first part analyzes the case where the activities may be delayed; this possibly
induces a delay on the project as a whole with additional costs. Associated delayed project games
are defined and are shown to have a nonempty core. The second part considers the case where the
activities may be expedited; this possibly induces an expedition of the project as a whole
creating profits. Corresponding expedited project games are introduced and are shown to be convex.
The third and last part studies situations where some activities may be delayed and some
activities may be expedited. Related project games are defined and shown to have a nonempty core.
|
|
-
Calleja, P., Estévez-Fernández, A., Borm, P., and Hamers, H.
(2006) "Job scheduling, cooperation and control", OR Letters 34, 22-28.
(Abstract) (Previously
CentER DP 2004-65)
|
This paper studies one machine job
scheduling situations where clients can have more than one job to be processed and where a job can
be of interest for different players. Corresponding cooperative games are introduced and a result
on balancedness is provided. |
|
-
Estévez-Fernández, A., Borm, P., and Hamers, H. (2006)
"On the core of multiple longest traveling salesman games",
European Journal of Operational Research 174, 1816-1827.
(Abstract) (Previously
CentER DP 2003-127)
|
In this paper we introduce multiple
longest traveling salesman (MLTS) games. An MLTS game arises from a network in which a salesman
has to visit each node (player) precisely once, except to his home location, in such an order that
maximizes the total reward. First it is shown that the value of a coalition of an MLTS game is
determined by taking the maximum of suitable combinations of one and two person coalitions.
Secondly it is shown that MLTS games with five or less players have a nonempty core. However, a
six player MLTS game may have an empty core. For the special instance in which the reward between
a pair of nodes is equal to 0 or 1, we provide relations between the structure of the core and the
underlying network. |
|
-
Estévez-Fernández, A. and Fiestras-Janiero, M.G. (2004)
"On properties of several refinements of optimal solutions in linear programming", Journal of
Optimization Theory and Applications 122, 41-62.
(Abstract)
|
In this paper we investigate the
properties of the optimal solutions we obtain when we translate the concepts of perfect, proper
and weakly proper solutions from the context of Linear Complementary into the framework of Linear
Programming. |
|
|
Research reports
-
Dietzenbacher, B., Estévez-Fernández, A., Borm, P., and Hendrickx, R. (2016) "Proportionality,
Equality, and Duality in Bankruptcy Problems with Nontransferable Utility",
CentER Discussion Paper; vol. 2016-026.
(Abstract)
|
This paper analyzes bankruptcy problems with nontransferable utility as a generalization of bankruptcy problems
with monetary estate and claims. Following the classical axiomatic theory of bankruptcy, we formulate some appropriate properties for NTU-bankruptcy rules and study their
implications. We explore duality of bankruptcy rules and we derive several characterizations of the generalized proportional rule and the constrained relative equal awards rule. |
|
-
Estévez-Fernández, A., Borm, P., Fiestras-Janeiro, M.G., Mosquera, M.A. and Sánchez, E.
(2015) "On the 1-nucleolus for classes of cooperative games",
TI 2015-123/II.
(Abstract)
|
This paper analyzes the 1-nucleolus and, in particular, its relation to the nucleolus and
compromise value. It is seen that the 1-nucleolus of a cooperative game can be characterized using a combination of
standard bankruptcy rules for associated bankruptcy problems. In particular, for any zero-normalized balanced game, the
1-nucleolus coincides with the Aumann-Maschler rule (Aumann and Maschler, 1985) in this sense. From this result,
not only necessary conditions on a compromise stable game are derived such that the 1-nucleolus and the nucleolus
coincide, but also necessary and sufficient conditions such that the 1-nucleolus and the compromise value of exact
games coincide. |
|
-
Estévez-Fernández, A., Borm, P., and Fiestras-Janeiro
(2014) "Nontransferable utility bankruptcy games",
TI 14-030/II.
(Abstract)
|
In this paper, we analyze bankruptcy problems with
nontransferable utility (NTU) from a game theoretical perspective by redefining
corresponding NTU-bankruptcy games in a tailor-made way. It is shown that NTU-bankruptcy
games are both coalitional merge convex and ordinal convex. Generalizing the notions of
core cover and compromise stability for transferable utility (TU) games to NTU-games, we
also show that each NTU-bankruptcy game is compromise stable. Thus, NTU-bankruptcy games
are shown to retain the two characterizing properties of TU-bankruptcy games: convexity
and compromise stability. As a first example of a game theoretical NTU-bankruptcy rule,
we analyze the NTU-adjusted proportional rule and show that this rule corresponds to the
compromise value of NTU-bankruptcy games. |
|
|
Working papers
"Chinese postman problems and related games"
(with Marloes Gerichhausen and Herbert Hamers).
"On generalizations of the Talmud rule"
(with Peter Borm).
"Generalization of bankruptcy problems".
|
|
|