Dominance-based Rough Set Approach to decision under uncertainty and time preference

We consider a problem of decision under uncertainty with outcomes distributed over time. We propose a rough set model based on a combination of time dominance and stochastic dominance. For the sake of simplicity we consider the case of traditional additive probability distribution over the set of states of the world, however, we show that the model is rich enough to handle non-additive probability distributions, and even qualitative ordinal distributions. The rough set approach gives a representation of decision maker’s time-dependent preferences under uncertainty in terms of “if…, then…” decision rules induced from rough approximations of sets of exemplary decisions.     

Strategy-proof coalition formation

We analyze coalition formation problems in which a group of agents is partitioned into coalitions and agents’ preferences only depend on the coalition to which they belong. We study rules that associate to each profile of preferences a partition of the society. We focus on strategy-proof rules on restricted domains of preferences, as the domains of additively representable or separable preferences. In such domains, the only strategy-proof and individually rational rules that satisfy either a weak version of efficiency or non-bossiness and flexibility are single-lapping rules. Single-lapping rules are characterized by severe restrictions on the set of feasible coalitions that are consistent with hierarchical organizations. These restrictions are necessary and sufficient for the existence of a unique core-stable partition. In fact, single-lapping rules always select the associated unique core-stable partition. Thus, our results highlight the relation between the non-cooperative concept of strategy-proofness and the cooperative concept of uniqueness of core-stable partitions.     

New decision rules for exact search in N-Queens

This paper presents a set of new decision rules for exact search in N-Queens. Apart from new tiebreaking strategies for value and variable ordering, we introduce the notion of ‘free diagonal’ for decision taking at each step of the search. With the proposed new decision heuristic the number of subproblems needed to enumerate the first K solutions (typically K = 1, 10 and 100) is greatly reduced w.r.t. other algorithms and constitutes empirical evidence that the average solution density (or its inverse, the number of subproblems per solution) remains constant independent of N. Specifically finding a valid configuration was backtrack free in 994 cases out of 1,000, an almost perfect decision ratio. This research is part of a bigger project which aims at deriving new decision rules for CSP domains by evaluating, at each step, a constraint value graph G _c . N-Queens has adapted well to this strategy: domain independent rules are inferred directly from G _c whereas domain dependent knowledge is represented by an induced hypergraph over G _c and computed by similar domain independent techniques. Prior work on the Number Place problem also yielded similar encouraging results.     

Up methods in the allocation of indivisibilities when preferences are single-peaked

We consider allocation problems with indivisible goods when agents’ preferences are single-peaked. We propose natural rules (called up methods) to solve such a class of problems and axiomatically characterize them. We also prove that these methods can be interpreted as extensions to the indivisible case of the so-called equal distance rule.      

Bi-criteria optimization problems for decision rules

We consider bi-criteria optimization problems for decision rules and rule systems relative to length and coverage. We study decision tables with many-valued decisions in which each row is associated with a set of decisions as well as single-valued decisions where each row has a single decision. Short rules are more understandable; rules covering more rows are more general. Both of these problems—minimization of length and maximization of coverage of rules are NP-hard. We create dynamic programming algorithms which can find the minimum length and the maximum coverage of rules, and can construct the set of Pareto optimal points for the corresponding bi-criteria optimization problem. This approach is applicable for medium-sized decision tables. However, the considered approach allows us to evaluate the quality of various heuristics for decision rule construction which are applicable for relatively big datasets. We can evaluate these heuristics from the point of view of (i) single-criterion—we can compare the length or coverage of rules constructed by heuristics; and (ii) bi-criteria—we can measure the distance of a point (length, coverage) corresponding to a heuristic from the set of Pareto optimal points. The presented results show that the best heuristics from the point of view of bi-criteria optimization are not always the best ones from the point of view of single-criterion optimization.     

Extension of the LINMAP for multiattribute decision making under Atanassov’s intuitionistic fuzzy environment

The aim of this article is further extending the linear programming techniques for multidimensional analysis of preference (LINMAP) to develop a new methodology for solving multiattribute decision making (MADM) problems under Atanassov’s intuitionistic fuzzy (IF) environments. The LINMAP only can deal with MADM problems in crisp environments. However, fuzziness is inherent in decision data and decision making processes. In this methodology, Atanassov’s IF sets are used to describe fuzziness in decision information and decision making processes by means of an Atanassov’s IF decision matrix. A Euclidean distance is proposed to measure the difference between Atanassov’s IF sets. Consistency and inconsistency indices are defined on the basis of preferences between alternatives given by the decision maker. Each alternative is assessed on the basis of its distance to an Atanassov’s IF positive ideal solution (IFPIS) which is unknown a prior. The Atanassov’s IFPIS and the weights of attributes are then estimated using a new linear programming model based upon the consistency and inconsistency indices defined. Finally, the distance of each alternative to the Atanassov’s IFPIS can be calculated to determine the ranking order of all alternatives. A numerical example is examined to demonstrate the implementation process of this methodology. Also it has been proved that the methodology proposed in this article can deal with MADM problems under not only Atanassov’s IF environments but also both fuzzy and crisp environments.     

