Interactive approaches for biobjective problems with progressively changing solution sets

• Published date: 01 January 2021
• Author: Murat Köksalan,Gülşah Karakaya
• Date: 01 January 2021
• DOI: http://doi.org/10.1111/itor.12576

Intl. Trans. in Op. Res. 28 (2021) 356–375

DOI: 10.1111/itor.12576

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Interactive approaches for biobjective problems

with progressively changing solution sets

G¨

uls¸ah Karakayaa,∗and Murat K¨

oksalanb,c

aDepartment of Business Administration, Middle East Technical University, 06800 Ankara, Turkey

bDepartment of Industrial Engineering, Middle East TechnicalUniversity, 06800 Ankara, Turkey

cOperations and Information Management, Georgetown University, Washington,DC 20057, USA

E-mail: kgulsah@metu.edu.tr [Karakaya]; koksalan@metu.edu.tr [K¨

oksalan]

Received 7 August2017; received in revised form 19 June 2018; accepted 21 June 2018

Abstract

In this study, we develop interactive approaches to find a satisfactory alternative of a decision maker (DM)

having a quasiconvex preference function where the alternativeset changes progressively. In this environment,

we keep searching the available set of alternatives and estimating the preference function of the DM. As new

alternatives emerge, we make better use of the available preference information and eventually converge to

a preferred alternative of the DM. We test our approaches on biobjective, multi-item, multi-round auction

problems. The results show that our approaches work well in terms of both the preference function value of

the obtained solution and the amount of preference information required.

Keywords:multi-objective optimization;progressively changing solution set; interactive approach;multi-attribute auctions

1. Introduction

In multi-objective problems, a common assumption is that thereis a fixed set of available alternatives

from which the decision maker (DM) makes choices. Depending on the natureof the problem, these

alternatives may be explicitly available or they may be generated (solving mathematical models) as

needed. In practice, the assumption that all alternatives are available at the outset is too strong. In

some problems, alternatives may emerge progressively over time. Determination of the winner(s)

in a multi-attribute multi-round auction setting is an example for such a situation. In this setting,

bidders update their bids at each round creating a new set of alternatives progressively. Korhonen

et al. (1993) mention recruiting processes as examples of such environments. E-commerce, where the

products sold online,and the real estate market, where the listed houses keep changing continuously.

∗Corresponding author.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

G. Karakayaand M. K ¨

oksalan / Intl. Trans. in Op. Res. 28 (2021) 356–375 357

At any point in time, the available set of alternatives may comprise two subsets: those that are still

available from earlier stages and those that have just emerged. Also, even if all the alternatives are

available at the outset, the DM may find it cognitively hard to consider all of them at once. After

considering a subset of the available alternativeshe/she may wish to stop if a satisfactory alternative

is reached.

The above discussions are in line with the satisficing and bounded rationality concepts of Herbert

Simon (1972), where he argues that there are limits to the “rationality” of humans. The problem’s

complexity in terms of risks, uncertainty, and the sophistication in the problem environment may

be prohibitive for an individual to evaluate everything and come up with the best decision. Simon

also argues that only limited, incomplete information may be available about all possible courses of

action. His arguments imply that the decision-making environment is typically dynamic, whether

due to the nature or the complexity of the problem. Therefore, he argues that an individual’s

rationality is bounded and that people make satisficing, rather than optimal decisions. He claims

that people either reduce their aspirations or search for additional alternatives in case they cannot

find satisfactory alternatives. In addition to these difficulties, the dynamic natureof the problem may

lead an individual to different sets of alternatives based on the choices made in earlier stages. We

will discuss one such case, the biattribute, multi-item, multi-round auction problem, as an example

in our computational studies later in this paper.

Korhonen et al. (1993) developed a progressive algorithm that uses pairwise comparisons of the

DM to test the form of his/her underlying preference function and provides a probability range

under a set of assumptions for finding better alternatives based on which the DM decides whether

or not to continue the selection process. Chun (2015) developed a decision model based on the

assumption that the DM has a major attribute to be optimized and minor attributes to be satisfied.

He devises search strategies to make a choice under uncertainty.

In this study, we develop algorithms that iterate progressively until finding a satisfactory alterna-

tive of a DM. Without loss of generality, we assume that both objectives are of minimization type

and the DM’s preferencesare consistent with a general quasiconvex function that is unknown to us.

We keep iterating and progressively evaluating alternatives as they become available until a suitable

stopping condition is satisfied. Quasiconcave preference functions have been considered to represent

human behavior well for maximization-type objectives (see K¨

oksalan et al., 1984; Silberberg and

Suen, 2001, pp. 260–261) and have been used in the literature extensively (see, e.g., Korhonen et al.,

1984; Lokman et al., 2016; ¨

Ozpeynirci et al., 2017). When the objectives are of minimization type,

quasiconvex preference functions aresuitable in an identical fashion. There are approaches that test

whether a DM’s preferences are consistent with such functions (Korhonen et al., 1986; K¨

oksalan

and Sagala, 1995) and they can be used as preprocessors to see if the assumption is approximately

satisfied.

Karakaya and K ¨

oksalan (2016) consider the multi-round auction problem under the assumption

of a linear preference function. In this paper, we consider a generalized version of their problemfrom

several perspectives. Our approach is not specific to auctions and can be appliedto any problem that

has a progressively changing solution set. We address issues such as when to stop with a satisfactory

solution in an environment where new solutions keep emerging in time.

Another general aspect of this paper is that, it allows for a wider class of preference structures

(quasiconvex preference functions) that have been considered to represent human behavior well.

We develop models and an algorithm to find the most preferred solution of a DM. We introduce

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies