Showing posts with label computer science. Show all posts
Showing posts with label computer science. Show all posts

Sunday, February 11, 2024

Fourth SIGecom Winter Meeting , Thursday, February 15, 2024

 I'll see some you Thursday, online, in Gather.town.

The Fourth Annual ACM SIGecom Winter Meeting will take place Thursday, February 15, 2024, at 11am–5pm Eastern time.  The workshop will take place on the Gather.town platform. 

"This year's topic is behavioral models. The meeting will feature two introductory talks and four research presentations that reflect an array of perspectives and active research directions. The event will also feature a fireside conversation with Noam Nisan and Al Roth."

Program

All times listed in US Eastern Time Zone (ET). All talks will take place in the auditorium unless otherwise noted.

11:10 - 1:00pm: Introductory Talks

11:10am - 12:00pm: John Kleinberg

12:00pm - 12:10pm: Break

12:10pm - 1:00pm: Ori Heffetz


1:00pm - 2:30pm: Social Break


1:15pm - 1:45pm: Student Fireside Chat with Noam Nisan and Al Roth


1:45pm - 2:30pm: SIGecom social events


2:30pm - 5:00pm: Spotlight talks

2:30pm - 3:00pm: Modibo Camara

3:00pm - 3:30pm: Ryan Oprea

3:30pm - 3:45pm: Break

3:45pm - 4:15pm: Gali Noti

4:15pm - 4:45pm: Nicole Immorlica


4:45pm - 5:00pm: Concluding Remarks

5:00pm - 6:00pm: Closing Reception

Organizers: Sigal Oren and Ran Shorrer

Monday, January 29, 2024

"There are tradeoffs everywhere" Alfred Spector on artificial intelligence.

 Alfred Spector has written an article called : Gaining Benefit from AI and Data Science: A Three-Part Framework. Among other things, he argues that neither technologists alone, nor ethicists alone, will find themselves automatically well equipped to think about the tradeoffs involved in developing, deploying, and regulating artificial intelligence.  

Here's a short (5 min) video produced by the ACM in which he calls for a broad approach.

Gaining Benefit from Artificial Intelligence and Data Science: A Three-Part Framework from CACM on Vimeo.

Saturday, December 2, 2023

Design of (international) kidney exchange: ex-post rejection versus ex-ante withholding

 Here's a paper by several Dutch computer scientists, which seems to be motivated by the problem of international kidney exchange within the EU, in which there are lots of concerns about fairness between countries.  But (as the paper notes) these could also apply to individual transplant centers, in the U.S. context.  The thrust of the paper is that looking for exchanges that won't be rejected ex post in a full information environment may be more productive than looking for ways to incentivize countries or transplant centers to reveal their full sets of patient donor pairs in an incomplete information environment.

Blom, Danny, Bart Smeulders, and Frits Spieksma. "Rejection-Proof Mechanisms for Multi-Agent Kidney Exchange." Games and Economic Behavior (2023).

Abstract: Kidney exchange programs (KEPs) increase kidney transplantation by facilitating the exchange of incompatible donors. Increasing the scale of KEPs leads to more opportunities for transplants. Collaboration between transplant organizations (agents) is thus desirable. As agents are primarily interested in providing transplants for their own patients, collaboration requires balancing individual and common objectives. In this paper, we consider ex-post strategic behavior, where agents can modify a proposed set of kidney exchanges. We introduce the class of rejection-proof mechanisms, which propose a set of exchanges such that agents have no incentive to reject them. We provide an exact mechanism and establish that the underlying optimization problem is 


we also describe computationally less demanding heuristic mechanisms. We show rejection-proofness can be achieved at a limited cost for typical instances. Furthermore, our experiments show that the proposed rejection-proof mechanisms also remove incentives for strategic behavior in the ex-ante setting, where agents withhold information.

Friday, December 1, 2023

Fairness in algorithms: Hans Sigrist Prize to Aaron Roth

 The University of Bern's Hans Sigrist Prize has been awarded to Penn computer scientist Aaron Roth, and will be celebrated today.

Here are today's symposium details and schedule:

Here's an interview:

Aaron Roth: Pioneer of fair algorithms  In December 2023, the most highly endowed prize of the University of Bern will go to the US computer scientist Aaron Roth. His research aims to incorporate social norms into algorithms and to better protect privacy.  by Ivo Schmucki 

"There are researchers who sit down and take on long-standing problems and just solve them, but I am not smart enough to do that," says Aaron Roth. "So, I have to be the other kind of researcher. I try to define a new problem that no one has worked on yet but that might be interesting."

"Aaron Roth's own modesty may stand in the way of understanding the depth of his contributions. In fact, when he authored his doctoral thesis on differential privacy about 15 years ago and then wrote on the fairness of algorithms a few years later, terms like “Artificial Intelligence” and “Machine Learning” were far from being as firmly anchored in our everyday lives as they are today. Aaron Roth was thus a pioneer, laying the foundation for a new branch of research.

"I am interested in real problems. Issues like data protection are becoming increasingly important as more and more data is generated and collected about all of us," says Aaron Roth about his research during the Hans Sigrist Foundation’s traditional interview with the prize winner. He focuses on algorithmic fairness, differential privacy, and their applications in machine learning and data analysis.

...

"It is important that more attention is paid to these topics," says Mathematics Professor Christiane Tretter, chair of this year's Hans Sigrist Prize Committee. Tretter says that many people perceive fairness and algorithms as two completely different poles, situated in different disciplines and incompatible with each other. "It is fascinating that Aaron Roth’s work shows that this is not a contradiction."

...

"The first step to improving the analysis of large data sets is to be aware of the problem: "We need to realize that data analysis can be problematic. Once we agree on this, we can consider how we can solve the problems," says Aaron Roth."





Wednesday, September 27, 2023

Facial recognition software and autocracy

 Here's a somewhat chilling recent NBER paper:

Exporting the Surveillance State via Trade in AI  by Martin Beraja, Andrew Kao, David Y. Yang & Noam Yuchtman  WORKING PAPER 31676   DOI 10.3386/w31676  September 2023

We document three facts about the global diffusion of surveillance AI technology, and in particular, the role played by China. First, China has a comparative advantage in this technology. It is substantially more likely to export surveillance AI than other countries, and particularly so as compared to other frontier technologies. Second, autocracies and weak democracies are more likely to import surveillance AI from China. This bias is not observed in AI imports from the US or in imports of other frontier technologies from China. Third, autocracies and weak democracies are especially more likely to import China’s surveillance AI in years of domestic unrest. Such imports coincide with declines in domestic institutional quality more broadly. To the extent that China may be exporting its surveillance state via trade in AI, this can enhance and beget more autocracies abroad. This possibility challenges the view that economic integration is necessarily associated with the diffusion of liberal institutions.

Saturday, September 9, 2023

Computer science award

A computer scientist whose work I follow has won an award that reflects on both his teachers and students.

Aaron Roth receives 2023 CyLab Distinguished Alumni Award 

"Aaron Roth, the Henry Salvatori Professor of Computer Science and Cognitive Science at the University of Pennsylvania, has been named CyLab's 2023 Distinguished Alumni Award winner.

...

"Roth earned his Ph.D. in Computer Science from Carnegie Mellon University in 2010, where he was advised by former CMU Professor Avrim Blum. His dissertation, 'New Algorithms for Preserving Differential Privacy,' gave new methods for performing computations on private data.

"Nominated by his former advisee, now Assistant Professor in CMU's School of Computer Science, Steven Wu, the award recognizes Roth's excellence in algorithms and machine learning, leadership in the field, and commitment to his students.

"As my advisor, Aaron is nothing less than a beacon of inspiration, marked by his relentless curiosity, exceptional instinct for identifying the most exciting questions, creative problem-solving acumen, and impeccable eloquence in communication," said Wu.

"Advising is one of the best parts of my job," said Roth. "Being recognized by one of my former students at the University where I earned my Ph.D. is really special."

Monday, May 29, 2023

Further progress on course allocation, by Budish, Gao, Othman, Rubinstein and Zhang

 Here are some new developments in the course allocation mechanism used initially in Wharton and now elsewhere.  It turns out that strategy-proofness in the (very) large doesn't imply strategyproofness in samples of realistic size, but this seems to be fixable (and profitable manipulations were not easy to find). The paper concludes with some far ranging thoughts on the econ-cs interface.

Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)   by ERIC BUDISH, RUIQUAN GAO, ABRAHAM OTHMAN  AVIAD RUBINSTEIN, and QIANFAN ZHANG

Abstract: "Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an equilibrium-based solution concept for fair division of discrete items to agents with combinatorial demands. In theory, it is known that in asymptotically large markets:

