The Adjusted Winner Procedure: Characterizations and Equilibria

Haris Aziz; Simina Brânzei; Aris Filos-Ratsikas; Søren Kristoffer Stiil Frederiksen

The Adjusted Winner Procedure: Characterizations and Equilibria

Haris Aziz, Simina Brânzei, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The Adjusted Winner procedure is an important mechanism proposed by Brams and Taylor for fairly allocating goods between two agents. It has been used in practice for divorce settlements and analyzing political disputes. Assuming truthful declaration of the valuations, it computes an allocation that is envy-free, equitable and Pareto optimal. We show that Adjusted Winner admits several elegant characterizations, which further shed light on the outcomes reached with strategic agents. We find that the procedure may not admit pure Nash equilibria in either the discrete or continuous variants, but is guaranteed to have Îµ-Nash equilibria for each Îµ > 0. Moreover, under informed tie-breaking, exact pure Nash equilibria always exist, are Pareto optimal, and their social welfare is at least 3/4 of the optimal.

Original language	English
Title of host publication	Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence
Place of Publication	Palo Alto, California USA
Publisher	AAAI Press / International Joint Conferences on Artificial Intelligence
Pages	454-460
Number of pages	7
ISBN (Electronic)	978-1-57735-738-4
Publication status	Published - 31 Jul 2015
Event	24th International Joint Conference on Artificial Intelligence 2015 - Buenos Aires, Argentina Duration: 25 Jul 2015 → 31 Jul 2015 https://ijcai-15.org/

Conference

Conference	24th International Joint Conference on Artificial Intelligence 2015
Abbreviated title	IJCAI 2015
Country/Territory	Argentina
City	Buenos Aires
Period	25/07/15 → 31/07/15
Internet address	https://ijcai-15.org/

Access to Document

https://www.ijcai.org/Abstract/15/070Licence: All Rights Reserved

Cite this

@inproceedings{a390b6aa510e426eaff80850278b1e53,

title = "The Adjusted Winner Procedure: Characterizations and Equilibria",

abstract = "The Adjusted Winner procedure is an important mechanism proposed by Brams and Taylor for fairly allocating goods between two agents. It has been used in practice for divorce settlements and analyzing political disputes. Assuming truthful declaration of the valuations, it computes an allocation that is envy-free, equitable and Pareto optimal. We show that Adjusted Winner admits several elegant characterizations, which further shed light on the outcomes reached with strategic agents. We find that the procedure may not admit pure Nash equilibria in either the discrete or continuous variants, but is guaranteed to have {\^I}µ-Nash equilibria for each {\^I}µ > 0. Moreover, under informed tie-breaking, exact pure Nash equilibria always exist, are Pareto optimal, and their social welfare is at least 3/4 of the optimal.",

author = "Haris Aziz and Simina Br{\^a}nzei and Aris Filos-Ratsikas and Frederiksen, {S{\o}ren Kristoffer Stiil}",

year = "2015",

month = jul,

day = "31",

language = "English",

pages = "454--460",

booktitle = "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence",

publisher = "AAAI Press / International Joint Conferences on Artificial Intelligence",

note = "24th International Joint Conference on Artificial Intelligence 2015, IJCAI 2015 ; Conference date: 25-07-2015 Through 31-07-2015",

url = "https://ijcai-15.org/",

}

Aziz, H, Brânzei, S, Filos-Ratsikas, A & Frederiksen, SKS 2015, The Adjusted Winner Procedure: Characterizations and Equilibria. in Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. AAAI Press / International Joint Conferences on Artificial Intelligence, Palo Alto, California USA, pp. 454-460, 24th International Joint Conference on Artificial Intelligence 2015, Buenos Aires, Argentina, 25/07/15. <https://www.ijcai.org/Abstract/15/070>

The Adjusted Winner Procedure: Characterizations and Equilibria. / Aziz, Haris; Brânzei, Simina; Filos-Ratsikas, Aris et al.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Palo Alto, California USA: AAAI Press / International Joint Conferences on Artificial Intelligence, 2015. p. 454-460.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The Adjusted Winner Procedure: Characterizations and Equilibria

AU - Aziz, Haris

AU - Brânzei, Simina

AU - Filos-Ratsikas, Aris

AU - Frederiksen, Søren Kristoffer Stiil

PY - 2015/7/31

Y1 - 2015/7/31

N2 - The Adjusted Winner procedure is an important mechanism proposed by Brams and Taylor for fairly allocating goods between two agents. It has been used in practice for divorce settlements and analyzing political disputes. Assuming truthful declaration of the valuations, it computes an allocation that is envy-free, equitable and Pareto optimal. We show that Adjusted Winner admits several elegant characterizations, which further shed light on the outcomes reached with strategic agents. We find that the procedure may not admit pure Nash equilibria in either the discrete or continuous variants, but is guaranteed to have Îµ-Nash equilibria for each Îµ > 0. Moreover, under informed tie-breaking, exact pure Nash equilibria always exist, are Pareto optimal, and their social welfare is at least 3/4 of the optimal.

AB - The Adjusted Winner procedure is an important mechanism proposed by Brams and Taylor for fairly allocating goods between two agents. It has been used in practice for divorce settlements and analyzing political disputes. Assuming truthful declaration of the valuations, it computes an allocation that is envy-free, equitable and Pareto optimal. We show that Adjusted Winner admits several elegant characterizations, which further shed light on the outcomes reached with strategic agents. We find that the procedure may not admit pure Nash equilibria in either the discrete or continuous variants, but is guaranteed to have Îµ-Nash equilibria for each Îµ > 0. Moreover, under informed tie-breaking, exact pure Nash equilibria always exist, are Pareto optimal, and their social welfare is at least 3/4 of the optimal.

M3 - Conference contribution

SP - 454

EP - 460

BT - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence

PB - AAAI Press / International Joint Conferences on Artificial Intelligence

CY - Palo Alto, California USA

T2 - 24th International Joint Conference on Artificial Intelligence 2015

Y2 - 25 July 2015 through 31 July 2015

ER -

The Adjusted Winner Procedure: Characterizations and Equilibria

Abstract

Conference

Access to Document

Fingerprint

Cite this