Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence
New York, New York, USA   9–15 July 2016
Edited by Subbarao Kambhampati, Arizona State University
Cosponsored by
International Joint Conferences on Artificial Intelligence (IJCAI)
Association for the Advancement of Artificial Intelligence
Published by
AAAI Press / International Joint Conferences on Artificial Intelligence

Palo Alto, California USA

Copyright © 2016 International Joint Conferences on Artificial Intelligence
All rights reserved. No part of this book may be reproduced in any form by any electronic

or mechanical means (including photocopying, recording, or information storage and

retrieval) without permission in writing from the publisher.

IJCAI Secretary-Treasurer: Prof. Dr. Bernhard Nebel, Computer Science Department, Albert

-Ludwigs-Universitaet Freiburg, Georges-Koehler-Allee, Geb. 052 D-79110 Freiburg, Germany

IJCAI Executive Secretary Ms. Vesna Sabljakovic-Fritz, Vienna University of Technology,

Institute of Discrete Mathematics and Geometry, E104 Wiedner Hauptstr. 8-10, A-1040

Vienna, Austria

Copublished and Distributed by AAAI Press, 2275 East Bayshore Road, Suite 160, Palo Alto

CA 94303 USA

ISBN 978-1-57735-770-4 (volumes 1-3)

ISBN 978-1-57735-771-1 (volumes 4-6)
Contents

Preface / xxxiii
Subbarao Kambhampati, Gerhard Brewka


Conference Organization / xxxv
Subbarao Kambhampati, Gerhard Brewka


Program Committee / xxxvii
Subbarao Kambhampati, Gerhard Brewka


Conference Organizers and Sponsors / liii
Subbarao Kambhampati, Gerhard Brewka


Awards and Distinguished Papers / lv
Subbarao Kambhampati, Gerhard Brewka


IJCAI Organization / lvii
Subbarao Kambhampati, Gerhard Brewka


Past IJCAI Conferences / lix
Subbarao Kambhampati, Gerhard Brewka


Interdependent Scheduling Games / 2
Andres Abeliuk, Haris Aziz, Gerardo Berbeglia, Serge Gaspers, Petr Kalina, Nicholas

Mattei, Dominik Peters, Paul Stursberg, Pascal Van Hentenryck, Toby Walsh


Scalable Greedy Algorithms for Task/Resource Constrained Multi-Agent Stochastic Planning

/ 10
Pritee Agrawal, Pradeep Varakantham, William Yeoh


Coco: Runtime Reasoning about Conflicting Commitments / 17
Nirav Ajmeri, Jiaming Jiang, Rada Chirkova, Jon Doyle, Munindar P. Singh


Verifying Existence of Resource-Bounded Coalition Uniform Strategies / 24
Natasha Alechina, Mehdi Dastani, Brian Logan


On Truthful Mechanisms for Maximin Share Allocations / 31
Georgios Amanatidis, Georgios Birmpas, Evangelos Markakis


Modeling and Reasoning about NTU Games via Answer Set Programming / 38
Giovanni Amendola, Gianluigi Greco, Nicola Leone, Pierfrancesco Veltri


Randomized Social Choice Functions under Metric Preferences / 46
Elliot Anshelevich, John Postl


Generalized Discrete Preference Games / 53
Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, Giuseppe

Persiano


Computing Pareto Optimal Committees / 60
Haris Aziz, Jérôme Lang, Jérôme Monnot


Control of Fair Division / 67
Haris Aziz, Ildikó Schlotter, Toby Walsh


A Characterization of Voting Power for Discrete Weight Distributions / 74
Yoram Bachrach, Yuval Filmus, Joel Oren, Yair Zick


Misrepresentation in District Voting / 81
Yoram Bachrach, Omer Lev, Yoad Lewenberg, Yair Zick


Conditional and Sequential Approval Voting on Combinatorial Domains / 88
Nathanaël Barrot, Jérôme Lang


On Logics of Strategic Ability Based on Propositional Control / 95
Francesco Belardinelli, Andreas Herzig


Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or

Utility Levels / 102
Bernhard Bliem, Robert Bredereck, Rolf Niedermeier


The Complexity of Playing Durak / 109
édouard Bonnet


Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving / 116
Florian Brandl, Felix Brandt, Christian Geist


To Give or Not to Give: Fair Division for Single Minded Valuations / 123
Simina Brânzei, Yuezhou Lv, Ruta Mehta


Pairwise Diffusion of Preference Rankings in Social Networks / 130
Markus Brill, Edith Elkind, Ulle Endriss, Umberto Grandi


Facility Location with Minimax Envy / 137
Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang


Achieving Proportional Representation in Conference Programs / 144
Ioannis Caragiannis, Laurent Gourvès, Jérôme Monnot


Subset Selection via Implicit Utilitarian Voting / 151
Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, Nisarg Shah


Trading on a Rigged Game: Outcome Manipulation in Prediction Markets / 158
Mithun Chakraborty, Sanmay Das


Congestion Games with Polytopal Strategy Spaces / 165
Hau Chan, Albert Xin Jiang


Robust Draws in Balanced Knockout Tournaments / 172
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Josef Tkadlec


Verifying Pushdown Multi-Agent Systems against Strategy Logics / 180
Taolue Chen, Fu Song, Zhilin Wu


Truthfulness of a Proportional Sharing Mechanism in Resource Exchange / 187
Yukun Cheng, Xiaotie Deng, Qi Qi, Xiang Yan


Better Strategyproof Mechanisms without Payments or Prior — An Analytic Approach / 194
Yun Kuen Cheung


Approximating Value Equivalence in Interactive Dynamic Influence Diagrams Using

Behavioral Coverage / 201
Ross Conroy, Yifeng Zeng, Jing Tang


Selective Norm Monitoring / 208
Natalia Criado, Jose M. Such


Elicitation for Preferences Single Peaked on Trees / 215
Palash Dey, Neeldhara Misra


Preference Elicitation for Single Crossing Domain / 222
Palash Dey, Neeldhara Misra


Complexity of Manipulation with Partial Information in Voting / 229
Palash Dey, Neeldhara Misra, Y. Narahari


Strategic Voting with Incomplete Information / 236
Ulle Endriss, Svetlana Obraztsova, Maria Polukarov, Jeffrey S. Rosenschein


Voting-Based Group Formation / 243
Piotr Faliszewski, Arkadii Slinko, Nimrod Talmon


Committee Scoring Rules: Axiomatic Classification and Hierarchy / 250
Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon


How Hard Is It for a Party to Nominate an Election Winner? / 257
Piotr Faliszewski, Laurent Gourvès, Jérôme Lang, Julien Lesca, Jérôme Monnot


Digital Good Exchange / 264
Wenyi Fang, Pingzhong Tang, Song Zuo


Parallel Behavior Composition for Manufacturing / 271
Paolo Felli, Brian Logan, Sebastian Sardina


Opinion Dynamics with Local Interactions / 279
Dimitris Fotakis, Dimitris Palyvos-Giannas, Stratis Skoulakis


Online Mechanism Design for Vehicle-to-Grid Car Parks / 286
Enrico H. Gerding, Sebastian Stein, Sofia Ceppi, Valentin Robu


Moving in a Crowd: Safe and Efficient Navigation among Heterogeneous Agents / 294
Julio Godoy, Ioannis Karamouzas, Stephen J. Guy, Maria Gini


A Network-Based Rating System and Its Resistance to Bribery / 301
Umberto Grandi, Paolo Turrini


Three Strategies to Success: Learning Adversary Models in Security Games / 308
Nika Haghtalab, Fei Fang, Thanh H. Nguyen, Arunesh Sinha, Ariel D. Procaccia, Milind

Tambe


Reconfigurability in Reactive Multiagent Systems / 315
Xiaowei Huang, Qingliang Chen, Jie Meng, Kaile Su


Probabilistic Matrix Inspection and Group Scheduling / 322
Hooyeon Lee, Ashish Goel


Catcher-Evader Games / 329
Yuqian Li, Vincent Conitzer, Dmytro Korzhyk


Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing / 338
Thanasis Lianeas, Evdokia Nikolova, Nicolas E. Stier-Moses


Social Choice for Agents with General Utilities / 345
Hongyao Ma, Reshef Meir, David C. Parkes


Incentivizing Reliability in Demand-Side Response / 352
Hongyao Ma, Valentin Robu, Na Li, David C. Parkes


Allocating Indivisible Items in Categorized Domains / 359
Erika Mackin, Lirong Xia


Correlated Voting / 366
Debmalya Mandal, David C. Parkes


Silk: A Simulation Study of Regulating Open Normative Multiagent Systems / 373
Mehdi Mashayekhi, Hongying Du, George F. List, Munindar P. Singh


Incentivizing Intelligent Customer Behavior in Smart-Grids: A Risk-Sharing Tariff &

Optimal Strategies / 380
Georgios Methenitis, Michael Kaisers, Han La Poutré


Dynamic Auctions with Bank Accounts / 387
Vahab Mirrokni, Renato Paes Leme, Pingzhong Tang, Song Zuo


SLIM: Semi-Lazy Inference Mechanism for Plan Recognition / 394
Reuth Mirsky, Ya’akov (Kobi) Gal


Sequential Plan Recognition / 401
Reuth Mirsky, Roni Stern, Ya’akov (Kobi) Gal, Meir Kalech


Distributed Decoupling of Multiagent Simple Temporal Problems / 408
Jayanth Krishna Mogali, Stephen F. Smith, Zachary B. Rubinstein


Role Assignment for Game-Theoretic Cooperation / 416
Catherine Moon, Vincent Conitzer


Core-Selecting Payment Rules for Combinatorial Auctions with Uncertain Availability of

Goods / 424
Dmitry Moor, Sven Seuken, Tobias Grubenmann, Abraham Bernstein


Automated Mechanism Design without Money via Machine Learning / 433
Harikrishna Narasimhan, Shivani Agarwal, David C. Parkes


Trembling Hand Equilibria of Plurality Voting / 440
Svetlana Obraztsova, Zinovi Rabinovich, Edith Elkind, Maria Polukarov, Nicholas R.

Jennings


Distributed Breakout: Beyond Satisfaction / 447
Steven Okamoto, Roie Zivan, Aviv Nahon


Mission Oriented Robust Multi-Team Formation and Its Application to Robot Rescue

Simulation / 454
Tenda Okimoto, Tony Ribeiro, Damien Bouchabou, Katsumi Inoue


Controlling Growing Tasks with Heterogeneous Agents / 461
James Parker, Maria Gini


Using Message-Passing DCOP Algorithms to Solve Energy-Efficient Smart Environment

Configuration Problems / 468
Pierre Rust, Gauthier Picard, Fano Ramparany


An Online Mechanism for Ridesharing in Autonomous Mobility-on-Demand Systems / 475
Wen Shen, Cristina V. Lopes, Jacob W. Crandall


Efficient Local Search in Coordination Games on Graphs / 482
Sunil Simon, Dominik Wojtczak


Assigning a Small Agreeable Set of Indivisible Items to Multiple Players / 489
Warut Suksompong


Preserving Privacy in Region Optimal DCOP Algorithms / 496
Tamir Tassa, Roie Zivan, Tal Grinshpoun


Nash Equilibria and Their Elimination in Resource Games / 503
Nicolas Troquard


An Empirical Game-Theoretic Analysis of Price Discovery in Prediction Markets / 510
Elaine Wah, Sébastien Lahaie, David M. Pennock


Hierarchical Approach to Transfer of Control in Semi-Autonomous Systems / 517
Kyle Hollins Wray, Luis Pineda, Shlomo Zilberstein


Coordinating Human-UAV Teams in Disaster Response / 524
Feng Wu, Sarvapali D. Ramchurn, Xiaoping Chen


Efficient Resource Allocation for Protecting Coral Reef Ecosystems / 531
Yue Yin, Bo An


Optimally Protecting Elections / 538
Yue Yin, Yevgeniy Vorobeychik, Bo An, Noam Hazon


Decision-Making Policies for Heterogeneous Autonomous Multi-Agent Systems with Safety

Constraints / 546
Ruohan Zhang, Yue Yu, Mahmoud El Chamie, Behçet Açıkmese, Dana H. Ballard


Towards a White Box Approach to Automated Algorithm Design / 554
Steven Adriaensen, Ann Nowé


Action Selection for Hammer Shots in Curling / 561
Zaheen Farraz Ahmad, Robert C. Holte, Michael Bowling


Fast Solving Maximum Weight Clique Problem in Massive Graphs / 568
Shaowei Cai, Jinkun Lin


Packing Graphs with ASP for Landscape Simulation / 575
Thomas Guyet, Yves Moinard, Jacques Nicolas, René Quiniou


On the Topology of Genetic Algorithms / 582
David Hofmeyr