•For incentives, the A-CEEI mechanism is Envy-Free-but-for-Tie-Breaking (EF-TB), which implies that it is Strategyproof-in-the-Large (SP-L).

•From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming PPAD≠FP).

We develop a new heuristic algorithm that outperforms the previous state-of-the-art by multiple orders of magnitude. This new, faster algorithm lets us perform experiments on real-world inputs for the first time. We discover that with real-world preferences, even in a realistic implementation that satisfies the EF-TB and SP-L properties, agents may have surprisingly simple and plausible deviations from truthful reporting of preferences. To this end, we propose a novel strengthening of EF-TB, which dramatically reduces the potential for strategic deviations from truthful reporting in our experiments. A (variant of ) our algorithm is now in production: on real course allocation problems it is much faster, has zero clearing error, and has stronger incentive properties than the prior state-of-the-art implementation"

Here's an intriguing passage:

"In Section 6 we use our manipulation-finding algorithm in combination with our fast A-CEEI finding algorithm to explore the plausibility of effective manipulations for students bidding in ACEEI. Originally, we had expected that since our mechanism satisfies the EF-TB and SP-L properties, it would at least be practically strategyproof — if even we don’t really understand the way our algorithm chooses among the many possible equilibria, how can a student with limited information learn to strategically bid in such a complex environment? 

"Indeed, in 2 out of 3 schools that we tested, our manipulation-finding algorithms finds very few or no statistically significant manipulations at all. However, when analyzing the 3rd school, we stumbled upon a simple and effective manipulation for (the first iteration of) our mechanism. We emphasize that although the manipulation is simple in hindsight, in over a year of working on this project we failed to predict it by analyzing the algorithm — the manipulation was discovered by the algorithm

"Inspired by this manipulation, we propose a natural strengthening of envy-free (discussed below), which we call contested-envy free. We encode the analogous contested EF-TB as a new constraint in our algorithm (specifically, the integer program for finding optimal budget perturbations). Fortunately, our algorithm is still very fast even with this more elaborate constraint. And, when we re-run our manipulation-finding experiments, we observe that contested EF-TB significantly reduces the potential for manipulations in practice."

...

"Conclusion:  In this work, we give a significantly faster algorithm for computing A-CEEI. Kamal Jain’s famous formulation “if your laptop cannot find it then neither can the market” [Papadimitriou 2007] was originally intended as a negative result, casting doubt on the practical implications of many famous economic concepts because of their worst-case computational complexity results. Even for course allocation, where a heuristic algorithm existed and worked in practice, Jain’s formulation seemed to still bind, as solving A-CEEI involved an intense day-long process with a fleet of high-powered cloud servers operating in parallel. The work detailed in this paper has significantly progressed what laptops can find: even the largest and most challenging real course allocation problems we have access to can now be solved in under an hour on a commodity laptop. 

"This significant practical improvement suggests that the relationship between prices and demand for the course allocation problem—and potentially other problems of economic interest with complex agent preferences and heterogeneous goods—may be much simpler than has been previously believed and may be far more tractable in practice than the worst-case theoretical bounds. Recalling Jain’s dictum, perhaps many more market equilibria can be found by laptops—or, perhaps, Walras’s original and seemingly naive description of how prices iterate in the real world may in fact typically produce approximate equilibria. 

"Our fast algorithm also opens the door for empirical research on A-CEEI, because we can now solve many instances and see how the solution changes for different inputs. We took it in one direction: empirically investigating the incentives properties of A-CEEI for the first time. For course allocation specifically, this faster algorithm opens up new avenues for improving student outcomes through experimentation. For instance, university administrators often want to subsidize some 6 group of students (e.g., second-year MBA students over first-year MBA students), but are unsure how large of a budget subsidy to grant those students to balance equity against their expectations. Being able to run more assignments with different subsidies can help to resolve this issue."

*************

Earlier related posts:

Thursday, April 23, 2009

Sunday, October 4, 2009

Thursday, May 30, 2013

Monday, August 3, 2015

Tuesday, June 9, 2020

Saturday, April 15, 2023

Jobs at risk from AI chatbots

 The WSJ has the alarming news:

The Fortune Cookie Industry Is in Upheaval. ‘Expect Big Changes Ahead.’ Factories split over whether to use software, instead of humans, to write the random bits of wisdom inside the wafers. ‘Society is moving too fast.’  By Angus Loten

"Over the past two decades, Charles Li, the owner and chief executive of Chicago-based fortune-cookie factory Winfar Foods Inc., has drawn on Chinese proverbs and popular sayings to write thousands of messages that go into the wafers. Mr. Li says he and his 80-year-old father-in-law spend long hours coming up with lines that are clever but still brief enough to fit on a ribbon of paper.

...

"OpenFortune Inc., a New York-based company that supplies printed messages to well over a dozen fortune-cookie factories around the world, says it has started using ChatGPT technology to potentially generate a near-limitless inventory of new messages.

"Making up the sayings in the cookies is a vigorous line of work. By some estimates, three billion fortune cookies are made by factories around the world every year. Nearly all are written by a handful of fortune-cookie factory owners, their families or small teams of copywriters."

Thursday, April 6, 2023

Introductory workshops to the Mathematics and Computer Science of Market and Mechanism Design semester at Berkeley MSRI

 The semester of Mathematics and Computer Science of Market and Mechanism Design August 21, 2023 to December 20, 2023 at Berkeley will lead off with two introductory sessions:

Connections Workshop: Mathematics and Computer Science of Market and Mechanism Design  September 07, 2023 - September 08, 2023

REGISTRATION DEADLINE: AUGUST 18, 2023

TO APPLY FOR FUNDING YOU MUST REGISTER BY: MAY 17, 2023

Organizers Michal Feldman (Tel-Aviv University), LEAD Nicole Immorlica (Microsoft Research)

"The Connections Workshop will consist of invited talks from leading researchers at all career stages in the field of market design.  Particular attention will be paid to real-world applications.  There will also be an AMA focused on career paths with highly visible individuals in the field, and a social event intended to help workshop attendees network with each other."

and

Introductory Workshop: Mathematics and Computer Science of Market and Mechanism Design  September 11, 2023 - September 15, 2023

REGISTRATION DEADLINE: AUGUST 25, 2023  TO APPLY FOR FUNDING YOU MUST REGISTER BY: MAY 21, 2023  

Organizers Scott Kominers (Harvard Business School), Paul Milgrom (Stanford University), Alvin Roth (Stanford University), Eva Tardos (Cornell University)

"The workshop  will  open  with  overview/perspective  talks  on  algorithmic  game  theory  and  the theory and practice of market design; the afternoon will feature a panel on active research areas in the field (again, at the overview level). The next 2 days will consist of introductory mini-course and tutorials, on topics such as game theory, matching, auctions, and mechanism design. The following day will focus on applicable tools and technology, such as lattice theory, limit methods, continuous optimization, and extremal graph theory. The workshop will conclude with a panel discussion on major open problems."


Earlier announcement:

Tuesday, November 8, 2022

Tuesday, December 6, 2022

Test of Time Award: call for nominations

 Test of Time Award

"The SIGecom Test of Time Award recognizes the author or authors of an influential paper or series of papers published between ten and twenty-five years ago that has significantly impacted research or applications exemplifying the interplay of economics and computation.

...

"The 2023 SIGecom Test of Time Award will be given for papers published no earlier than 1998 and no later than 2013. Nominations are due by February 28th, 2023 

...

"The 2022 Test of Time Award Committee: Alvin Roth, Stanford University; Moshe Tennenholtz, The Technion; Noam Nisan (chair), The Hebrew University of Jerusalem"

Tuesday, November 8, 2022

Mathematics and Computer Science of Market and Mechanism Design, at Berkeley MSRI, August 21-December 20, 2023 (applications open)

 Apply now to join a semester of interdisciplinary workshops on market and mechanism design, from the point of view of mathematicians, computer scientists, and economists.

Mathematicsand Computer Science of Market and Mechanism Design at the Mathematical Sciences Research Institute in Berkeley, California, August 21, 2023 to December 20, 2023

 Seeking applications for Research Members and Postdoctoral Fellows:

  • Research Members are scholars in economics, computer science, operations research, mathematics, or related fields who have a PhD at the time of application and will be in residence for at least 30 consecutive days of the program.
  • Postdoctoral Fellows are scholars in those fields who received their PhD on or after August 31, 2018, and will be in residence for the entire program.

Apply here by December 1, 2022https://www.msri.org/web/msri/scientific/member-application

 Program Summary:

In recent years, economists and computer scientists have collaborated with mathematicians, operations research experts, and practitioners to improve the design and operations of real-world marketplaces. Such work relies on robust feedback between theory and practice, inspiring new mathematics closely linked – and directly applicable – to market and mechanism design questions. This cross-disciplinary program seeks to expand the domains in which existing market design solutions can be applied; address foundational questions regarding our ways of developing and evaluating mechanisms; and build useful analytic frameworks for applying theory to practical marketplace design.

 https://www.msri.org/programs/333

 Program Organizers:

Michal Feldman (Tel-Aviv University); Nicole Immorlica (Microsoft Research); Scott Kominers (Harvard Business School); Shengwu Li (Harvard University); Paul Milgrom (Stanford University); Alvin Roth (Stanford University); Tim Roughgarden (Columbia University); Eva Tardos (Cornell University)

 About MSRI:

Acknowledged as the premier center for collaborative mathematical research, MSRI  organizes and hosts semester-length programs that become the leading edge in that field of study. Mathematicians worldwide come to the Institute to engage in the research of classical fundamental mathematics, modern applied mathematics, statistics, computer science and other mathematical sciences.

 Questions? See attached flyer, or reach out to mcsorgs@msri.org

**********

This could be a nice way to spend a semester--apply now (MSRI loves company:)


Tuesday, September 20, 2022

Investment Incentives in Truthful Approximation Mechanisms by Akbarpour, Kominers, Li, Li and Milgrom

Computationally intractable optimization problems often allow approximate solutions that are 'close enough' to the optimal solution.  But these approximation algorithms can radically change the incentives to the participants, or not.  Here's a paper on frontier of market design and computer science, from the KIT — Paris — ZEW Workshop on Market Design from June 2022.

Investment Incentives in Truthful Approximation Mechanisms, by Mohammad Akbarpour, Scott Duke Kominers, Kevin Michael Li, Shengwu Li, and Paul Milgrom.   May 16, 2022

"Abstract: We study investment incentives in truthful mechanisms that allocate resources using approximation algorithms instead of exact optimization. In such mechanisms, the price a bidder pays to acquire resources is generally not equal to the change in other bidders’ welfare—and these externalities skew investment incentives. Some allocation algorithms are arbitrarily close to efficient, but create such perverse investment incentives that their worst-case welfare guarantees fall to zero when bidders can invest before participating in the mechanism. We show that an algorithm’s guarantees in the allocation and investment problems coincide if and only if that algorithm’s “confirming” negative externalities are sufficiently small. Algorithms that exclude confirming negative externalities entirely (XCONE algorithms) thus have the same worst-case performance for the allocation and investment problems."

 

A "confirming" negative externality is an investment that doesn't change the investor's allocation but imposes a negative externality on the market.

Wednesday, July 6, 2022

Mark Braverman wins Abacus Medal (formerly Nevanlinna Prize)

 Mark Braverman, a computer scientist whose work touches on mechanism design, has won the Abacus Medal of the International Mathematical Union.

Here are some links: citationvideowrite-upCV/publicationsproceedingsinterviewPlus magazine! article

Readers of this blog may be interested in these papers:

Optimization-friendly generic mechanisms without money

"The goal of this paper is to develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from n players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we call \apex (Adaptive Pricing Equalizing Externalities). The framework is sufficiently general to be combined with any optimization algorithm that is based on local search. We outline an agenda for studying the algorithm's properties and its applications. As a special case of applying the framework to the problem of one-sided assignment with lotteries, we obtain a strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits that there is a (fractional) allocation and a set of item prices such that the allocation is a competitive equilibrium given prices. We further show that there is always a reweighing of the players' utility values such that running unit-demand VCG with reweighed utilities leads to a HZ-equilibrium prices. Interestingly, not all HZ competitive equilibria come from VCG prices. As part of our proof, we re-prove the [HZ79] result using only Brouwer's fixed point theorem (and not the more general Kakutani's theorem). This may be of independent interest."

**********

Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations by Itai Ashlagi , Mark Braverman, Yash Kanoria , Peng Shi , Management Science, 2020, 66(5), pp.2163-2193.  https://doi.org/10.1287/mnsc.2018.3265

Abstract: "We study how to reduce congestion in two-sided matching markets with private preferences. We measure congestion by the number of bits of information that agents must (i) learn about their own preferences, and (ii) communicate with others before obtaining their final match. Previous results suggest that a high level of congestion is inevitable under arbitrary preferences before the market can clear with a stable matching. We show that when the unobservable component of agent preferences satisfies certain natural assumptions, it is possible to recommend potential matches and encourage informative signals such that the market reaches a stable matching with a low level of congestion. Moreover, under our proposed approach, agents have negligible incentive to leave the marketplace or to look beyond the set of recommended partners. The intuitive idea is to only recommend partners with whom there is a nonnegligible chance that the agent will both like them and be liked by them. The recommendations are based on both the observable component of preferences and signals sent by agents on the other side that indicate interest."

 ***********

Update: from Quanta.

The Scientist Who Developed a New Way to Understand Communication. Mark Braverman has spent his career translating thorny problems into the language of information complexity.  by Stephen Ornes

"While Braverman continues to guide the theory as his former students and postdocs push it forward, the bulk of his work is done. Now his interests are more focused on a new field called mechanism design, which uses the mathematical approaches of economics and game theory. "

Saturday, March 12, 2022

Summer School for Computational and Experimental Economics, Universitat Pompeu Fabra, June 12-19, 2022

 Here's the announcement (more at the links):

Summer School for Computational and Experimental Economics, Universitat Pompeu Fabra, Spain, June 12-19, 2022

Graduate students and young faculty interested in computational and experimental economics are invited to attend this intensive 7-day summer school (which will include the two-day Workshop on Computational and Experimental Economics on June 13-14, 2022).

The summer school will be held from June 12 to June 19 at Beslab of Universitat Pompeu Fabra, Spain. The summer school includes the two-day Workshop on Computational and Experimental Economics on June 13-14, 2022.

The deadline for applications is April 15, 2022.

Organizers

Guest lecturer

Monday, January 24, 2022

23rd ACM Conference on Economics and Computation (EC’22)--call for papers (by Feb 10)

 The deadline is 11:59pm EDT on Feb 10, but I'm guessing that papers have a good chance of being received as late as midnight.

23rd ACM Conference on Economics and Computation (EC’22): Call for Contributions

"TL;DR for Seasoned Authors:

Papers submitted to EC’22 must select one of four methodological tracks and up to two content areas. The list of tracks and content areas can be found below.

EC’22 is continuing the forward-to-journal option as in previous years.

EC’22 is currently planned as a primarily in-person event, with some components (e.g., poster sessions and tutorials) to be held either virtually or in a hybrid format. Presenters of accepted papers who cannot (or do not feel comfortable to) travel to EC’22 will have the option to present their paper virtually.

...

Timetable for Authors

February 10, 2022 (11:59 pm EST): Paper submission deadline

April 11, 2022 (11:59pm EDT): Reviews sent to authors for feedback

April 14, 2022 (11:59pm EDT): Author responses due

May 8, 2022: Paper accept/reject notifications

May 18, 2022 (11:59pm EDT): Camera-ready versions of accepted papers due

July 11-15, 2022: Conference technical program"

...

Program Chairs:

Sven Seuken (University of Zurich and ETH AI Center)

Ilya Segal (Stanford University)

Contact the PC chairs at ec22chairs@gmail.com 

Track Chairs:

Theory: Robert Kleinberg (Cornell University) and Aaron Roth (University of Pennsylvania)

Applied Modeling: Gabriel Weintraub (Stanford University)

Empirics: Georgios Zervas (Boston University)

AI: Kevin Leyton-Brown (University of British Columbia)


EC’22 will use the following areas:

Mechanism design

Auctions and pricing

Market design and matching markets

Contract design

Online platforms and applications

Econometrics, ML, and data science

Equilibria, learning, and dynamics in games

Social choice and voting theory

Social networks and social learning

Fair division

Market equilibria

Crowdsourcing and information elicitation

Privacy, algorithmic fairness, social good, and ethics

Blockchain and cryptocurrencies

Behavioral economics and bounded rationality


Area Chairs: Nick Arnosti (University of Minnesota)  Haris Aziz (University of New South Wales)  Moshe Babaioff (Microsoft Research)  Yakov Babichenko (Technion)  Bruno Biais (Toulouse School of Economics)  Martin Bichler (Technical University of Munich)  Larry Blume (Cornell University)  Liad Blumrosen (Hebrew University)  Benjamin Brooks (University of Chicago) Yang Cai (Yale University)  Agostino Capponi (Columbia University)  Yeon-Koo Che (Columbia University)  Rachel Cummings (Columbia University)  Nikhil Devanur (Amazon)  John Dickerson (University of Maryland)  Laura Doval (Columbia University)  Paul Duetting (Google Research)  Michal Feldman (Tel Aviv University)  Ashish Goel (Stanford University)  Hanna Halaburda (New York University Stern School of Business)  Hoda Heidari (Carnegie Mellon University)  Martin Hoefer (Goethe University Frankfurt)  Ian Kash (University of Illinois at Chicago)  Fuhito Kojima (University of Tokyo)  Nicolas Lambert (MIT)  Jacob Leshno (The University of Chicago Booth School of Business)  Shengwu Li (Harvard University)  Annie Liang (University of Pennsylvania)  Brendan Lucier (Microsoft Research)  Mohammad Mahdian (Google Research)  Azarakhsh Malekian (University of Toronto)  R. Preston McAfee  Reshef Meir (Technion)  Jamie Morgenstern (University of Washington)  Thayer Morril (North Carolina State University)  Denis Nekipelov (University of Virginia)  Sigal Oren (Ben-Gurion University)  Michael Ostrovsky (Stanford University)  Rafael Pass (Cornell University)  Ariel Procaccia (Harvard University)  Marek Pycia (University of Zurich)  Marzena Rostek (University of Wisconsin-Madison)  Jay Sethuraman (Columbia University)  Nisarg Shah (University of Toronto)  Peng Shi (University of Southern California)  Alex Slivkins (Microsoft Research)  Eric Sodomka  Nicolas Stier-Moses (Facebook)  Siddharth Suri (Microsoft Research)  Steve Tadelis (Berkeley–Haas)  Inbal Talgam-Cohen (Technion)  Alexander Teytelboym (University of Oxford)  Utku Unver (Boston College)  Vijay Vazirani (University of California, Irvine)  Jens Witkowski (Frankfurt School of Finance & Management)  James Wright (University of Alberta)  Lirong Xia (Rensselaer Polytechnic Institute)  Bumin Yenmez (Boston College)  Yair Zick (University of Massachusetts, Amherst)  Aviv Zohar (The Hebrew University of Jerusalem)

Monday, November 2, 2020

Ethics of machine learning--an interview with Michael Kearns and Aaron Roth

 Amazon Scholars Michael Kearns and Aaron Roth discuss the ethics of machine learning--Two of the world’s leading experts on algorithmic bias look back at the events of the past year and reflect on what we’ve learned, what we’re still grappling with, and how far we have to go.  By Stephen Zorio



"In November of 2019, University of Pennsylvania computer science professors Michael Kearns and Aaron Roth released The Ethical Algorithm: The Science of Socially Aware Algorithm Design. Kearns is the founding director of the Warren Center for Network and Data Sciences, and the faculty founder and former director of Penn Engineering’s Networked and Social Systems Engineering program. Roth is the co-director of Penn’s program in Networked and Social Systems Engineering and co-authored The Algorithmic Foundations of Differential Privacy with Cynthia Dwork. Kearns and Roth are leading researchers in machine learning, focusing on both the design and real-world application of algorithms.

Their book’s central thesis, which involves “the science of designing algorithms that embed social norms such as fairness and privacy into their code,” was already pertinent when the book was released. Fast forward one year, and the book’s themes have taken on even greater significance.

Amazon Science sat down with Kearns and Roth, both of whom recently became Amazon Scholars, to find out whether the events of the past year have influenced their outlook. We talked about what it means to define and pursue fairness, how differential privacy is being applied in the real world and what it can achieve, the challenges faced by regulators, what advice the two University of Pennsylvania professors would give to students studying artificial intelligence and machine learning, and much more."

Thursday, July 16, 2020

Market clearing by queuing, by Ashlagi, Leshno, Qian and Saberi



Queue Lengths as Constantly Adapting Prices: Allocative Efficiency Under Random Dynamics
Itai Ashlagi, Jacob Leshno, Pengyu Qian, and Amin Saberi
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation July 2020 Pages 317–318 https://doi.org/10.1145/3391403.3399539

ABSTRACT
"Waiting lists are common mechanisms for allocating scarce items without monetary transfers. Examples include the allocation of cadaver organs to patients in need of a transplant, public housing apartments to applicants, health care services to patients, and even spots at childcare centers to parents. In all these markets waiting times play the role of prices in guiding the allocation and rationing items. But while prices are set by the designer, waiting times are endogenously determined by the number of agents waiting. Moreover, waiting times are not fixed, and continuously adjust as items arrive or agents join. When agents and items arrive stochastically over time, waiting times stochastically adjust over time.

