 Award ID(s):
 1739295
 NSFPAR ID:
 10076435
 Date Published:
 Journal Name:
 American Control Conference 2018
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Deligkas, Argyrios ; FilosRatsikas, 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 (perround) allocation, namely to assign the demand to multiple agents in a single round. We focus on threshold mechanisms as a simple way to achieve expost incentive compatibility, akin to reserves in revenuemaximizing 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

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 principalagent 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 wellbeing 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

Abstract In this paper, we investigate the dichotomy between system design delegation driven by requirement allocation and delegation driven by objective allocation. Specifically, we investigate this dichotomy through the lens of agency theory, which addresses cases where an agent makes decisions on behalf of another, that is, a principal. In current practice, design delegation largely involves requirement allocation as a means to inform agents of the desirable system characteristics. The value‐driven design paradigm proposes replacing requirements with objective, or trade‐off, functions to better guide agents toward optimal systems. We apply and adapt the principal–agent mathematical model to the design delegation problem to determine if a principal, that is, the delegator, should communicate using requirements or objectives with her agent. In this model, we assume the case of a single principal and single agent where the agent has certain domain knowledge the principal does not have and the agent accrues costs while solving a delegated design problem. Under the assumptions of the mathematical model, we show that the requirement allocation paradigm can yield greater value to the principal over objective despite limitations requirement allocation places on the principal to learn information from the agent. However, relaxing model assumptions can impact the value proposition of requirement allocation in favor of objective allocation. Therefore, a resolution to the requirement–objective dichotomy may be context dependent. The results and the analytical framework used to derive them provide a new, foundational perspective with which to investigate allocation strategies.

d. Many of the infrastructure sectors that are considered to be crucial by the Department of Homeland Security include networked systems (physical and temporal) that function to move some commodity like electricity, people, or even communication from one location of importance to another. The costs associated with these flows make up the price of the network’s normal functionality. These networks have limited capacities, which cause the marginal cost of a unit of flow across an edge to increase as congestion builds. In order to limit the expense of a network’s normal demand we aim to increase the resilience of the system and specifically the resilience of the arc capacities. Divisions of critical infrastructure have faced difficulties in recent years as inadequate resources have been available for needed upgrades and repairs. Without being able to determine future factors that cause damage both minor and extreme to the networks, officials must decide how to best allocate the limited funds now so that these essential systems can withstand the heavy weight of society’s reliance. We model these resource allocation decisions using a twostage stochastic program (SP) for the purpose of network protection. Starting with a general form for a basic twostage SP, we enforce assumptions that specify characteristics key to this type of decision model. The second stage objective—which represents the price of the network’s routine functionality—is nonlinear, as it reflects the increasing marginal cost per unit of additional flow across an arc. After the model has been designed properly to reflect the network protection problem, we are left with a nonconvex, nonlinear, nonseparable riskneutral program. This research focuses on key reformulation techniques that transform the problematic model into one that is convex, separable, and much more solvable. Our approach focuses on using perspective functions to convexify the feasibility set of the second stage and second order conic constraints to represent nonlinear constraints in a form that better allows the use of computational solvers. Once these methods have been applied to the riskneutral model we introduce a risk measure into the first stage that allows us to control the balance between an efficient, solvable model and the need to hedge against extreme events. Using Benders cuts that exploit linear separability, we give a decomposition and solution algorithm for the general network model. The innovations included in this formulation are then implemented on a transportation network with given flow demandmore » « less

The classic VickreyClarkeGroves (VCG) mechanism ensures incentive compatibility, i.e., that truthtelling of all agents is a dominant strategy, for a static oneshot 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 sufﬁcient to guarantee incentive compatibility. In fact, it does not appear to be feasible to construct mechanisms that ensure the dominance of dynamic truthtelling 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 LinearQuadraticGaussian (LQG) agents with a careful construction of a sequence of layered payments over time. We propose a layered version of a modiﬁed VCG mechanism for payments that decouples the intertemporal effect of current bids on future payoffs, and prove that truthtelling 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 pricetaking 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 inﬂuenced by factors such as local temperatures and thermal inertias of facilities.more » « less