New Zealand


We propose an agent-based network formation model under uncertainty with the objective of relaxing the common assumption of complete information, calling attention to the role beliefs may play in segregation. We demonstrate that our model is capable of generating a set of networks that encompasses those of a complete information model. Further, we show that by allowing agents to hold biased beliefs toward each other based on social group membership, individual utility-maximising decisions may lead to group segregation at the cost of social welfare. We accompany our theoretical results with a simulation-based investigation of the relationship between beliefs and segregation and show that biased beliefs are an important driver of segregation under incomplete information.

AAMAS 2022

Segregation in social networks of heterogeneous agents acting under incomplete information

heterogeneous agents

incomplete information

segregation

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

technical paper


Gerrymandering is the process of creating electoral districts for partisan advantage, allowing a party to win more seats than what is reasonable for their vote. While research on gerrymandering has recently grown, many issues are still not fully understood such as what influences the degree to which a party can gerrymander and what techniques can be used to counter it. One commonly suggested (and, in some US states, mandated) requirement is that districts be “geographically compact”. However, there are many competing compactness definitions and the impact of compactness on the gerrymandering abilities of the parties is not well understood. Also not well understood is how the growing urban-rural divide between supporters of different parties impacts redistricting.

We develop a modular, scalable, and efficient algorithm that can design districts for various criteria. We confirm its effectiveness on several US states by pitting it against maps “hand-drawn” by political experts. Using real data from US political elections we use our algorithm to study the interaction between population distri- bution, partisanship, and geographic compactness. We find that compactness can lead to more fair plans (compared to implemented plans) and limit gerrymandering potential, but there is a consistent asymmetry where the party with rural supporters has an advan- tage. We also show there are plans which are fair from a partisan perspective, but they are far from optimally compact.

Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution


We develop an algorithm for the axiomatic justification problem in social choice that is sufficiently efficient to be applicable in decision making scenarios of real practical interest. Given a profile of individual preferences, a suggested election outcome, and a corpus of axioms encoding fundamental normative principles of electoral fairness, solving this justification problem involves computing a minimal set of instances of some of the axioms in the corpus that together rule out any outcome that is different from the one we want to justify. Our approach combines the use of state-of-the-art tools for computing minimally unsatisfiable sets of constraints with a graph-search algorithm. The latter searches the graph induced by the set of all axiom instances in an incremental manner and relies on a number of heuristics to further improve performance.

A Graph-Based Algorithm for the Automated Justification of Collective Decisions


A major open question in fair allocation of indivisible items is whether there always exists an allocation of chores that is Pareto optimal (PO) and envy-free up to one item (EF1). We answer this question affirmatively for the natural class of bivalued utilities, where each agent partitions the chores into easy and difficult ones, and has cost p > 1 for chores that are difficult for her and cost 1 for chores that are easy for her. Such an allocation can be found in polynomial time using an algorithm based on the Fisher market.

We also show that for a slightly broader class of utilities, where each agent i can have a potentially different integer p_i, an allocation that is maximin share fair (MMS) always exists and one that is both PO and MMS can be computed in polynomial time, provided that each p_i is an integer. Our MMS arguments also hold when allocating goods instead of chores, and extend to another natural class of utilities, namely weakly lexicographic utilities.

How to Fairly Allocate Easy and Difficult Chores


This paper presents a path-following combinatorial framework based on systems of polynomial equations to compute mixed Nash equilibria in $N$-person games.
We provide the first detailed implementable description of Wilson's path-following method, which extends Lemke-Howson's algorithm to N-persons games and handles degenerate games as well.
Our approach resembles, in some respects, support enumeration methods.
We thus compare both approaches, theoretically and experimentally.
Then, we show that the path-following approach allows to deal with a large family of succinctly expressed games: hypergraphical games, graphical games and polymatrix games.
The described algorithms have been implemented in Python, making use of Sagemath libraries to solve systems of polynomial equations, allowing an experimental comparison of the different combinatorial approaches on a large variety of games.

A path-following polynomial equations systems approach for computing Nash equilibria


Nash equilibrium is a central concept in game theory. Several Nash solvers exist, yet none scale to normal-form games with many actions and many players, especially those with payoff tensors too big to be stored in memory. In this work, we propose an approach that iteratively improves an approximation to a Nash equilibrium through joint play. It accomplishes this by tracing a previously established homotopy that defines a continuum of equilibria for the game regularized with decaying levels of entropy. This continuum asymptotically approaches the \emph{limiting logit equilibrium}, proven by McKelvey and Palfrey (1995) to be unique in \emph{almost} all games, thereby partially circumventing the well-known equilibrium selection problem of many-player games. To encourage iterates to remain near this path, we efficiently minimize \emph{average deviation incentive} via stochastic gradient descent, intelligently sampling entries in the payoff tensor as needed. Monte Carlo estimates of the stochastic gradient from joint play are biased due to the appearance of a nonlinear max operator in the objective, so we introduce additional innovations to the algorithm to alleviate gradient bias. The descent process can also be viewed as repeatedly constructing and reacting to a polymatrix approximation to the game. In these ways, our proposed approach, \emph{average deviation incentive descent with adaptive sampling} (ADIDAS), is most similar to three classical approaches, namely homotopy-type, Lyapunov, and iterative polymatrix solvers. The lack of local convergence guarantees for biased gradient descent prevents guaranteed convergence to Nash, however, we demonstrate through extensive experiments the ability of this approach to approximate a unique Nash equilibrium in normal-form games with as many as seven players and twenty one actions (several billion outcomes) that are orders of magnitude larger than those possible with prior algorithms.

Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent


The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the \epsilon-approximate ADHZ model, and we give the following results.

1. Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability.

