Constraint proposal method for computing Pareto solutions in multi-party negotiations

The constraint proposal method for computing Pareto-optimal solutions is extended to multi-party negotiations. In the method a neutral coordinator assists decision makers in finding Pareto-optimal solutions so that the elicitation of the decision makers' value functions is not required. During the procedure the decision makers have to indicate their most preferred points on different sets of linear constraints. The method can be used to generate either one Pareto-optimal solution dominating the status quo solution of the negotiation or an approximation to the Pareto frontier. In the latter case a distributive negotiation among the efficient agreements can be carried out afterwards.     

Game theoretic models for climate change negotiations

Negotiations to reduce greenhouse gas accumulation in the atmosphere are modeled as extensive games of perfect information. Various solution concepts, such as Nash equilibrium, reaction function equilibrium, correlated equilibrium and bargaining solutions are applied, analyzed and computed. Special reduction techniques are used when the size of the game tree becomes excessive. A new solution concept, the tree-correlated equilibrium is also introduced. Main features of an Excel add-in designed to compute various solutions are briefly described and a sample policy analysis for a special negotiating scenario is discussed.     

Decentralized method for computing Pareto solutions in multiparty negotiations

This paper presents a decentralized method for computing Pareto-optimal solutions in multiparty negotiations over continuous issues. The method is based on the well known weighting method which is decomposed by introducing an own decision variable for each decision maker and by applying the dual decomposition method to the resulting problem. The method offers a systematic way for generating some or all Pareto-optimal solutions so that decision makers do not have to know each others' value functions. Under the assumption of quasilinear value function the requirement that a decision maker knows the explicit form for his value function can be relaxed. In that case the decision maker is asked to solve a series of multiobjective programming problems where an additional artificial decision variable is introduced.     

Searching for losers

We investigate the following process: N people select b losers by flipping coins. The 0-party continues until there are less than b losers; then the 1-party has to find the other losers by the same process. The average time for this process is about long₂ N, but this result requires rather advanced methods. Furthermore, the average size of a binary tree associated to this process and the average number of coin flippings are computed. The method used in this article can be used to give asympotical solutions of a special type of bivariate recurrences. © 1993 John Wiley & Sons, Inc.     

Identifying Pareto-optimal settlements for two-party resource allocation negotiations

We explore models to identify Pareto-optimal outcomes in two-party multiple program resource allocation post-settlement settlement negotiations. The approximation of the contract curve, that is the set of Pareto-optimal outcomes, is also discussed. We consider the case where the parties split a shared hard resource. An application of the models to a resource allocation problem in a Finnish university is also discussed.     

Satisfiability and completeness of protocols for electronic negotiations

Many of the existing e-negotiation support systems are built around one negotiation protocol. This effectively restricts their use to those problems and interactions that had been assumed a priori by the systems’ designers. Field and experimental studies show that the way the negotiation process is structured depends on the negotiators’ characteristics, the problem and the context in which an agreement is sought. It has also been recognized in literature that both the way a problem is represented and the solution process implemented strongly influence the results at which individual decision-makers and negotiators arrive. Building on the e-negotiation Montreal taxonomy this article proposes a more complete typology of protocols and their characteristics. It also presents the elements of a theory for the design of negotiation protocols. The proposed protocol formalism allows for the construction of models from which users can select a protocol instance that suits them and/or is appropriate for the problem at-hand. Furthermore, this formalism allows for the construction of protocols that can be modified during the user–system interactions. The paper also presents two key requirements for negotiation protocols embedded in support systems, namely their satisfiability and completeness.     

Flexibility of disagreement actions in negotiations

Negotiation games in which two players engage in disagreement games to determine their payoffs during the bargaining generally admit multiple perfect equilibrium outcomes, including inefficient ones. This paper shows that if the two players cannot change their disagreement actions as frequent as they bargain, then the set of perfect equilibrium payoffs shrinks. As disagreement actions become completely inflexible relative to the bargaining frequency, the set of equilibrium payoffs shrinks to Nash's (1953) bargaining solution with strategic threat. Received January 1999/Final version March 2001     

搜索三个目标