Investment under ambiguity with the best and worst in mind

Recent literature on optimal investment has stressed the difference between the impact of risk and the impact of ambiguity—also called Knightian uncertainty—on investors’ decisions. In this paper, we show that a decision maker’s attitude towards ambiguity is similarly crucial for investment decisions. We capture the investor’s individual ambiguity attitude by applying α-MEU preferences to a standard investment problem. We show that the presence of ambiguity often leads to an increase in the subjective project value, and entrepreneurs are more eager to invest. Thereby, our investment model helps to explain differences in investment behavior in situations which are objectively identical.     

The computational complexity of bilevel assignment problems

In bilevel optimization problems there are two decision makers, the leader and the follower, who act in a hierarchy. Each decision maker has his own objective function, but there are common constraints. This paper deals with bilevel assignment problems where each decision maker controls a subset of edges and each edge has a leader’s and a follower’s weight. The edges selected by the leader and by the follower need to form a perfect matching. The task is to determine which edges the leader should choose such that his objective value which depends on the follower’s optimal reaction is maximized. We consider sum- and bottleneck objective functions for the leader and follower. Moreover, if not all optimal reactions of the follower lead to the same leader’s objective value, then the follower either chooses an optimal reaction which is best (optimistic rule) or worst (pessimistic rule) for the leader. We show that all the variants arising if the leader’s and follower’s objective functions are sum or bottleneck functions are NP-hard if the pessimistic rule is applied. In case of the optimistic rule the problem is shown to be NP-hard if at least one of the decision makers has a sum objective function.     

Preference elicitation for a ranking method based on multiple reference profiles

4OR - Multiple criteria decision aid methodologies support decision makers (DM) facing decisions involving conflicting objectives. DM’s preferences should be captured to provide meaningful...     

Dual-Role Based Pricing in a Dynamic and Competitive Environment

The dual role of price, as a product attribute signaling quality and as a measure of sacrifice, serving as a benchmark for comparing the utility gains from superior product quality, is now well established in the marketing and economic literature. However, knowledge about their long-run impact and the influence of competition on these effects still remains very sparse. In the current paper, with reference to a dynamic and competitive framework, an analytical model is proposed to help determining optimal decision rules for price incorporating both roles. The main results are as follows: (i) The optimal pricing policy is determined as a Nash equilibrium strategy. (ii) The resulting equilibrium price is higher than an equilibrium that disregards the carryover price effects. (iii) For a symmetric competition, we provide normative rules on how firms should set prices as a function of the perceived quality; particularly, how the price should be set initially, when there is little product familiarity and the perceived quality is low, and how this price should vary as the perceived quality increases. (iv) At steady state, we find that the level of equilibrium margin, in percentage terms, decreases with the elasticity of demand with respect to the brand price, but this decrease is moderated by the elasticity of demand with respect to the brand perceived quality, the cross elasticity of demand with respect to the competitor’s perceived quality and the effect of the competitor’s current price on the firm’s perceived quality deterioration. The author thanks Konstantin Kogan for helpful discussions and comments.     

Analysis and design of selection committees: a game theoretic secretary problem

Firms often delegate important decisions to committees which are set up specifically for that purpose; for example selection committees. We analyze the equilibrium behavior of a game in which committee members (the players) interview candidates sequentially, either hiring or going on to the next one. The players have differing evaluations of candidates (e.g. one cares about typing skills; the other about IT skills), which become their utilities if the candidate is hired. We then consider the optimal design (rules of the game) of such a committee, from the point of view of the firm. That is, which rules hire candidates which maximize the firm’s utility. Our committee game has a first round in which the members sequentially, by order of player number, say ‘yea’ or ‘nea’ to the candidate. If there are sufficient ‘yeas’ then she is tentatively hired; otherwise she is rejected. In the former case, members who said nea can veto the candidate in the second round. Thus the candidate is either hired, rejected, or vetoed. In the last case, the member casting a veto has one less to use on later candidates. We analyze equilibria where a player may say ‘yea’ to a candidate he would prefer not to hire, in order to force the other player to use up a valuable veto. We show that for the uniform candidate distribution there is a unique equilibrium and better candidates for the firm are hired when there are more vetoes. However we exhibit a candidate distribution where increasing the numbers of vetoes results in hiring worse candidates.     

Corrigendum to “Resource-monotonicity for house allocation problems”

Ehlers and Klaus (Int J Game Theory 32:545–560, 2003) study so-called allocation problems and claim to characterize all rules satisfying efficiency, independence of irrelevant objects, and resource-monotonicity on two preference domains (Ehlers and Klaus 2003, Theorem 1). They explicitly prove Theorem 1 for preference domain R₀{\mathcal{R}_0} which requires that the null object is always the worst object and mention that the corresponding proofs for the larger domain R{\mathcal{R}} of unrestricted preferences “are completely analogous.” In Example 1 and Lemma 1, this corrigendum provides a counterexample to Ehlers and Klaus (2003, Theorem 1) on the general domain R{\mathcal{R}} . We also propose a way of correcting the result on the general domain R{\mathcal{R}} by strengthening independence of irrelevant objects: in addition to requiring that the chosen allocation should depend only on preferences over the set of available objects (which always includes the null object), we add a situation in which the allocation should also be invariant when preferences over the null object change. Finally, we offer a short proof of the corrected result that uses the established result of Theorem 1 for the restricted domain R₀{\mathcal{R}_0}.     

