David C. Parkes

AAMAS Conference 2025 Conference Paper

On Diffusion Models for Multi-Agent Partial Observability: Shared Attractors, Error Bounds, and Composite Flow

• Tonghan Wang
• Heng Dong
• Yanchen Jiang
• David C. Parkes
• Milind Tambe

Multiagent systems grapple with partial observability (PO), and the decentralized POMDP (Dec-POMDP) model highlights the fundamental nature of this challenge. Whereas recent approaches to addressing PO have appealed to deep learning models, providing a rigorous understanding of how these models and their approximation errors a�ect agents’ handling of PO and their interactions remain a challenge. In addressing this challenge, we investigate reconstructing global states from local action-observation histories in Dec-POMDPs using di�usion models. We� rst� nd that di�usion models conditioned on local history represent possible states as stable� xed points. In collectively observable (CO) Dec-POMDPs, individual di�usion models conditioned on agents’ local histories share a unique� xed point corresponding to the global state, while in non-CO settings, shared� xed points yield a distribution of possible states given joint history. We further� nd that, with deep learning approximation errors, � xed points can deviate from true states and the deviation is negatively correlated to the Jacobian rank. Inspired by this low-rank property, we bound a deviation by constructing a surrogate linear regression model that approximates the local behavior of a di�usion model. With this bound, we propose a composite di�usion process iterating over agents with theoretical convergence guarantees to the true state.

ICLR Conference 2024 Conference Paper

Decongestion by Representation: Learning to Improve Economic Welfare in Marketplaces

• Omer Nahum
• Gali Noti
• David C. Parkes
• Nir Rosenfeld

Congestion is a common failure mode of markets, where consumers compete inefficiently on the same subset of goods (e.g., chasing the same small set of properties on a vacation rental platform). The typical economic story is that prices decongest by balancing supply and demand. But in modern online marketplaces, prices are typically set in a decentralized way by sellers, and the information about items is inevitably partial. The power of a platform is limited to controlling *representations*---the subset of information about items presented by default to users. This motivates the present study of *decongestion by representation*, where a platform seeks to learn representations that reduce congestion and thus improve social welfare. The technical challenge is twofold: relying only on revealed preferences from the choices of consumers, rather than true preferences; and the combinatorial problem associated with representations that determine the features to reveal in the default view. We tackle both challenges by proposing a *differentiable proxy of welfare* that can be trained end-to-end on consumer choice data. We develop sufficient conditions for when decongestion promotes welfare, and present the results of extensive experiments on both synthetic and real data that demonstrate the utility of our approach.

ICLR Conference 2024 Conference Paper

Generative Adversarial Equilibrium Solvers

• Denizalp Goktas
• David C. Parkes
• Ian Gemp
• Luke Marris
• Georgios Piliouras
• Romuald Elie
• Guy Lever
• Andrea Tacchetti

We introduce the use of generative adversarial learning to compute equilibria in general game-theoretic settings, specifically the generalized Nash equilibrium (GNE) in pseudo-games, and its specific instantiation as the competitive equilibrium (CE) in Arrow-Debreu competitive economies. Pseudo-games are a generalization of games in which players' actions affect not only the payoffs of other players but also their feasible action spaces. Although the computation of GNE and CE is intractable in the worst-case, i.e., PPAD-hard, in practice, many applications only require solutions with high accuracy in expectation over a distribution of problem instances. We introduce Generative Adversarial Equilibrium Solvers (GAES): a family of generative adversarial neural networks that can learn GNE and CE from only a sample of problem instances. We provide computational and sample complexity bounds for Lipschitz-smooth function approximators in a large class of concave pseudo-games, and apply the framework to finding Nash equilibria in normal-form games, CE in Arrow-Debreu competitive economies, and GNE in an environmental economic model of the Kyoto mechanism.

ICML Conference 2024 Conference Paper

Multi-Sender Persuasion: A Computational Perspective

• Safwan Hossain
• Tonghan Wang 0001
• Tao Lin 0013
• Yiling Chen 0001
• David C. Parkes
• Haifeng Xu

We consider multiple senders with informational advantage signaling to convince a single self-interested actor to take certain actions. Generalizing the seminal Bayesian Persuasion framework, such settings are ubiquitous in computational economics, multi-agent learning, and machine learning with multiple objectives. The core solution concept here is the Nash equilibrium of senders’ signaling policies. Theoretically, we prove that finding an equilibrium in general is PPAD-Hard; in fact, even computing a sender’s best response is NP-Hard. Given these intrinsic difficulties, we turn to finding local Nash equilibria. We propose a novel differentiable neural network to approximate this game’s non-linear and discontinuous utilities. Complementing this with the extra-gradient algorithm, we discover local equilibria that Pareto dominates full-revelation equilibria and those found by existing neural networks. Broadly, our theoretical and empirical contributions are of interest to a large class of economic problems.

ICML Conference 2024 Conference Paper

Position: Social Environment Design Should be Further Developed for AI-based Policy-Making

• Edwin Zhang
• Sadie Zhao
• Tonghan Wang 0001
• Safwan Hossain
• Henry Gasztowtt
• Stephan Zheng
• David C. Parkes
• Milind Tambe

Artificial Intelligence (AI) holds promise as a technology that can be used to improve government and economic policy-making. This paper proposes a new research agenda towards this end by introducing Social Environment Design, a general framework for the use of AI in automated policy-making that connects with the Reinforcement Learning, EconCS, and Computational Social Choice communities. The framework seeks to capture general economic environments, includes voting on policy objectives, and gives a direction for the systematic analysis of government and economic policy through AI simulation. We highlight key open problems for future research in AI-based policymaking. By solving these challenges, we hope to achieve various social welfare objectives, thereby promoting more ethical and responsible decision making.

STOC Conference 2023 Conference Paper

Credible Decentralized Exchange Design via Verifiable Sequencing Rules

• Matheus Venturyne Xavier Ferreira
• David C. Parkes

Trading on decentralized exchanges has been one of the primary use cases for permissionless blockchains with daily trading volume exceeding billions of U.S. ‍dollars. In the status quo, users broadcast transactions they wish to execute in the exchange and miners are responsible for composing a block of transactions and picking an execution ordering — the order in which transactions execute in the exchange. Due to the lack of a regulatory framework, it is common to observe miners exploiting their privileged position by front-running transactions and obtaining risk-fee profits. Indeed, the Flashbots service institutionalizes this exploit, with miners auctioning the right to front-run transactions. In this work, we propose to modify the interaction between miners and users and initiate the study of verifiable sequencing rules . As in the status quo, miners can determine the content of a block; however, they commit to respecting a sequencing rule that constrains the execution ordering and is verifiable (there is a polynomial time algorithm that can verify if the execution ordering satisfies such constraints). Thus in the event a miner deviates from the sequencing rule, anyone can generate a proof of non-compliance. We ask if there are sequencing rules that limit price manipulation from miners in a two-token liquidity pool exchange. Our first result is an impossibility theorem: for any sequencing rule, there is an instance of user transactions where the miner can obtain non-zero risk-free profits. In light of this impossibility result, our main result is a verifiable sequencing rule that provides execution price guarantees for users. In particular, for any user transaction A , it ensures that either (1) the execution price of A is at least as good as if A was the only transaction in the block, or (2) the execution price of A is worse than this “standalone” price and the miner does not gain when including A in the block. Our framework does not require users to use countermeasures against predatory trading strategies, for example, set limit prices or split large transactions into smaller ones. This is likely to improve user experience relative to the status quo.

NeurIPS Conference 2023 Conference Paper

Data Market Design through Deep Learning

• Sai Srivatsa Ravindranath
• Yanchen Jiang
• David C. Parkes

The data market design problem is a problem in economic theory to find a set of signaling schemes (statistical experiments) to maximize expected revenue to the information seller, where each experiment reveals some of the information known to a seller and has a corresponding price. Each buyer has their own decision to make in a world environment, and their subjective expected value for the information associated with a particular experiment comes from the improvement in this decision and depends on their prior and value for different outcomes. In a setting with multiple buyers, a buyer's expected value for an experiment may also depend on the information sold to others. We introduce the application of deep learning for the design of revenue-optimal data markets, looking to expand the frontiers of what can be understood and achieved. Relative to earlier work on deep learning for auction design, we must learn signaling schemes rather than allocation rules and handle obedience constraints - these arising from modeling the downstream actions of buyers - in addition to incentive constraints on bids. Our experiments demonstrate that this new deep learning framework can almost precisely replicate all known solutions from theory, expand to more complex settings, and be used to establish the optimality of new designs for data markets and make conjectures in regard to the structure of optimal designs.

NeurIPS Conference 2023 Conference Paper

Deep Contract Design via Discontinuous Networks

• Tonghan Wang
• Paul Duetting
• Dmitry Ivanov
• Inbal Talgam-Cohen
• David C. Parkes

Contract design involves a principal who establishes contractual agreements about payments for outcomes that arise from the actions of an agent. In this paper, we initiate the study of deep learning for the automated design of optimal contracts. We introduce a novel representation: the Discontinuous ReLU (DeLU) network, which models the principal's utility as a discontinuous piecewise affine function of the design of a contract where each piece corresponds to the agent taking a particular action. DeLU networks implicitly learn closed-form expressions for the incentive compatibility constraints of the agent and the utility maximization objective of the principal, and support parallel inference on each piece through linear programming or interior-point methods that solve for optimal contracts. We provide empirical results that demonstrate success in approximating the principal's utility function with a small number of training samples and scaling to find approximately optimal contracts on problems with a large number of actions and outcomes.

ICML Conference 2023 Conference Paper

Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learning

• Matthias Gerstgrasser
• David C. Parkes

Stackelberg equilibria arise naturally in a range of popular learning problems, such as in security games or indirect mechanism design, and have received increasing attention in the reinforcement learning literature. We present a general framework for implementing Stackelberg equilibria search as a multi-agent RL problem, allowing a wide range of algorithmic design choices. We discuss how previous approaches can be seen as specific instantiations of this framework. As a key insight, we note that the design space allows for approaches not previously seen in the literature, for instance by leveraging multitask and meta-RL techniques for follower convergence. We propose one such approach using contextual policies, and evaluate it experimentally on both standard and novel benchmark domains, showing greatly improved sample efficiency compared to previous approaches. Finally, we explore the effect of adopting algorithm designs outside the borders of our framework.

AAAI Conference 2023 Conference Paper

Predictive Multiplicity in Probabilistic Classification

• Jamelle Watson-Daniels
• David C. Parkes
• Berk Ustun

Machine learning models are often used to inform real world risk assessment tasks: predicting consumer default risk, predicting whether a person suffers from a serious illness, or predicting a person's risk to appear in court. Given multiple models that perform almost equally well for a prediction task, to what extent do predictions vary across these models? If predictions are relatively consistent for similar models, then the standard approach of choosing the model that optimizes a penalized loss suffices. But what if predictions vary significantly for similar models? In machine learning, this is referred to as predictive multiplicity i.e. the prevalence of conflicting predictions assigned by near-optimal competing models. In this paper, we present a framework for measuring predictive multiplicity in probabilistic classification (predicting the probability of a positive outcome). We introduce measures that capture the variation in risk estimates over the set of competing models, and develop optimization-based methods to compute these measures efficiently and reliably for convex empirical risk minimization problems. We demonstrate the incidence and prevalence of predictive multiplicity in real-world tasks. Further, we provide insight into how predictive multiplicity arises by analyzing the relationship between predictive multiplicity and data set characteristics (outliers, separability, and majority-minority structure). Our results emphasize the need to report predictive multiplicity more widely.

ICLR Conference 2022 Conference Paper

CrowdPlay: Crowdsourcing Human Demonstrations for Offline Learning

• Matthias Gerstgrasser
• Rakshit S. Trivedi
• David C. Parkes

Crowdsourcing has been instrumental for driving AI advances that rely on large-scale data. At the same time, reinforcement learning has seen rapid progress through benchmark environments that strike a balance between tractability and real-world complexity, such as ALE and OpenAI Gym. In this paper, we aim to fill a gap at the intersection of these two: The use of crowdsourcing to generate large-scale human demonstration data in the support of advancing research into imitation learning and offline learning. To this end, we present CrowdPlay, a complete crowdsourcing pipeline for any standard RL environment including OpenAI Gym (made available under an open-source license); a large-scale publicly available crowdsourced dataset of human gameplay demonstrations in Atari 2600 games, including multimodal behavior and human-human and human-AI multiagent data; offline learning benchmarks with extensive human data evaluation; and a detailed study of incentives, including real-time feedback to drive high quality data. We hope that this will drive the improvement in design of algorithms that account for the complexity of human, behavioral data and thereby enable a step forward in direction of effective learning for real-world settings. Our code and dataset are available at https://mgerstgrasser.github.io/crowdplay/.

NeurIPS Conference 2022 Conference Paper

Explainable Reinforcement Learning via Model Transforms

• Mira Finkelstein
• Nitsan levy
• Lucy Liu
• Yoav Kolumbus
• David C. Parkes
• Jeffrey S Rosenschein
• Sarah Keren

Understanding emerging behaviors of reinforcement learning (RL) agents may be difficult since such agents are often trained in complex environments using highly complex decision making procedures. This has given rise to a variety of approaches to explainability in RL that aim to reconcile discrepancies that may arise between the behavior of an agent and the behavior that is anticipated by an observer. Most recent approaches have relied either on domain knowledge, that may not always be available, on an analysis of the agent’s policy, or on an analysis of specific elements of the underlying environment, typically modeled as a Markov Decision Process (MDP). Our key claim is that even if the underlying model is not fully known (e. g. , the transition probabilities have not been accurately learned) or is not maintained by the agent (i. e. , when using model-free methods), the model can nevertheless be exploited to automatically generate explanations. For this purpose, we suggest using formal MDP abstractions and transforms, previously used in the literature for expediting the search for optimal policies, to automatically produce explanations. Since such transforms are typically based on a symbolic representation of the environment, they can provide meaningful explanations for gaps between the anticipated and actual agent behavior. We formally define the explainability problem, suggest a class of transforms that can be used for explaining emergent behaviors, and suggest methods that enable efficient search for an explanation. We demonstrate the approach on a set of standard benchmarks.

