skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Incentive Design in a Distributed Problem with Strategic Agents
In this paper, we consider a general distributed system with multiple agents who select and then implement actions in the system. The system has an operator with a centralized objective. The agents, on the other hand, are selfinterested and strategic in the sense that each agent optimizes its own individual objective. The operator aims to mitigate this misalignment by designing an incentive scheme for the agents. The problem is difficult due to the cost functions of the agents being coupled, the objective of the operator not being social welfare, and the operator having no direct control over actions being implemented by the agents. This problem has been studied in many fields, particularly in mechanism design and cost allocation. However, mechanism design typically assumes that the operator has knowledge of the cost functions of the agents and the actions being implemented by the operator. On the other hand, cost allocation classically assumes that agents do not anticipate the effect of their actions on the incentive that they obtain. We remove these assumptions and present an incentive rule for this setup by bridging the gap between mechanism design and classical cost allocation. We analyze whether the proposed design satisfies various desirable properties such as social optimality, budget balance, participation constraint, and so on. We also analyze which of these properties can be satisfied if the assumptions of cost functions of the agents being private and the agents being anticipatory are relaxed.  more » « less
Award ID(s):
1739295
PAR ID:
10076435
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
American Control Conference 2018
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Lecture notes in computer science)
    Deligkas, Argyrios; Filos-Ratsikas, Aris (Ed.)
    We study a dynamic model of procurement auctions in which the agents (sellers) will abandon the auction if their utility does not satisfy their private target, in any given round. We call this “abandonment” and analyze its consequences on the overall cost to the mechanism designer (buyer), as it reduces competition in future rounds of the auction and drives up the price. We show that in order to maintain competition and minimize the overall cost, the mechanism designer has to adopt an inefficient (per-round) allocation, namely to assign the demand to multiple agents in a single round. We focus on threshold mechanisms as a simple way to achieve ex-post incentive compatibility, akin to reserves in revenue-maximizing forward auctions. We then consider the optimization problem of finding the optimal thresholds. We show that even though our objective function does not have the optimal substructure property in general, if the underlying distributions satisfy some regularity properties, the global optimal solution lies within a region where the optimal thresholds are monotone and can be calculated with a greedy approach, or even more simply in a parallel fashion. 
    more » « less
  2. ; ; ; ; (, ACM Conference on Economics and Computation (EC))
    We study the design of a class of incentive mechanisms that can effectively prevent cheating in a strategic classification and regression problem. A conventional strategic classification or regression problem is modeled as a Stackelberg game, or a principal-agent problem between the designer of a classifier (the principal) and individuals subject to the classifier's decisions (the agents), potentially from different demographic groups. The former benefits from the accuracy of its decisions, whereas the latter may have an incentive to game the algorithm into making favorable but erroneous decisions. While prior works tend to focus on how to design an algorithm to be more robust to such strategic maneuvering, this study focuses on an alternative, which is to design incentive mechanisms to shape the utilities of the agents and induce effort that genuinely improves their skills, which in turn benefits both parties in the Stackelberg game. Specifically, the principal and the mechanism provider (which could also be the principal itself) move together in the first stage, publishing and committing to a classifier and an incentive mechanism. The agents are (simultaneous) second movers and best respond to the published classifier and incentive mechanism. When an agent's strategic action merely changes its observable features, it hurts the performance of the algorithm. However, if the action leads to improvement in the agent's true label, it not only helps the agent achieve better decision outcomes, but also preserves the performance of the algorithm. We study how a subsidy mechanism can induce improvement actions, positively impact a number of social well-being metrics, such as the overall skill levels of the agents (efficiency) and positive or true positive rate differences between different demographic groups (fairness). 
    more » « less
  3. ; ; (, Operations Research)
    A central goal in the long literature on fair division is the design of mechanisms that implement fair outcomes, despite the participants’ strategic behavior. We study this question by measuring the fairness of an allocation using the geometric mean of the agents’ values, known as the Nash social welfare (NSW). This objective is maximized by widely known concepts such as the Nash bargaining solution, proportional fairness, and the competitive equilibrium with equal incomes; we focus on (approximately) implementing this objective and analyze the Trading Post mechanism. We consider allocating goods that are substitutes or complements and show that this mechanism achieves an approximation of two for concave utility functions and becomes essentially optimal for complements, where it can reach [Formula: see text] for any [Formula: see text]. Moreover, we show that the Nash equilibria of this mechanism are pure and provide individual fairness in the sense of proportionality. 
    more » « less
  4. ; ; ; (, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence)
    Incentives are explored in the sharing economy to inspire users for better resource allocation. Previous works build a budget-feasible incentive mechanism to learn users' cost distribution. However, they only consider a special case that all tasks are considered as the same. The general problem asks for finding a solution when the cost for different tasks varies. In this paper, we investigate this general problem by considering a system with k levels of difficulty. We present two incentivizing strategies for offline and online implementation, and formally derive the ratio of utility between them in different scenarios. We propose a regret-minimizing mechanism to decide incentives by dynamically adjusting budget assignment and learning from users' cost distributions. Our experiment demonstrates utility improvement about 7 times and time saving of 54% to meet a utility objective compared to the previous works. 
    more » « less
  5. (, IEEE Conference on Decision and Control (CDC) Miami Beach, FL, USA, Dec. 17-19, 2018.)
    The classic Vickrey-Clarke-Groves (VCG) mech-anism ensures incentive compatibility, i.e., that truth-telling of all agents is a dominant strategy, for a static one-shot game. However, in a dynamic environment that unfolds over time, the agents’ intertemporal payoffs depend on the expected future controls and payments, and a direct extension of the VCG mechanism is not sufficient to guarantee incentive compati-bility. In fact, it does not appear to be feasible to construct mechanisms that ensure the dominance of dynamic truth-telling for agents comprised of general stochastic dynamic systems. The contribution of this paper is to show that such a dynamic stochastic extension does exist for the special case of Linear-Quadratic-Gaussian (LQG) agents with a careful construction of a sequence of layered payments over time. We propose a layered version of a modified VCG mechanism for payments that decouples the intertemporal effect of current bids on future payoffs, and prove that truth-telling of dynamic states forms a dominant strategy if system parameters are known and agents are rational. An important example of a problem needing such optimal dynamic coordination of stochastic agents arises in power systems where an Independent System Operator (ISO) has to ensure balance of generation and consumption at all time instants, while ensuring social optimality (maximization of the sum of the utilities of all agents). Addressing strategic behavior is critical as the price-taking assumption on market participants may not hold in an electricity market. Agents, can lie or otherwise game the bidding system. The challenge is to determine a bidding scheme between all agents and the ISO that maximizes social welfare, while taking into account the stochastic dynamic models of agents, since renewable energy resources such as solar/wind are stochastic and dynamic in nature, as are consumptions by loads which are influenced by factors such as local temperatures and thermal inertias of facilities. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email