Assignment markets that are uniquely determined by their core

A matrix A defines an assignment market, where each row represents a buyer and each column a seller. If buyer i is matched with seller j, the market produces a_ij units of utility. Quint (1991) points out that usually many different assignment matrices exist that define markets with the same core and poses the question of when the matrix is uniquely determined by the core of the related market. We characterize these matrices in terms of a strong form of the doubly dominant diagonal property. A matching between buyers and sellers is optimal if it produces the maximum units of utility. Our characterization allows us to show that the number of optimal matchings in markets uniquely characterized by their core is a power of two.     

On multi-choice TU games arising from replica of economies

In this paper we derive a multi-choice TU game from r-replica of exchange economy with continuous, concave and monetary utility functions, and prove that the cores of the games converge to a subset of the set of Edgeworth equilibria of exchange economy as r approaches to infinity. We prove that the dominance core of each balanced multi-choice TU game, where each player has identical activity level r, coincides with the dominance core of its corresponding r-replica of exchange economy. We also give an extension of the concept of the cover of the game proposed by Shapley and Shubik (J Econ Theory 1: 9-25, 1969) to multi-choice TU games and derive some sufficient conditions for the nonemptyness of the core of multi-choice TU game by using the relationship among replica economies, multi-choice TU games and their covers.     

The partition bargaining problem

Consider the problem of partitioning n items among d players where the utility of each player for bundles of items is additive; so, player r has utility for item i and the utility of that player for a bundle of items is the sum of the 's over the items i in his/her bundle. Each partition S of the items is then associated with a d-dimensional utility vector V^S whose coordinates are the utilities that the players assign to the bundles they get under S. Also, lotteries over partitions are associated with the corresponding expected utility vectors. We model the problem as a Nash bargaining game over the set of lotteries over partitions and provide methods for computing the corresponding Nash solution, to prescribed accuracy, with effort that is polynomial in n. In particular, we show that points in the pareto-optimal set of the corresponding bargaining set correspond to lotteries over partitions under which each item, with the possible exception of at most d(d-1)/2 items, is assigned in the same way.     

On competitiveness in uniform utility allocation markets

We call a market competitive if increasing the endowment of one buyer does not increase the equilibrium utility of another. We show that every competitive uniform utility allocation market is a submodular utility allocation market, answering a question of Jain and Vazirani [K. Jain, V.V. Vazirani, Eisenberg-Gale markets: Algorithms and structural properties, in: STOC, 2007]. Our proof proceeds via characterizing non-submodular fractionally sub-additive functions.     

Optimal trading strategy for European options with transaction costs

The European option with transaction costs is studied. The cost of making a transaction is taken to be proportional by a factor λ to the value (in dollars) of stock traded. When there are no transaction costs (i.e. when λ=0) the well-known Black-Scholes strategy tells how to hedge the option. Since no non-trivial perfect hedging strategy exists when λ>0 (see (Ann. Appl. Probab. 5(2) (1995) 327)), we instead try to maximize the expected utility attainable. We seek to understand the effect transaction costs have on the maximum attainable expected utility over all strategies, when λ is small but non-zero. It turns out that transaction costs diminish the expected utility by an amount which has the order of magnitude λ^2/3. We will compute that correction explicitly modulo an error which is small compared to λ^2/3. We will exhibit an explicit strategy whose expected utility differs from the maximum attainable expected utility by an error small in comparison to λ^2/3.     

On dynamic programming equations for utility indifference pricing under delta constraints

In this paper we study the problem of utility indifference pricing in a constrained financial market, using a utility function defined over the positive real line. We present a convex risk measure −v(•:y) satisfying q(x,F)=x+v(F:u₀(x)), where u₀(x) is the maximal expected utility of a small investor with the initial wealth x, and q(x,F) is a utility indifference buy price for a European contingent claim with a discounted payoff F. We provide a dynamic programming equation associated with the risk measure (−v), and characterize v as a viscosity solution of this equation.     

A perturbed version of an inexact generalized Newton method for solving nonsmooth equations

