Exposing market mechanism design trade-offs via multi-objective evolutionary search

Arjun Chandra, Richard Allmendinger, Peter R. Lewis, Xin Yao, Jim Torresen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Market mechanisms are a means by which resources in contention can be allocated between contending parties, both in human economies and those populated by software agents. Designing such mechanisms has traditionally been carried out by hand, and more recently by automation. Assessing these mechanisms typically involves them being evaluated with respect to multiple conflicting objectives, which can often be nonlinear, noisy, and expensive to compute. For typical performance objectives, it is known that designed mechanisms often fall short on being optimal across all objectives simultaneously. However, in all previous automated approaches, either only a single objective is considered, or else the multiple performance objectives are combined into a single objective. In this paper we do not aggregate objectives, instead considering a direct, novel application of multi-objective evolutionary algorithms (MOEAs) to the problem of automated mechanism design. This allows the automatic discovery of trade-offs that such objectives impose on mechanisms. We pose the problem of mechanism design, specifically for the class of linear redistribution mechanisms, as a naturally existing multi-objective optimisation problem. We apply a modified version of NSGA-II in order to design mechanisms within this class, given economically relevant objectives such as welfare and fairness. This application of NSGA-II exposes tradeoffs between objectives, revealing relationships between them that were otherwise unknown for this mechanism class. The understanding of the trade-off gained from the application of MOEAs can thus help practitioners with an insightful application of discovered mechanisms in their respective real/artificial markets.

Original languageEnglish
Title of host publication2013 IEEE Congress on Evolutionary Computation
PublisherIEEE
Pages1515-1522
Number of pages8
ISBN (Electronic)978-1-4799-0452-5
ISBN (Print)978-1-4799-0453-2
DOIs
Publication statusPublished - 2013
Event2013 IEEE Congress on Evolutionary Computation - Cancún, Mexico
Duration: 20 Jun 201323 Jun 2013

Congress

Congress2013 IEEE Congress on Evolutionary Computation
Abbreviated titleCEC 2013
CountryMexico
CityCancún
Period20/06/1323/06/13

Fingerprint

Mechanism Design
Trade-offs
Evolutionary algorithms
Software agents
NSGA-II
Multi-objective Evolutionary Algorithm
Multiobjective optimization
Automation
Software Agents
Market
Multiple Objectives
Multiobjective Optimization Problems
Redistribution
Welfare
Contention
Fairness
Unknown
Resources

Bibliographical note

© 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Keywords

  • automated mechanism design
  • fairness
  • market based interaction
  • redistribution
  • resource allocation
  • welfare

Cite this

Chandra, A., Allmendinger, R., Lewis, P. R., Yao, X., & Torresen, J. (2013). Exposing market mechanism design trade-offs via multi-objective evolutionary search. In 2013 IEEE Congress on Evolutionary Computation (pp. 1515-1522). IEEE. https://doi.org/10.1109/CEC.2013.6557742
Chandra, Arjun ; Allmendinger, Richard ; Lewis, Peter R. ; Yao, Xin ; Torresen, Jim. / Exposing market mechanism design trade-offs via multi-objective evolutionary search. 2013 IEEE Congress on Evolutionary Computation . IEEE, 2013. pp. 1515-1522
@inproceedings{24268c694f764ea1bd8ec50244a9d56c,
title = "Exposing market mechanism design trade-offs via multi-objective evolutionary search",
abstract = "Market mechanisms are a means by which resources in contention can be allocated between contending parties, both in human economies and those populated by software agents. Designing such mechanisms has traditionally been carried out by hand, and more recently by automation. Assessing these mechanisms typically involves them being evaluated with respect to multiple conflicting objectives, which can often be nonlinear, noisy, and expensive to compute. For typical performance objectives, it is known that designed mechanisms often fall short on being optimal across all objectives simultaneously. However, in all previous automated approaches, either only a single objective is considered, or else the multiple performance objectives are combined into a single objective. In this paper we do not aggregate objectives, instead considering a direct, novel application of multi-objective evolutionary algorithms (MOEAs) to the problem of automated mechanism design. This allows the automatic discovery of trade-offs that such objectives impose on mechanisms. We pose the problem of mechanism design, specifically for the class of linear redistribution mechanisms, as a naturally existing multi-objective optimisation problem. We apply a modified version of NSGA-II in order to design mechanisms within this class, given economically relevant objectives such as welfare and fairness. This application of NSGA-II exposes tradeoffs between objectives, revealing relationships between them that were otherwise unknown for this mechanism class. The understanding of the trade-off gained from the application of MOEAs can thus help practitioners with an insightful application of discovered mechanisms in their respective real/artificial markets.",
keywords = "automated mechanism design, fairness, market based interaction, redistribution, resource allocation, welfare",
author = "Arjun Chandra and Richard Allmendinger and Lewis, {Peter R.} and Xin Yao and Jim Torresen",
note = "{\circledC} 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.",
year = "2013",
doi = "10.1109/CEC.2013.6557742",
language = "English",
isbn = "978-1-4799-0453-2",
pages = "1515--1522",
booktitle = "2013 IEEE Congress on Evolutionary Computation",
publisher = "IEEE",
address = "United States",

}

Chandra, A, Allmendinger, R, Lewis, PR, Yao, X & Torresen, J 2013, Exposing market mechanism design trade-offs via multi-objective evolutionary search. in 2013 IEEE Congress on Evolutionary Computation . IEEE, pp. 1515-1522, 2013 IEEE Congress on Evolutionary Computation, Cancún, Mexico, 20/06/13. https://doi.org/10.1109/CEC.2013.6557742

Exposing market mechanism design trade-offs via multi-objective evolutionary search. / Chandra, Arjun; Allmendinger, Richard; Lewis, Peter R.; Yao, Xin; Torresen, Jim.

2013 IEEE Congress on Evolutionary Computation . IEEE, 2013. p. 1515-1522.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Exposing market mechanism design trade-offs via multi-objective evolutionary search

AU - Chandra, Arjun

AU - Allmendinger, Richard

AU - Lewis, Peter R.

AU - Yao, Xin

AU - Torresen, Jim

N1 - © 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2013

Y1 - 2013

N2 - Market mechanisms are a means by which resources in contention can be allocated between contending parties, both in human economies and those populated by software agents. Designing such mechanisms has traditionally been carried out by hand, and more recently by automation. Assessing these mechanisms typically involves them being evaluated with respect to multiple conflicting objectives, which can often be nonlinear, noisy, and expensive to compute. For typical performance objectives, it is known that designed mechanisms often fall short on being optimal across all objectives simultaneously. However, in all previous automated approaches, either only a single objective is considered, or else the multiple performance objectives are combined into a single objective. In this paper we do not aggregate objectives, instead considering a direct, novel application of multi-objective evolutionary algorithms (MOEAs) to the problem of automated mechanism design. This allows the automatic discovery of trade-offs that such objectives impose on mechanisms. We pose the problem of mechanism design, specifically for the class of linear redistribution mechanisms, as a naturally existing multi-objective optimisation problem. We apply a modified version of NSGA-II in order to design mechanisms within this class, given economically relevant objectives such as welfare and fairness. This application of NSGA-II exposes tradeoffs between objectives, revealing relationships between them that were otherwise unknown for this mechanism class. The understanding of the trade-off gained from the application of MOEAs can thus help practitioners with an insightful application of discovered mechanisms in their respective real/artificial markets.

AB - Market mechanisms are a means by which resources in contention can be allocated between contending parties, both in human economies and those populated by software agents. Designing such mechanisms has traditionally been carried out by hand, and more recently by automation. Assessing these mechanisms typically involves them being evaluated with respect to multiple conflicting objectives, which can often be nonlinear, noisy, and expensive to compute. For typical performance objectives, it is known that designed mechanisms often fall short on being optimal across all objectives simultaneously. However, in all previous automated approaches, either only a single objective is considered, or else the multiple performance objectives are combined into a single objective. In this paper we do not aggregate objectives, instead considering a direct, novel application of multi-objective evolutionary algorithms (MOEAs) to the problem of automated mechanism design. This allows the automatic discovery of trade-offs that such objectives impose on mechanisms. We pose the problem of mechanism design, specifically for the class of linear redistribution mechanisms, as a naturally existing multi-objective optimisation problem. We apply a modified version of NSGA-II in order to design mechanisms within this class, given economically relevant objectives such as welfare and fairness. This application of NSGA-II exposes tradeoffs between objectives, revealing relationships between them that were otherwise unknown for this mechanism class. The understanding of the trade-off gained from the application of MOEAs can thus help practitioners with an insightful application of discovered mechanisms in their respective real/artificial markets.

KW - automated mechanism design

KW - fairness

KW - market based interaction

KW - redistribution

KW - resource allocation

KW - welfare

UR - http://www.scopus.com/inward/record.url?scp=84881560392&partnerID=8YFLogxK

U2 - 10.1109/CEC.2013.6557742

DO - 10.1109/CEC.2013.6557742

M3 - Conference contribution

SN - 978-1-4799-0453-2

SP - 1515

EP - 1522

BT - 2013 IEEE Congress on Evolutionary Computation

PB - IEEE

ER -

Chandra A, Allmendinger R, Lewis PR, Yao X, Torresen J. Exposing market mechanism design trade-offs via multi-objective evolutionary search. In 2013 IEEE Congress on Evolutionary Computation . IEEE. 2013. p. 1515-1522 https://doi.org/10.1109/CEC.2013.6557742