Stable and Pareto optimal group activity selection from ordinal preferences

In several situations agents need to be assigned to activities on basis of their preferences, and each agent can take part in at most one activity. Often, the preferences of the agents do not depend only on the activity itself but also on the number of participants in the respective activity. In the setting we consider, the agents hence have preferences over pairs “(activity, group size)” including the possibility “do nothing”; in this work, these preferences are assumed to be strict orders. The task will be to find stable assignments of agents to activities, for different concepts of stability such as Nash or core stability, and Pareto optimal assignments respectively. In this respect, particular focus is laid on two natural special cases of agents’ preferences inherent in the considered model, namely increasing and decreasing preferences, where agents want to share an activity with as many (as few, respectively) agents as possible.     

Least manipulable Envy-free rules in economies with indivisibilities

We consider envy-free and budget-balanced allocation rules for problems where a number of indivisible objects and a fixed amount of money is allocated among a group of agents. In finite economies, we identify under classical preferences each agent’s maximal gain from manipulation. Using this result we find the envy-free and budget-balanced allocation rules which are least manipulable for each preference profile in terms of any agent’s maximal gain. If preferences are quasi-linear, then we can find an envy-free and budget-balanced allocation rule such that for any problem, the maximal utility gain from manipulation is equalized among all agents.     

House exchange and residential segregation in networks

This paper considers a Schelling model in an arbitrary fixed network where there are no vacant houses. Agents have preferences either for segregation or for mixed neighborhoods. Utility is non-transferable. Two agents exchange houses when the trade is mutually beneficial. We find that an allocation is stable when for two agents of opposite-color each black (white) agent has a higher proportion of neighbors who are black (white). This result holds irrespective of agents’ preferences. When all members of both groups prefer mixed neighborhoods, an allocation is also stable provided that if an agent belongs to the minority (majority), then any neighbor of opposite-color is in a smaller minority (larger majority).     

A principal–agent problem with heterogeneous demand distributions for a carbon capture and storage system

Mechanism design problems optimize contract offerings from a principal to different types of agents who have private information about their demands for a product or a service. We study the implications of uncertainty in agents’ demands on the principal’s contracts. Specifically, we consider the setting where agents’ demands follow heterogeneous distributions and the principal offers a menu of contracts stipulating quantities and transfer payments for each demand distribution. We present analytical solutions for the special case when there are two distributions each taking two discrete values, as well as a method for deriving analytical solutions from numerical solutions. We describe one application of the model in carbon capture and storage systems to demonstrate various types of optimal solutions and to obtain managerial insights.     

Nash equilibria in optimal reinsurance bargaining

We introduce a strategic behavior in reinsurance bilateral transactions, where agents choose the risk preferences they will appear to have in the transaction. Within a wide class of risk measures, we identify agents’ strategic choices to a range of risk aversion coefficients. It is shown that at the strictly beneficial Nash equilibria, agents appear homogeneous with respect to their risk preferences. While the game does not cause any loss of total welfare gain, its allocation between agents is heavily affected by the agents’ strategic behavior. This allocation is reflected in the reinsurance premium, while the insurance indemnity remains the same in all strictly beneficial Nash equilibria. Furthermore, the effect of agents’ bargaining power vanishes through the game procedure and the agent who gets more welfare gain is the one who has an advantage in choosing the common risk aversion at the equilibrium.     

Estimating the winning chances of a solution suggested by the first player under conditions of voting by veto

This work studies voting according to the veto model used by a board of directors to choose between several ways of development of a corporation. Several rules for choosing are considered, including the possibility of a certain player determining the order of the other players’ moves. The specified task is to find the most advantageous preferences of the voters from the viewpoint of the player who makes his choice first. Of special interest is a situation in which one of the players predominates and can determine the order of the other voters’ moves. The problem is solved for three players both in a case of strict preferences and in a case where the voters decide between several equally preferable ways of developing the corporation.     

Computational aspects of assigning agents to a line

We consider the problem of assigning agents to slots on a line, where only one agent can be served at a slot and each agent prefers to be served as close as possible to his target. We introduce a general approach to compute aggregate gap-minimizing assignments, as well as gap-egalitarian assignments. The approach relies on an algorithm which is shown to be faster than general purpose algorithms for the assignment problem. We also extend the approach to probabilistic assignments and explore the computational features of existing, as well as new, methods for this setting.     

Manipulation games in economies with indivisible goods

In this paper we study the strategic aspects of the No-Envy solution for the problem of allocating a finite set of indivisible goods among a group of agents when monetary compensations are possible. In the first part of the paper we consider the case where each agent receives, at most, one indivisible good. We prove that the set of equilibrium allocations of any direct revelation game associated with a subsolution of the No-Envy solution coincides with the set of envy-free allocations for the true preferences. Under manipulation all the subsolutions of the No-Envy solution are equivalent. In the second part of the paper, we allow each agent to receive more than one indivisible good. In this situation the above characterization does not hold any more. We prove that any Equal Income Walrasian allocation for the true preferences can be supported as an equilibrium allocation of any direct revelation game associated with subsolutions of the No-Envy solution, but also non-efficient allocations can be supported.     

Efficient portfolios in financial markets with proportional transaction costs

In this article, we characterize efficient portfolios, i.e. portfolios which are optimal for at least one rational agent, in a very general multi-currency financial market model with proportional transaction costs. In our setting, transaction costs may be random, time-dependent, have jumps and the preferences of the agents are modeled by multivariate expected utility functions. We provide a complete characterization of efficient portfolios, generalizing earlier results of Dybvig (Rev Financ Stud 1:67–88, 1988) and Jouini and Kallal (J Econ Theory 66: 178–197, 1995). We basically show that a portfolio is efficient if and only if it is cyclically anticomonotonic with respect to at least one consistent price system that prices it. Finally, we introduce the notion of utility price of a given contingent claim as the minimal amount of a given initial portfolio allowing any agent to reach the claim by trading, and give a dual representation of it as the largest proportion of the market price necessary for all agents to reach the same expected utility level.     

Experimentation and Learning in Repeated Cooperation

We study an agency model, in which the principal has only incomplete information about the agent's preferences, in a dynamic setting. Through repeated interaction with the agent, the principal learns about the agent's preferences and can thus adjust the inventive system. In a dynamic computational model, we compare different learning strategies of the principal when facing different types of agents. The results indicate that better learning of preferences can improve the situation of both parties, but the learning process is rather sensitive to random disturbances.     

基于贝叶斯推断的异质投资行为主体下理性投资者学习行为研究

从金融市场运行的微观角度出发,考虑市场中存在着具有双曲型绝对风险厌恶效用函数的理性投资者和广义行为效用函数的行为投资者两类代表性异质投资者.理性投资者会考虑行为投资者对价格的影响效应,进而通过遵循贝叶斯条件概率方式调整自身投资组合中的资产配置,这一过程称为学习过程.通过构建理性投资者的学习模型并分别设计与效用水平相一致的资产表现衡量指标以反应不同类型投资者对于资产的偏好排序,并可依此决定并比较理性投资者、理性学习型投资者和行为投资者的投资组合的资产筛选结果.通过以我国股票市场为对象进行实证研究,结果发现在市场处于上涨周期,可以明显的发现理性投资者会更多地考虑行为投资者的影响,学习过程较为明显;而在市场处于下跌周期,理性投资者则更多的根据先验判据决定资产组合配置.     

Two-stage non-cooperative games with risk-averse players

This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and recourse decisions in the second stage after the uncertainty is realized. Each agent’s overall objective consists of a deterministic first-stage component plus a second-stage mean-risk component defined by a coherent risk measure describing the agent’s risk aversion. We direct our analysis towards a broad class of quantile-based risk measures and linear-quadratic recourse functions. For this class of non-cooperative games under uncertainty, the agents’ objective functions can be shown to be convex in their own decision variables, provided that the deterministic component of these functions have the same convexity property. Nevertheless, due to the non-differentiability of the recourse functions, the agents’ objective functions are at best directionally differentiable. Such non-differentiability creates multiple challenges for the analysis and solution of the game, two principal ones being: (1) a stochastic multi-valued variational inequality is needed to characterize a Nash equilibrium, provided that the players’ optimization problems are convex; (2) one needs to be careful in the design of algorithms that require differentiability of the objectives. Moreover, the resulting (multi-valued) variational formulation cannot be expected to be of the monotone type in general. The main contributions of this paper are as follows: (a) Prior to addressing the main problem of the paper, we summarize several approaches that have existed in the literature to deal with uncertainty in a non-cooperative game. (b) We introduce a unified formulation of the two-stage SNEP with risk-averse players and convex quadratic recourse functions and highlight the technical challenges in dealing with this game. (c) To handle the lack of smoothness, we propose smoothing schemes and regularization that lead to differentiable approximations. (d) To deal with non-monotonicity, we impose a generalized diagonal dominance condition on the players’ smoothed objective functions that facilitates the application and ensures the convergence of an iterative best-response scheme. (e) To handle the expectation operator, we rely on known methods in stochastic programming that include sampling and approximation. (f) We provide convergence results for various versions of the best-response scheme, particularly for the case of private recourse functions. Overall, this paper lays the foundation for future research into the class of SNEPs that provides a constructive paradigm for modeling and solving competitive decision making problems with risk-averse players facing uncertainty; this paradigm is very much at an infancy stage of research and requires extensive treatment in order to meet its broad applications in many engineering and economics domains.     

Interaction dynamics of two reinforcement learners

The paper investigates a stochastic model where two agents (persons, companies, institutions, states, software agents or other) learn interactive behavior in a series of alternating moves. Each agent is assumed to perform “stimulus-response-consequence” learning, as studied in psychology. In the presented model, the response of one agent to the other agent's move is both the stimulus for the other agent's next move and part of the consequence for the other agent's previous move. After deriving general properties of the model, especially concerning convergence to limit cycles, we concentrate on an asymptotic case where the learning rate tends to zero (“slow learning”). In this case, the dynamics can be described by a system of deterministic differential equations. For reward structures derived from [2×2] bimatrix games, fixed points are determined, and for the special case of the prisoner's dilemma, the dynamics is analyzed in more detail on the assumptions that both agents start with the same or with different reaction probabilities.     