NeurIPS Conference 2022 Conference Paper

Learning to Mitigate AI Collusion on Economic Platforms

• Gianluca Brero
• Eric Mibuari
• Nicolas Lepore
• David C. Parkes

Algorithmic pricing on online e-commerce platforms raises the concern of tacit collusion, where reinforcement learning algorithms learn to set collusive prices in a decentralized manner and through nothing more than profit feedback. This raises the question as to whether collusive pricing can be prevented through the design of suitable "buy boxes, " i. e. , through the design of the rules that govern the elements of e-commerce sites that promote particular products and prices to consumers. In this paper, we demonstrate that reinforcement learning (RL) can also be used by platforms to learn buy box rules that are effective in preventing collusion by RL sellers. For this, we adopt the methodology of Stackelberg POMDPs, and demonstrate success in learning robust rules that continue to provide high consumer welfare together with sellers employing different behavior models or having out-of-distribution costs for goods.

AAAI Conference 2022 Short Paper

Reinforcement Learning Explainability via Model Transforms (Student Abstract)

• Mira Finkelstein
• Lucy Liu
• Yoav Kolumbus
• David C. Parkes
• Jeffrey S. Rosenshein
• Sarah Keren

Understanding the emerging behaviors of reinforcement learning agents may be difficult because such agents are often trained using highly complex and expressive models. In recent years, most approaches developed for explaining agent behaviors rely on domain knowledge or on an analysis of the agent’s learned policy. For some domains, relevant knowledge may not be available or may be insufficient for producing meaningful explanations. We suggest using formal model abstractions and transforms, previously used mainly for expediting the search for optimal policies, to automatically explain discrepancies that may arise between the behavior of an agent and the behavior that is anticipated by an observer. We formally define this problem of Reinforcement Learning Policy Explanation (RLPE), suggest a class of transforms which can be used for explaining emergent behaviors, and suggest methods for searching efficiently for an explanation. We demonstrate the approach on standard benchmarks.

ICML Conference 2021 Conference Paper

Learning Representations by Humans, for Humans

• Sophie Hilgard
• Nir Rosenfeld
• Mahzarin R. Banaji
• Jack Cao
• David C. Parkes

When machine predictors can achieve higher performance than the human decision-makers they support, improving the performance of human decision-makers is often conflated with improving machine accuracy. Here we propose a framework to directly support human decision-making, in which the role of machines is to reframe problems rather than to prescribe actions through prediction. Inspired by the success of representation learning in improving performance of machine predictors, our framework learns human-facing representations optimized for human performance. This “Mind Composed with Machine” framework incorporates a human decision-making model directly into the representation learning paradigm and is trained with a novel human-in-the-loop training procedure. We empirically demonstrate the successful application of the framework to various tasks and representational forms.

AAMAS Conference 2021 Conference Paper

Learning Robust Helpful Behaviors in Two-Player Cooperative Atari Environments

• Paul Tylkin
• Goran Radanovic
• David C. Parkes

We study the problem of learning helpful behavior, specifically, learning to cooperate with differently-skilled and diverse partners in the context of two-player, cooperative Atari games. We show robust performance of these so-called Helper-AIs when paired with different kinds of partners (both human and artificial agents), including partners that they have not previously encountered during training. In particular, while pairing an expert AI with a non-expert AI leads to performance that is worse than when pairing the nonexpert AI with a copy of itself, these Helper-AIs provide a substantial boost in joint performance.

NeurIPS Conference 2020 Conference Paper

From Predictions to Decisions: Using Lookahead Regularization

• Nir Rosenfeld
• Anna Hilgard
• Sai Srivatsa Ravindranath
• David C. Parkes

Machine learning is a powerful tool for predicting human-related outcomes, from creditworthiness to heart attack risks. But when deployed transparently, learned models also affect how users act in order to improve outcomes. The standard approach to learning predictive models is agnostic to induced user actions and provides no guarantees as to the effect of actions. We provide a framework for learning predictors that are accurate, while also considering interactions between the learned model and user decisions. For this, we introduce look-ahead regularization which, by anticipating user actions, encourages predictive models to also induce actions that improve outcomes. This regularization carefully tailors the uncertainty estimates that govern confidence in this improvement to the distribution of model-induced actions. We report the results of experiments on real and synthetic data that show the effectiveness of this approach.

AIJ Journal 2020 Journal Article

How do fairness definitions fare? Testing public attitudes towards three algorithmic definitions of fairness in loan allocations

• Nripsuta Ani Saxena
• Karen Huang
• Evan DeFilippis
• Goran Radanovic
• David C. Parkes
• Yang Liu

What is the best way to define algorithmic fairness? While many definitions of fairness have been proposed in the computer science literature, there is no clear agreement over a particular definition. In this work, we investigate ordinary people's perceptions of three of these fairness definitions. Across three online experiments, we test which definitions people perceive to be the fairest in the context of loan decisions, and whether fairness perceptions change with the addition of sensitive information (i. e. , race or gender of the loan applicants). Overall, one definition (calibrated fairness) tends to be more preferred than the others, and the results also provide support for the principle of affirmative action.

KR Conference 2020 Conference Paper

Reasoning About Plan Robustness Versus Plan Cost for Partially Informed Agents

• Sarah Keren
• Sara Bernardini
• Kofi Kwapong
• David C. Parkes

A common approach to planning with partial information is replanning: compute a plan based on assumptions about unknown information and replan if these assumptions are refuted during execution. To date, most planners with incomplete information have been designed to provide guarantees on completeness and soundness for the generated plans. Switching focus to performance, we measure the robustness of a plan, which quantifies the plan’s ability to avoid failure. Given a plan and an agent’s belief, which describes the set of states it deems as possible, robustness counts the number of world states in the belief from which the plan will achieve the goal without the need to replan. We formally describe the trade-off between robustness and plan cost and offer a solver that is guaranteed to produce plans that satisfy a required level of robustness. By evaluating our approach on a set of standard benchmarks, we demonstrate how it can improve the performance of a partially informed agent.

ICML Conference 2020 Conference Paper

The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation

• Zhe Feng 0004
• David C. Parkes
• Haifeng Xu

Motivated by economic applications such as recommender systems, we study the behavior of stochastic bandits algorithms under \emph{strategic behavior} conducted by rational actors, i. e. , the arms. Each arm is a \emph{self-interested} strategic player who can modify its own reward whenever pulled, subject to a cross-period budget constraint, in order to maximize its own expected number of times of being pulled. We analyze the robustness of three popular bandit algorithms: UCB, $\varepsilon$-Greedy, and Thompson Sampling. We prove that all three algorithms achieve a regret upper bound $\mathcal{O}(\max \{ B, K\ln T\})$ where $B$ is the total budget across arms, $K$ is the total number of arms and $T$ is the running time of the algorithms. This regret guarantee holds for \emph{arbitrary adaptive} manipulation strategy of arms. Our second set of main results shows that this regret bound is \emph{tight}— in fact, for UCB, it is tight even when we restrict the arms’ manipulation strategies to form a \emph{Nash equilibrium}. We do so by characterizing the Nash equilibrium of the game induced by arms’ strategic manipulations and show a regret lower bound of $\Omega(\max \{ B, K\ln T\})$ at the equilibrium.

AAAI Conference 2019 Conference Paper

Bayesian Fairness

• Christos Dimitrakakis
• Yang Liu
• David C. Parkes
• Goran Radanovic

We consider the problem of how decision making can be fair when the underlying probabilistic model of the world is not known with certainty. We argue that recent notions of fairness in machine learning need to explicitly incorporate parameter uncertainty, hence we introduce the notion of Bayesian fairness as a suitable candidate for fair decision rules. Using balance, a definition of fairness introduced in (Kleinberg, Mullainathan, and Raghavan 2016), we show how a Bayesian perspective can lead to well-performing and fair decision rules even under high uncertainty.

AAMAS Conference 2019 Conference Paper

Contingent Payment Mechanisms for Resource Utilization

• Hongyao Ma
• Reshef Meir
• David C. Parkes
• James Zou

We introduce the problem of assigning resources to improve their utilization, for settings where agents have uncertainty about their own values for using a resource, and where it is in the interest of the society or the planner that resources be used and not wasted. Done in the right way, improved utilization maximizes social welfare— balancing the utility of a high value but unreliable agent with the group’s preference that resources be used. We introduce the family of contingent payment mechanisms (CP), which may charge an agent contingent on use (a penalty). A CP mechanism is parameterized by a maximum penalty, and has a simple dominant-strategy equilibrium. Under a set of axiomatic properties, we establish welfareoptimality for the special case CP(W ), with CP instantiated for a maximum penalty equal to societal value W for utilization. The special case with no upper bound on penalty, the contingent secondprice mechanism, maximizes utilization. We extend the mechanisms to assign multiple, heterogeneous resources, and present a simulation study of the welfare properties of these mechanisms.

ICML Conference 2019 Conference Paper

Fairness without Harm: Decoupled Classifiers with Preference Guarantees

• Berk Ustun
• Yang Liu 0018
• David C. Parkes

In domains such as medicine, it can be acceptable for machine learning models to include sensitive attributes such as gender and ethnicity. In this work, we argue that when there is this kind of treatment disparity, then it should be in the best interest of each group. Drawing on ethical principles such as beneficence ("do the best") and non-maleficence ("do no harm"), we show how to use sensitive attributes to train decoupled classifiers that satisfy preference guarantees. These guarantees ensure the majority of individuals in each group prefer their assigned classifier to (i) a pooled model that ignores group membership (rationality), and (ii) the model assigned to any other group (envy-freeness). We introduce a recursive procedure that adaptively selects group attributes for decoupling, and present formal conditions to ensure preference guarantees in terms of generalization error. We validate the effectiveness of the procedure on real-world datasets, showing that it improves accuracy without violating preference guarantees on test data.

ICML Conference 2019 Conference Paper

Learning to Collaborate in Markov Decision Processes

• Goran Radanovic
• Rati Devidze
• David C. Parkes
• Adish Singla

We consider a two-agent MDP framework where agents repeatedly solve a task in a collaborative setting. We study the problem of designing a learning algorithm for the first agent (A1) that facilitates a successful collaboration even in cases when the second agent (A2) is adapting its policy in an unknown way. The key challenge in our setting is that the first agent faces non-stationarity in rewards and transitions because of the adaptive behavior of the second agent. We design novel online learning algorithms for agent A1 whose regret decays as $O(T^{1-\frac{3}{7} \cdot \alpha})$ with $T$ learning episodes provided that the magnitude of agent A2’s policy changes between any two consecutive episodes are upper bounded by $O(T^{-\alpha})$. Here, the parameter $\alpha$ is assumed to be strictly greater than $0$, and we show that this assumption is necessary provided that the learning parity with noise problem is computationally hard. We show that sub-linear regret of agent A1 further implies near-optimality of the agents’ joint return for MDPs that manifest the properties of a smooth game.

ICML Conference 2019 Conference Paper

Optimal Auctions through Deep Learning

• Paul Dütting
• Zhe Feng 0004
• Harikrishna Narasimhan
• David C. Parkes
• Sai Srivatsa Ravindranath

Designing an incentive compatible auction that maximizes expected revenue is an intricate task. The single-item case was resolved in a seminal piece of work by Myerson in 1981. Even after 30-40 years of intense research the problem remains unsolved for seemingly simple multi-bidder, multi-item settings. In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal auctions. We model an auction as a multi-layer neural network, frame optimal auction design as a constrained learning problem, and show how it can be solved using standard pipelines. We prove generalization bounds and present extensive experiments, recovering essentially all known analytical solutions for multi-item settings, and obtaining novel mechanisms for settings in which the optimal mechanism is unknown.

IJCAI Conference 2019 Conference Paper

Ridesharing with Driver Location Preferences

• Duncan Rheingans-Yoo
• Scott Duke Kominers
• Hongyao Ma
• David C. Parkes

We study revenue-optimal pricing and driver compensation in ridesharing platforms when drivers have heterogeneous preferences over locations. If a platform ignores drivers' location preferences, it may make inefficient trip dispatches; moreover, drivers may strategize so as to route towards their preferred locations. In a model with stationary and continuous demand and supply, we present a mechanism that incentivizes drivers to both (i) report their location preferences truthfully and (ii) always provide service. In settings with unconstrained driver supply or symmetric demand patterns, our mechanism achieves (full-information) first-best revenue. Under supply constraints and unbalanced demand, we show via simulation that our mechanism improves over existing mechanisms and has performance close to the first-best.

IJCAI Conference 2018 Conference Paper

Deep Learning for Multi-Facility Location Mechanism Design

• Noah Golowich
• Harikrishna Narasimhan
• David C. Parkes

Moulin [1980] characterizes the single-facility, deterministic strategy-proof mechanisms for social choice with single-peaked preferences as the set of generalized median rules. In contrast, we have only a limited understanding of multi-facility strategy-proof mechanisms, and recent work has shown negative worst case results for social cost. Our goal is to design strategy-proof, multi-facility mechanisms that minimize expected social cost. We first give a PAC learnability result for the class of multi-facility generalized median rules, and utilize neural networks to learn mechanisms from this class. Even in the absence of characterization results, we develop a computational procedure for learning almost strategy-proof mechanisms that are as good as or better than benchmarks from the literature, such as the best percentile and dictatorial rules.

AAMAS Conference 2018 Conference Paper

Deep Learning for Revenue-Optimal Auctions with Budgets

• Zhe Feng
• Harikrishna Narasimhan
• David C. Parkes