Multi-criteria semantic dominance: A linguistic decision aiding technique based on incomplete preference information

A linguistic decision aiding technique for multi-criteria decision is presented. We define a relation between alternatives as multi-criteria semantic dominance (MCSD). It adopts the similar ideal of the stochastic dominance by utilizing the partial information of the decision maker’s preference, which is only ordinal or partially cardinal. The MCSD rules based on three typical types of semanteme functions are introduced and proven. By using these rules, all the alternatives under consideration are divided into two mutually exclusive sets called efficient set and inefficient set. The decision maker who has such a semanteme function will never choose the alternative from the corresponding inefficient set as the optimal one. In such a way, when we analyze the linguistic decision information, the inherent fuzziness of preference can be handled and several controversial operations of the linguistic terms can be avoided. An example is also provided to illustrate the procedure of the proposed method.     

Less is more: an observability paradox in repeated games

We present a repeated prisoners’ dilemma game with imperfect public monitoring, which exhibits the following paradoxical feature: the (limit) equilibrium payoff set achieves full efficiency asymptotically as the public signal becomes insensitive to the hidden actions of the players. The basic logic behind this result also provides an example where the Folk theorem is obtained, while Fudenberg et al.’s (in Econometrica 62:997–1040, 1994) sufficient conditions for Folk theorem are violated.We would like to thank Drew Fudenberg, David Levine, an associate editor and two anonymous referees for their helpful comments and suggestions.     

On one extremal problem for positive series

The approximation properties of the spaces S _ϕ ^p introduced by Stepanets’ were studied in a series of works of Stepanets’ and his disciples. In these works, problems related to the determination of exact values of n-term approximations of q-ellipsoids in these spaces were reduced to some extremal problems for series with terms that are products of elements of two nonnegative sequences one of which is fixed and the other varies on a certain set. Since solutions of these extremal problems may be of independent interest, in the present work we develop a new method for finding these solutions that enables one to obtain the required result in a substantially shorter and more transparent way. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 12, pp. 1677–1683, December, 2005.     

How to find all roots of complex polynomials by Newton’s method

We investigate Newton’s method to find roots of polynomials of fixed degree d, appropriately normalized: we construct a finite set of points such that, for every root of every such polynomial, at least one of these points will converge to this root under Newton’s map. The cardinality of such a set can be as small as 1.11 d log² d; if all the roots of the polynomial are real, it can be 1.30 d. Oblatum 24-II-2000 & 14-II-2001?Published online: 20 July 2001     

Noetherianity of the space of irreducible representations

LetR be an associative ring with identity. We study an elementary generalization of the classical Zariski topology, applied to the set of isomorphism classes of simple leftR-modules (or, more generally, simple objects in a complete abelian category). Under this topology the points are closed, and whenR is left noetherian the corresponding topological space is noetherian. IfR is commutative (or PI, or FBN) the corresponding topological space is naturally homeomorphic to the maximal spectrum, equipped with the Zariski topology. WhenR is the first Weyl algebra (in characteristic zero) we obtain a one-dimensional irreducible noetherian topological space. Comparisons with topologies induced from those on A. L. Rosenberg’s spectra are briefly noted. The author’s research was supported in part by NSF grants DMS-9970413 and DMS-0196236.     

Chi-square Control Charts with Runs Rules

The Hotelling’s χ² control chart is one of the most widely used multivariate charting procedures for monitoring the vector of means of several quality characteristics. As a Shewhart-type control chart, it incorporates information pertaining to most recently inspected sample and subsequently it is relatively insensitive in quickly detecting small magnitude shifts in the process mean vector. A popular solution suggested to overcome this handicap was the use of runs and scans rules as criteria to declare a process out-of-control. During the last years, the examination of Hotelling’s χ² control charts supplemented with various runs rules has attracted continuous research interest. In the present article we study the performance of the Hotelling’s χ² control chart supplemented with a r-out-of-m runs rule. The new control chart demonstrates an improved performance over other competitive runs rules based control charts.     

Moment inequalities and central limit properties of isotropic convex bodies

The object of our investigations are isotropic convex bodies , centred at the origin and normed to volume one, in arbitrary dimensions. We show that a certain subset of these bodies – specified by bounds on the second and fourth moments – is invariant under forming ‘expanded joinsrsquo;. Considering a body K as above as a probability space and taking , we define random variables on K. It is known that for subclasses of isotropic convex bodies satisfying a ‘concentration of mass property’, the distributions of these random variables are close to Gaussian distributions, for high dimensions n and ‘most’ directions . We show that this ‘central limit property’, which is known to hold with respect to convergence in law, is also true with respect to -convergence and -convergence of the corresponding densities. Received: 21 March 2001 / in final form: 17 October 2001 / Published online: 4 April 2002