Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by
trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.

Mechanism Design for Connecting Regions Under Disruptions

**Anthology paper link:**

https://aclanthology.org/2021.emnlp-main.760/

**Abstract:**

The task of knowledge base population (KBP) aims to discover facts about entities from texts and expand a knowledge base with these facts. Previous studies shape end-to-end KBP as a machine translation task, which is required to convert unordered fact into a sequence according to a pre-specified order. However, the facts stated in a sentence are unordered in essence. In this paper, we formulate end-to-end KBP as a direct set generation problem, avoiding considering the order of multiple facts. To solve the set generation problem, we propose networks featured by transformers with non-autoregressive parallel decoding. Unlike previous approaches that use an autoregressive decoder to generate facts one by one, the proposed networks can directly output the final set of facts in one shot. Furthermore, to train the networks, we also design a set-based loss that forces unique predictions via bipartite matching. Compared with cross-entropy loss that highly penalizes small shifts in fact order, the proposed bipartite matching loss is invariant to any permutation of predictions. Benefiting from getting rid of the burden of predicting the order of multiple facts, our proposed networks achieve state-of-the-art (SoTA) performance on two benchmark datasets.

Set Generation Networks for End-to-End Knowledge Base Population

In the facility location problem with continuous demands, where customers are continuously distributed on an area, a planner wants to locate the facilities and allocate the customers to their closest facilities under the proximity rule. In this work, we focus on the fairness and system efficiency from the facility's perspective. Each facility is assumed to have a preference (represented as valuation function) over the subsets of customers. For the fairness of facilities, we provide approximation guarantees for the proportionality and envy-freeness. For the efficiency, we study the utilitarian and egalitarian social welfare. In addition, we are interested in quantifying the possible trade-offs between meeting the fairness criteria and maximizing social welfare, measured by the price of fairness.

Fairness and Efficiency in Facility Location Problems with Continuous Demands

Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic  applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is  to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations  as well as polynomial-time algorithms for the general setting and important restricted settings.

Multi-Robot Task Allocation—Complexity and Approximation

We study the problem faced by a decision maker who wants to locate a set of facilities on a real line and allocate agents/items to the facilities. The items have given locations on the line, and can only be assigned to one of their closest facilities. The facilities are controlled by managers, who have additive utility over the items. An optimal solution that maximizes the (utilitarian or egalitarian) social welfare of the facilities may present a very unbalanced allocation of the items to the facilities and hence be perceived as unfair. In this paper, we are interested in fair allocation among facility managers and consider the well-studied proportionality and envy-freeness fairness notions and their relaxations. We assess the availability, existence, approximability, and the quality (price of fairness) of fair solutions, where the quality measures the system efficiency loss under a fair allocation compared to the one that maximizes the social welfare. Further, we show that one can find a Pareto-optimal solution in polynomial time.

Facility’s Perspective to Fair Facility Location Problems

Poster Session 3

poster

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

AAAI 2025

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



**Session Chair: **Christos Christodoulopoulos 
**In Person Volunteer:** Fabian Kögel 
** Remote Volunteer:** Chenglei Si

8C: Information Extraction 4

technical paper

EMNLP 2021 is planned to be a hybrid event in Punta Cana, Dominican Republic, with both on-site and fully virtual participation possible. The experience for on-site participants would closely approximate a normal pre-COVID *ACL conference, with 5-6 thematically organized parallel sessions and live Q/A and interactive discussion immediately after the talks. Presentations by virtual participants will be equitably interleaved with those of on-site participants, projected on the auditorium screens as if on-site, and also followed immediately by live Q/A and interactive discussion at a time during reasonable waking hours for the virtual presenter. For all participants, on-site and virtual, who are unable to attend a session due to either time-zone issues or because they are participating in another session live, talk recordings and slides will be available online at a minimum after the live presentation (and in many cases before as well), and questions may be submitted in advance on session-specific discussion boards and answered live in session with the usual visual aids if desired.

<iframe style="width:700px;height:400px" src="https://online.fliphtml5.com/ebtyf/ceby/" seamless="seamless" scrolling="no" frameborder="0" allowtransparency="true" allowfullscreen="true" ></iframe>

Please Note: The EMNLP registration system is not currently connected to the underline site as we are still in the process of building out EMNLP 2021. You will receive access instructions from underline the week of November 1st. 

Access is given only to EMNLP upon registration, if you have not registered please do so [here](https://2021.emnlp.org/registration).

Registered attendees will receive access the week of November 1st.

EMNLP 2021

EMNLP 2021 is planned to be a hybrid event in Punta Cana, Dominican Republic, with both on-site and fully virtual participation possible.

S1: Computational Social Choice 5

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

AAMAS 2021

S1: Computational Social Choice 1

Main Track

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

Chenhao Wang

5

5

Presentations

Mechanism Design for Connecting Regions Under Disruptions

Set Generation Networks for End-to-End Knowledge Base Population

Fairness and Efficiency in Facility Location Problems with Continuous Demands

Multi-Robot Task Allocation—Complexity and Approximation

Facility’s Perspective to Fair Facility Location Problems

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES