Author name cluster

James P. Bailey

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

AAMAS Conference 2025 Conference Paper

On the Gale-Shapley Algorithm for Stable Matchings with a Partial Honesty Nash Refinement

James P. Bailey
Craig A. Tovey

It has long been known that every individually rational matching is obtainable by some Nash equilibrium — even those that make little sense in practice. In the social choice and voting literature, Nash refinements are commonly used to avoid these spurious equilibria. In this paper, we examine the Gale-Shapley algorithm (deferred acceptance) where agents behave strategically but are minimally dishonest, a common refinement in the social choice and voting literature. Under this condition we show that when men propose, every equilibrium corresponds to the woman-optimal marriage, thereby yielding a unique prediction for the outcome for the stable matching problem.

PDF

AAMAS Conference 2025 Conference Paper

The Price of Anarchy in Spatial Social Choice

James P. Bailey
Craig A. Tovey

Except for a few strategy-proof mechanisms on the real line, spatial social choice mechanisms are usually manipulable. But is it wise to treat all manipulations as equally bad? We use the price of anarchy to make finer distinctions than between “strategy-proof” and “manipulable. ” The price of anarchy measures how much strategic behavior can alter the cost in social choice. Supported by experimental economics data, our measure employs a novel minimal dishonesty criterion to refine the set of Nash equilibria. Using the price of anarchy, we study standard spatial selection rules and uncover a class of selection rules that are immune to the negative consequences of manipulation despite remaining manipulable. This is in contrast to standard approaches that sacrifice other beneficial properties, e. g. , unbiased tie-breaking, to gain strategy-proofness. The concepts herein could be applied to other social choice scenarios in which a publicly known mechanism relies on private information.

PDF

AAMAS Conference 2024 Conference Paper

Impact of Tie-Breaking on the Manipulability of Elections

James P. Bailey
Craig A. Tovey

In this paper, we quantify the impact of manipulation using the price of anarchy measurement and study the impact of the lexicographic and the random candidate tie-breaking rules. We show that neither dominates the other in terms of mitigating the impact of manipulation. Specifically, we show that the random candidate tie-breaking rule lowers the impact of manipulation in plurality elections whereas the lexicographic tie-breaking rule lowers the impact of manipulation in elections determined by majority judgment.

PDF

AIJ Journal 2021 Journal Article

Path-length analysis for grid-based path planning

James P. Bailey
Alex Nash
Craig A. Tovey
Sven Koenig

In video games and robotics, one often discretizes a continuous 2D environment into a regular grid with blocked and unblocked cells and then finds shortest paths for the agents on the resulting grid graph. Shortest grid paths, of course, are not necessarily true shortest paths in the continuous 2D environment. In this article, we therefore study how much longer a shortest grid path can be than a corresponding true shortest path on all regular grids with blocked and unblocked cells that tessellate continuous 2D environments. We study 5 different vertex connectivities that result from both different tessellations and different definitions of the neighbors of a vertex. Our path-length analysis yields either tight or asymptotically tight worst-case bounds in a unified framework. Our results show that the percentage by which a shortest grid path can be longer than a corresponding true shortest path decreases as the vertex connectivity increases. Our path-length analysis is topical because it determines the largest path-length reduction possible for any-angle path-planning algorithms (and thus their benefit), a class of path-planning algorithms in artificial intelligence and robotics that has become popular.

Details DOI

AAMAS Conference 2019 Conference Paper

Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System

James P. Bailey
Georgios Piliouras

Zero-sum games are natural, if informal, analogues of closed physical systems where no energy/utility can enter or exit. This analogy can be extended even further if we consider zero-sum network (polymatrix) games where multiple agents interact in a closed economy. Typically, (network) zero-sum games are studied from the perspective of Nash equilibria. Nevertheless, this comes in contrast with the way we typically think about closed physical systems, e. g. , Earth-moon systems which move perpetually along recurrent trajectories of constant energy. We establish a formal and robust connection between multiagent systems and Hamiltonian dynamics – the same dynamics

PDF