2. A combinatorial polynomial-time algorithm for an \epsilon-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities.

3. An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium.

4. A rational convex program for HZ under dichotomous utilities; a combinatorial polynomial-time algorithm for this case was given in \cite{VY20}.

The \epsilon-approximate ADHZ model fills a void in the space of general mechanisms for one-sided matching markets; see details in the paper.

One-Sided Matching Markets with Endowments: Equilibria and Algorithms


The behavior of no-regret learning algorithms is well understood in two-player min-max (i.e, zero-sum) games. In this paper, we investigate the behavior of no-regret learning in min-max games with dependent strategy sets, where the strategy of the first player constrains the behavior of the second. Such games are best understood as sequential, i.e., min-max Stackelberg, games. We consider two settings, one in which only the first player chooses their actions using a no-regret algorithm while the second player best responds, and one in which both players use no-regret algorithms. For the former case, we show that no-regret dynamics converge to a Stackelberg equilibrium. For the latter case, we introduce a new type of regret, which we call Lagrangian regret, and show that if both players minimize their Lagrangian regret, then play converges to a Stackelberg equilibrium. We then observe that online mirror descent (OMD) dynamics in these two settings correspond respectively to a known nested (i.e., sequential) gradient descent-ascent (GDA) algorithm and a new simultaneous GDA-like algorithm, thereby establishing convergence of these algorithms to Stackelberg equilibrium. Finally, we analyze the robustness of OMD dynamics to perturbations by investigating dynamic min-max Stackelberg games. We prove that OMD dynamics are robust for a large class of dynamic min-max games (with independent strategy sets). In the dependent case, we demonstrate the robustness of OMD dynamics experimentally by simulating them in dynamic Fisher markets, a canonical example of a min-max Stackelberg game (with dependent strategy sets).

Robust No-Regret Learning in Min-Max Stackelberg Games


The way opinions spread in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion.
Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. 

In the social variant of the Hegselmann-Krause model, agents are connected by a social network and their opinions evolve in an iterative process. Opinions are modeled as elements in the $d$-dimensional Euclidean space. When an agent is activated it adopts the average of the opinions of its influencing neighbors which are those neighbors having a similar opinion. Note that by this update process the set of influencing neighbors of an agent may change over time. Activation schemes focused on in the literature are synchronous agent activation where all agents are activated in parallel and asynchronous random agent activation where randomly chosen agents are activated sequentially.

Interestingly, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied assuming the complete graph as social network. In this paper we show that the social Hegselmann-Krause opinion dynamics with asynchronous random agent activation is guaranteed to converge for any social network. We provide an upper bound of $\mathcal{O}(n|E|^2 (\eps/\delta)^2)$ on the expected number of opinion updates until convergence, where $|E|$ is the number of edges of the social network. For the already investigated setting on a complete social network we show an even better bound of $\mathcal{O}(n^3(n^2 + (\eps/\delta)^2))$ that yields a major improvement over the previously best known upper bound of $\mathcal{O}(n^9 (\eps/\delta)^2)$. We complement our upper bounds by providing an example showing that our potential function based analysis cannot be improved easily. Moreover, empirical agent-based simulations on specific social network topologies yield asymptotically matching lower bounds.

Asynchronous Opinion Dynamics in Social Networks


Influence maximization has now been a widely studied topic, but only in recent years have studies considered overexposure. Overexposure is usually measured as the negative cost associated with reaching unintended recipients during an information cascade. A polynomial-time algorithm is known for cascades with overexposure when we can select as many seed nodes as we want. This paper focuses on overexposure for the budgeted case of seeding, which has received little to no attention. We show that the problem is NP-hard even for a restricted case. For various special cases, we devise provable approximation algorithms, dynamic programming solutions, linear programming solutions, and heuristics. For the general case, we provide a linear programming solution and several fast and effective heuristics, mostly of the greedy flavor. We perform an extensive experimental study using synthetic and real-world networks. We investigate how network properties and model parameters impact our algorithms. It brings out interesting findings like why a low-quality product needs a smarter algorithm, and why certain algorithms do well on some networks but not others.

Cascades and Overexposure in Social Networks: The Budgeted Case


Collective risk dilemmas (CRDs) are a class of $n$-player games that represent societal challenges where groups need to coordinate to avoid the risk of hazardous consequences. Multi-agent systems incurring such dilemmas face difficulties achieving cooperation and often converge to sub-optimal solutions where everyone defects. In these contexts, empirical observations suggest that there is a strong discrepancy in risk, as often some parties are (or feel) more threatened than others. Here we investigate the role of risk diversity in groups of agents learning to play CRDs. We show that risk diversity places new challenges to cooperation that are not observed in homogeneous groups. While increasing average risk contributes, in general, for agents to cooperate with higher probability, increasing risk diversity significantly reduces a population's ability to achieve a collective target. Risk diversity leads to asymmetrical changes in agents policies --- i.e. the increase in contributions from individuals at high risk is unable to compensate for the decrease in contributions from individuals at low risk --- which reduces the total contributions in a population and overall social welfare. At the same time, risk diversity offers novel opportunities in the design of financial incentives, which, as we show, can foster higher cooperation, target achievement and global welfare than the ones obtained in the absence of diversity. Our results highlight the need to align risk perceptions among agents when possible and implement diversity-based incentive policies in order to improve collectives' abilities to coordinate and avoid future catastrophic events.

Segregation in social networks of heterogeneous agents acting under incomplete information

Downloads

Next from AAMAS 2022

Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution

Similar lecture

Cooperation and learning dynamics under risk diversity and financial incentives

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Segregation in social networks of heterogeneous agents acting under incomplete information

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2022

Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution

Similar lecture

Cooperation and learning dynamics under risk diversity and financial incentives

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads