WINE 2022 - The 18th Conference on Web and Internet Economics

Troy, NY, USA, December 12 - 15, 2022

Overview

Over the past decade, research in theoretical computer science, artificial intelligence, operations research, and economics has joined forces to tackle problems involving incentives and computation. These problems are of particular importance in application areas like the Web and the Internet that involve large and diverse populations. The Conference on Web and Internet Economics (WINE) is an interdisciplinary forum for the exchange of ideas and results on incentives and computation arising from these various fields.

WINE 2022 will take place on December 12 - 15, 2022, in Troy, NY, USA, hosted by Rensselaer Polytechnic Institute (RPI).

Sponsors

Important Dates

Paper submission deadline:

July 7, 2022, 11:59pm Pacific Time

Author notification:

Before September 7, 2022

Contact

wine2022chairs@gmail.com

Call for Papers: Eighteenth Conference on Web and Internet Economics (WINE 2022)

Troy, NY, USA, December 12 - 15, 2022

Webpage: https://www.cs.rpi.edu/wine2022/

Over the past two decades, researchers in theoretical computer science, artificial intelligence, operations research, and economics have joined forces to understand the interplay of incentives and computation. These issues are of particular importance in the Web and the Internet that enable the interaction of large and diverse populations. The Conference on Web and Internet Economics (WINE) is an interdisciplinary forum for the exchange of ideas and results on incentives and computation arising from these various fields. WINE 2022 continues the successful tradition of the Conference on Web and Internet Economics (named Workshop on Internet & Network Economics until 2013), which was held annually from 2005 to present.

The program will feature invited talks, tutorials, paper presentations, a poster session, and a plenary session on spotlights beyond WINE. All paper submissions will be peer-reviewed and evaluated on the basis of the quality of their contribution, originality, soundness, and significance. Submissions are invited in, but not limited to, the following topics:

  • Algorithmic Game Theory
  • Algorithmic Mechanism Design
  • Market Design
  • Auction Algorithms and Analysis
  • Computational Advertising
  • Computational Aspects of Equilibria
  • Computational Social Choice
  • Learning in Markets and Mechanism Design
  • Learning under Strategic Behavior
  • Coalitions, Coordination, and Collective Action
  • Economic Aspects of Security and Privacy
  • Economic Aspects of Distributed Computing and Cryptocurrencies
  • Econometrics, ML, and Data Science
  • Behavioral Economics and Behavioral Modeling
  • Fairness and Trust in Games and Markets
  • Price Differentiation and Price Dynamics
  • Revenue Management
  • Social Networks and Network Games

Authors of the accepted papers will have a choice to attend the conference virtually.


Important Dates

Paper submission deadline: July 7, 2022, 11:59pm Pacific Time

Author notification: before September 7, 2022


Submission Server

Easychair submission link: https://easychair.org/conferences/?conf=wine2022


Submission Format

Authors are invited to submit extended abstracts presenting original research on any of the research fields related to WINE 2022.

An extended abstract submitted to WINE 2022 should start with the title of the paper, each author’s name, affiliation and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work.

The extended abstract should not exceed 18 single-spaced pages (including references) using reasonable margins (at least one-inch margins all around) and at least 11-point font. If the authors believe that more details are essential to substantiate the claims of the paper, they may include a clearly marked appendix (with no space limit) that will be read at the discretion of the Program Committee. It is strongly recommended that submissions adhere to the specified format and length. Submissions that are clearly too long may be rejected immediately. The above specifications are meant to provide more freedom to the authors at the time of submission. Note that accepted papers will be allocated 18 pages (including references) in the LNCS format in the proceedings (see below).

The proceedings of the conference will be published by Springer-Verlag in the ARCoSS/LNCS series, and will be available for distribution at the conference. Accepted papers will be allocated 18 pages total in the LNCS format in the proceedings. Submissions are encouraged, though not required, to follow the LNCS format (Latex, Word). More information about the LNCS format can be found on the author instructions page of Springer-Verlag.


Questions regarding the submissions can be directed to the PC chairs via wine2022chairs@gmail.com.


Conflict of Interest Policy

A conflict of interest (COI) is limited to the following categories:

  1. Family member or close friend.
  2. Ph.D. advisor or advisee (no time limit), or postdoctoral or undergraduate mentor or mentee within the past five years.
  3. Person with the same affiliation (department, not institute).
  4. Involved in an alleged incident of harassment (it is not required that the incident be reported).
  5. Reviewer owes author a favor (e.g., recently requested a reference letter).
  6. Frequent or recent collaborator whom you believe cannot objectively review your work.

Declaring COIs prevents the specified person from reviewing a paper, thereby constraining the matching process and so potentially negatively impacting review quality. For this reason, COIs should not be declared automatically based on a prior relationship (e.g., coauthor, friend, colleague in a different department at the same institution, etc.). Authors can contact the PC chairs directly if they have a conflict with an individual who is likely to be asked to serve as a subreviewer for the paper.


Even though EasyChair asks the authors to specify the type of conflict of interest when they declare one, the authors do *not* need to answer that question. They may avoid answering it by choosing the option “Others”.


Best Paper Award

The program committee will decide upon a best paper award and a best student paper award.


Important Notice

To accommodate the publishing traditions of different fields, authors of accepted papers can ask that only a one-page abstract of the paper appear in the proceedings, along with a URL pointing to the full paper. The authors should guarantee the link to be reliable for at least two years. This option is available to accommodate subsequent publication in journals that would not consider results that have been published in preliminary form in conference proceedings. Such papers must be submitted and formatted just like papers submitted for full-text publication.

Simultaneous submission of results to another conference with published proceedings is not allowed. Results previously published or presented at another archival conference prior to WINE 2022, or published (or accepted for publication) at a journal prior to the submission deadline of WINE 2022, will not be considered. Simultaneous submission of results to a journal is allowed only if the authors intend to publish the paper as a one-page abstract in WINE 2022. Papers that are accepted and appear as a one-page abstract can be subsequently submitted for publication in a journal but may not be submitted to any other conference that has a published proceeding.


Forward to Journal

Upon submission, WINE authors would have a chance to select at most one from the following journals:



How does it work? If a WINE paper is accepted and the authors plan to use the forward-to-journal option, the authors must submit a one-page extended abstract by the deadline for the camera-ready version of the conference proceeding.

The authors then have the option of submitting their journal paper by January 20, 2023, to the journal they have selected. The cover letter to the journal should specify that the submission is part of the WINE '22 forward-to-journal process. WINE papers that submit a final version by this deadline will be forwarded to the journal of choice along with the de-anonymized conference reviews. Note that a journal's participation in the WINE forward-to-journal option does not mean that other forms of previous publication are acceptable.

What are the implications? The journal's department editor and/or associate editor can use the conference reviews to guide the decision-making process in whatever way the journal finds appropriate. We suspect the AEs might choose referees from among the set of conference reviewers, especially if they found the conference reviews informative. We would like to emphasize, however, that the conference reviewers are not required to accept such review requests. Furthermore, journals are not required to accept these papers (and may even choose to desk-reject them depending on fit).

Call for Nominations