Finding strongly popular b-matchings in bipartite graphs

The computational complexity of the bipartite popular matching problem depends on how indifference appears in the preference lists. If one side has strict preferences while nodes on the other side are all indifferent (but prefer to be matched), then a popular matching can be found in polynomial time (Cseh et al., 2015). However, as the same paper points out, the problem becomes NP-complete if nodes with strict preferences are allowed on both sides and indifferent nodes are allowed on one side. We show that the problem of finding a strongly popular matching is polynomial-time solvable even in the latter case. More generally, we give a polynomial-time algorithm for the many-to-many version, i.e. the strongly popular $b$-matching problem, in the setting where one side has strict preferences while agents on the other side may have one tie of arbitrary length at the end of their preference list.     

Resource allocation on condition of random resource demand of network activities

A general network model is considered. Each activity may require several storable and productive resources. Fixed amounts of storable resources are delivered at fixed times. The capacities of the productive resources are assumed to be constant. A general resource allocation problem is derived in order to optimize the cost for the execution of the network activities, In the main, the case is considered where the resource demands of the activities are random variables. For this case, the means of resource demands are estimated and a method is presented to obtain a vector of start times and durations of the activities so that a cost function is minimized and the probability that, at any time, there appears no lack of resources is maximized.     

Paths to stability and uniqueness in two-sided matching markets

The deferred acceptance algorithm introduced by Gale and Shapley is a centralized algorithm, where a social planner solicits the preferences from two sides of a market and generates a stable matching. On the other hand, the algorithm proposed by Knuth is a decentralized algorithm. In this article, we discuss conditions leading to the convergence of Knuth’s decentralized algorithm. In particular, we show that Knuth’s decentralized algorithm converges to a stable matching if either the Sequential Preference Condition (SPC) holds or if the market admits no cycle. In fact, acyclicity turns out to be a special case of SPC. We then consider markets where agents may prefer to remain single rather than being matched with someone. We introduce a generalized version of SPC for such markets. Under this notion of generalized SPC, we show that the market admits a unique stable matching, and that Knuth’s decentralized algorithm converges. The generalized SPC seems to be the most general condition available in the literature for uniqueness in two-sided matching markets.     

Where do preferences come from?

Rational choice theory analyzes how an agent can rationally act, given his or her preferences, but says little about where those preferences come from. Preferences are usually assumed to be fixed and exogenously given. Building on related work on reasons and rational choice (Dietrich and List, Nous, forthcoming), we describe a framework for conceptualizing preference formation and preference change. In our model, an agent’s preferences are based on certain ‘motivationally salient’ properties of the alternatives over which the preferences are held. Preferences may change as new properties of the alternatives become salient or previously salient properties cease to be salient. Our approach captures endogenous preferences in various contexts and helps to illuminate the distinction between formal and substantive concepts of rationality, as well as the role of perception in rational choice.     

Dialogue strategy for horizontal communication in MAS organization

A multi agent organization model defines the structure, roles, interaction ways and coordination styles of a multi agent system. Multi agent organizations may constrain the communication between included members. Organizations’ communication is the process of sending or receiving all the messages through a group of agents in order to achieve common goals. In a dialogue, agents follow some rules that define the permissive speech acts called dialogue protocol. Aiming for common goals, the dialogue strategy is the policy of agents to choose a particular speech act among the allowed ones by the protocol. In this paper a formal model for dialogue strategy for a group of agents in an organization is proposed in order to choose the most preferable speech acts. The argumentation theory is applied to the proposed method to define the values of plausible speech acts and to rank them. The algorithm finds the best option to utter and also it decreases the volume of exchanging messages. The proposed dialogue strategy is illustrated via a deliberation dialogue example in a group of agents.     

Minimizing maximum cost on a single machine with two competing agents and job rejection

The classical Lawler’s Algorithm provides an optimal solution to the single-machine scheduling problem, where the objective is minimizing maximum cost, given general non-decreasing, job-dependent cost functions, and general precedence constraints. First, we extend this algorithm to allow job rejection, where the scheduler may decide to process only a subset of the jobs. Then, we further extend the model to a setting of two competing agents, sharing the same processor. Both extensions are shown to be solved in polynomial time.     

Multiscale decision-making: Bridging organizational scales in systems with distributed decision-makers

Decision-making in organizations is complex due to interdependencies among decision-makers (agents) within and across organizational hierarchies. We propose a multiscale decision-making model that captures and analyzes multiscale agent interactions in large, distributed decision-making systems. In general, multiscale systems exhibit phenomena that are coupled through various temporal, spatial and organizational scales. Our model focuses on the organizational scale and provides analytic, closed-form solutions which enable agents across all organizational scales to select a best course of action. By setting an optimal intensity level for agent interactions, an organizational designer can align the choices of self-interested agents with the overall goals of the organization. Moreover, our results demonstrate when local and aggregate information exchange is sufficient for system-wide optimal decision-making. We motivate the model and illustrate its capabilities using a manufacturing enterprise example.