The design of revenue-maximizing auctions for settings with private budgets is a hard task. Even the single-item case is not fully understood, and there are no analytical results for optimal, dominantstrategy incentive compatible, two-item auctions. In this work, we model the rules of an auction as a neural network, and use machine learning for the automated design of optimal auctions. We extend the RegretNet framework (Dütting et al. ’17) to handle private budget constraints, as well as Bayesian incentive compatibility. We discover new auctions with high revenue for multi-unit auctions with private budgets, including problems with unit-demand bidders. For benchmarking purposes, we also demonstrate that RegretNet can obtain essentially optimal designs for simpler settings where analytical solutions are available [12, 24, 29].

AAMAS Conference 2017 Conference Paper

Fair Division via Social Comparison

• Rediet Abebe
• Jon Kleinberg
• David C. Parkes

We study cake cutting on a graph, where agents can only evaluate their shares relative to their neighbors. This is an extension of the classical problem of fair division to incorporate the notion of social comparison from the social sciences. We say an allocation is locally envy-free if no agent envies a neighbor’s allocation, and locally proportional if each agent values its own allocation as much as the average value of its neighbors’ allocations. We generalize the classical “Cut and Choose” protocol for two agents to this setting, by fully characterizing the set of graphs for which an oblivious single-cutter protocol can give locally envy-free (thus also locally-proportional) allocations. We study the price of envy-freeness, which compares the total value of an optimal allocation with that of an optimal, locally envy-free allocation. Surprisingly, a lower bound of Ω( √ n) on the price of envy-freeness for global allocations also holds for local envy-freeness in any connected graph, so sparse graphs do not provide more flexibility asymptotically with respect to the quality of envy-free allocations.

AAMAS Conference 2017 Conference Paper

Generalizing Demand Response Through Reward Bidding

• Hongyao Ma
• David C. Parkes
• Valentin Robu

Demand-side response (DR) is emerging as a crucial technology to assure stability of modern power grids. The uncertainty about the cost agents face for reducing consumption imposes challenges in achieving reliable, coordinated response. In recent work, Ma et al. [13] introduce DR as a mechanism design problem and solve it for a setting where an agent has a binary preparation decision and where, contingent on preparation, the probability an agent will be able to reduce demand and the cost to do so are fixed. We generalize this model to allow uncertainty in agents’ costs of responding, and also multiple levels of effort agents can exert in preparing. For both cases, the design of contingent payments now affects the probability of response. We design a new, truthful and reliable mechanism that uses a “rewardbidding”approach rather than the“penalty-bidding”approach. It has good performance when compared to natural benchmarks. The mechanism also extends to handle multiple units of demand response from each agent.

AAMAS Conference 2017 Conference Paper

On AI, Markets and Machine Learning

• David C. Parkes

What is fun about artificial intelligence (AI) is that it is fundamentally constructive! Rather than theorizing about the behavior of an existing, say social system, or understanding the way in which decisions are currently being made, one gets to ask a profound question: how should a system for making intelligent decisions be designed? In multi-agent systems we’re often interested, in particular, in what happens when multiple participants, each with autonomy, selfinterest and potentially misaligned incentives come together. These systems involve people (frequently people and firms), as well as the use of AI to automate some parts of decision making. How should such a system be designed? In adopting this normative viewpoint, we follow a successful branch of economic theory that includes mechanism design, social choice and matching. But in pursuit of success, we must grapple with problems that are more complex than has been typical in economic theory, and solve these problems at scale. We want to attack difficult problems by using the methods of AI together with the methods of economic theory. In this talk, I will highlight the following themes from my own research, themes that emerge as one lifts nice ideas from economic theory and brings them to bear on the kinds of problems that are at the heart of modern AI research: 1. Preferences need to be elicited, and cannot be assumed to be known or easily represented. 2. Mechanisms don’t need to be centralized. Rather, we can use (incentive aligned) distributed optimization! 3. Many interesting problems are temporal and involve uncertainty, leading to rich challenges that have been largely untouched by economic theory. 4. Markets become algorithms, and market-based optimization is a powerful and increasingly real paradigm. 5. Scale becomes an opportunity, as large systems beget data, this data enabling new approaches to robust incentive alignment. 6. Computation becomes a tool— machine learning has taken automated mechanism design up to the frontier of knowledge from 35 years of auction theory. Appears in: Proc. of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), S. Das, E. Durfee, K. Larson, M. Winikoff (eds.), May 8–12, 2017, São Paulo, Brazil. Copyright c 2017, International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved. The future will bring a tighter and ever more compelling integration of AI with markets. The human and societal interface will remain, and become ever more important as there is more that can be automated. The anticipated“agentmediated economy”is almost upon us, and holds much promise as long as we make sure that AIs represent our preferences and system designs capture our values as society. CCS Concepts •Information systems → Electronic commerce; •Theory of computation → Algorithmic mechanism design; Computational pricing and auctions; •Computing methodologies → Multi-agent systems; Supervised learning;

AAMAS Conference 2017 Conference Paper

Thwarting Vote Buying Through Decoy Ballots

• David C. Parkes
• Paul Tylkin
• Lirong Xia

IJCAI Conference 2017 Conference Paper

Thwarting Vote Buying Through Decoy Ballots

• David C. Parkes
• Paul Tylkin
• Lirong Xia

There is increasing interest in promoting participatory democracy, in particular by allowing voting by mail or internet and through random-sample elections. A pernicious concern, though, is that of vote buying, which occurs when a bad actor seeks to buy ballots, paying someone to vote against their own intent. This becomes possible whenever a voter is able to sell evidence of which way she voted. We show how to thwart vote buying through decoy ballots, which are not counted but are indistinguishable from real ballots to a buyer. We show that an Election Authority can significantly reduce the power of vote buying through a small number of optimally distributed decoys, and model societal processes by which decoys could be distributed.

UAI Conference 2016 Conference Paper

A General Statistical Framework for Designing Strategy-proof Assignment Mechanisms

• Harikrishna Narasimhan
• David C. Parkes

We develop a statistical framework for the design of a strategy-proof assignment mechanism that closely approximates a target outcome rule. The framework can handle settings with and without money, and allows the designer to employ techniques from machine learning to control the space of strategy-proof mechanisms searched over, by providing a rule class with appropriate capacity. We solve a sample-based optimization problem over a space of mechanisms that correspond to agent-independent price functions (virtual prices in the case of settings without money), subject to a feasibility constraint on the sample. A transformation is applied to the obtained mechanism to ensure feasibility on all type profiles, and strategy-proofness. We derive a sample complexity bound for our approach in terms of the capacity of the chosen rule class and provide applications for our results.

IJCAI Conference 2016 Conference Paper

Automated Mechanism Design without Money via Machine Learning

• Harikrishna Narasimhan
• Shivani Agarwal
• David C. Parkes