本文通过建立简洁而有效的搜索方法 ,证明了对于无穷多个n来说 ,三个目标的最优搜索问题的最小试验次数等于信息论下界 .同时也研究了上述问题的修正情形 ,证明了对于所有整数n来说 ,对应的最小试验次数或者等于信息论下界或者超过信息论下界 1次并且对于无穷多个区间 ,信息论下界均是可以达到的 .     

Searching for semifield flocks

Searches are performed in PG(3,q), q odd, for finding semifield and likeable flocks. For small values of q exhaustive searches are performed; limited searches are done for larger q. The main result of this paper is: In PG(3,27) any semifield flock is isomorphic either to the linear, Kantor–Knuth or Ganley flock. No new semifield or likeable flocks have been found.     

Searching for counterfeit coins

The well-known counterfeit problem asks for the minimum number of weighings necessary to determine all fake coins in a given set ofn coins. We derive a new upper bound when we know that at mostd coins are defective, improving a previous result of L. Pyber.     

Searching for an edge in a graph

Consider the problem of determining the endpoints of an unknown edge x in a given graph G by asking questions of the form “Is vertex v an endpoint of edge e in G?”. Sharp upper and lower bounds are derived, and it is shown that determining the minimum number of questions in NP-complete.     

Searching for K3,3in linear time

It is shown that the search version of the subgraph homeomorphism problem for K_3,3 can be solved in time linear in the number of vertices of an arbitrary graph. This improves upon a previous result of Asano [1], who described a linear-time algorithm for the decision version of the problem and a quadratic-time algorithm for the search problem.     

Searching for extensible Korobov rules

Extensible lattice sequences have been proposed and studied in [F.J. Hickernell, H.S. Hong, Computing multivariate normal probabilities using rank-1 lattice sequences, in: G.H. Golub, S.H. Lui, F.T. Luk, R.J. Plemmons (Eds.), Proceedings of the Workshop on Scientific Computing (Hong Kong), Singapore, Springer, Berlin, 1997, pp. 209–215; F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138; F.J. Hickernell, H.Niederreiter, The existence of good extensible rank-1 lattices, J. Complexity 19 (2003) 286–300]. For the special case of extensible Korobov sequences, parameters can be found in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C.Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138]. The searches made to obtain these parameters were based on quality measures that look at several projections of the lattice. Because it is often the case in practice that low-dimensional projections are very important, it is of interest to find parameters for these sequences based on measures that look more closely at these projections. In this paper, we prove the existence of “good” extensible Korobov rules with respect to a quality measure that considers two-dimensional projections. We also report results of experiments made on different problems where the newly obtained parameters compare favorably with those given in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138].     

Searching for perfection on hypergraphs

In this paper we study the family of oriented transitive 3-hypergraphs that arise from cyclic permutations and intervals in the circle, in order to search for the notion of perfection on hypergraphs.     

Searching for partially ordered structures

General methods are developed to search for minimal and dead-end payoff operators for a class of sources endowed with a partial order structure. It is shown that the results can be used in the design of experiments with automata and in the minimization of Boolean functions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 2, pp. 253–260, February, 1992.     

两伪币的搜索问题

考虑两伪币的搜索问题: 给定外观相同的n个硬币, 其中有两个比较重的伪币, 通过等臂天平在尽可能少的称量次数下去找出两个伪币. L^{(2)}(n)为最坏情况下找到两伪币的最小称量步数. 对于任意的 n\geq2, 满足\lceil \log_3\binom{n}{2}\rceil \leq L^{(2)}(n)\leq\lceil \log_3\binom{n}{2}\rceil+1. 猜想信息理论下界均可达. 通过一个新的方法扩大了满足信息理论下界的n的取值范围.     

Searching in trees

In (Discrete Math. 17 (1977)181) Rivest introduced the search complexity of binary trees and proved that among all binary trees with a fixed search complexity the smallest ones are the so-called Fibonacci trees. This result is extended for q-trees. The structure of the smallest q-trees is again Fibonacci-like but more complicated than in the binary case. In addition an upper bound for the asymptotic growth of these trees is given.