In this paper, we present the combination of the inexact Newton method and the generalized Newton method for solving nonsmooth equations F(x)?=?0, characterizing the local convergence in terms of the perturbations and residuals. We assume that both iteration matrices taken from the B-differential and vectors F(x ^(k)) are perturbed at each step. Some results are motivated by the approach of C?tina? regarding to smooth equations. We study the conditions, which determine admissible magnitude of perturbations to preserve the convergence of method. Finally, the utility of these results is considered based on some variant of the perturbed inexact generalized Newton method for solving some general optimization problems.     

An <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">N</Emphasis> log (1/<Emphasis Type="Italic">ɛ</Emphasis>)) Algorithm for the Two-resource Allocation Problem with a Non-differentiable Convex Objective Function

This paper considers a job consisting of N totally ordered tasks. There is a budget for each of the two non-substitutable resources needed for the tasks. The processing time of each task is inversely proportional to the amount of resource allocated. We determine how to distribute the resources to the tasks so that the completion time of the job is minimized. A search procedure is presented that solves the problem with a worst case performance O(N log (1/?)), where ? is a given accuracy.     

On Ordered Weighted Averaging Social Optima

In this paper, we look at the classical problem of aggregating individual utilities and study social orderings which are based on the concept of Ordered Weighted Averaging Aggregation Operator. In these social orderings, called Ordered Weighted Averaging Social Welfare Functions, weights are assigned a priori to the positions in the social ranking and, for every possible alternative, the total welfare is calculated as a weighted sum in which the weight corresponding to the kth position multiplies the utility in the kth position. In the α-Ordered Weighted Averaging Social Welfare Function, the utility in the kth position is the kth smallest value assumed by the utility functions, whereas in the β-Ordered Weighted Averaging Social Welfare Function it is the utility of the kth poorest individual. We emphasize the differences between the two concepts, analyze the continuity issue, and provide results on the existence of maximum points.     

Population solidarity, population fair-ranking, and the egalitarian value

We investigate the implications of two axioms specifying how a value should respond to changes in the set of players for TU games. Population solidarity requires that the arrival of new players should affect all the original players in the same direction: all gain together or all lose together. On the other hand, population fair-ranking requires that the arrival of new players should not affect the relative positions of the original players. As a result, we obtain characterizations of the egalitarian value, which assigns to each player an equal share over an individual utility level. It is the only value satisfying either one of the two axioms together with efficiency, symmetry and strategic equivalence.     

OPTIMAL EXPLOITATION OF RENEWABLE RESOURCES BY THE VISCOSITY SOLUTION METHOD

We study the stochastic optimization problem of renewable resources to maximize the expected discounted utility of exploitation. We develop the viscosity solution method to the associated Hamilton–Jacobi–Bellman equation and further show the C ²-regularity of the viscosity solution under the strict concavity of the utility function. The optimal policy is shown to exist and given in a feedback form or a stochastic version of Hotelling's rule.     

Properties of consistent voting systems

We consider exactly and strongly consistent voting functions where the alternative set is the set of real numbers and each person's preference ordering is determined by a utility function ¦x?x^*¦ wherex ^* is his most preferred alternative. We prove that a voting function which is continuous, anonymous, weakly Pareto, and strongly and exactly consistent must coincide with a class of generalized medians studied byMoulin [1978]. Thus, such a function is actually strategyproof. The continuity assumption can be weakened a little, but we give an example of a noncontinuous function which is strongly and exactly consistent, anonymous, and weakly Pareto, but is not strategyproof.     

Hybrid Modelling for Robust Solving

We study a balanced academic curriculum problem and an industrial steel mill slab design problem. These problems can be modelled in different ways, using both Integer Linear Programming (ILP) and Constraint Programming (CP) techniques. We consider the utility of each model. We also propose integrating the models to create hybrids that benefit from the complementary strengths of each model. Experimental results show that hybridization significantly increases the domain pruning and decreases the run-time on many instances. Furthermore, a CP/ILP hybrid model gives a more robust performance in the face of varying instance data.     

Equilibrium semantics of languages of imperfect information

In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu (1989) [9] under the header of independence-friendly (IF) languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of the game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich (1986) [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics.     

Applications of utility functions defined on quasi-metric spaces

A quasi-metric space (X,d) is called sup-separable if (X,d^s) is a separable metric space, where d^s(x,y)=max{d(x,y),d(y,x)} for all x,y∈X. We characterize those preferences, defined on a sup-separable quasi-metric space, for which there is a semi-Lipschitz utility function. We deduce from our results that several interesting examples of quasi-metric spaces which appear in different fields of theoretical computer science admit semi-Lipschitz utility functions. We also apply our methods to the study of certain kinds of dynamical systems defined on quasi-metric spaces.     

Indifference prices of structured catastrophe (CAT) bonds

We present a method for pricing structured CAT bonds based on utility indifference pricing. The CAT bond considered here is issued in two distinct notes called tranches, specifically senior and junior tranches each with its own payment schedule. Our contributions to the literature of CAT bond pricing are two-fold. First, we apply indifference pricing to structured CAT bonds. We find a price for the senior tranche as a relative indifference price, that is, relative to the price of the junior tranche. Alternatively, one could take the approach that the senior tranche is priced first and the price of the junior tranche is relative to that. Second, instead of simply supposing that the “not-issue-a-CAT-bond” strategy of the reinsurer is to do nothing, we suppose that the reinsurer reduces its risk by reinsuring proportionally less claims. We assume that the reinsurance claims follow a (Poisson) jump-diffusion process.     

Optimal investment and consumption decision of a family with life insurance

We study an optimal portfolio and consumption choice problem of a family that combines life insurance for parents who receive deterministic labor income until the fixed time T. We consider utility functions of parents and children separately and assume that parents have an uncertain lifetime. If parents die before time T, children have no labor income and they choose the optimal consumption and portfolio with remaining wealth and life insurance benefit. The object of the family is to maximize the weighted average of utility of parents and that of children. We obtain analytic solutions for the value function and the optimal policies, and then analyze how the changes of the weight of the parents’ utility function and other factors affect the optimal policies.     

Borch’s theorem,equal margins,and efficient allocation

The economic concept of margin guides or justifies the sharing of risks and resources. Broadly, by Borch’s theorem, competing claimants, ends or users ought see equal margins along any efficient allocation.However helpful this maxim, its application is often hampered, and occasionally misguided, by concerns with the differentiability of objectives—or with the interiority of solutions. Circumventing such concerns, this paper introduces a quite applicable, generalized notion, called essential margin.Presuming transferable or quasi-linear utility, the coincidence of such margins supports efficiency, competitive equilibria, and core solutions. The said coincidence also defines deductibles and prioritized claims, seen in finance and insurance.     

Equilibrium resource distribution in a network model

A network is modeled by a weighted undirected graph G. Some certain time invariable resource is assigned to each node and is distributed among the incident edges at each time (time is assumed to be discrete). A state of the network corresponds to a distribution of resources of all nodes among the edges of G. At each time a vertex i evaluates its relationship with an adjacent vertex j according to a given function c _ij (x _ij , x _ji ) of the resources x _ij and x _ji provided by the nodes i and j to the edge (i, j). Since resources of the nodes are redistributed at every time, the state of the system varies in time. Some sufficient conditions are found for the existence of the limit and equilibrium states of the model; and precise formulas are given to compute these states in the case of a special function c _ij for an arbitrary graph G.     

Resource leveling in a machine environment

We address resource leveling problems in a machine environment. Given a set of m machines, one or more renewable resources, and a set of n tasks, each assigned to exactly one of the machines. Each task has a processing time, an earliest start time, a deadline, and resource requirements. There are no precedence relations between the tasks. The tasks have to be sequenced on the machines while minimizing a function of the level of resource utilization from each resource over time. We provide various complexity results including a polynomial time algorithm for a one machine special case. We also propose an exact method using various techniques to find optimal or close-to-optimal solutions. The computational experiments show that our exact method significantly outperforms heuristics and a commercial MIP solver.