The computation of leastcore and prenucleolus is an efficient way of allocating a common resource among N players. It has, however, the drawback being a linear programming problem with 2^N-2 constraints. In this paper we show how, in the case of convex production games, generate constraints by solving small size linear programming problems, with both … Read more
We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and $n$ players. Both of them have the arithmetic operation complexity bound of $O(n^4\log(1/\epsilon))$ for computing an $\epsilon$-equilibrium solution. If the problem data are rational numbers and their bit-length is $L$, then the bound to generate an … Read more
We extend the analysis of [27] to handling more general utility functions: piece-wise linear functions, which include Leontief’s utility. We show that the problem reduces to the general analytic center model discussed in [27]. Thus, the same linear programming complexity bound applies to approximating the Fisher equilibrium problem with these utilities. More importantly, we show … Read more
A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance apart between the two players is 2. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best … Read more
In this paper we show that if all agents are equipped with discrete concave production functions, then a feasible price allocation pair is a market equilibrium if and only if it solves a linear programming problem, similar to, but perhaps simpler than the one invoked in Yang (2001). Using this result, but assuming discrete concave … Read more
Given a finite set of outlets with joint normally distributed demands and identical holding and penalty costs, inventory centralization induces a cooperative cost allocation game with nonempty core. It is well known that for this newsvendor inventory setting the expected cost of centralization can be expressed as a constant multiple of the standard deviation of … Read more
This paper proves the existence of non-empty cores for directed network and two-sided network problems with quotas. ArticleDownload View PDF
In this paper we investigate the properties of the sampled version of the fictitious play algorithm, familiar from game theory, for games with identical payoffs, and propose a heuristic based on fictitious play as a solution procedure for discrete optimization problems of the form $\max\{u(y):y=(y^1,\ldots,y^n)\in\setY^1\times\cdots\times\setY^n\}$, i.e., in which the feasible region is a Cartesian product … Read more
In this paper we provide sufficient conditions for the existence of pair-wise envy free and stable matchings for two-sided systems with techniques. ArticleDownload View PDF
A sufficient condition is provided for the existence of stable matchings for three sided systems. ArticleDownload View PDF