The 18th conference on Web and Internet Economics (WINE'22) will host a 'Spotlight beyond WINE' session to highlight some of the best works in algorithmic game theory that appeared in conferences and journals other than WINE, or mature working papers. The intention of this session is to expose WINE attendees to exciting works beyond the boundary of their current awareness. We seek nominations for papers on topics that are relevant to Web and Internet Economics and have made breakthrough advances, provided new directions, or had significant impact on practice.

Examples of relevant conferences and journals include:
EC/STOC/FOCS/SODA/ITCS, AAAI/IJCAI/AAMAS, NeurIPS/ICML/COLT, WWW/KDD, AER/Econometrica/JPE/QJE/RESTUD/TE/AEJ/JET/GEB, and Math of OR/Management Science/Operations Research.

Nomination

Anyone can nominate, and self-nomination is allowed. We particularly encourage members of PCs or editorial boards in various venues to submit nominations.

Deadline: Sep 16, 2022

Nomination format: Nominations should be emailed to spotlightbeyondwine2022@gmail.com, and should include:

  • Paper title and author names.
  • Publication venue or online working version. Preference will be given to papers that have appeared in a related conference or journal within the past two years, or have a working version circulated within the past two years.
  • A few sentences explaining why the paper is a good fit for spotlights beyond WINE.
  • Names of 1-3 experts in the area of the paper.

Committee members

  • Edith Elkind (U. of Oxford)
  • Michal Feldman (Tel Aviv U.)
  • Philipp Strack (Yale U.)
  • Gabriel Weintraub (Stanford U.)

Call for Posters

WINE 2022 will feature an online poster session. The poster session is envisioned to be a great way to attract attention to recent work and start a discussion.

Submission Information

Please complete the form at https://forms.gle/Phc5EZ9K9ugo52zX9 before November 1, 2022, 11:59 PM AOE (you will need a Google ID to register).

To submit a paper for the poster session, you will need to provide the following information:

  1. Title and abstract for the poster
  2. Name and email address of the presenter, and names of coauthors
  3. Either a link to the full paper, or the full paper itself
  4. Details if the paper has appeared at a conference or in a journal

For accepted posters, the presenter must also register for WINE 2022 and agree to be present during the online poster session (early registration deadline Nov. 12). The date and time for the poster session will be decided later.

Important Dates

Please fill up the submission form before November 1, 2022, 11:59 PM AOE. Acceptance notifications will be sent by November 7, 2022.

Posters are non-archival, and will not appear as part of WINE 2022 proceedings.

Questions? Send an email to wine2022posters@gmail.com

Accepted Papers


Jad Salem, Swati Gupta and Vijay Kamble.

Algorithmic Challenges in Ensuring Fairness at the Time of Decision


Kamesh Munagala, Yiheng Shen and Kangning Wang.

Auditing for Core Stability in Participatory Budgeting


Pinyan Lu, Enze Sun and Chenghan Zhou.

Better Approximation for Interdependent SOS Valuations


Lirong Xia and Weiqiang Zheng.

Beyond the Worst Case: Semi-Random Complexity Analysis of Winner Determination


Tim Oosterwijk, Daniel Schmand and Marc Schroder.

Bicriteria Nash Flows over Time


Xiaotie Deng, Ningyuan Li, Weian Li and Qi Qi.

Competition Among Parallel Contests


Will Ma and David Simchi-Levi.

Constructing Demand Curves from a Single Observation of Bundle Sales


Grzegorz Pierczyński and Piotr Skowron.

Core-Stable Committees under Restricted Domains


Peng Shi and Junxiong Yin.

Eliminating Waste in Cadaveric Organ Allocation


Christine Konicki, Mithun Chakraborty and Michael Wellman.

Exploiting Extensive-Form Structure in Empirical Game-Theoretic Analysis


Pan Xu.

Exploring the Tradeoff between Competitive Ratio and Variance in Online-Matching Markets


Xiaohui Bei, Zihao Li and Junjie Luo.

Fair and Efficient Multi-Resource Allocation for Cloud Computing


Yumou Fei.

Improved Approximation to First-Best Gains-from-Trade


Bainian Hao and Carla Michini.

Inefficiency of pure Nash equilibria in series-parallel network congestion games


Yi-Chun Chen, Gaoji Hu and Xiangqian Yang.

Information Design in Allocation with Costly Verification


Mengqian Zhang, Yuhao Li, Jichen Li, Chaozhe Kong and Xiaotie Deng.

Insightful Mining Equilibria


Zhibin Tan, Zhigang Cao and Zhengxing Zou.

Matrix-exact Covers of Minimum-Cost-Spanning-Tree Games


Siddharth Barman, Anand Krishna, Yadati Narahari and Soumyarup Sadhukhan.

Nash Welfare Guarantees for Fair and Efficient Coverage


Moshe Babaioff, Tomer Ezra and Uriel Feige.

On Best-of-Both-Worlds Fair-Share Allocations


Susanne Albers and Sebastian Schubert.

Online Ad Allocation in Bounded-Degree Graphs


Melika Abolhassani, Hossein Esfandiari, Yasamin Nazari, Balasubramanian Sivan, Yifeng Teng and Creighton Thomas.

Online Allocation and Display Ads Optimization with Surplus Supply


Matthew Eichhorn, Siddhartha Banerjee and David Kempe.

Online Team Formation under Different Synergies


Titing Cui and Michael Hamilton.

Optimal Feature-Based Market Segmentation and Pricing


Javier Cembrano, Felix Fischer and Max Klimm.

Optimal Impartial Correspondences


Yurong Chen, Xiaotie Deng and Yuhao Li.

Optimal Private Payoff Manipulation against Commitment in Extensive-form Games


Nick Gravin, Hao Li and Zhihao Gavin Tang.

Optimal Prophet Inequality with Less than One Sample


Boris Epstein and Will Ma.

Order Selection Problems in Hiring Pipelines


Tong Xie and Zizhuo Wang.

Personalized Assortment Optimization under Consumer Choice Models with Local Network Effects


Sumit Goel and Wade Hann-Caruthers.

Project selection with partially verifiable information


Bo Jiang, Zizhuo Wang and Nanxi Zhang.

Revenue Management Under a Price Alert Mechanism


Adam Elmachtoub, Vineet Goyal, Roger Lederman and Harsh Sheth.

Revenue Management with Product Retirement and Customer Selection


Cuimin Ba.

Robust Model Misspecification and Paradigm Shifts


Hu Fu, Qun Hu and Jia'Nan Lin.

Stability of Queueing Networks Beyond Complete Bipartite Cases


Haris Aziz, Alexander Lam, Barton Lee and Toby Walsh.

Strategyproof and Proportionally Fair Facility Location


Itai Feigenbaum.

Strategyproofness in Kidney Exchange with Cancellations


Atanas Dinev and S. Matthew Weinberg.

Tight Bounds on 3-Team Manipulations in Randomized Death Match


Jugal Garg, Edin Husić, Aniket Murhekar and László Végh.

Tractable Fragments of the Maximum Nash Welfare Problem


Yuan Qiu, Jinyan Liu and Di Wang.

Truthful Generalized Linear Models

Vignesh Viswanathan and Yair Zick

A General Framework for Fair Allocation with Matroid Rank Valuations

We study the problem of fairly allocating a set of indivisible goods among agents with matroid rank valuations. We present a simple framework that efficiently computes any fairness objective that satisfies some mild assumptions. Along with maximizing a fairness objective, the framework is guaranteed to run in polynomial time, maximize utilitarian social welfare and ensure strategyproofness. We show how our framework can be used to achieve four different fairness objectives: (a) Prioritized Lorenz dominance, (b) Maxmin fairness, (c) Weighted leximin, and (d) Max weighted Nash welfare. In particular, our framework provides the first polynomial time algorithms to compute weighted leximin and max weighted Nash welfare allocations for matroid rank valuations.

Link: https://arxiv.org/abs/2208.07311

Peng Shi

Optimal Matchmaking Strategy in Two-Sided Marketplaces

Online platforms that match customers with suitable service providers utilize a wide variety of matchmaking strategies; some create a searchable directory of one side of the market (i.e., Airbnb, Google Local Finder), some allow both sides of the market to search and initiate contact (i.e., Care.com, Upwork), and others implement centralized matching (i.e., Amazon Home Services, TaskRabbit). This paper compares these strategies in terms of their efficiency of matchmaking as proxied by the amount of communication needed to facilitate a good market outcome. The paper finds that the relative performance of these matchmaking strategies is driven by whether the preferences of agents on each side of the market are easy to describe. Here, “easy to describe” means that the preferences can be inferred with sufficient accuracy based on responses to standardized questionnaires. For markets with suitable characteristics, each of these matchmaking strategies can provide near-optimal performance guarantees according to an analysis based on information theory. The analysis provides prescriptive insights for online platforms.

Link: https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2022.4444

Emily Ryu, Jon Kleinberg, Éva Tardos

Ordered Submodularity and its Applications to Diversifying Recommendations

A fundamental task underlying many important optimization problems, from influence maximization to sensor placement to content recommendation, is to select the optimal group of $k$ items from a larger set. Submodularity has been very effective in allowing approximation algorithms for such subset selection problems. However, in several applications, we are interested not only in the elements of a set, but also the \emph{order} in which they appear, breaking the assumption that all selected items receive equal consideration. One such category of applications involves the presentation of search results, product recommendations, news articles, and other content, due to the well-documented phenomenon that humans pay greater attention to higher-ranked items. As a result, optimization in content presentation for diversity, user coverage, calibration, or other objectives more accurately represents a sequence selection problem, to which traditional submodularity approximation results no longer apply. Although extensions of submodularity to sequences have been proposed, none is designed to model settings where items contribute based on their position in a ranked list, and hence they are not able to express these types of optimization problems. In this paper, we aim to address this modeling gap. Here, we propose a new formalism of \emph{ordered submodularity} that captures these ordering problems in content presentation, and more generally a category of optimization problems over ranked sequences in which different list positions contribute differently to the objective function. We analyze the natural ordered analogue of the greedy algorithm and show that it provides a $2$-approximation. We also show that this bound is tight, establishing that our new framework is conceptually and quantitatively distinct from previous formalisms of set and sequence submodularity.

Link: https://arxiv.org/pdf/2203.00233.pdf

Jerry Anunrojwong, Santiago R. Balseiro, Omar Besbes

On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design

Classical Bayesian mechanism design relies on the common prior assumption, but such prior is often not available in practice. We study the design of prior-independent mechanisms that relax this assumption: the seller is selling an indivisible item to n buyers such that the buyers' valuations are drawn from a joint distribution that is unknown to both the buyers and the seller; buyers do not need to form beliefs about competitors, and the seller assumes the distribution is adversarially chosen from a specified class. We measure performance through the worst-case regret, or the difference between the expected revenue achievable with perfect knowledge of buyers' valuations and the actual mechanism revenue. We study a broad set of classes of valuation distributions that capture a wide spectrum of possible dependencies: independent and identically distributed (i.i.d.) distributions, mixtures of i.i.d. distributions, affiliated and exchangeable distributions, exchangeable distributions, and all joint distributions. We derive in quasi closed form the minimax values and the associated optimal mechanism. In particular, we show that the first three classes admit the same minimax regret value, which is decreasing with the number of competitors, while the last two have the same minimax regret equal to that of the single buyer case. Furthermore, we show that the minimax optimal mechanisms have a simple form across all settings: a second-price auction with random reserve prices, which shows its robustness in prior-independent mechanism design. En route to our results, we also develop a principled methodology to determine the form of the optimal mechanism and worst-case distribution via first-order conditions that should be of independent interest in other minimax problems.

Link: https://arxiv.org/abs/2204.10478

Farhad Mohsin, Ao Liu, Pin-Yu Chen, Francesca Rossi, Lirong Xia

Learning to Design Fair and Private Voting Rules

Voting is used widely to identify a collective decision for a group of agents, based on their preferences. In this paper, we focus on evaluating and designing voting rules that support both the privacy of the voting agents and a notion of fairness over such agents. To do this, we introduce a novel notion of group fairness and adopt the existing notion of local differential privacy. We then evaluate the level of group fairness in several existing voting rules, as well as the trade-offs between fairness and privacy, showing that it is not possible to always obtain maximal economic efficiency with high fairness or high privacy levels. Then, we present both a machine learning and a constrained optimization approach to design new voting rules that are fair while maintaining a high level of economic efficiency. Finally, we empirically examine the effect of adding noise to create local differentially private voting rules and discuss the three-way trade-off between economic efficiency, fairness, and privacy.

Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, and Nisarg Shah

Class Fairness in Online Matching

We initiate the study of fairness among \textit{classes} of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions (e.g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves $\half$-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves $(\e)$-approximation of class envy-freeness and class proportionality; we prove $\e$ to be tight for class proportionality and establish a $\sfrac{3}{4}$ upper bound on class envy-freeness.

Nicolas Pastrian

Monopolistic Screening with Buyers Who Sample

We study a monopolistic screening problem with boundedly rational buyers and a noisy communication technology. In our model the seller designs a menu of quality-price pairs to a continuum of buyers that remain unaware of the offered menu. Instead, buyers will have access only to a finite number of samples from the menu offered by the seller and then decide which sampled alternative to purchase if any. This procedure give arise to random consideration sets from the perspective of the buyers. We show that if there is a single sample available, the seller will optimally choose to offer a single alternative, while if two samples are available then neither offering a single alternative nor two alternatives is necessarily optimal.

Maneesha Papireddygari, Rafael Frongillo and Bo Waggoner

An Axiomatic and Elicitation Perspective on Market Makers for Decentralized Exchanges

We introduce axioms for general asset market making, and apply them to study automated maker makers for decentralized exchanges. Our first result is a characterization of constant-function market makers (CFMMs) without transaction fees. We then give a general conceptual bridge between asset market making and Arrow-Debreu prediction markets. As a special case, we derive a precise equivalence between CFMMs and cost-function market makers from the prediction markets literature.

Jiaxin Song, Xiaolin Bu, Zihao Li, Shengxin Liu, Biaoshuai Tao

On the Complexity of Maximizing Social Welfare of Indivisible Items within Fairness Constraints

Fair division is a classical topic studied in various disciplines and captures many real applications. One important issue in fair division is to cope with (economic) efficiency and fairness. A natural question along this direction that receives considerable attention is: How to obtain the most efficient allocations among all the fair allocations? In this paper, we study the complexity of maximizing social welfare within envy-free up to one item (EF1) allocations of indivisible goods for both normalized and unnormalized valuations. With two agents, we show a fully polynomial time approximation scheme (FPTAS) and complement this positive result with the NP-hardness result where the latter resolves an open problem raised by the previous work. Further, when the number of agents n is a constant, we provide a bi-criteria algorithm that finds the optimal social welfare while relaxing EF1 by a factor arbitrarily close to 1. We complement this by providing several strong inapproximability results if EF1 is not allowed to relax. In particular, we demonstrate that the inapproximability becomes stronger as n increases. Last, we consider the case with a general number of agents. In this case, we give a variant of the round-robin algorithm with an approximation ratio of 1/n for unnormalized valuations and provide inapproximability results of n^{1/3−ε} and m^{1/2−ε} for normalized valuations. In addition, we show that our results of bi-criteria optimization for constant n cannot be extended to the setting here unless P=NP.

Qishen Han, Grant Schoenebeck, Biaoshuai Tao, Lirong Xia

Do not Worry about Equilibrium Selection in Binary Voting

We study the Condorcet Jury Theorem under a game-theoretical context. A key challenge in such a setting is the multiplicity of equilibria. We reveal the surprising equivalence between a strategy profile being a strong equilibrium and leading to the decision favored by the majority: every epsilon-strong equilibrium with small epsilon formed by strategic agents will lead to a good collective decision. We quantify the probability of error which goes to 0 as the number of agents grows. In our model, voters' preferences between two alternatives depend on a discrete state variable that is not directly observable. Each voter receives a private signal that is correlated with the state variable.

Zihan Tan, Yifeng Teng and Mingfei Zhao

Worst-Case Welfare of Item Pricing in the Tollbooth Problem

We study the worst-case welfare of item pricing in the tollbooth problem. The problem was first introduced by Guruswami et al., and is a special case of the combinatorial auction in which (i) each of the $m$ items in the auction is an edge of some underlying graph; and (ii) each of the n buyers is single-minded and only interested in buying all edges of a single path. We consider the competitive ratio between the hindsight optimal welfare and the optimal worst-case welfare among all item-pricing mechanisms, when the order of the arriving buyers is adversarial. We assume that buyers own the tie-breaking power, i.e. they can choose whether or not to buy the demand path at 0 utility. We prove a tight competitive ratio of 3/2 when the underlying graph is a single path (also known as the highway problem), whereas item-pricing can achieve the hindsight optimal if the seller is allowed to choose a proper tie-breaking rule to maximize the welfare. Moreover, we prove an O(1) upper bound of the competitive ratio when the underlying graph is a tree. For general graphs, we prove an \Omega(m^{1/8}) lower bound of the competitive ratio. We show that an m^{\Omega(1)} competitive ratio is unavoidable even if the graph is a grid, or if the capacity of every edge is augmented by a constant factor c. The results hold even if the seller has tie-breaking power.

Yue Han, Christopher Jerrett, Elliot Anshelevich

Optimizing Multiple Simultaneous Objectives for Voting and Facility Location

We study the classic facility location setting, where we are given $n$ clients and $m$ possible facility locations in some arbitrary metric space, and want to choose a location to build a facility. The exact same setting also arises in spatial social choice, where voters are the clients and the goal is to choose a candidate or outcome, with the distance from a voter to an outcome representing the cost of this outcome for the voter (e.g., based on their ideological differences). Unlike most previous work, we do not focus on a single objective to optimize (e.g., the total distance from clients to the facility, or the maximum distance, etc.), but instead attempt to optimize several different objectives *simultaneously*. More specifically, we consider the l-centrum family of objectives, which includes the total distance, max distance, and many others. We present tight bounds on how well any pair of such objectives (e.g., max and sum) can be simultaneously approximated compared to their optimum outcomes. In particular, we show that for any such pair of objectives, it is always possible to choose an outcome which simultaneously approximates both objectives within a factor of $1+\sqrt{2}$, and give a precise characterization of how this factor improves as the two objectives being optimized become more similar. For $q>2$ different centrum objectives, we show that it is always possible to approximate all $q$ of these objectives within a small constant, and that this constant approaches 3 as q increases. Our results show that when optimizing only a few simultaneous objectives, it is always possible to form an outcome which is a significantly better than 3 approximation for all of these objectives.

TBD

Monday, December 12 (Virtual Tutorial Day)

9:00-11:00

Economics of Distributed Systems

11:00-13:00 Break
13:00-15:00

AI and Marketing

15:00-15:30 Break
15:30-17:30

Machine Learning in Strategic Settings

Tuesday, December 13

CBIS Auditorium (west end of the building) or on Virtual Chair
8:30-8:55 Breakfast
8:55-9:00 Welcome
9:00-10:00
Session 1: Invited talk
Chair: Tracy Liu
Invited talk: Marzena Rostek. Decentralized-Market Design
10:00-10:30 Coffee break
10:30-11:30
Session 2: Mechanism Design
Chair: Mithun Chakraborty
Pinyan Lu, Enze Sun and Chenghan Zhou. Better Approximation for Interdependent SOS Valuations
Xiaohui Bei, Zihao Li and Junjie Luo. Fair and Efficient Multi-Resource Allocation for Cloud Computing
Yi-Chun Chen, Gaoji Hu and Xiangqian Yang. Information Design in Allocation with Costly Verification
11:20-11:40 Coffee break
11:40-12:40
Session 3: Learning, Algorithm and Pricing
Chair:
Jad Salem, Swati Gupta and Vijay Kamble. Algorithmic Challenges in Ensuring Fairness at the Time of Decision
Tim Oosterwijk, Daniel Schmand and Marc Schroder. Bicriteria Nash Flows over Time
Siddharth Barman, Anand Krishna, Yadati Narahari and Soumyarup Sadhukhan. Nash Welfare Guarantees for Fair and Efficient Coverage
12:40-14:10 Lunch at EMPAC: the Mezzanine area
14:10-15:10
Session 4: Social Choice
Chair:
Kamesh Munagala, Yiheng Shen and Kangning Wang. Auditing for Core Stability in Participatory Budgeting
Lirong Xia and Weiqiang Zheng. Beyond the Worst Case: Semi-Random Complexity Analysis of Winner Determination
Grzegorz Pierczyński and Piotr Skowron. Core-Stable Committees under Restricted Domains
15:10-15:40 Coffee break
15:40-16:40
Session 5: Learning, Algorithm and Pricing
Chair: Will Ma
Moshe Babaioff, Tomer Ezra and Uriel Feige. On Best-of-Both-Worlds Fair-Share Allocations
Susanne Albers and Sebastian Schubert. Online Ad Allocation in Bounded-Degree Graphs
Melika Abolhassani, Hossein Esfandiari, Yasamin Nazari, Balasubramanian Sivan, Yifeng Teng and Creighton Thomas. Online Allocation and Display Ads Optimization with Surplus Supply
16:40-16:50 Break
16:50-17:30
Session 6: Market Design
Chair: Tomer Ezra
Pan Xu. Exploring the Tradeoff between Competitive Ratio and Variance in Online-Matching Markets
Itai Feigenbaum. Strategyproofness in Kidney Exchange with Cancellations

Wednesday, December 14

CBIS Auditorium (west end of the building) or on Virtual Chair

8:00-9:00 Breakfast and business meeting
9:00-10:00
Session 1: Invited talk
Chair: Azarakhsh Malekian
Invited talk: David Simchi-Levi. Statistical Learning in Operations: The Interplay between Online and Offline learning
10:00-10:30 Coffee break
10:30-11:10
Session 7: Game Theory
Chair: Zhigang Cao (Virtual)
Xiaotie Deng, Ningyuan Li, Weian Li and Qi Qi. Competition Among Parallel Contests
Zhibin Tan, Zhigang Cao and Zhengxing Zou. Matrix-exact Covers of Minimum-Cost-Spanning-Tree Games
11:10-11:20 Break
11:20-12:40 Spotlight papers
12:40-14:10 Lunch at EMPAC: the Mezzanine area
14:10-14:50
Session 8: Best Paper
Chair: David Pennock
Peng Shi and Junxiong Yin. Eliminating Waste in Cadaveric Organ Allocation
Yurong Chen, Xiaotie Deng and Yuhao Li. Optimal Private Payoff Manipulation against Commitment in Extensive-form Games
14:50-15:00 Break
15:00-16:00
Session 9: Keynote Speech
Chair: Lirong Xia
Invited talk: Vincent Conitzer.
16:00-16:30 Coffee break
16:30-17:30
Session 10: Network
Chair: Andson Balieiro
Bainian Hao and Carla Michini. Inefficiency of pure Nash equilibria in series-parallel network congestion games
Tong Xie and Zizhuo Wang. Personalized Assortment Optimization under Consumer Choice Models with Local Network Effects
Hu Fu, Qun Hu and Jia'Nan Lin. Stability of Queueing Networks Beyond Complete Bipartite Cases
17:30-17:40 Break
17:40-18:20
Session 11: Learning
Chair: Chun Wang
Will Ma and David Simchi-Levi. Constructing Demand Curves from a Single Observation of Bundle Sales
Yumou Fei. Improved Approximation to First-Best Gains-from-Trade

Thursday, December 15

CBIS Auditorium (west end of the building) or on Virtual Chair

8:00-9:00 Breakfast and the virtual poster session
9:00-10:00
Session 1: Invited talk
Chair: Kristoffer Arnsfelt Hansen
Invited talk: Robert Kleinberg
10:00-10:30 Coffee break
10:30-11:30
Session 12: Game Theory
Chair: Rohit Vaish (virtual)
Christine Konicki, Mithun Chakraborty and Michael Wellman. Exploiting Extensive-Form Structure in Empirical Game-Theoretic Analysis
Mengqian Zhang, Yuhao Li, Jichen Li, Chaozhe Kong and Xiaotie Deng. Insightful Mining Equilibria
Haris Aziz, Alexander Lam, Barton Lee and Toby Walsh. Strategyproof and Proportionally Fair Facility Location
11:30-11:40 Break
11:40-12:40
Session 13: Learning
Chair: Yuqing Kong (virtual)
Matthew Eichhorn, Siddhartha Banerjee and David Kempe. Online Team Formation under Different Synergies
Titing Cui and Michael Hamilton. Optimal Feature-Based Market Segmentation and Pricing
Javier Cembrano, Felix Fischer and Max Klimm. Optimal Impartial Correspondences
12:40-14:10 Lunch at EMPAC: the Mezzanine area
14:10-15:10
Session 14: Mechanism Design
Chair: Sujoy Sikdar (virtual)
Sumit Goel and Wade Hann-Caruthers. Project selection with partially verifiable information
Cuimin Ba. Robust Model Misspecification and Paradigm Shifts
Atanas Dinev and S. Matthew Weinberg. Tight Bounds on 3-Team Manipulations in Randomized Death Match
15:10-15:40 Coffee break
15:40-16:40
Session 15: Learning
Chair: Yifeng Teng
Nick Gravin, Hao Li and Zhihao Gavin Tang. Optimal Prophet Inequality with Less than One Sample
Boris Epstein and Will Ma. Order Selection Problems in Hiring Pipelines
Jugal Garg, Edin Husić, Aniket Murhekar and László Végh. Tractable Fragments of the Maximum Nash Welfare Problem
16:40-16:50 Break
16:50-17:30
Session 16: Revenue Management
Chair: Pan Xu
Bo Jiang, Zizhuo Wang and Nanxi Zhang. Revenue Management Under a Price Alert Mechanism
Adam Elmachtoub, Vineet Goyal, Roger Lederman and Harsh Sheth. Revenue Management with Product Retirement and Customer Selection
Yuan Qiu, Jinyan Liu and Di Wang. Truthful Generalized Linear Models

Invited Speakers


Vincent Conitzer

Professor of Computer Science, Economics and Philosophy,
Carnegie Melon University
Director of the Foundations of Cooperative AI Lab


Robert Kleinberg

Professor of Computer Science, Cornell University


Marzena Rostek

Juli Plant Grainger Distinguished Chair of Economics,
University of Wisconsin-Madison

Title: Decentralized-Market Design

Most markets are fragmented; many are dominated by large traders who have price impact. One of the most salient developments in market design in recent years has been the work motivated by new data and questions concerning market fragmentation and imperfect competition. This talk will review recent advances in the literature on (primarily though not exclusively financial) market design and highlight active research areas.

Bio. Marzena Rostek is the Juli Plant Grainger Distinguished Chair of Economics at the University of Wisconsin-Madison. She received her Ph.D. from Yale University (2006) and was a postdoctoral research fellow at Nuffield College at Oxford University (2007/8). Her research is in the area of market design, with a special focus on the effects of market fragmentation and the strategic behavior of large players. Rostek currently serves as an editor of the Journal of Economic Theory and an associate editor of Econometrica, Economic Theory, Economic Theory Bulletin, and the Journal of Economic Literature. She is a board member of the Finance Theory Group, and a Fellow of the Econometric Society and the Society for the Advancement of Economic Theory.

David Simchi-Levi

Professor of Engineering Systems, MIT
Director of MIT Data Science Lab

Title: Statistical Learning in Operations: The Interplay between Online and Offline learning

Machine learning is playing an increasingly important role in decision making, with key applications ranging from dynamic pricing and recommendation systems to personalized medicine and clinical trials. While supervised machine learning traditionally excels at making predictions based on i.i.d. offline data, many modern decision-making tasks require making sequential decisions based on data collected online. Bridging the gap between offline supervised learning and online decision making may help significantly improve decisions. In this talk, we first show how difficult online decision-making problems can be reduced to well-understood offline regression problems. We than show the impact of pre-existing offline data on online learning and characterize conditions under which offline data helps (does not help) improve online learning. We demonstrate the impact of our work in the context of recommendation systems, multiclass classification problems and dynamic pricing.

Bio. David Simchi-Levi is a Professor of Engineering Systems at MIT and serves as the head of the MIT Data Science Lab. He is considered one of the premier thought leaders in supply chain management and business analytics. His Ph.D. students have accepted faculty positions in leading academic institutes including U. of California Berkeley, Carnegie Mellon U., Columbia U., Cornell U., Duke U., Georgia Tech, Harvard U., U. of Illinois Urbana-Champaign, U. of Michigan, Purdue U. and Virginia Tech. Professor Simchi-Levi is the current Editor-in-Chief of Management Science, one of the two flagship journals of INFORMS. He served as the Editor-in-Chief for Operations Research (2006-2012), the other flagship journal of INFORMS and for Naval Research Logistics (2003-2005). In 2020, he was awarded the prestigious INFORMS Impact Prize for playing a leading role in developing and disseminating a new highly impactful paradigm for the identification and mitigation of risks in global supply chains. He is an INFORMS Fellow and MSOM Distinguished Fellow and the recipient of the 2020 INFORMS Koopman Award given to an outstanding publication in military operations research; Ford Motor Company 2015 Engineering Excellence Award; 2014 INFORMS Daniel H. Wagner Prize for Excellence in Operations Research Practice; 2014 INFORMS Revenue Management and Pricing Section Practice Award; and 2009 INFORMS Revenue Management and Pricing Section Prize. He was the founder of LogicTools which provided software solutions and professional services for supply chain optimization. LogicTools became part of IBM in 2009. In 2012 he co-founded OPS Rules, an operations analytics consulting company. The company became part of Accenture in 2016. In 2014, he co-founded Opalytics, a cloud analytics platform company focusing on operations and supply chain decisions. The company became part of the Accenture Applied Intelligence in 2018.

General Chairs

Program Committee Chairs

Senior Program Committee Members

Program Committee Members

Steering Committee

Tutorials Dec 12

1. Economics of Distributed Systems (9-11 am ET)

The design of consensus protocols for blockchain applications is an emerging field at the intersection of economics and computation. The field is truly interdisciplinary, requiring background in areas not typically present at EC, such as distributed computing and cryptography. The goal of this tutorial is to provide background in these core areas, and connect them to modern blockchain research. The tutorial will cover the following themes:

  • Theory of Distributed Systems This section of the tutorial will cover classical modeling approaches and impossibility results. It will also introduce simple, practical algorithms, and relate this theory to modern cryptocurrencies like Bitcoin.
  • Cryptography This section of the tutorial will introduce cryptographic primitives through the lens of ‘replacing a trusted mediator’, and use this view to relate these concepts to modern cryptocurrencies.
  • Mechanism Design Challenges This section of the tutorial will briefly highlight existing examples of work with an EC flavor, and describe their models through lenses introduced by the previous two themes.

This tutorial will be accessible to both Economists and Computer Scientists. No prior knowledge of distributed systems or cryptography will be assumed. We hope that the tutorial will also be valuable to researchers in the EC community with moderate background in distributed systems or cryptography, and who wish to engage further with blockchain research.

2. AI and Marketing (1-3 pm ET)

  • Oded Netzer (Columbia University)Automating the B2B Salesperson Pricing Decisions: Can Machines Replace Humans and When? (AI Ethics)
  • Gideon Nave (University of Pennsylvania, Wharton)We Are What We Watch: Movie Plots Predict the Personalities of Their Fans (Supervised Learning, NLP)
  • Robert Moakler (Meta) – Close enough? A large-scale exploration of non-experimental approaches to advertising measurement (Machine learning for Causal inference)
  • Xiao Liu (New York University, Stern)Dynamic Coupon Targeting Using Batch Deep Reinforcement Learning: An Application to Livestream Shopping (Reinforcement Learning)

Marketing, according to Phillip Kotler’s textbook, is the process by which companies create value for customers and build strong customer relationships to capture value from customers in return. Marketing contains the marketing mix, which is the four Ps, namely, product, price, place, and promotion strategies. So, in essence, we can think of marketing research as a function f, which connects the 4P strategies, or the X variables, to the outcome Y variable, which is the customer value and relationship, i.e., Y=f(X).

AI can affect each element in this function and each of the 4Ps. And the way AI helps solve marketing questions depends on the type of the question, namely, descriptive, predictive, or prescriptive questions. If the question is descriptive, AI can help describe the marketing stimuli by creating new variables from unstructured data, i.e., new X and Y variables. For instance, in this tutorial, one study will demonstrate how to use NLP algorithms to analyze movies, a popular product for consumers. If the question is predictive where the variable interest is the predicted outcome, beta Y, AI can be used for more accurate prediction. For instance, one paper in this tutorial uses machine learning algorithms to predict firm profit. If the question is prescriptive, AI can assist in scalable causal inference and policy designs via innovations in the f function. In this tutorial, we demonstrate two examples of prescriptive questions, one in a static setting for promotion analysis (advertisement effect measurement) and the other in a dynamic setting for pricing. Lastly, we also discuss an AI ethics topic about whether machines can replace humans in a standard marketing place, the B2B salesforce context.

3. Machine Learning in Strategic Settings (3:30-5:30 ET)

This tutorial will cover the setting where a deployed machine learning model will face strategic actions at the test time. In this setup, each data (X (feature),Y (label)) that is to be classified will correspond to an agent who can respond in their own best interest by reporting an X’ that can differ from X. Knowing the presence of strategic behavior, the goal of the learner is to train a model (using the available training data) that minimizes the test prediction error while carrying the thought that the test data will come from the agent’s strategic reports. This above setting is often referred to as the “strategic machine learning” problem.

The tutorial will start by briefly introducing adversarial machine learning, a highly relevant concept, and the “classical” way of looking at this class of problems from the machine learning+security perspective. We then introduce the formal setup of strategic machine learning, motivated by different considerations and targeting different domains, but with most models having a similar formalization. We will discuss the technical challenges, as well as solutions to this problem. Several variants of the strategic machine learning setups will be discussed as well. The second half of the tutorial will highlight some emerging challenges and technical questions, including fairness concerns in the strategic machine learning setting.

TBD

By Air

The nearest airport is Albany International Airport (ALB). Major US airline companies offer flights to the Albany International airport.

By Train

Albany–Rensselaer station serves 10 trains each way between Albany and New York City per day. Each trip takes about 2.5 hours. There are also at least two buses between Albany and Boston per day. Each trip takes about 3.5 hours.

From Airport/Train/Bus station to RPI

The best way is by taxi, Uber, or Lyft. Public transportation in Albany area is not very convenient.

Location

The main conference venue is CBIS Auditorium and Gallery at RPI (marked in red)

Accommodation

Two hotels are within walking distance (see the map above). Please make your reservation directly with the hotel.

Hotels that need driving. Please make your reservation directly with the hotel.

More affordable housing options can be found on airbnb.


Registrations on or before
November 12, 2022
Registrations after
November 12, 2022
Students $100 $150
Regular rate applied to all others $200 $300
Virtual attendance $50 $50

Cancellation deadline: Dec. 1

  • All registrations must be prepaid with a credit card (VISA/Mastercard accepted) or echeck at the time of registration.
  • Registration fees include: participation in the main conference (Dec 13-15), tutorial day (Dec 12), as well as breakfast, lunch, breaks and any scheduled social events (if applicable) during the main conference days (Dec 13-15).