We use statistical machine learning to develop methods for automatically designing mechanisms in domains without money. Our goal is to find a mechanism that best approximates a given target function subject to a design constraint such as strategy-proofness or stability. The proposed approach involves identifying a rich parametrized class of mechanisms that resemble discriminant-based multiclass classifiers, and relaxing the resulting search problem into an SVM-style surrogate optimization problem. We use this methodology to design strategy-proof mechanisms for social choice problems with single-peaked preferences, and stable mechanisms for two-sided matching problems. To the best of our knowledge, ours is the first automated approach for designing stable matching rules. Experiments on synthetic and real-world data confirm the usefulness of our methods.

IJCAI Conference 2016 Conference Paper

Correlated Voting

• Debmalya Mandal
• David C. Parkes

We study the social choice problem where a group of n voters report their preferences over alternatives and a voting rule is used to select an alternative. We show that when the preferences of voters are positively correlated according to the Kendall-Tau distance, the probability that any scoring rule is not ex post incentive compatible (EPIC) goes to zero exponentially fast with the number of voters, improving over the previously known rate of 1/√ n for independent preferences. Motivated by rank-order models from machine learning, we introduce two examples of positively-correlated models, namely Conditional Mallows and Conditional Plackett-Luce. Conditional Mallows satisfies Kendall-Tau correlation and fits our positive result. We also prove that Conditional Plackett-Luce becomes EPIC exponentially quickly.

IJCAI Conference 2016 Conference Paper

Incentivizing Reliability in Demand-Side Response

• Hongyao Ma
• Valentin Robu
• Na Li
• David C. Parkes

We study the problem of incentivizing reliable demand-response in modern electricity grids. Each agent is uncertain about her future ability to reduce demand and unreliable. Agents who choose to participate in a demand-response scheme may be paid when they respond and penalized otherwise. The goal is to reliably achieve a demand reduction target while selecting a minimal set of agents from those willing to participate. We design incentive-aligned, direct and indirect mechanisms. The direct mechanism elicits both response probabilities and costs, while the indirect mechanism elicits willingness to accept a penalty in the case of non-response. We benchmark against a spot auction, in which demand reduction is purchased from agents when needed. Both the direct and indirect mechanisms achieve the reliability target in a dominant-strategy equilibrium, select a small number of agents to prepare, and do so at low cost and with much lower variance in payments than the spot auction.

IJCAI Conference 2016 Conference Paper

Measuring Performance of Peer Prediction Mechanisms Using Replicator Dynamics

• Victor Shnayder
• Rafael M. Frongillo
• David C. Parkes

Peer prediction is the problem of eliciting private, but correlated, information from agents. By rewarding an agent for the amount that their report "predicts" that of another agent, mechanisms can promote effort and truthful reports. A common concern in peer prediction is the multiplicity of equilibria, perhaps including high-payoff equilibria that reveal no information. Rather than assume agents counter-speculate and compute an equilibrium, we adopt replicator dynamics as a model for population learning. We take the size of the basin of attraction of the truthful equilibrium as a proxy for the robustness of truthful play. We study different mechanism designs, using models estimated from real peer evaluations in several massive on-line courses. Among other observations, we confirm that recent mechanisms present a significant improvement in robustness over earlier approaches.

AAMAS Conference 2016 Conference Paper

Personalized Hitting Time for Informative Trust Mechanisms Despite Sybils

• Brandon K. Liu
• David C. Parkes
• Sven Seuken

Informative and scalable trust mechanisms that are robust to manipulation by strategic agents are a critical component of multi-agent systems. While the global hitting time mechanism (GHT) introduced by Hopcroft and Sheldon [9] is more robust to manipulation than PageRank, strategic agents can still benefit significantly under GHT by performing sybil attacks. In this paper, we introduce the personalized hitting time mechanism (PHT), which we show to be significantly more robust to sybil attacks than GHT. Specifically, if an agent has already cut all of its outlinks under PHT (which only leads to a negligible benefit), then adding sybils leads to no additional benefit. We provide an experimental analysis which demonstrates that, in the presence of strategic agents that create sybils, PHT dominates GHT (as well as PageRank and personalized PageRank) in terms of informativeness. We find the large dominance of PHT over GHT particularly surprising given the small difference between the two mechanisms. Finally, we provide a Monte Carlo algorithm to compute approximate PHT scores at scale, and we show that PHT retains its robustness to manipulation when used with approximate scores. CCS Concepts •Applied computing → Economics; •Information systems → Reputation systems;

IJCAI Conference 2016 Conference Paper

Social Choice for Agents with General Utilities

• Hongyao Ma
• Reshef Meir
• David C. Parkes

The existence of truthful social choice mechanisms strongly depends on whether monetary transfers are allowed. Without payments there are no truthful, non-dictatorial mechanisms under mild requirements, whereas the VCG mechanism guarantees truthfulness along with welfare maximization when there are payments and utility is quasi-linear in money. In this paper we study mechanisms in which we can use payments but where agents have non quasi-linear utility functions. Our main result extends the Gibbard-Satterthwaite impossibility result by showing that, for two agents, the only truthful mechanism for at least three alternatives under general decreasing utilities remains dictatorial. We then show how to extend the VCG mechanism to work under a more general utility space than quasi-linear (the "parallel domain) and show that the parallel domain is maximal-no mechanism with the VCG properties exists in any larger domain.

RLDM Conference 2015 Conference Abstract

Mechanism design as a toolbox for alignment of reward

• David C. Parkes

The economic theory of mechanism design seeks to align incentives to promote optimal decision making in a setting with multiple, rational self-interested agents. The framing of my talk will be to ask whether mechanism design may be applicable to the design of reward architectures for artificial, single-agent or multi-agent systems. In mechanism design, each agent has private information about its preferences on different decisions, and there is a social choice function, capturing the optimal (system-wide) decision. A classical problem in mechanism design is that of resource allocation. A mechanism prescribes a way to make a decision as well as payments that can be viewed as modifying agents’ extrinsic rewards. In this sense, mechanism design may play a role in the design of intrinsic reward functions. I will outline the three main approaches in the mechanism designer’s toolbox: monotonicity, the taxation principle, and Groves mechanisms. I will mention optimal mechanism design, mechanism design for dynamic problems and the idea of indirect mechanisms where actions are decentralized to agents. Tuesday, June 9, 2015

ICML Conference 2014 Conference Paper

Computing Parametric Ranking Models via Rank-Breaking

• Hossein Azari Soufiani
• David C. Parkes
• Lirong Xia

Rank breaking is a methodology introduced by Azari Soufiani et al. (2013a) for applying a Generalized Method of Moments (GMM) algorithm to the estimation of parametric ranking models. Breaking takes full rankings and breaks, or splits them up, into counts for pairs of alternatives that occur in particular positions (e. g. , first place and second place, second place and third place). GMMs are of interest because they can achieve significant speed-up relative to maximum likelihood approaches and comparable statistical efficiency. We characterize the breakings for which the estimator is consistent for random utility models (RUMs) including Plackett-Luce and Normal-RUM, develop a general sufficient condition for a full breaking to be the only consistent breaking, and provide a trichotomy theorem in regard to single-edge breakings. Experimental results are presented to show the computational efficiency along with statistical performance of the proposed method.

AIJ Journal 2013 Journal Article

Computing cooperative solution concepts in coalitional skill games

• Yoram Bachrach
• David C. Parkes
• Jeffrey S. Rosenschein

We consider a simple model of cooperation among agents called Coalitional Skill Games (CSGs). This is a restricted form of coalitional games, where each agent has a set of skills that are required to complete various tasks. Each task requires a set of skills in order to be completed, and a coalition can accomplish the task only if the coalitionʼs agents cover the set of required skills for the task. The gain for a coalition depends only on the subset of tasks it can complete. We consider the computational complexity of several problems in CSGs, such as testing if an agent is a dummy or veto agent, computing the core and core-related solution concepts, and computing power indices such as the Shapley value and Banzhaf power index.

IJCAI Conference 2013 Conference Paper

Efficient Interdependent Value Combinatorial Auctions with Single Minded Bidders

• Valentin Robu
• David C. Parkes
• Takayuki Ito
• Nicholas R. Jennings

We study the problem of designing efficient auctions where bidders have interdependent values; i. e. , values that depend on the signals of other agents. We consider a contingent bid model in which agents can explicitly condition the value of their bids on the bids submitted by others. In particular, we adopt a linear contingent bidding model for single minded combinatorial auctions (CAs), in which submitted bids are linear combinations of bids received from others. We extend the existing state of the art, by identifying constraints on the interesting bundles and contingency weights reported by the agents which allow the efficient second priced, fixed point bids auction to be implemented in single minded CAs. Moreover, for domains in which the required single crossing condition fails (which characterizes when efficient, IC auctions are possible), we design a two-stage mechanism in which a subset of agents (“experts”) are allocated first, using their reports to allocate the remaining items to the other agents.

UAI Conference 2013 Conference Paper

Preference Elicitation For General Random Utility Models

• Hossein Azari Soufiani
• David C. Parkes
• Lirong Xia

This paper discusses General Random Utility Models (GRUMs). These are a class of parametric models that generate partial ranks over alternatives given attributes of agents and alternatives. We propose two preference elicitation scheme for GRUMs developed from principles in Bayesian experimental design, one for social choice and the other for personalized choice. We couple this with a general Monte-Carlo- Expectation-Maximization (MC-EM) based algorithm for MAP inference under GRUMs. We also prove uni-modality of the likelihood functions for a class of GRUMs. We examine the performance of various criteria by experimental studies, which show that the proposed elicitation scheme increases the precision of estimation.

AAMAS Conference 2011 Conference Paper

Incentive Design for Adaptive Agents

• Yiling Chen
• Jerry Kung
• David C. Parkes
• Ariel D. Procaccia
• Haoqi Zhang

We consider a setting in which a principal seeks to induce an adaptive agent to select a target action by providing incentives on one or more actions. The agent maintains a belief about the value for each action-which may update based on experience-and selects at each time step the action with the maximal sum of value and associated incentive. The principal observes the agent's selection, but has no information about the agent's current beliefs or belief update process. For inducing the target action as soon as possible, or as often as possible over a fixed time period, it is optimal for a principal with a per-period budget to assign the budget to the target action and wait for the agent to want to make that choice. But with an across-period budget, no algorithm can provide good performance on all instances without knowledge of the agent's update process, except in the particular case in which the goal is to induce the agent to select the target action once. We demonstrate ways to overcome this strong negative result with knowledge about the agent's beliefs, by providing a tractable algorithm for solving the offline problem when the principal has perfect knowledge, and an analytical solution for an instance of the problem in which partial knowledge is available.

AAMAS Conference 2011 Conference Paper

Online Mechanism Design for Electric Vehicle Charging

• Enrico H. Gerding
• Valentin Robu
• Sebastian Stein
• David C. Parkes
• Alex Rogers
• Nicholas R. Jennings

Plug-in hybrid electric vehicles are expected to place a considerable strain on local electricity distribution networks, requiring charging to be coordinated in order to accommodate capacity constraints. We design a novel online auction protocol for this problem, wherein vehicle owners use agents to bid for power and also state time windows in which a vehicle is available for charging. This is a multi-dimensional mechanism design domain, with owners having non-increasing marginal valuations for each subsequent unit of electricity. In our design, we couple a greedy allocation algorithm with the occasional "burning" of allocated power, leaving it unallocated, in order to adjust an allocation and achieve monotonicity and thus truthfulness. We consider two variations: burning at each time step or on-departure. Both mechanisms are evaluated in depth, using data from a real-world trial of electric vehicles in the UK to simulate system dynamics and valuations. The mechanisms provide higher allocative efficiency than a fixed price system, are almost competitive with a standard scheduling heuristic which assumes non-strategic agents, and can sustain a substantially larger number of vehicles at the same per-owner fuel cost saving than a simple random scheme.

ECAI Conference 2010 Conference Paper

Dynamic Matching with a Fall-back Option

• Sujit Gujar
• David C. Parkes

We study dynamic matching without money when one side of the market is dynamic with arrivals and departures and the other is static and agents have strict preferences over agents on the other side of the market. In enabling stability properties, so that no pair of agents can usefully deviate from the match, we consider the use of a fall-back option where the dynamic agents can be matched, if needed, with a limited number of agents from a separate “reserve” pool. We introduce the GSODAS mechanism, which is truthful for agents on the static side of the market and stable. In simulations, we establish that GSODAS dominates in rank-efficiency a pair of randomized mechanisms that operate without the use of a fall-back option. In addition, we demonstrate good rank-efficiency in comparison to a non-truthful mechanism that employs online stochastic optimization.

IJCAI Conference 2009 Conference Paper

• Benjamin Lubin
• Jeffrey O. Kephart
• Rajarshi Das
• David C. Parkes

As data-center energy consumption continues to rise, efficient power management is becoming increasingly important. In this work, we examine the use of a novel market mechanism for finding the right balance between power and performance. The market enables a separation between a ‘buyer side’ that strives to maximize performance and a ‘seller side’ that strives to minimize power and other costs. A concise and scalable description language is de- fined for agent preferences that admits a mixedinteger program for computing optimal allocations. Experimental results demonstrate the robustness, flexibility, practicality and scalability of the architecture.

AIJ Journal 2009 Journal Article

An options-based solution to the sequential auction problem

• Adam I. Juda
• David C. Parkes

The sequential auction problem is commonplace in open, electronic marketplaces such as eBay. This is the problem where a buyer has no dominant strategy in bidding across multiple auctions when the buyer would have a simple, truth-revealing strategy if there was but a single auction event. Our model allows for multiple, distinct goods and market dynamics with buyers and sellers that arrive over time. Sellers each bring a single unit of a good to the market while buyers can have values on bundles of goods. We model each individual auction as a second-price (Vickrey) auction and propose an options-based, proxied solution to provide price and winner-determination coordination across auctions. While still allowing for temporally uncoordinated market participation, this options-based approach solves the sequential auction problem and provides truthful bidding as a weakly dominant strategy for buyers. An empirical study suggests that this coordination can enable a significant efficiency and revenue improvement over the current eBay market design, and highlights the effect on performance of complex buyer valuations (buyers with substitutes and complements valuations) and varying the market liquidity.

UAI Conference 2009 Conference Paper

Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions

• Benjamin Lubin
• David C. Parkes

Strategyproof mechanisms provide robust equilibrium with minimal assumptions about knowledge and rationality but can be unachievable in combination with other desirable properties such as budget-balance, stability against deviations by coalitions, and computational tractability. In the search for maximally-strategyproof mechanisms that simultaneously satisfy other desirable properties, we introduce a new metric to quantify the strategyproofness of a mechanism, based on comparing the payoff distribution, given truthful reports, against that of a strategyproof “reference” mechanism that solves a problem relaxation. Focusing on combinatorial exchanges, we demonstrate that the metric is informative about the eventual equilibrium, where simple regretbased metrics are not, and can be used for online selection of an effective mechanism.

JAAMAS Journal 2009 Journal Article

Specifying and monitoring economic environments using rights and obligations

• Loizos Michael
• David C. Parkes
• Avi Pfeffer

Abstract We provide a formal scripting language to capture the semantics of economic environments. The language is based on a set of well-defined design principles and makes explicit an agent’s rights, as derived from property, and an agent’s obligations, as derived from restrictions placed on its actions either voluntarily or as a consequence of other actions. Coupled with the language is a run-time system that is able to monitor and enforce rights and obligations in an agent-mediated economic environment. The framework allows an agent to formally express guarantees (obligations) in relation to its actions, and the run-time system automatically checks that these obligations are met and verifies that an agent has appropriate rights before executing an action. Rights and obligations are viewed as first-class goods that can be transferred from one agent to another. This treatment makes it easy to define natural and expressive recursive statements, so that, for instance, one may have rights or obligations in selling or trading some other right or obligation. We define fundamental axioms about well-functioning markets in terms of rights and obligations, and delineate the difference between ownership and possession, arguably two of the most important notions in economic markets. The framework provides a rich set of action-related constructs for modeling conditional and non-deterministic effects, and introduces the use of transactions to safely bundle actions, including the issuing of rights and taking on of obligations. By way of example, we show that our language can represent a variety of economic mechanisms, ranging from simple two-agent single-good exchanges to complicated combinatorial auctions. The framework, which is fully implemented, can be used to formalize the semantics of markets; as a platform for prototyping, testing and evaluating agent-mediated markets; and also provide a basis for deploying an electronic market.

UAI Conference 2008 Conference Paper

Learning and Solving Many-Player Games through a Cluster-Based Representation

• Sevan G. Ficici
• David C. Parkes
• Avi Pfeffer

In addressing the challenge of exponential scaling with the number of agents we adopt a cluster-based representation to approximately solve asymmetric games of very many players. A cluster groups together agents with a similar “strategic view” of the game. We learn the clustered approximation from data consisting of strategy profiles and payoffs, which may be obtained from observations of play or access to a simulator. Using our clustering we construct a reduced “twins” game in which each cluster is associated with two players of the reduced game. This allows our representation to be individuallyresponsive because we align the interests of every individual agent with the strategy of its cluster. Our approach provides agents with higher payoffs and lower regret on average than model-free methods as well as previous cluster-based methods, and requires only few observations for learning to be successful. The “twins” approach is shown to be an important component of providing these low regret approximations.

AAAI Conference 2007 Conference Paper

An Ironing-Based Approach to Adaptive Online Mechanism Design in Single-Valued Domains

• David C. Parkes

Online mechanism design considers the problem of sequential decision making in a multi-agent system with selfinterested agents. The agent population is dynamic and each agent has private information about its value for a sequence of decisions. We introduce a method (“ironing") to transform an algorithm for online stochastic optimization into one that is incentive-compatible. Ironing achieves this by canceling decisions that violate a form of monotonicity. The approach is applied to the CONSENSUS algorithm and experimental results in a resource allocation domain show that not many decisions need to be canceled and that the overhead of ironing is manageable.

AAMAS Conference 2007 Conference Paper

Online Auctions for Bidders with Interdependent Values

• Florin Constantin
• Takayuki Ito
• David C. Parkes

Interdependent values (IDV) is a valuation model allowing bidders in an auction to express their value for the item(s) to sell as a function of the other bidders' information. We investigate the incentive compatibility (IC) of single-item auctions for IDV bidders in dynamic environments. We provide a necessary and sufficient characterization for IC in this setting. We show that if bidders can misreport departure times and private signals, no reasonable auction can be IC. We present a reasonable IC auction for the case where bidders cannot misreport departures.

UAI Conference 2006 Conference Paper

Optimal Coordinated Planning Amongst Self-Interested Agents with Private State

• Ruggiero Cavallo
• David C. Parkes
• Satinder Singh 0001

Consider a multi-agent system in a dynamic and uncertain environment. Each agent's local decision problem is modeled as a Markov decision process (MDP) and agents must coordinate on a joint action in each period, which provides a reward to each agent and causes local state transitions. A social planner knows the model of every agent's MDP and wants to implement the optimal joint policy, but agents are self-interested and have private local state. We provide an incentive-compatible mechanism for eliciting state information that achieves the optimal joint plan in a Markov perfect equilibrium of the induced stochastic game. In the special case in which local problems are Markov chains and agents compete to take a single action in each period, we leverage Gittins allocation indices to provide an efficient factored algorithm and distribute computation of the optimal policy among the agents. Distributed, optimal coordinated learning in a multi-agent variant of the multi-armed bandit problem is obtained as a special case.

UAI Conference 2005 Conference Paper

Models for Truthful Online Double Auctions

• Jonathan Bredin
• David C. Parkes

Online double auctions (DAs) model a dynamic two-sided matching problem with private information and self-interest, and are relevant for dynamic resource and task allocation problems. We present a general method to design truthful DAs, such that no agent can benefit from misreporting its arrival time, duration, or value. The family of DAs is parameterized by a pricing rule, and includes a generalization of McAfee's truthful DA to this dynamic setting. We present an empirical study, in which we study the allocative-surplus and agent surplus for a number of different DAs. Our results illustrate that dynamic pricing rules are important to provide good market efficiency for markets with high volatility or low volume.

AAAI Conference 2004 Conference Paper

GROWRANGE: Anytime VCG-Based Mechanisms

• David C. Parkes
• Grant Schoenebeck

We introduce anytime mechanisms for distributed optimization with self-interested agents. Anytime mechanisms retain good incentive properties even when interrupted before the optimal solution is computed, and provide better quality solutions when given additional time. Anytime mechanisms can solve easy instances of a hard problem quickly and optimally, while providing approximate solutions on very hard instances. In a particular instantiation, GROWRANGE, we successively expand the range of outcomes considered, computing the optimal solution for each range. Truth-revelation remains a dominant strategy equilibrium with a stage-based interruption, and is a best-response with high probability when the interruption is time-based.