"The stochastic adaptation of waiting times adversely impacts the allocative efficiency. If utility is quasi-linear in waiting time, standard competitive equilibrium (CE) arguments show that fixed waiting times can serve as market clearing prices and yield the optimal allocative efficiency. But even if one may expect the endogenously generated waiting times to tend towards market clearing prices, the waiting times keep fluctuating and never converge. Agents may arrive when waiting times are far from the market clearing prices, and their assignment can be inefficient.

"This paper evaluates the allocative efficiency loss due to the random fluctuations. We consider a standard waiting list mechanism, which holds a separate First Come First Served (FCFS) queue for each of finitely many items. Items arrive over time according to a Poisson process, and are assigned to the first agent in the respective queue. Agents arrive over time according to a Poisson process, observe the length of each queue, and then choose a queue to join or leave the system. An agent who joins a queue must wait there until he receives the item. Agents have heterogeneous private values over the items, and their utility is quasi-linear in waiting costs. That is, all agents have the same waiting costs. We interpret the expected waiting costs at each queue as prices that stochastically adjust as items arrive or agents join the queues.

"Our key technical observation is that the waiting list's random price adaptation process is equivalent to that of a stochastic gradient descent algorithm (SGD). While each arrival randomly adjusts prices, the expected price adjustment from each arrival moves waiting times towards market clearing prices. However, waiting times never converge. Standard usage of SGD optimization algorithms requires reducing the step size to zero as the algorithm gets closer to the optimal solution. In contrast, the step-size for the waiting list mechanism is determined by the granularity of waiting costs C>0, which is the maximal price impact (i.e., increase in expected waiting costs) of adding one agent to a queue.

"Our first result states that the allocative efficiency loss from the random price fluctuations is O(C), and this bound is tight. We further show that, if there are finitely many agent types and the optimal static assignment problem has a unique dual solution (which generically holds), then the allocative efficiency loss becomes exponentially small as C -> 0."

Saturday, July 11, 2020

Economics and Computation 2020 updated program, July 13-16

Scott Kominers forwards this update on the EC conference program, including a shortcut to identify those sessions on market design.


Economics and Computation 2020
The main programming of EC 2020, the leading scientific conference on advances in theory, empirics, and applications at the interface of economics and computation, will be held next week from July 13 to July 16.  The program features invited speakers, a highlight of papers from other conferences and journals, a technical program of paper presentations and posters, workshops, tutorials, and ample opportunities for casual interactions and networking. The conference will be run virtually on the Gather platform, an innovative 2D world that facilitates spontaneous small-group conversations. 

Participation by members of related fields is strongly encouraged.  Registration is mandatory (register here) but complimentary with ACM/SIGecom membership of $10 ($5 for students).  Details on joining events will be emailed to registered participants.

All events are listed on this Google calendar.  Paper sessions are broken down by areas of interest in the Google calendars below.  You can add these calendars to your personal Google calendar by clicking the “+Google” button on the bottom right.

4.     Mechanism Design

Unanswered questions about EC’20 can be directed to the Conference Hosts at sigecom-virtual-EC2020@googlegroups.com.

Saturday, June 27, 2020

Strategy proofness in auctions, beyond the frontiers of our most reliable knowledge

A lot of market design goes on beyond the frontiers for which we have robust general theorems. Computational methods are important in these cases (and sometimes the theory follows along eventually).   Here's a recent auction paper on archiv.org that sheds some light on strategy proofness.

Certifying Strategyproof Auction Networks
Michael J. Curry∗ Ping-Yeh Chiang∗ Tom Goldstein and  John P. Dickerson
 
Abstract: Optimal auctions maximize a seller’s expected revenue subject to individual rationality and strategyproofness for the buyers. Myerson’s seminal work in 1981 settled the case of auctioning a single item; however, subsequent decades of work have yielded little progress moving beyond a single item, leaving the design of revenue-maximizing auctions as a central open problem in the field of mechanism design. A recent thread of work in “differentiable economics” has used tools from modern deep learning to instead learn good mechanisms. We focus on the RegretNet architecture, which can represent auctions with arbitrary numbers of items and participants; it is trained to be empirically strategyproof, but the property is never exactly verified leaving potential loopholes for market participants to exploit. We propose ways to explicitly verify strategyproofness under a particular valuation profile using techniques from the neural network verification literature. Doing so requires making several modifications to the RegretNet architecture in order to represent it exactly in an integer program. We train our network and produce certificates in several settings, including settings for which the optimal strategyproof mechanism is not known